[lttng-dev] Query on the rcu red-black tree status

[mathieu.desnoyers@efficios.com (Mathieu Desnoyers)]

* ?? (tailai.ly at alibaba-inc.com) wrote:
> Hi List
> 
>   I am developer of Sheepdog project, which is a heavy user of urcu
> library. I noticed there is a branch which implement rcu red-black tree
> and it seems to halt on the late 2011. Is there roadmap to merge this
> into master branch?

Hi Yuan,

There are a couple of factors that are making me uncomfortable with
pulling the RCU red-black tree (single-producer, multiple RCU consumers
Red Black tree) into the Userspace RCU master branch at this point.
It might be a good think to bring them up for discussion:

1) My own understanding of the code is not sufficient to vouch for it.

The code, which has been sitting here since late 2011:

git://git.lttng.org/userspace-rcu.git branch: rbtree2

Files:

urcu/rcurbtree.h  (API)
urcu-rbtree.c (implementation)
tests/test_urcu_rbtree.c (tests, example usage)

I implemented this code to show that it is possible to implement a
red-black tree that allows completely wait-free RCU readers, but along
the way, the code grew to a certain level of complexity. For instance, I
could not say that I would be comfortable to do changes to it without
very thorough testing. I don't currently feel confident about my own
ability to understand each corner-case of this code. If something
breaks, the turn-around time to identify the fault might be unacceptably
long.

2) Lack of review.

If I look at my recent experience with the wait-free and lock-free
queues and stack, as well as with the RCU lock-free hash table, a lot of
review, discussion about semantics, added testing from many people, as
well as feedback from API users are all necessary to get to a point
where we can feel comfortable with the implementation, the level of
documentation, as well as the API per se. I don't think the RCU
red-black tree is at this level yet.

3) Not tested thoroughly enough for my own standards.

Even though I created some stress-tests for the data structure that make
me rather confident that it works well, we would need to farther in
terms of test-cases: creating customized stress-tests that purposefully
stress specific aspects of the data structure (e.g. corner-cases that
happen rarely) would increase my own confidence in the quality of the
implementation.

4) No user so far.

This is always a chicken-and-egg problem: we need users to get feedback
on the API, but as soon as we settle on an API and release a version
with it, it becomes very painful to change it (in fact, we create new
APIs and slowly deprecate an old one rather than break an API). So,
ideally, I prefer to wait until some users actually show interest (like
you are currently doing) before I merge APIs into the master branch.
This lets us do some back-and-forth and allow the API to evolve before
we finalize it.

5) I am currently working on other, similar data structures

As you are probably aware, I am currently working on a RCU
implementation of Judy Arrays, which target Multiple-Producers
Multiple-Consumers use-cases. The design is well underway, but the
implementation is far from complete (I do this part-time as a research
track within my own company). At some point, I want to compare the
RBtree and RCU judy array implementations in terms of performance,
scalability, real-time behavior, and other aspects. I feel it is
important that we compare those, and learn from this comparison, before
pushing those data structures into production.

Thoughts, comments, and feedback are welcome!

Thanks,

Mathieu

> 
> Thanks,
> Yuan

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