Re: [RFC] RCU Judy array with distributed locking for FS extents

[Mathieu Desnoyers <mathieu.desnoyers@efficios.com>]

* Chris Mason (clmason@fusionio.com) wrote:
> Quoting Mathieu Desnoyers (2013-06-03 01:27:58)
> > Hi Chris,
> > 
> > I stumbled the LWN article "A kernel skiplist implementation (Part 1)",
> > and really thought I should tell you about the side-project I am
> > currently working on: RCU Judy array, with locking distributed within
> > the data structure. I developed my own design of this structure
> > specifically to be usable with RCU. (ref. my LPC2012 presentation:
> > https://www.efficios.com/lpc2012-scaling-rcu-judy-arrays-cache-efficient-compact-fast-and-scalable-trie)
> > 
> > I think it would fit your extents use-case perfectly, with excellent
> > cache usage, constant lookup time, near-linear scalability for lookups,
> > and pretty good update scability.
> > 
> > The code is available in a development branch of the Userspace RCU
> > library:
> > 
> > git://git.lttng.org/userspace-rcu.git branch: urcu/rcuja
> > https://git.lttng.org/?p=userspace-rcu.git;a=shortlog;h=refs/heads/urcu/rcuja
> > 
> > It runs entirely in user-space, although it can be ported easily to the
> > Linux kernel. I'd be curious to see how it behaves with your workload.
> > 
> > Relevant files:
> > - rcuja/design.txt: design document of the data structure,
> > - urcu/rcuja.h (public API)
> > - rcuja/*.[ch]: implementation
> > - tests/test_urcu_ja.c: stress-tests, example usage.
> > 
> > After reading the article on skiplists, I added a new API specifically
> > to handle non-overlapping ranges:
> > 
> > struct cds_hlist_head cds_ja_lookup_lower_equal(struct cds_ja *ja,
> >                 uint64_t key);
> > 
> > AFAIU, "extents", as far as keys are concerned, are nothing more than
> > segments, with start and end values.
> > 
> > Extents can be indexed by the Judy array in the following way: we use
> > the start of segment as node key, and keep the end of segment value
> > within the leaf node. We add those nodes into the judy array, indexed by
> > start-of-segment value. Then, when we want to figure out if a value
> > matches a segment, we do the following:
> > 
> > 1) lookup the possible segment match with cds_ja_lookup_lower_equal(),
> >    passing the key to lookup as parameter,
> > 
> > 2) check that our key fits within the range of the segment using the
> >    end-of-segment value within the leaf node.
> > 
> > Of course, this approach is limited to non-overlapping segments, so I
> > hope this is what you need.
> 
> Hi Mathieu,
> 
> One problem here is that XFS wants to allow duplicate keys in the tree.
> This is possible with some modifications to the skiplist code, but I'm
> not sure if it fits into your description above.

Are those segments that completely overlap, or partially overlap ?

> 
> Regardless, it is worth trying out.  I'll pull my current code back into
> userland and try out the userspace-rcu port (I had planned this anyway).
> That way we can have a proper head-to-head benchmark ;)

Cool! Don't hesitate to ping me if I can be of any help.

Thanks,

Mathieu

> 
> -chris
> 

-- 
Mathieu Desnoyers
EfficiOS Inc.
http://www.efficios.com