[CS] Persistent Data structure

Kafka 공식문서를 읽는 중에, Constant Time Suffices 항목에서 몰랐던 개념이 등장했다.

The persistent data structure used in messaging systems are often a per-consumer queue with an associated BTree or other general-purpose random access data structures to maintain metadata about messages. BTrees are the most versatile data structure available, and make it possible to support a wide variety of transactional and non-transactional semantics in the messaging system. They do come with a fairly high cost, though: Btree operations are O(log N). Normally O(log N) is considered essentially equivalent to constant time, but this is not true for disk operations. Disk seeks come at 10 ms a pop, and each disk can do only one seek at a time so parallelism is limited. Hence even a handful of disk seeks leads to very high overhead. Since storage systems mix very fast cached operations with very slow physical disk operations, the observed performance of tree structures is often superlinear as data increases with fixed cache--i.e. doubling your data makes things much worse than twice as slow.

Persistent는 어떤 자료구조를 계속 업데이트하면서도 이전 버전에 접근할 수 있을 때 붙는다고 한다.

이전 모든 버전에 접근, 수정이 가능하다면 Fully persistent, 이전의 모든 버전에 접근이 가능하나 최종 상태 제외 모두 read only라면 Partially persistent 혹은 Confluently persistent라고 한다.

 

이런 구조는 자료구조의 k-th state에 빠르게 접근할 수 있어 사용된다