{"owner":"pmeunier","repo":"nest","channel":"main","channels":["main"],"can_delete":true,"inode":{"File":{"path":[{"basename":"site","pos":"AX7NN2MQXFV32.4XSQC","meta":576},{"basename":"src","pos":"AX7NN2MQXFV32.LF2TG","meta":576},{"basename":"posts","pos":"AX7NN2MQXFV32.VQKTI","meta":576},{"basename":"2019-03-20-sanakirja-0.10.md","pos":"AX7NN2MQXFV32.GNHTW","meta":0}],"file":"---\ntitle: 'Sanakirja gets its full concurrency model'\ndate: 2019-03-20T15:20:00+00:00\nauthor: Pierre-Étienne Meunier\n---\n\nI just fixed a few remaining bugs in Sanakirja, the database backend\nbehind Pijul, and took the opportunity to update its concurrency\nmodel.\n\n## The design\n\nSanakirja implements transactional operations on [B-trees](https://en.wikipedia.org/wiki/B-tree) stored on disk. Its distinctive feature is to allow fast clones of a database (in O(log n), where n is the size of the database).\n\nI'll review in this post how we achieve this.\n\n### B-trees\n\nB-trees are an amazing datastructure. They are trees whose nodes are \"blocks\" (usually memory pages, which are equal to disk blocks). We always insert in a block, which might cause blocks to split when the new insertion would make them larger than the size of a page.\n\nMoreover, insertion only happens at the leaves, which means that the depth of the tree can only increase by splitting the root. This is how B-trees stay balanced: there is no special operation to do.\n\nDeletions are somewhat trickier to implement, since the key we want to delete might be at an internal node.\n\n### Copy-on-write\n\nIn our case, the key to transactionality is a copy-on-write strategy: each time we want to write something, we clone the page first, and modify just the copy. I know this sounds like a costly operation, it's actually not that costly, since data is loaded from most hard disks one full page at a time anyway, and also written one full page at a time. There are other ways of implementing transactions, but I won't discuss them here: we have a very good reason for choosing copy-on-write, and that is fast clones (see below).\n\nThis strategy, however, is not without its problems. The main issue is that in B-trees, a change in a leaf might propagate upwards and cause the root to split when the root becomes overfull, or to disappear if we manage to merge all its children. Therefore, if we copy a page to update it, and later merge that same page with one of its siblings in the tree, the first copy would have been be useless.\n\nThe solution to this in Sanakirja is laziness: instead of changing anything in the page, we just remember that we should do it after we take care of the next level.\n\n### More design: fast clones\n\nIn Sanakirja, fast clones are done by keeping reference counts of all the pages. However, this could potentially break transactionality: if we cancel a transaction, how would we revert all changes in reference counts at the same time?\n\nOur solution is to use an extra B-tree mapping page numbers to reference counts. In order to avoid circularity (since B-trees are implemented using reference counting), we store only reference counts that are at least 2, and never clone the reference-counting B-tree.\n\n## The recent bug\n\nAs strange as it may seem, the `del` method might sometimes cause some pages to split, increasing the total number of nodes in the tree. Moreover, a split can \"cascade\", meaning that the key between the two newly created pages causes the parent to also split.\n\nIn the bug we discovered recently, we were freeing the page containing the separator key after the split had been updated. However, if the cascade happens with _the same key_, or in other words if the separator for the first split falls is used as the next separator, this is wrong: we should instead wait until the cascade is over before freeing any page containing keys.\n\n## The concurrency model\n\nIn Sanakirja 0.10, writers (also called \"mutable transactions\") exclude each other, but do not exclude readers (or \"immutable transactions\"). Until now, we had a stricter concurrency implemented using read-write locks.\n\nAs explained [in the docs](https://docs.rs/sanakirja), in the new concurrency model, mutable transactions wait before starting, until all readers started before the latest transaction commit are finished.\n\n**Edit (23/4/2019)**\n\nIn the `sanakirja::transaction` module, we add a number of variables to \"environments\":\n\n```rust\nuse std::sync::{Condvar, Mutex, MutexGuard};\npub struct Env {\n …,\n /// The clock is incremented every time a Txn starts, and every\n /// time a MutTxn ends.\n clock: Mutex,\n /// Every time we commit, we count the number of active Txns.\n txn_counter: Mutex,\n /// Last commit date (according to clock) + number of active Txns\n /// at the time of the last commit. At the end of a Txn started\n /// before the last commit date, decrement the counter.\n last_commit_date: Mutex<(u64, usize)>,\n concurrent_txns_are_finished: Condvar,\n\n /// Ensure only one mutable transaction can be started.\n mutable: Mutex<()>,\n}\n\n```\n\nThe `clock` variable is used to compare the start \"date\" of immutable\ntransactions, and compare them to the \"date\" of the last commit. The\n`txn_counter` variable counts the number of active immutable\ntransactions: whenever we start an immutable transaction, we increment the\nclock, and the immutable transaction counter:\n\n```rust\n /// Start a read-only transaction.\n pub fn txn_begin<'env>(&'env self) -> Result, Error> {\n let mut read = self.clock.lock()?;\n *read += 1;\n let mut counter = self.txn_counter.lock()?;\n *counter += 1;\n Ok(Txn {\n env: self,\n start_date: *read,\n })\n }\n```\n\nI also added a variable `last_commit_date`, containing two pieces of\ninformation: one is the date of the last commit (a `u64`), and the\nother one is the number of transactions that were active at the time\nof the last commit.\n\nFinally, when we drop an immutable transaction, we decrement\n`txn_counter`. Moreover, if we are dropping the last transaction that\nstarted before the last commit, we signal condition variable\n`concurrent_txns_are_finished`.\n\n```rust\nimpl<'env> Drop for Txn<'env> {\n fn drop(&mut self) {\n let mut m = self.env.txn_counter.lock().unwrap();\n *m -= 1;\n let mut m = self.env.last_commit_date.lock().unwrap();\n if self.start_date <= m.0 {\n m.1 -= 1\n }\n if m.1 == 0 {\n self.env.concurrent_txns_are_finished.notify_one()\n }\n }\n}\n```\n\nAnd every time we start a mutable transaction, we wait for the end of\nall transactions that were started before the last transaction.\n\n```rust\n pub fn mut_txn_begin<'env>(&'env self) -> Result, Error> {\n let guard = self.mutable.lock()?;\n\n // Wait until all transactions that were started before\n // the start of the last mutable transaction are finished.\n let mut last_commit = self.last_commit_date.lock()?;\n while last_commit.1 > 0 {\n last_commit = self.concurrent_txns_are_finished.wait(last_commit)?;\n }\n …\n }\n```\n\nHere is the relevant section of `commit`:\n\n```rust\nimpl<'env> Commit for MutTxn<'env, ()> {\n fn commit(mut self) -> Result<(), Error> {\n …\n let mut last_commit = self.env.last_commit_date.lock()?;\n let n_txns = self.env.txn_counter.lock()?;\n let mut clock = self.env.clock.lock()?;\n *clock += 1;\n last_commit.0 = *clock;\n last_commit.1 = *n_txns;\n …\n }\n}\n```\n\nNote that unlike the other new variables, where the Mutex could\nprobably be replaced by atomic operations, the race condition on\n`last_commit_date` is slightly more serious: indeed, if an immutable\ntransaction could be dropped at the same time as a commit, then the\nnext call to `mut_txn_begin` would keep waiting for that immutable\ntransaction to finish.\n\n## More news about Pijul\n\nWe've improved Pijul _a lot_ since the last release (0.11, in November 2018). In particular, the new diff algorithms mean that Pijul is now a lot faster when recording. This impacts most operations, since Pijul automatically creates a temporary patch containing the unrecorded changes in the working copy before applying other patches to the repository.\n\nMoreover, we're working on making signing keys easier to use, thanks to the amazing work done by [the Sequoia team](https://sequoia-pgp.org/) on implementing PGP in Rust.\n"}},"token":"uIt+QgV3af7SN+tF1cXfkZ+h+H5qIH6yGLg7slFIpUI=","login":null}