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
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
Yes, and no. You can avoid dealing with consistency, it's just
on how you manage the readers
That imposes memory consistency guarantees that we currently
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