, we start with basic concepts such as processes and links and start building more complex communication patterns. We quickly discover that communication is unreliable and discuss which guarantees we have and how to achieve those. We cover the Important concepts such as Failure Detection, Leader Election and Gossip Dissemination. After that, we explore different Consistency Models and talk about ways to achieve them. After covering Atomic Commitment and Broadcast, we move to the pinnacle of Distributed Systems research: Consensus Algorithms.
(This book includes references to
Many modern databases such as PostgeSQL, MySQL and many others implement variants. of the mutable in-place update data structure: B-Tree. We’ll discuss its origins, binary on-disk layout, organization and popular variants such as Blink-Trees, B * -Trees, Copy-On-Write B-Trees and many others.
Storage Engines consists of a primary storage data structure and several auxiliary subsystems that take care of garbage collection, maintenance, compression. Many modern databases use Write-Ahead Log for restore and recovery and implement buffer management in a form of Page Cache.
With advent of SSDs, we’ve seen many databases implementing and using Log-Structured storage. We’ll explore the whole spectrum of immutable data structures, ranging from B-Tree like LSM-Trees and Bw-Trees to unsorted variants such as LLAMA, Bitcask, WisconsinKey.
How are the Distributed Systems different from the single-node ones? What is FLP Impossibility and Two-Generals problems. How network and communication using message passing puts limits on what we can and not do and how we can build reliable systems despite these complications.
In a replicated systems, where we have multiple copies of data, we have to make to keep nodes in sync to return consistent results. We talk about concepts of Linearizability, Serializability, Eventual and Causal Consistency, their guarantees and limitations.
Many distributed databases use a concept of Leadership to have a single point of reference and make some of the decisions locally. However, both the leader and participant may fail. We explore several Failure Detection algorithms that help us to detect these failures and react to them.