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...