Atomic "copy" of the Trie


#1

The comment in the tutorial on maintaining separate Read and Write copies of the trie, is formally correct, but doesn’t reflect the only possible R/W solution. While entire trie cannot be copied atomically without locking out reads for long time, individual nodes of the trie can be, given that per-design we limit storage on each node to a small fixed number of terms. Suppose individual node contains two copies of the trie, one is for reading ®, and another is for writing (W). Update-related operations, such as checking whether top 5 set needs to change, and actually updating top 5 set can be applied to W by offline process, which doesn’t touch R and therefore doesn’t affect the latency of reads against R. Periodically W can be copied atomically (with a lock taken) to W’, and then atomic pointer redirection can happen where W becomes new R, W’ becomes new W and old R is discarded. Assuming that pointer re-direction can happen either lock-free or with a very short lock, the only set of data that needs to be periodically locked is W, which will slow down offline process which is not latency-sensitive. Furthermore, because only a small set of data needs to be copied on each node, the duration of the lock will be quite small.