Re: WIP: dynahash replacement for buffer table

On 16/10/2014 7:59 AM, Robert Haas wrote:
> On Thu, Oct 16, 2014 at 9:30 AM, Andres Freund <andres(at)2ndquadrant(dot)com> wrote:
>> On 2014-10-16 09:19:16 -0400, Robert Haas wrote:
>>> On Thu, Oct 16, 2014 at 8:03 AM, Ryan Johnson
>>> <ryan(dot)johnson(at)cs(dot)utoronto(dot)ca> wrote:
>>>> Why not use an RCU mechanism [1] and ditch the hazard pointers? Seems like
>>>> an ideal fit...
>>>>
>>>> In brief, RCU has the following requirements:
>>>>
>>>> Read-heavy access pattern
>>>> Writers must be able to make dead objects unreachable to new readers (easily
>>>> done for most data structures)
>>>> Writers must be able to mark dead objects in such a way that existing
>>>> readers know to ignore their contents but can still traverse the data
>>>> structure properly (usually straightforward)
>>>> Readers must occasionally inform the system that they are not currently
>>>> using any RCU-protected pointers (to allow resource reclamation)
>>> Have a look at http://lwn.net/Articles/573424/ and specifically the
>>> "URCU overview" section. Basically, that last requirement - that
>>> readers inform the system tat they are not currently using any
>>> RCU-protected pointers - turns out to require either memory barriers
>>> or signals.
>> Well, there's the "quiescent-state-based RCU" - that's actually
>> something that could reasonably be used inside postgres. Put something
>> around socket reads (syscalls are synchronization points) and non-nested
>> lwlock acquires. That'd mean it's nearly no additional overhead.
> Sure, so, you reuse your existing barriers instead of adding new ones.
> Making it work sounds like a lot of work for an uncertain benefit
> though.
Perhaps RCU is too much work and/or too little benefit to justify
replacing the current latch-based code. I personally am not convinced,
but have no hard data to offer other than to point at the rapid (even
accelerating) uptake of RCU throughout the Linux kernel (cf. Fig. 1 of
http://www2.rdrop.com/users/paulmck/techreports/RCUUsage.2013.02.24a.pdf)

However---
If we are convinced the latch-based code needs to go and the question is
whether to replace it with RCU or hazard pointers, then RCU wins
hands-down IMO. It's comparable work to implement, easier to reason
about (RCU read protocol is significantly simpler), and a clearer
performance benefit (hazard pointers require more barriers, more atomic
ops, more validating, and more pointer chasing than RCU). The only
metric where RCU loses to hazard pointers is if you have really tight
timing constraints on resource reclamation. Hazard pointers give a tight
bound on the number of dead objects that cannot be reclaimed at any
given moment, while RCU does not. I've not heard that this is a major
concern, though, and in practice it doesn't seem to be a problem unless
you forget to annotate an important quiescent point (like a blocking
syscall).

Ryan