Compacting a qp-trie

https://dotat.at/@/2022-06-22-compact-qp.html

My new job is working on BIND for ISC, and my main project is to replace BIND's core red-black tree data structure with my qp-trie.

previously

In the summer of 2021 I wrote some notes on page-based GC for qp-trie RCU which I then went on to implement in my fork of NSD.

Since the start of May 2022 I have ported the NSD version of my qp-trie to BIND, with several improvements:

• multi-version concurrency, instead of just two versions, one for readers and one for the writer;

• the rather sketchy locking has been completed;

• two flavours of write transaction: minimum space for authoritative DNS; and minimum time for recursive caches;

• rollback for failed transactions.

The notes I wrote last summer turned into code very nicely: NSD proved to be a good place to try out the ideas. And more recently, I am pleased with how the code adapted to the more complicated demands of BIND.

But there's one area that has been problematic: compaction.

( Read more... )