Systems reading list

“LSM trees, like other search trees, maintain key-value pairs.”

“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.”

“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.”

“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.”

“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.”

“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".”

“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.”

“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.”

“A write ahead log is an append-only auxiliary disk-resident structure used for crash and transaction recovery.”

“In a system using WAL, all modifications are written to a log before they are applied.”

“Consistent hashing is used by Content Delivery Networks because it is useful for distributing requests for content from a rotating population of web servers.”

“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.”

“Raft is a consensus algorithm designed as an alternative to the Paxos family of algorithms.”

“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.”

“CRDTs have also been used in online chat systems, online gambling, and in the SoundCloud audio distribution platform.”

“The NoSQL distributed databases Redis, Riak and Cosmos DB have CRDT data types.”