Re: [PATCH RFC 0/2] skiplists for range indexes

[Jan Kara <jack@suse.cz>]

  Hi,

On Thu 02-05-13 22:02:11, Chris Mason wrote:
> I've been working on skiplists for indexing off/on for a little while
> now.  For btrfs, I really need a fast way to manage extents that doesn't
> bog down in lock contention for reads or writes.  Dave Chinner has
> mentioned this as well, so I've cc'd him.
  But I guess you still need writer-writer exclusion, don't you? Or are you
able to do some partial locking of the structure to allow parallel
modifications?

> Liu Bo started this skiplist code, but at the time it didn't make
> a huge difference.  I've reworked things a bit and used the IOMMU
> to test things.  I ran some benchmarks on a single socket
> server with two SSD cards to get a baseline of how much it is helping.
> 
> I tried to keep the basic structure of the IOMMU code, and there are probably
> many better ways to fix the IOMMU contention.  Really I'm just trying to
> compare with rbtrees, not fix the IOMMU.
  There also exist some research papers on RCU friendly RB-trees (or other
trees). Maybe they would be interesting to try? The basic trick is to use a
copy-on-write when you need to do a rotation. This is slightly impractical
because it requires memory allocation (or alternatively doubles memory
footprint of an rb node) but you need to do a similar stuff in skip lists
anyway. Just an idea...

								Honza

> Basic numbers (all aio/dio):
> 
> Streaming writes
> IOMMU off  2,575MB/s
> skiplist   1,715MB/s
> rbtree     1,659MB/s
> 
> Not a huge improvement, but the CPU time was lower.
> 
> 16 threads, iodepth 10, 20MB random reads
> IOMMU off  2,861MB/s (mostly idle)
> skiplist   2,484MB/s (100% system time)
> rbtree        99MB/s (100% system time)
> 
> 16 threads, iodepth 10, 20MB random writes
> IOMMU off  2,548MB/s
> skiplist   1,649MB/s
> rbtree        33MB/s
> 
> I ran this a bunch of times to make sure I got the rbtree numbers right,
> lowering the thread count did improve the rbtree performance, but the
> best I could do was around 300MB/s.  For skiplists, all of the CPU time
> is being spent in skiplist_insert_hole, which has a lot of room for
> improvement.
> 
> From here the code needs a lot of testing, and I need to fill out the API
> to make it a little easier to use.  But, I wanted to send this around
> for comments and to see how other might want to use things.  More
> details on all internals are below.
> 
> It starts with a basic skiplist implementation where:
> 
> * skiplist nodes are dynamically sized.  There is a slab cache for each
> node height, so every node is actively using all of the pointers allocated
> for it.
> 
> * Each node has a back pointer as well as a forward pointer
> 
> * Each skiplist node stores an array of pointers to items.  This is a huge
> speed improvement because the array of keys is much more cache friendly.
> 
> Since the array of item pointers is something of an extension
> to the basic skiplist, I've separated them out into two structs.
> First sl_node (just the indexing pointers) and then sl_leaf,
> which has an sl_node and the array of item pointers.
> 
> There's no cache benefit to the leaves if I'm just storing
> an array of pointers though, so it also has an array
> of keys:
> 
>         unsigned long keys[SKIP_KEYS_PER_NODE];
> 	struct sl_slot *ptrs[SKIP_KEYS_PER_NODE];
> 
> The keys array is used for the first search pass, and based
> on that result I narrow things down and only have to follow
> one or two pointers from the corresponding ptrs array.
> 
> The sl_slot is very simple:
> 
> struct sl_slot {
> 	unsigned long key;
> 	unsigned long size;
> }
> 
> The idea is to embed the sl_slot in your struct, giving us something like
> this:
> 
>                    sl_leaf
>                 ________________
>                 | node ptr N    |
>                 |   ....        |
>                 | node ptr 0    |
>                 |_______________|
>                 |   | keys   |  |
>                 |___|________|__|
>                 | . | ptrs   |. |
>                 |___|________|__|
>                  /             \
>                 /               \
>          -------------            ------------
>          | sl_slot 0 |           | sl_slot N |
>          |           |           |           |
>          | data      |           |  data     |
>          -------------           -------------
> 	    your
> 	    struct
> 
> This basic setup gives us similar performance to rbtrees, but uses less memory.
> The performance varies (a lot really) with the size of the keys array.
> 
> Locking is a mixture of RCU and per-node locking.  For searches,
> it can be pure RCU, or it can use the per-node lock to synchronize
> the final search though the last leaf.  But, everything from the
> skiplist head to that final node is RCU either way.
> 
> Insert locking is slightly different.  Before the insert is started,
> a new node is preallocated.  The height of this node is used to
> pick the level where we start locking nodes during the insert.  Much
> of the time we're able to get through huge portions of the list
> without any locks.
> 
> For deletes, it does an RCU search for the leaf, and hold the per-node lock
> while we remove a specific slot.  If the leaf is empty it is marked as dead and
> then unlinked from the skiplist level by level.
> 
> All the locking and tries does slow things down a bit, but the benefits
> for concurrent access make a big difference.
> 
> --
> To unsubscribe from this list: send the line "unsubscribe linux-fsdevel" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
-- 
Jan Kara <jack@suse.cz>
SUSE Labs, CR