--- title: "Systems reading list" curator: "Insee Thaopech" updated: "2026-10-01" sources: 8 --- # Systems reading list Storage engines, data structures and distributed systems, with the passages worth remembering. ## Log-structured merge-tree Source: Why RocksDB and Cassandra turn random writes into sequential ones. > LSM trees, like other search trees, maintain key-value pairs. Why RocksDB and Cassandra turn random writes into sequential ones. #storage #databases --- > LSM trees maintain data in two or more separate structures, each of which is optimized for its respective underlying storage medium; data is synchronized between the two structures efficiently, in batches. #storage #databases ## B-tree Source: The read-optimised counterpart to LSM trees; still the default index in Postgres. > In computer science, a B-tree is a self-balancing tree data structure that maintains sorted data and allows searches, sequential access, insertions, and deletions in logarithmic time. The read-optimised counterpart to LSM trees; still the default index in Postgres. #storage #databases --- > By allowing more children under one node than a regular self-balancing binary search tree, the B-tree reduces the height of the tree and puts the data in fewer separate blocks. #storage #databases ## Bloom filter Source: How LSM engines skip SSTables that cannot contain a key. > In computing, a Bloom filter is a space-efficient probabilistic data structure, conceived by Burton Howard Bloom in 1970, that is used to test whether an element is a member of a set. How LSM engines skip SSTables that cannot contain a key. #data-structures --- > False positive matches are possible, but false negatives are not – in other words, a query returns either "possibly in set" or "definitely not in set". #data-structures ## Skip list Source: The ordered structure behind many memtables, e.g. LevelDB. > In computer science, a skip list (or skiplist) is a probabilistic data structure that allows average complexity for search as well as average complexity for insertion within an ordered sequence of elements. The ordered structure behind many memtables, e.g. LevelDB. #data-structures --- > Thus it can get the best features of a sorted array (for searching) while maintaining a linked list-like structure that allows insertion, which is not possible with a static array. #data-structures ## Write-ahead logging Source: Durability first: log the change before touching the data pages. > A write ahead log is an append-only auxiliary disk-resident structure used for crash and transaction recovery. Durability first: log the change before touching the data pages. #storage #durability --- > In a system using WAL, all modifications are written to a log before they are applied. #storage #durability ## Consistent hashing Source: Adding a node only moves about 1/n of the keys. > Consistent hashing is used by Content Delivery Networks because it is useful for distributing requests for content from a rotating population of web servers. Adding a node only moves about 1/n of the keys. #distributed-systems --- > The addition of a server and the removal of a server (during scalability or outage) requires only items to be re-shuffled when the number of slots (i.e. servers) change. #distributed-systems ## Raft (algorithm) Source: Consensus designed to be understandable: leader election plus log replication. > Raft is a consensus algorithm designed as an alternative to the Paxos family of algorithms. Consensus designed to be understandable: leader election plus log replication. #distributed-systems #consensus --- > Raft is not Byzantine fault tolerant in the base form; the nodes trust the elected leader, and the algorithm assumes all participants are trustworthy, yielding only crash fault tolerance. #distributed-systems #consensus ## Conflict-free replicated data type Source: Replicas that merge without coordination, the basis of local-first apps. > CRDTs have also been used in online chat systems, online gambling, and in the SoundCloud audio distribution platform. Replicas that merge without coordination, the basis of local-first apps. #distributed-systems #local-first --- > The NoSQL distributed databases Redis, Riak and Cosmos DB have CRDT data types. #distributed-systems #local-first