[Date Prev][Date Next] [Chronological] [Thread] [Top]

MDB write concurrency

If anyone is interested in doing some research...

Instead of enforcing single-writer concurrency, we can investigate
single-committer concurrency. The idea goes something like this:

1) at the beginning of a write txn, record the ID of the last committed txn
2) at commit time, if the last commit txn is unchanged, proceed as usual
3) if last committed has changed, look for write conflicts:
  - since every page that was touched in a txn goes onto the freelist, we can
quickly identify which pages have been updated by other commits
  - likewise, since we maintain a dirty page list for each txn, we can quickly
identify which pages were updated in the current txn

  For every dirty leaf page in the current txn, search for its page ID showing
up in the freelist entries of the intervening committed txns. If the same page
ID is found, then fail the commit.

  For dirty branch pages - what steps are required? Due to the copy-on-write
design, every leaf page update causes every superior branch page to be
updated. In the absence of leaf inserts or deletes, all of these branch page
updates are actually non-conflicting. But I'm not sure we can readily
determine this fact - we would need to compare NUMKEYS() between the old page
and the new page, and we don't record the association from old page to new
page. We would have to look inside the committed txn's tree structure to find it.

  In addition, for each dirty page, we would need to record a trail of how to
reach that page from the root, so that we can follow these trails when
comparing nodes in the committed txn's tree. Even if all of the leaf page
updates are found to be non-conflicting, we still need find which parent pages
need to be updated to point at them.

  It's quite possible that determining if the txn conflicts or not may be so
much work that it overwhelms any potential boost in throughput from the added
write concurrency, especially if it requires so much more state to be
remembered in the progress of a write txn. But we won't know for sure until
someone has modeled the code.

-- 
  -- Howard Chu
  CTO, Symas Corp.           http://www.symas.com
  Director, Highland Sun     http://highlandsun.com/hyc/
  Chief Architect, OpenLDAP  http://www.openldap.org/project/