The routing table uses an immutable radix tree to store its indexes, giving it the (mostly) lock-free properties we have come to enjoy. However, this also means insertions -- and particularly updates -- allocate new tree nodes. Below is a benchmark of the routing table's Upsert() method.
cpu: Intel(R) Core(TM) i7-1068NG7 CPU @ 2.30GHz
BenchmarkRoutingTable_upsert/Insert-8 43494 27782 ns/op 36280 B/op 210 allocs/op
BenchmarkRoutingTable_upsert/Drop-8 1000000 1003 ns/op 256 B/op 6 allocs/op
BenchmarkRoutingTable_upsert/Re-Insert-8 48871 24032 ns/op 33753 B/op 235 allocs/op
The 3rd benchmark (Re-Insert) tests an update operation on an existing record. This one is particularly interesting because in real-world access patterns, the bulk of operations is expected to be updates on existing records, with inserts and deletions happening only in short bursts (for instance, during partition merging). This suggests an optimization strategy.
Optimization Strategy
Rather than storing routing.Records directly in the database, we might consider storing an atomic.Value in the database that contains routing.Record, allowing us to mutate existing records on updates. This should be safe, since updates occur on records that are strictly identical, save for the increased sequence number. Three invariants guarantee that no other thread is reading the sequence number during an atomic mutation:
- Atomic mutations MUST take place in a Write transaction
- Sequence numbers MUST NOT be indexed
- Iteration over read-only snapshots MUST NOT depend on
Seq (e.g.: no filtering based on Seq).
Note that this mutation may make it appear to read-only iterators as if the sequence number has changed within a snapshot. Invariant 2 ensures that this does not cause any incorrect or dangling indexes. Invariant 3 ensures that no behaviors depend on mutable data that can be accessed from a read-only snapshot.
The routing table uses an immutable radix tree to store its indexes, giving it the (mostly) lock-free properties we have come to enjoy. However, this also means insertions -- and particularly updates -- allocate new tree nodes. Below is a benchmark of the routing table's
Upsert()method.The 3rd benchmark (
Re-Insert) tests an update operation on an existing record. This one is particularly interesting because in real-world access patterns, the bulk of operations is expected to be updates on existing records, with inserts and deletions happening only in short bursts (for instance, during partition merging). This suggests an optimization strategy.Optimization Strategy
Rather than storing
routing.Records directly in the database, we might consider storing anatomic.Valuein the database that containsrouting.Record, allowing us to mutate existing records on updates. This should be safe, since updates occur on records that are strictly identical, save for the increased sequence number. Three invariants guarantee that no other thread is reading the sequence number during an atomic mutation:Seq(e.g.: no filtering based onSeq).Note that this mutation may make it appear to read-only iterators as if the sequence number has changed within a snapshot. Invariant 2 ensures that this does not cause any incorrect or dangling indexes. Invariant 3 ensures that no behaviors depend on mutable data that can be accessed from a read-only snapshot.