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

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

[泰来]

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?

Thanks,
Yuan

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

[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

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

[泰来]

On 01/21/2013 09:05 AM, Mathieu Desnoyers wrote:
> * ?? (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,
> 

Hi Mathieu

  Thanks for your detailed explanation and I have taken note of it. Judy
Arrays looks more powerful, looks forward to seeing it in a production
level.

Thanks,
Yuan