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

[Dave Chinner <dchinner@redhat.com>]

On Mon, Jun 03, 2013 at 08:46:01AM -0400, Mathieu Desnoyers wrote:
> * 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 ?

Partial overlap. Can be wholly within an existing exist, or overlap
start, end or both.

Cheers,

Dave.
-- 
Dave Chinner
dchinner@redhat.com