Re: Freeing unused pages between two revisions...

[Emmanuel Lécharny <elecharny@gmail.com>]

Le 10/12/14 18:07, Howard Chu a écrit :
> Emmanuel Lécharny wrote:
>> Hi guys,
>>
>> we have had long discussions with Howard on LMDB about the release of
>> pages that are not anymore in use. This is a critical part of a MVCC
>> based B-tree, as each update will copy many pages, and we want to re-use
>> the copied pages.
>>
>> The problem is that those copied pages may be still in use by older
>> readers. Let's quickly explain how it all works.
>
> This is a good analysis, but I have to state that the investigation
> down this path has stalled for a major reason:
>
> The current reader/writer interaction depends on the fact that we only
> need to know the oldest reader, and that we can be lazy about
> determining what the oldest reader is. 

You have to keep all the readers in memory, just to be able to find the
oldest when it leaves. Then, when the oldest leave, you have to find the
new oldest in a way or another, which should be easy. Or you have to
check that the leaving reader is the oldest by controlling all the other
ones (and in this case, you have to iterate over the existing LDAP
sessions).

In any case, you should know about the readers, no matter what.

> Once you start looking at intervals between ordered ages of readers,
> that means you require continuously up to date reader status, 

Yes. It's just a set associated with a list (the set to retrieve
immediately the position in the list of the leaving reader).

How do you manage readers currently ?

> which means you require highly consistent updating and reading of the
> readers table. 
Yes, and no. You can avoid dealing with consistency, it's just depending
on how you manage the readers

> That imposes memory consistency guarantees that we currently don't
> require, and adding those guarantees has a significant performance cost.

Ok no let's suppose each thread handling reads (and there is a limited
number of threads for that) has its own list of readers. This list is
clearly not protected against concurrent access, because it's specific
to each thread. Now, when a reader, managed by the thread, leaves, you
can tell the writer that some cleanup can occur. This cleanup will be
done regardless what the reader thread will do, because it implies an
already dead reader.
From the writer thread POV, it's a matter of checking on every reader
threads to see if the released revision is in use, or not. If not, then
it's time to cleanup the pages.

This is totally thread safe, with no contention at all.

Of course, I'm assumling that the reader threads keep a set of readers
information...