# Database Internals  ## Metadata - Author: [[Alex Petrov]] - Full Title: Database Internals - Category: #books - Source: kindle - Last Highlighted: 2020-07-12 04:56:00+00:00 ## Highlights - The Dynamo paper [DECANDIA07], published by the team at Amazon in 2007, had so much impact on the database community that within a short period it inspired many variants and implementations. The most prominent of them were Apache Cassandra, created at Facebook; Project Voldemort, created at LinkedIn; and Riak, created by former Akamai engineers. ([Location 39](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=39)) - Having an overview and a general understanding of how database systems work will help in case something goes wrong. Using this knowledge, you’ll be able to form a hypothesis, validate it, find the root cause, and present it to other project maintainers. ([Location 55](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=55)) - One of the advantages of learning the fundamental concepts, proofs, and algorithms is that they never grow old. Of course, there will always be new ones, but new algorithms are often created after finding a flaw or room for improvement in a classical one. Knowing the history helps to understand differences and motivation better. ([Location 69](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=69)) - This is neither a book about relational database management systems nor about NoSQL ones, but about the algorithms and concepts used in all kinds of database systems, with a focus on a storage engine and the components responsible for distribution. ([Location 74](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=74)) - You can find some pointers to useful literature in the Part II Conclusion and in the chapter summaries. ([Location 79](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=79)) - The most significant distinctions between database systems are concentrated around two aspects: how they store and how they distribute the data. ([Location 88](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=88)) - We continue with storage structures and try to understand how disk-based structures are different from in-memory ones, introduce B-Trees, and cover algorithms for efficiently maintaining B-Tree structures on disk, including serialization, page layout, and on-disk representations. ([Location 94](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=94)) - We start with the importance of understanding the theoretical concepts for building fault-tolerant distributed systems, how distributed systems are different from single-node applications, and which problems, constraints, and complications we face in a distributed environment. ([Location 98](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=98)) - one of the most difficult things in distributed systems is achieving data consistency, we discuss concepts of replication, followed by consistency models, possible divergence between replicas, and eventual consistency. Since eventually consistent systems sometimes rely on anti-entropy for convergence and gossip for data dissemination, we discuss several anti-entropy and gossip approaches. ([Location 103](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=103)) - Databases are modular systems and consist of multiple parts: a transport layer accepting requests, a query processor determining the most efficient way to run queries, an execution engine carrying out the operations, and a storage engine (see “DBMS Architecture” ([Location 157](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=157)) - The storage engine (or database engine) is a software component of a database management system responsible for storing, retrieving, and managing data in memory and on disk, designed to capture a persistent, long-term memory of each node [REED78] ([Location 159](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=159)) - database management systems are applications built on top of storage engines, offering a schema, a query language, indexing, transactions, and many other useful features. ([Location 164](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=164)) - At the same time, clear separation between database system components opens up an opportunity to switch between different engines, potentially better suited for particular use cases. For ([Location 175](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=175)) - To detect potential problems, it is best to have long-running tests in an environment that simulates the real-world production setup as closely as possible. ([Location 197](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=197)) - It’d be great if we could use databases as black boxes and never have to take a look inside them, but the practice shows that sooner or later a bug, an outage, a performance regression, or some other problem pops up, and it’s better to be prepared for it. If ([Location 213](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=213)) - The more knowledge you have about the database before using it, the more time you’ll save when running it in production. ([Location 234](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=234)) - We need to design the physical data layout and organize pointers, decide on the serialization format, understand how data is going to be garbage-collected, how the storage engine fits into the semantics of the database system as a whole, figure out how to make it work in a concurrent environment, and, finally, make sure we never lose any data, under any circumstances. ([Location 244](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=244)) - To draw a parallel with city planning, it is possible to build a city for a specific population and choose to build up or build out. In both cases, the same number of people will fit into the city, but these approaches lead to radically different lifestyles. When building the city up, people live in apartments and population density is likely to lead to more traffic in a smaller area; in a more spread-out city, people are more likely to live in houses, but commuting will require covering larger distances. ([Location 253](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=253)) - Terminology can sometimes be ambiguous and hard to understand without a complete context. ([Location 270](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=270)) - The query is usually presented in the form of an execution plan (or query plan): a sequence of operations that have to be carried out for its results to be considered complete. ([Location 316](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=316)) - Main memory database systems are different from their disk-based counterparts not only in terms of a primary storage medium, but also in which data structures, organization, and optimization techniques they use. ([Location 349](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=349)) - Programming for main memory is also significantly simpler than doing so for the disk. ([Location 351](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=351)) - In practice, it all comes down to the fact that disks are easier to maintain and have significantly lower prices. ([Location 356](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=356)) - NVM storage reduces or completely eliminates (depending on the exact technology) asymmetry between read and write latencies, further improves read and write performance, and allows byte-addressable access. ([Location 359](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=359)) - Before the operation can be considered complete, its results have to be written to a sequential log file. We discuss write-ahead logs in more detail in “Recovery” ([Location 365](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=365)) - The backup copy is maintained as a sorted disk-based structure, and modifications to this structure are often asynchronous (decoupled from client requests) and applied in batches to reduce the number of I/O operations. ([Location 367](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=367)) - Log records are usually applied to backup in batches. After the batch of log records is processed, backup holds a database snapshot for a specific point in time, and log contents up to this point can be discarded. This process is called checkpointing. ([Location 369](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=369)) - Disk-based databases use specialized storage structures, optimized for disk access. In memory, pointers can be followed comparatively quickly, and random memory access is significantly faster than the random disk access. ([Location 376](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=376)) - Disk-based storage structures often have a form of wide and short trees (see “Trees for Disk-Based Storage”), while memory-based implementations can choose from a larger pool of data structures and perform optimizations that would otherwise be impossible or difficult to implement on disk [MOLINA92] ([Location 379](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=379)) - Most database systems store a set of data records, consisting of columns and rows in tables. Field is an intersection of a column and a row: a single value of some type. ([Location 386](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=386)) - Tables can be partitioned either horizontally (storing values belonging to the same row together), or vertically (storing values belonging to the same column together). ([Location 394](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=394)) - Since row-oriented stores are most useful in scenarios when we have to access data by row, storing entire rows together improves spatial locality2 [DENNING68]. ([Location 410](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=410)) - Because data on a persistent medium such as a disk is typically accessed block-wise (in other words, a minimal unit of disk access is a block), a single block will contain data for all columns. ([Location 412](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=412)) - but makes queries accessing individual fields of multiple user records (for example, queries fetching only the phone numbers) more expensive, since data for the other fields will be paged in as well. ([Location 414](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=414)) - Column-oriented database management systems partition data vertically (i.e., by column) instead of storing it in rows. ([Location 416](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=416)) - Storing values for different columns in separate files or file segments allows efficient queries by column, since they can be read in one pass rather than consuming entire rows and discarding data for columns that weren’t queried. ([Location 419](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=419)) - Column-oriented stores are a good fit for analytical workloads that compute aggregates, such as finding trends, computing average values, etc. ([Location 420](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=420)) - To reconstruct data tuples, which might be useful for joins, filtering, and multirow aggregates, we need to preserve some metadata on the column level to identify which data points from other columns it is associated with. ([Location 429](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=429)) - If you do this explicitly, each value will have to hold a key, which introduces duplication and increases the amount of stored data. ([Location 430](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=430)) - use implicit identifiers (virtual IDs) instead and use the position of the value (in other words, its offset) to map it back to the related values [ABADI13] ([Location 431](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=431)) - Reading multiple values for the same column in one run significantly improves cache utilization and computational efficiency. ([Location 442](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=442)) - Storing values that have the same data type together (e.g., numbers with other numbers, strings with other strings) offers a better compression ratio. We can use different compression algorithms depending on the data type and pick the most effective compression method for each case. ([Location 444](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=444)) - To decide whether to use a column- or a row-oriented store, you need to understand your access patterns. ([Location 446](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=446)) - If scans span many rows, or compute aggregate over a subset of columns, it is worth considering a column-oriented approach. ([Location 449](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=449)) - Column-oriented databases should not be mixed up with wide column stores, such as BigTable or HBase, where data is represented as a multidimensional map, columns are grouped into column families (usually storing data of the same type), and inside each column family, data is stored row-wise. ([Location 451](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=451)) - Data is stored in a multidimensional sorted map with hierarchical indexes: we ([Location 462](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=462)) - Database systems store data records, consisting of multiple fields, in tables, where each table is usually represented as a separate file. Each record in the table can be looked up using a search key. To locate a record, database systems use indexes: auxiliary data structures that allow it to efficiently locate data records without scanning an entire table on every access. Indexes are built using a subset of fields identifying the record. ([Location 484](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=484)) - Index files are typically smaller than the data files. Files are partitioned into pages, which typically have the size of a single or multiple disk blocks. ([Location 490](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=490)) - Most modern storage systems do not delete data from pages explicitly. Instead, they use deletion markers (also called tombstones), which contain deletion metadata, such as a key and a timestamp. ([Location 493](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=493)) - Space occupied by the records shadowed by their updates or deletion markers is reclaimed during garbage collection, which reads the pages, writes the live (i.e., nonshadowed) records to the new place, and discards the shadowed ones. ([Location 496](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=496)) - Records in heap files are not required to follow any particular order, and most of the time they are placed in a write order. ([Location 504](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=504)) - Heap files require additional index structures, pointing to the locations where data records are stored, to make them searchable. ([Location 506](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=506)) - In hashed files, records are stored in buckets, and the hash value of the key determines which bucket a record belongs to. ([Location 506](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=506)) - Index-organized tables (IOTs) store data records in the index itself. Since records are stored in key order, range scans in IOTs can be implemented by sequentially scanning its contents. ([Location 508](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=508)) - index files hold data entries, uniquely identifying data records and containing enough information to locate them in the data file. ([Location 511](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=511)) - we can store file offsets (sometimes called row locators), locations of data records in the data file, ([Location 513](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=513)) - An index is a structure that organizes data records on disk in a way that facilitates efficient retrieval operations. ([Location 517](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=517)) - A pointer to a data record can hold an offset to a heap file or an index-organized table. ([Location 524](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=524)) - Multiple secondary indexes can point to the same record, allowing a single data record to be identified by different fields and located through different indexes. ([Location 525](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=525)) - If the order of data records follows the search key order, this index is called clustered (also known as clustering). ([Location 527](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=527)) - Index-organized tables store information in index order and are clustered by definition. Primary indexes are most often clustered. Secondary indexes are nonclustered by definition, since they’re used to facilitate access by keys other than the primary one. Clustered indexes can be both index-organized or have separate index and data files. ([Location 537](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=537)) - In cases when the primary key is not specified, the storage engine can create an implicit primary key (for example, MySQL InnoDB adds a new auto-increment column and fills in its values automatically). ([Location 541](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=541)) - By referencing data directly, we can reduce the number of disk seeks, but have to pay a cost of updating the pointers whenever the record is updated or relocated during a maintenance process. ([Location 552](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=552)) - Using indirection in the form of a primary index allows us to reduce the cost of pointer updates, but has a higher cost on a read path. ([Location 553](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=553)) - Updating just a couple of indexes might work if the workload mostly consists of reads, but this approach does not work well for write-heavy workloads with multiple indexes. ([Location 554](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=554)) - To reduce the costs of pointer updates, instead of payload offsets, some implementations use primary keys for indirection. ([Location 555](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=555)) - It is also possible to use a hybrid approach and store both data file offsets and primary keys. ([Location 562](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=562)) - First, you check if the data offset is still valid and pay the extra cost of going through the primary key index if it has changed, updating the index file after finding a new offset. ([Location 563](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=563)) - Buffering, Immutability, and Ordering ([Location 567](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=567)) - Note: Gist of the optimizations - Storage structures have three common variables: they use buffering (or avoid using it), use immutable (or mutable) files, and store values in order (or out of order). ([Location 573](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=573)) - Of course, every on-disk structure has to use buffering to some degree, since the smallest unit of data transfer to and from the disk is a block, and it is desirable to write full blocks. ([Location 577](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=577)) - Immutable structures are append-only: once written, file contents are not modified. ([Location 585](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=585)) - One of them is copy-on-write (see “Copy-on-Write”), where the modified page, holding the updated version of the record, is written to the new location in the file, instead of its original location. ([Location 587](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=587)) - Often the distinction between LSM and B-Trees is drawn as immutable against in-place update storage, but there are structures (for example, “Bw-Trees”) that are inspired by B-Trees but are immutable. ([Location 589](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=589)) - the keys that sort closely are stored in contiguous segments on disk. ([Location 593](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=593)) - Trees are not a recent invention: they were introduced by Rudolph Bayer and Edward M. McCreight back in 1971 and gained popularity over the years. By 1979, there were already quite a few variants of B-Trees. Douglas Comer collected and systematized some of them [COMER79] ([Location 631](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=631)) - The balanced tree is defined as one that has a height of log2 N, where N is the total number of items in the tree, and the difference in height between the two subtrees is not greater than one1 [KNUTH98] ([Location 659](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=659)) - One of the ways to keep the tree balanced is to perform a rotation step after nodes are added or removed. If the insert operation leaves a branch unbalanced (two consecutive nodes in the branch have only one child), we can rotate nodes around the middle one. In the example shown in Figure 2-4, during rotation the middle node (3), known as a rotation pivot, is promoted one level higher, and its parent becomes its right child. ([Location 668](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=668)) - Balanced trees give us an average O(log2 N). At the same time, due to low fanout (fanout is the maximum allowed number of children per node), we have to perform balancing, relocate nodes, and update pointers rather frequently. Increased maintenance costs make BSTs impractical as on-disk data structures [NIEVERGELT74] ([Location 676](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=676)) - One problem is locality: since elements are added in random order, there’s no guarantee that a newly created node is written close to its parent, which means that node child pointers may span across several disk pages. ([Location 679](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=679)) - High fanout to improve locality of the neighboring keys. ([Location 689](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=689)) - Low height to reduce the number of seeks during traversal. ([Location 689](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=689)) - Fanout and height are inversely correlated: the higher the fanout, the lower the height. If fanout is high, each node can hold more children, reducing the number of nodes and, subsequently, reducing height. ([Location 690](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=690)) - On spinning disks, seeks increase costs of random reads because they require disk rotation and mechanical head movements to position the read/write head to the desired location. ([Location 707](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=707)) - The smallest transfer unit of a spinning drive is a sector, so when some operation is performed, at least an entire sector can be read or written. Sector sizes typically range from 512 bytes to 4 Kb. ([Location 710](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=710)) - This is one of the reasons we often hear about the positive effects of sequential I/O: reading and writing contiguous memory segments from disk. ([Location 712](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=712)) - A typical SSD is built of memory cells, connected into strings (typically 32 to 64 cells per string), strings are combined into arrays, arrays are combined into pages, and pages are combined into blocks [LARRIVEE15] ([Location 719](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=719)) - Depending on the exact technology used, a cell can hold one or multiple bits of data. Pages vary in size between devices, but typically their sizes range from 2 to 16 Kb. Blocks typically contain 64 to 512 pages. ([Location 721](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=721)) - Blocks are organized into planes and, finally, planes are placed on a die. ([Location 722](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=722)) - The smallest unit that can be written (programmed) or read is a page. ([Location 725](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=725)) - The smallest erase entity is not a page, but a block that holds multiple pages, which is why it is often called an erase block. Pages in an empty block have to be written sequentially. ([Location 726](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=726)) - The part of a flash memory controller responsible for mapping page IDs to their physical locations, tracking empty, written, and discarded pages, is called the Flash Translation Layer (FTL) (see “Flash Translation Layer” for more about FTL). It ([Location 728](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=728)) - It hides an internal disk structure and buffers I/O operations internally, so when we’re reading a single word from a block device, the whole block containing it is read. ([Location 736](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=736)) - In SSDs, we don’t have a strong emphasis on random versus sequential I/O, as in HDDs, because the difference in latencies between random and sequential reads is not as large. ([Location 738](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=738)) - Even though garbage collection is usually a background operation, its effects may negatively impact write performance, especially in cases of random and unaligned write workloads. ([Location 740](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=740)) - Besides the cost of disk access itself, the main limitation and design condition for building efficient on-disk structures is the fact that the smallest unit of disk operation is a block. ([Location 744](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=744)) - Since we already have to do that, we can change the layout of the data structure to take advantage of ([Location 747](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=747)) - We can do this by improving locality, optimizing the internal representation of the structure, and reducing the number of out-of-page pointers. ([Location 755](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=755)) - additional space overhead coming from pointers, and maintenance overhead from remapping these pointers as a result of balancing. B-Trees combine these ideas: increase node fanout, and reduce tree height, the number of node pointers, and the frequency of balancing operations. ([Location 759](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=759)) - B-Trees are sorted: keys inside the B-Tree nodes are stored in order. ([Location 786](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=786)) - Using B-Trees, we can efficiently execute both point and range queries. Point ([Location 791](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=791)) - The relation between the node capacity and the number of keys it actually holds is called occupancy. ([Location 807](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=807)) - B-Trees are characterized by their fanout: the number of keys stored in each node. Higher fanout helps to amortize the cost of structural changes required to keep the tree balanced and to reduce the number of seeks by storing keys and pointers to child nodes in a single block or multiple consecutive blocks. ([Location 809](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=809)) - Keys stored in B-Tree nodes are called index entries, separator keys, or divider cells. They split the tree into subtrees (also called branches or subranges), holding corresponding key ranges. ([Location 824](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=824)) - Some B-Tree variants also have sibling node pointers, most often on the leaf level, to simplify range scans. These pointers help avoid going back to the parent to find the next sibling. ([Location 835](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=835)) - Since B-Trees reserve extra space inside nodes for future insertions and updates, tree storage utilization can get as low as 50%, but is usually considerably higher. Higher occupancy does not influence B-Tree performance negatively. ([Location 839](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=839)) - There are N times more nodes on each new level, and following a child pointer reduces the search space by the factor of N. During lookup, at most logN M (where M is a total number of items in the B-Tree) pages are addressed to find a searched key. ([Location 844](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=844)) - From the perspective of number of comparisons, the logarithm base is 2, since searching a key inside each node is done using binary search. Every comparison halves the search space, so complexity is log2 M. ([Location 847](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=847)) - 2 B-Tree lookup complexity is generally referenced as log M. Logarithm base is generally not used in complexity analysis, since changing the base simply adds a constant factor, and multiplication by a constant factor does not change complexity. ([Location 851](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=851)) - Finding an exact match is used for point queries, updates, and deletions; finding its predecessor is useful for range scans and inserts. ([Location 858](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=858)) - If the target node doesn’t have enough room available, we say that the node has overflowed [NICHOLS66] and has to be split in two to fit the new data. ([Location 883](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=883)) - Splits are done by allocating the new node, transferring half the elements from the splitting node to it, and adding its first key and pointer to the parent node. In this case, we say that the key is promoted. The index at which the split is performed is called the split point (also called the midpoint). ([Location 888](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=888)) - The tree height changes when the root node is split and the new root is allocated, or when two nodes are merged to form a new root. ([Location 896](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=896)) - A split point value is placed into the parent node to serve as a separator key. ([Location 899](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=899)) - To perform a split, we first create a new node and move elements starting from index N/2 + 1 to it. The split point key is promoted to the parent. ([Location 903](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=903)) - If neighboring nodes have too few values (i.e., their occupancy falls under a threshold), the sibling nodes are merged. This situation is called underflow. ([Location 917](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=917)) - Creating a file format is in many ways similar to how we create data structures in languages with an unmanaged memory model. ([Location 975](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=975)) - For a disk-resident data structure to be efficient, we need to lay out data on disk in ways that allow quick access to it, and consider the specifics of a persistent storage medium, come up with binary data formats, and find a means to serialize and deserialize data efficiently. ([Location 980](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=980)) - To store data on disk efficiently, it needs to be encoded using a format that is compact and easy to serialize and deserialize. ([Location 992](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=992)) - byte value is 8 bits, short is 2 bytes (16 bits), int is 4 bytes (32 bits), and long is 8 bytes (64 bits). ([Location 1026](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1026)) - Strings and other variable-size data types (such as arrays of fixed-size data) can be serialized as a number, representing the length of the array or string, followed by size bytes: the actual data. ([Location 1044](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1044)) - For strings, this representation is often called UCSD String or Pascal String, named after the popular implementation of the Pascal programming language. We can express it in pseudocode as follows: ([Location 1046](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1046)) - An alternative to Pascal strings is null-terminated strings, where the reader consumes the string byte-wise until the end-of-string symbol is reached. ([Location 1049](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1049)) - Another closely related concept is flags, kind of a combination of packed booleans and enums. ([Location 1062](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1062)) - Usually, you start designing a file format by deciding how the addressing is going to be done: whether the file is going to be split into same-sized pages, which are represented by a single block or multiple contiguous blocks. ([Location 1077](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1077)) - as soon as the page fills up in memory, it is flushed on disk. ([Location 1081](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1081)) - The file usually starts with a fixed-size header and may end with a fixed-size trailer, ([Location 1081](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1081)) - Many data stores have a fixed schema, specifying the number, order, and type of fields the table can hold. Having a fixed schema helps to reduce the amount of data stored on disk: instead of repeatedly writing field names, we can use their positional identifiers. ([Location 1086](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1086)) - To avoid calculations involving multiple fields, we can encode both offset and length to the fixed-size area. ([Location 1096](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1096)) - Database files often consist of multiple parts, with a lookup table aiding navigation and pointing to the start offsets of these parts written either in the file header, trailer, or in the separate file. ([Location 1100](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1100)) - Database systems store data records in data and index files. These files are partitioned into fixed-size units called pages, which often have a size of multiple filesystem blocks. Page sizes usually range from 4 to 16 Kb. ([Location 1102](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1102)) - When storing variable-size records, the main problem is free space management: reclaiming the space occupied by removed records. If ([Location 1117](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1117)) - To simplify space management for variable-size records, we can split the page into fixed-size segments. However, we end up wasting space if we do that, too. ([Location 1122](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1122)) - We organize the page into a collection of slots or cells and split out pointers and cells in two independent memory regions residing on different sides of the page. This means that we only need to reorganize pointers addressing the cells to preserve the order, and deleting a record can be done either by nullifying its pointer or removing it. ([Location 1133](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1133)) - the only overhead incurred by slotted pages is a pointer array holding offsets to the exact positions where the records are stored. ([Location 1140](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1140)) - Key cells hold a separator key and a pointer to the page between two neighboring pointers. ([Location 1146](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1146)) - Key-value cells hold keys and data records associated with them. ([Location 1147](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1147)) - This means we can store metadata describing cells once on the page level, instead of duplicating it in every cell. ([Location 1149](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1149)) - Since pages have a fixed size and are managed by the page cache (see “Buffer Management”), we only need to store the page ID, which is later translated to the actual offset in the file using the lookup table. ([Location 1164](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1164)) - Keys can be inserted out of order and their logical sorted order is kept by sorting cell offset pointers in key order. This design allows appending cells to the page with minimal effort, since cells don’t have to be relocated during insert, update, or delete operations. ([Location 1180](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1180)) - To improve locality (especially when keys are small in size), some implementations store keys and values separately on the leaf level. Keeping keys together can improve the locality during the search. ([Location 1212](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1212)) - In summary, to simplify B-Tree layout, we assume that each node occupies a single page. A page consists of a fixed-size header, cell pointer block, and cells. Cells hold keys and pointers to the pages representing child nodes or associated data records. B-Trees use simple pointer hierarchies: page identifiers to locate the child nodes in the tree file, and cell offsets to locate cells within the page. ([Location 1215](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1215)) - The version can also be stored directly in the index file header. In this case, a part of the header (or an entire header) has to be encoded in a format that does not change between versions. After ([Location 1228](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1228)) - Files on disk may get damaged or corrupted by software bugs and hardware failures. To identify these problems preemptively and avoid propagating corrupt data to other subsystems or even nodes, we can use checksums and cyclic redundancy checks (CRCs). ([Location 1232](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1232)) - Noncryptographic hashes and CRCs should not be used to verify whether or not the data has been tampered with. For this, you should always use strong cryptographic hashes designed for security. The main goal of CRC is to make sure that there were no unintended and accidental changes in data. These algorithms are not designed to resist attacks and intentional changes in data. ([Location 1242](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1242)) - Before writing the data on disk, we compute its checksum and write it together with the data. ([Location 1245](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1245)) - Since computing a checksum over the whole file is often impractical and it is unlikely we’re going to read the entire content every time we access it, page checksums are usually computed on pages and placed in the page header. ([Location 1247](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1247)) - It usually contains flags that describe page contents and layout, number of cells in the page, lower and upper offsets marking the empty space (used to append cell offsets and data), and other useful metadata. ([Location 1278](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1278)) - Usually, it’s a multibyte block, containing a constant value that can be used to signal that the block represents a page, specify its kind, or identify its version. ([Location 1287](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1287)) - Some implementations store forward and backward links, pointing to the left and right sibling pages. These links help to locate neighboring nodes without having to ascend back to the parent. ([Location 1293](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1293)) - One of the downsides of storing sibling links is that they have to be updated during splits and merges. Since updates have to happen in a sibling node, not in a splitting/merging node, it may require additional locking. ([Location 1303](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1303)) - separator keys have strict invariants: they’re used to split the tree into subtrees and navigate them, so there is always one more pointer to child pages than there are keys. ([Location 1307](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1307)) - If the rightmost child is split and the new cell is appended to its parent, the rightmost child pointer has to be reassigned. ([Location 1316](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1316)) - Node size and tree fanout values are fixed and do not change dynamically. ([Location 1341](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1341)) - The B-Tree algorithm specifies that every node keeps a specific number of items. ([Location 1344](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1344)) - To implement variable-size nodes without copying data to the new contiguous region, we can build nodes from multiple linked pages. ([Location 1348](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1348)) - These linked page extensions are called overflow pages. ([Location 1350](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1350)) - When the first overflow page is allocated, its page ID is stored in the header of the primary page. ([Location 1363](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1363)) - If all data records are oversize, it is worth considering specialized blob storage for large values. ([Location 1368](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1368)) - Binary search works only for sorted data. ([Location 1373](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1373)) - A negative return value indicates that the searched key is not present in the input array and gives us an insertion point. ([Location 1376](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1376)) - The insertion point is the index of the first element that is greater than the given key. ([Location 1377](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1377)) - Breadcrumbs contain references to the nodes followed from the root and are used to backtrack them in reverse when propagating splits or merges. ([Location 1410](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1410)) - The most natural data structure for this is a stack. ([Location 1411](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1411)) - Some B-Tree implementations attempt to postpone split and merge operations to amortize their costs by rebalancing elements within the level, or moving elements from more occupied nodes to less occupied ones for as long as possible before finally performing a split or merge. ([Location 1422](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1422)) - To improve space utilization, instead of splitting the node on overflow, we can transfer some of the elements to one of the sibling nodes and make space for the insertion. Similarly, during delete, instead of merging the sibling nodes, we may choose to move some of the elements from the neighboring nodes to ensure the node is at least half full. ([Location 1428](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1428)) - Higher utilization also means more efficient searches, because the height of the tree is smaller and fewer pages have to be traversed on the path to the searched leaf. ([Location 1434](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1434)) - Balancing might add some complexity to the code, but since its use cases are isolated, it can be implemented as an optimization at a later stage. ([Location 1441](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1441)) - since all the insertions are happening toward the end of the index (in the rightmost leaf), so most of the splits occur on the rightmost node on each level. Moreover, since the keys are monotonically incremented, given that the ratio of appends versus updates and deletes is low, nonleaf pages are also less fragmented than in the case of randomly ordered keys. ([Location 1445](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1445)) - One approach for implementing bulk loading is to write presorted data on the leaf level page-wise (rather then inserting individual elements). ([Location 1462](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1462)) - The main benefits of this approach are that we do not have to perform any splits or merges on disk and, at the same time, have to keep only a minimal part of the tree (i.e., all parents of the currently filling leaf node) in memory for the time of construction. ([Location 1467](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1467)) - Immutable B-Trees can be created in the same manner but, unlike mutable B-Trees, they require no space overhead for subsequent modifications, since all operations on a tree are final. All pages can be completely filled up, improving occupancy and resulting into better performance. ([Location 1469](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1469)) - Storing the raw, uncompressed data can induce significant overhead, and many databases offer ways to compress it to save space. ([Location 1472](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1472)) - The apparent trade-off here is between access speed and compression ratio: larger compression ratios can improve data size, allowing you to fetch more data in a single access, but might require more RAM and CPU cycles to compress and decompress it. ([Location 1475](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1475)) - Even though compressing entire files can yield better compression ratios, it has limited application as a whole file has to be recompressed on an update, and more granular compression is usually better-suited for larger datasets. ([Location 1477](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1477)) - An alternative is to compress data page-wise. ([Location 1480](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1480)) - However, a compressed page in this case can occupy only a fraction of a disk block and, since transfers are usually done in units of disk blocks, it might be necessary to page in extra bytes ([Location 1482](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1482)) - Another approach is to compress data only, either row-wise (compressing entire data records) or column-wise (compressing columns individually). In this case, page management and compression are decoupled. ([Location 1487](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1487)) - Most of the open source databases reviewed while writing this book have pluggable compression methods, using available libraries such as Snappy, zLib, lz4, and many others. ([Location 1489](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1489)) - There are many overviews available that evaluate different compression algorithms for different block sizes (for example, Squash Compression Benchmark), usually focusing on four metrics: memory overhead, compression performance, decompression performance, and compression ratio. ([Location 1493](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1493)) - there are other processes that happen in parallel with queries that maintain storage integrity, reclaim space, reduce overhead, and keep pages in order. ([Location 1499](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1499)) - Performing these operations in the background allows us to save some time and avoid paying the price of cleanup during inserts, updates, and deletes. ([Location 1500](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1500)) - subsequent splits and merges in internal nodes or inserts, updates, and deletes on the leaf level can result in a page that has enough logical space but does not have enough contiguous space, since it is fragmented. ([Location 1503](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1503)) - Nonaddressable data records are said to be garbage: these records are not referenced anywhere and cannot be read or interpreted, so their contents are as good as nullified. ([Location 1509](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1509)) - Zero-filling of garbage areas is often skipped for performance reasons, as eventually these areas are overwritten by the new data anyway. ([Location 1512](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1512)) - On the leaf level, deletes only remove cell offsets from the header, leaving the cell itself intact. After this is done, the cell is not addressable anymore, its contents will not appear in the query results, and nullifying it or moving neighboring cells is not necessary. ([Location 1516](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1516)) - rest of the page is not addressable, cells whose offsets were truncated are not reachable, so they will be overwritten whenever the new data arrives, or garbage-collected when the vacuum process kicks in. ([Location 1518](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1518)) - Some databases rely on garbage collection, and leave removed and updated cells in place for multiversion concurrency control (see “Multiversion Concurrency Control”). Cells remain accessible for the concurrently executing transactions until the update is complete, and can be collected as soon as no other thread accesses them. ([Location 1520](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1520)) - Since deletes only discard cell offsets and do not relocate remaining cells or physically remove the target cells to occupy the freed space, freed bytes might end up scattered across the page. In this case, we say that the page is fragmented and requires defragmentation. ([Location 1525](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1525)) - but having naturally sorted tuples can help with cache prefetch during sequential reads. ([Location 1529](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1529)) - Updates are mostly applicable to the leaf level: ([Location 1529](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1529)) - The process that takes care of space reclamation and page rewrites is called compaction, vacuum, or just maintenance. ([Location 1534](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1534)) - but compaction is mostly referred to as a distinct, asynchronous process of walking through pages, performing garbage collection, and rewriting their contents. ([Location 1537](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1537)) - When pages are rewritten, they may also get relocated to new positions in the file. Unused in-memory pages become available and are returned to the page cache. IDs of the newly available on-disk pages are added to the free page list (sometimes called a freelist3). ([Location 1539](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1539)) - A transaction is an indivisible logical unit of work in a database management system, allowing you to represent multiple operations as a single step. Operations executed by transactions include reading and writing database records. ([Location 1575](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1575)) - A database transaction has to preserve atomicity, consistency, isolation, and durability. These properties are commonly referred as ACID [HAERDER83]: ([Location 1577](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1577)) - Consistency is the most weakly defined property, possibly because it is the only property that is controlled by the user and not only by the database itself. ([Location 1588](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1588)) - Multiple concurrently executing transactions should be able to run without interference, as if there were no other transactions executing at the same time. ([Location 1590](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1590)) - Many databases use isolation levels that are weaker than the given definition of isolation for performance reasons. ([Location 1592](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1592)) - On the node locally, the transaction manager coordinates, schedules, and tracks transactions and their individual steps. ([Location 1599](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1599)) - The lock manager guards access to these resources and prevents concurrent accesses that would violate data integrity. ([Location 1599](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1599)) - The page cache serves as an intermediary between persistent storage (disk) and the rest of the storage engine. It stages state changes in main memory and serves as a cache for the pages that haven’t been synchronized with persistent storage. All changes to a database state are first applied to the cached pages. ([Location 1605](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1605)) - The log manager holds a history of operations (log entries) applied to cached pages but not yet synchronized with persistent storage to guarantee they won’t be lost in case of a crash. ([Location 1607](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1607)) - In other words, the log is used to reapply these operations and reconstruct the cached state during startup. ([Location 1608](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1608)) - entries can also be used to undo changes done by the aborted transactions. ([Location 1609](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1609)) - Cached pages available in memory can be reused under the assumption that no other process has modified the data on disk. This approach is sometimes referenced as virtual disk [BAYER72] ([Location 1616](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1616)) - A more common name for the same concept is page cache or buffer pool. ([Location 1619](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1619)) - In case of a database system crash or unorderly shutdown, cached contents are lost. ([Location 1621](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1621)) - The term buffer pool sounds like its primary purpose is to pool and reuse empty buffers, without sharing their contents, which can be a useful part of a page cache or even as a separate component, but does not reflect the entire purpose as precisely. ([Location 1622](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1622)) - Operating systems have the concept of a page cache, too. Operating systems utilize unused memory segments to transparently cache disk contents to improve performance of I/O syscalls. ([Location 1625](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1625)) - Uncached pages are said to be paged in when they’re loaded from disk. If any changes are made to the cached page, it is said to be dirty, until these changes are flushed back on disk. ([Location 1626](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1626)) - the page cache eventually fills up and, in order to page in a new page, one of the cached pages has to be evicted. ([Location 1629](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1629)) - The page cache loads pages into free slots out of order, so there’s no direct mapping between how pages are ordered on disk and in memory. ([Location 1632](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1632)) - The primary functions of a page cache can be summarized as: It keeps cached page contents in memory. It allows modifications to on-disk pages to be buffered together and performed against their cached versions. When a requested page isn’t present in memory and there’s enough space available for it, it is paged in by the page cache, and its cached version is returned. If an already cached page is requested, its cached version is returned. If there’s not enough space available for the new page, some other page is evicted and its contents are flushed to disk. ([Location 1634](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1634)) - Many database systems open files using O_DIRECT flag. This flag allows I/O system calls to bypass the kernel page cache, access the disk directly, and use database-specific buffer management. This is sometimes frowned upon by the operating systems folks. ([Location 1639](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1639)) - We can gain some control over how the kernel evicts pages from its cache is by using fadvise, but this only allows us to ask the kernel to consider our opinion and does not guarantee it will actually happen. To avoid syscalls when performing I/O, we can use memory mapping, but then we lose control over caching. ([Location 1645](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1645)) - As no other process is allowed to make changes to the backing file, this synchronization is a one-way process: from memory to disk, and not vice versa. ([Location 1651](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1651)) - You can think of it as an application-specific equivalent of the kernel page cache: it accesses the block device directly, implements similar functionality, and serves a similar purpose. It abstracts disk accesses and decouples logical write operations from the physical ones. ([Location 1652](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1652)) - Once returned, the buffer with cached page contents is said to be referenced, and the storage engine has to hand it back to the page cache or dereference it once it’s done. ([Location 1658](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1658)) - The page cache can be instructed to avoid evicting pages by pinning them. ([Location 1660](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1660)) - If the page is modified (for example, a cell was appended to it), it is marked as dirty. A dirty flag set on the page indicates that its contents are out of sync with the disk and have to be flushed for durability. ([Location 1661](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1661)) - If page contents are in sync with the disk (i.e., were already flushed or were never modified) and the page is not pinned or referenced, it can be evicted right away. ([Location 1666](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1666)) - Dirty pages have to be flushed before they can be evicted. Referenced pages should not be evicted while some other thread is using them. ([Location 1667](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1667)) - Since triggering a flush on every eviction might be bad for performance, some databases use a separate background process that cycles through the dirty pages that are likely to be evicted, updating their disk versions. ([Location 1669](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1669)) - Another important property to keep in mind is durability: if the database has crashed, all data that was not flushed is lost. ([Location 1671](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1671)) - To make sure that all changes are persisted, flushes are coordinated by the checkpoint process. ([Location 1673](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1673)) - The checkpoint process controls the write-ahead log (WAL) and page cache, and ensures that they work in lockstep. ([Location 1674](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1674)) - Only log records associated with operations applied to cached pages that were flushed can be discarded from the WAL. ([Location 1675](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1675)) - Since B-Tree gets “narrower” toward the top, higher-level nodes (ones that are closer to the root) are hit for most of the reads. Splits and merges also eventually propagate to the higher-level nodes. ([Location 1684](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1684)) - We can “lock” pages that have a high probability of being used in the nearest time. Locking pages in the cache is called pinning. ([Location 1686](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1686)) - Operations performed against a subtree may result in structural changes that contradict each other — for example, multiple delete operations causing merges followed by writes causing splits, or vice versa. ([Location 1692](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1692)) - Some databases, for example, PostgreSQL, use a circular buffer (in other words, FIFO page replacement policy) for large sequential scans. ([Location 1702](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1702)) - However, unless we evict pages that are least likely to be accessed again soon, we might end up loading them several times subsequently even though we could’ve just kept them in memory for all that time. ([Location 1708](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1708)) - For this, we can say that pages should be evicted according to the eviction policy (also sometimes called the page-replacement policy). It attempts to find pages that are least likely to be accessed again any time soon. ([Location 1710](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1710)) - It seems logical that we can reduce the number of evictions by simply using a larger cache. However, this does not appear to be the case. One of the examples demonstrating this dilemma this is called Bélády’s anomaly [BEDALY69]. It shows that increasing the number of pages might increase the number of evictions if the used page-replacement algorithm is not optimal. ([Location 1716](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1716)) - For example, the root and topmost-level pages are paged in first and, according to this algorithm, are the first candidates for eviction, even though it’s clear from the tree structure that these pages are likely to paged in again soon, if not immediately. ([Location 1726](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1726)) - A natural extension of the FIFO algorithm is least-recently used (LRU) [TANENBAUM14]. It also maintains a queue of eviction candidates in insertion order, but allows you to place a page back to the tail of the queue on repeated accesses, as if this was the first time it was paged in. However, updating references and relinking nodes on every access can become expensive in a concurrent environment. ([Location 1728](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1728)) - 2Q (Two-Queue LRU) maintains two queues and puts pages into the first queue during the initial access and moves them to the second hot queue on subsequent accesses, allowing you to distinguish between the recently and frequently accessed pages [JONSON94] ([Location 1733](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1733)) - In some situations, efficiency may be more important than precision. CLOCK algorithm variants are often used as compact, cache-friendly, and concurrent alternatives to LRU [SOUNDARARARJAN06]. Linux, for example, uses a variant of the CLOCK algorithm. ([Location 1737](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1737)) - CLOCK-sweep holds references to pages and associated access bits in a circular buffer. ([Location 1741](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1741)) - An advantage of using a circular buffer is that both the clock hand pointer and contents can be modified using compare-and-swap operations, and do not require additional locking mechanisms. ([Location 1751](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1751)) - LRU is not always the best replacement strategy for a database system. Sometimes, it may be more practical to consider usage frequency rather than recency as a predictive factor. ([Location 1753](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1753)) - To improve the situation, we can start tracking page reference events rather than page-in events. ([Location 1758](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1758)) - TinyLFU, a frequency-based page-eviction policy [EINZIGER17], does precisely this: instead of evicting pages based on page-in recency, it orders pages by usage frequency. It is implemented in the popular Java library called Caffeine. ([Location 1761](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1761)) - TinyLFU uses a frequency histogram [CORMODE11] to maintain compact cache access history, since preserving an entire history might be prohibitively expensive for practical purposes. ([Location 1764](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1764)) - Rather than choosing which elements to evict every time, this approach chooses which ones to promote for retention. ([Location 1769](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1769)) - The choice of a page-replacement strategy has a significant impact on latency and the number of performed ([Location 1776](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1776)) - A write-ahead log (WAL for short, also known as a commit log) is an append-only auxiliary disk-resident structure used for crash and transaction recovery. ([Location 1784](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1784)) - The page cache allows buffering changes to page contents in memory. ([Location 1785](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1785)) - Until the cached contents are flushed back to disk, the only disk-resident copy preserving the operation history is stored in the WAL. ([Location 1786](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1786)) - Allow the page cache to buffer updates to disk-resident pages while ensuring durability semantics in the larger context of a database system. ([Location 1790](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1790)) - Persist all operations on disk until the cached copies of pages affected by these operations are synchronized on disk. Every operation that modifies the database state has to be logged on disk before the contents of the associated pages can be modified. ([Location 1791](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1791)) - Allow lost in-memory changes to be reconstructed from the operation log in case of a crash. ([Location 1793](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1793)) - In addition to this functionality, the write-ahead log plays an important role in transaction processing. It is hard to overstate the importance of the WAL as it ensures that data makes it to the persistent storage and is available in case of a crash, as uncommitted data is replayed from the log and the pre-crash database state is fully restored. ([Location 1793](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1793)) - In this section, we will often refer to ARIES (Algorithm for Recovery and Isolation Exploiting Semantics), a state-of-the-art recovery algorithm that is widely used and cited [MOHAN92]. ([Location 1796](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1796)) - Synchronizing dirty page contents with disk is done by making the fsync() kernel call, which is supposed to sync dirty pages to disk, and unset the dirty flag on the kernel pages. ([Location 1801](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1801)) - The write-ahead log is append-only and its written contents are immutable, so all writes to the log are sequential. ([Location 1812](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1812)) - Since the WAL is an immutable, append-only data structure, readers can safely access its contents up to the latest write threshold while the writer continues appending data to the log tail. ([Location 1814](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1814)) - Every record has a unique, monotonically increasing log sequence number (LSN). ([Location 1815](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1815)) - Since log records do not necessarily occupy an entire disk block, their contents are cached in the log buffer and are flushed on disk in a force operation. ([Location 1817](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1817)) - All log records have to be flushed on disk in LSN order. ([Location 1819](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1819)) - A transaction can’t be considered committed until the log is forced up to the LSN of its commit record. ([Location 1820](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1820)) - The WAL is usually coupled with a primary storage structure by the interface that allows trimming it whenever a checkpoint is reached. ([Location 1823](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1823)) - Checkpoints are a way for a log to know that log records up to a certain mark are fully persisted and aren’t required anymore, which significantly reduces the amount of work required during the database startup. ([Location 1827](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1827)) - A process that forces all dirty pages to be flushed on disk is generally called a sync checkpoint, as it fully synchronizes the primary storage structure. ([Location 1828](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1828)) - Flushing the entire contents on disk is rather impractical and would require pausing all running operations until the checkpoint is done, so most database systems implement fuzzy checkpoints. ([Location 1830](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1830)) - CHAMBERLIN81], use shadow paging: a copy-on-write technique ensuring data durability and transaction atomicity. ([Location 1841](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1841)) - A recovery method that allows flushing a page modified by the transaction even before the transaction has committed is called a steal policy. ([Location 1860](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1860)) - A no-steal policy does not allow flushing any uncommitted transaction contents on disk. ([Location 1861](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1861)) - To steal a dirty page here means flushing its in-memory contents to disk and loading a different page from disk in its place. ([Location 1861](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1861)) - A force policy requires all pages modified by the transactions to be flushed on disk before the transaction commits. ([Location 1862](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1862)) - On the other hand, a no-force policy allows a transaction to commit even if some pages modified during this transaction were not yet flushed on disk. ([Location 1863](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1863)) - To force a dirty page here means to flush it on disk before the commit. ([Location 1864](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1864)) - In both cases, transaction cannot commit until either undo or redo records are written to the logfile. ([Location 1874](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1874)) - In other words, transactions do not block each other, maintain histories of their operations, and check these histories for possible conflicts before commit. If execution results in a conflict, one of the conflicting transactions is aborted. ([Location 1899](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1899)) - Guarantees a consistent view of the database at some point in the past identified by the timestamp by allowing multiple timestamped versions of the record to be present. ([Location 1902](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1902)) - Lock-based approaches require transactions to maintain locks on database records to prevent other transactions from modifying locked records and assessing records that are being modified until the transaction releases its locks. ([Location 1908](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1908)) - Nonlocking approaches maintain read and write operation lists and restrict execution, depending on the schedule of unfinished transactions. ([Location 1910](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1910)) - A schedule is a list of operations required to execute a set of transactions from the database-system perspective (i.e., only ones that interact with the database state, such as read, write, commit, or abort operations), since all other operations are assumed to be side-effect free (in other words, have no impact on the database state) [MOLINA08]. ([Location 1919](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1919)) - Correct schedules are logical equivalents to the original lists of operations, but their parts can be executed in parallel or get reordered for optimization purposes, as long as this does not violate ACID properties and the correctness of the results of individual transactions [WEIKUM01]. ([Location 1923](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1923)) - A schedule is said to be serial when transactions in it are executed completely independently and without any interleaving: every preceding transaction is fully executed before the next one starts. ([Location 1927](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1927)) - A schedule is serializable if it is equivalent to some complete serial schedule over the same set of transactions. ([Location 1932](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1932)) - An isolation level specifies how and when parts of the transaction can and should become visible to other transactions. ([Location 1940](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1940)) - isolation levels describe the degree to which transactions are isolated from other concurrently executing transactions, and what kinds of anomalies can be encountered during execution. ([Location 1941](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1941)) - Achieving isolation comes at a cost: to prevent incomplete or temporary writes from propagating over transaction boundaries, we need additional coordination and synchronization, which negatively impacts the performance. ([Location 1942](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1942)) - The SQL standard [MELTON06] refers to and describes read anomalies that can occur during execution of concurrent transactions: dirty, nonrepeatable, and phantom reads. ([Location 1945](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1945)) - dirty read is a situation in which a transaction can read uncommitted changes from other transactions. ([Location 1947](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1947)) - A nonrepeatable read (sometimes called a fuzzy read) is a situation in which a transaction queries the same row twice and gets different results. ([Location 1952](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1952)) - phantom read is when a transaction queries the same set of rows twice and receives different results. It is similar to a nonrepeatable read, but holds for range queries. ([Location 1958](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1958)) - A lost update occurs when transactions T1 and T2 both attempt to update the value of V. T1 and T2 read the value of V. T1 updates V and commits, and T2 updates V after that and commits as well. Since the transactions are not aware about each other’s existence, if both of them are allowed to commit, the results of T1 will be overwritten by the results of T2, and the update from T1 will be lost. ([Location 1961](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1961)) - A dirty write is a situation in which one of the transactions takes an uncommitted value (i.e., dirty read), modifies it, and saves it. In other words, when transaction results are based on the values that have never been committed. ([Location 1966](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1966)) - A write skew occurs when each individual transaction respects the required invariants, but their combination does not satisfy these invariants. ([Location 1968](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1968)) - The lowest (in other words, weakest) isolation level is read uncommitted. Under this isolation level, the transactional system allows one transaction to observe uncommitted changes of other concurrent transactions. In other words, dirty reads are allowed. ([Location 1978](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1978)) - In other words, dirty reads are not permitted, but phantom and nonrepeatable reads are. This isolation level is called read committed. ([Location 1984](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1984)) - Disallowing concurrent execution would have a substantial negative impact on the database performance. Transactions can get reordered, as long as their internal invariants hold and can be executed concurrently, but their outcomes have to appear in some serial order. ([Location 1989](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1989)) - serializability is a property of multiple operations executed in arbitrary order. ([Location 1996](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1996)) - Isolation in ACID terms means serializability [BAILIS14a] ([Location 1997](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=1997)) - Optimistic concurrency control assumes that transaction conflicts occur rarely and, instead of using locks and blocking transaction execution, we can validate transactions to prevent read/write conflicts with concurrently executing transactions and ensure serializability before committing their results. ([Location 2013](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=2013)) - Of course, optimistic concurrency still has a critical section, which transactions can enter one at a time. ([Location 2040](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=2040)) - a way to achieve transactional consistency in database management systems by allowing multiple record versions and using monotonically incremented transaction IDs or timestamps. ([Location 2046](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=2046)) - Generally, the goal of the transaction manager in this case is to have at most one uncommitted value at a time. ([Location 2050](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=2050)) - These schemes determine transaction conflicts while they’re running and block or abort their execution. ([Location 2058](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=2058)) - One of the simplest pessimistic (lock-free) concurrency control schemes is timestamp ordering, where each transaction has a timestamp. Whether or not transaction operations are allowed to be executed is determined by whether or not any transaction with a later timestamp has already been committed. ([Location 2059](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=2059)) - One of the most widespread lock-based techniques is two-phase locking (2PL), which separates lock management into two phases: The growing phase (also called the expanding phase), during which all locks required by the transaction are acquired and no locks are released. The shrinking phase, during which all locks acquired during the growing phase are released. ([Location 2075](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=2075)) - A rule that follows from these two definitions is that a transaction cannot acquire any locks as soon as it has released at least one of them. ([Location 2079](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=2079)) - A situation may occur when two transactions, while attempting to acquire locks they require in order to proceed with execution, end up waiting for each other to release the other locks they hold. This situation is called a deadlock. ([Location 2089](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=2089)) - The simplest way to handle deadlocks is to introduce timeouts and abort long-running transactions under the assumption that they might be in a deadlock. ([Location 2094](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=2094)) - Another strategy, conservative 2PL, requires transactions to acquire all the locks before they can execute any of their operations and abort if they cannot. ([Location 2095](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=2095)) - To avoid deadlocks and restrict lock acquisition to cases that will not result in a deadlock, the transaction manager can use transaction timestamps to determine their priority. A lower timestamp usually implies higher priority and vice versa. ([Location 2103](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=2103)) - In transaction processing, there’s a distinction between the mechanisms that guard the logical and physical data integrity. The two concepts responsible logical and physical integrity are, correspondingly, locks and latches. ([Location 2119](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=2119)) - Locks are used to isolate and schedule overlapping transactions and manage database contents but not the internal storage structure, and are acquired on the key. ([Location 2123](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=2123)) - Locks are generally stored and managed outside of the tree implementation and represent a higher-level concept, managed by the database lock manager. ([Location 2125](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=2125)) - latches guard the physical representation: leaf page contents are modified during insert, update, and delete operations. ([Location 2128](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=2128)) - Latches guard the physical tree representation (page contents and the tree structure) during these operations and are obtained on the page level. Any ([Location 2130](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=2130)) - Lockless concurrency control techniques still have to use latches. ([Location 2132](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=2132)) - Executing queries should not be able to observe pages in an inconsistent state, such as incomplete writes or partial node splits, during which data might be present in both the source and target node, or not yet propagated to the parent. ([Location 2133](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=2133)) - These scenarios also apply to accesses that overlap with database maintenance (such as background processes, as described in “Vacuum and Maintenance” ([Location 2140](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=2140)) - For example, reads can access pages concurrently without causing any trouble, so we only need to make sure that multiple concurrent writers do not overlap, and readers do not overlap with writers. ([Location 2145](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=2145)) - To achieve this level of granularity, we can use a readers-writer lock or RW lock. ([Location 2147](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=2147)) - An RW lock allows multiple readers to access the object concurrently, and only writers (which we usually have fewer of) have to obtain exclusive access to the object. ([Location 2148](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=2148)) - The most straightforward approach for latch acquisition is to grab all the latches on the way from the root to the target leaf. ([Location 2167](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=2167)) - The time during which a latch is held should be minimized. ([Location 2170](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=2170)) - Latch crabbing is a rather simple method that allows holding latches for less time and releasing them as soon as it’s clear that the executing operation does not require them anymore. ([Location 2171](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=2171)) - Blink-Trees allow a state called half-split, where the node is already referenced by the sibling pointer, but not by the child pointer from its parent. ([Location 2205](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=2205)) - To improve efficiency, we need to allow concurrent transaction execution. ([Location 2220](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=2220)) - To preserve correctness, we have to ensure that concurrently executing transactions preserve ACID properties. ([Location 2221](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=2221)) - a few things in common: tree structure, balancing through splits and merges, and lookup and delete algorithms. ([Location 2260](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=2260)) - parallel tree hierarchy is created. Old tree versions remain accessible for readers that run concurrently to the writer, while writers accessing modified pages have to wait until preceding write operations are complete. ([Location 2275](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=2275)) - Buffering is one of the ideas that is widely used in database storage: it helps to avoid many small random writes and performs a single larger write instead. ([Location 2355](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=2355)) - An alternative approach is to group updates targeting different nodes together by using append-only storage and merge processes, an idea that has also inspired LSM Trees (see “LSM Trees” ([Location 2361](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=2361)) - small B-Tree buffering the updates. As soon as the head tree fills up, its contents are transferred to the immutable run. ([Location 2366](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=2366)) - Write amplification is one of the most significant problems with in-place update implementations of B-Trees: subsequent updates to a B-Tree page may require updating a disk-resident page copy on every update. ([Location 2411](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=2411)) - The second problem is space amplification: we reserve extra space to make updates possible. ([Location 2414](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=2414)) - The third problem is complexity in solving concurrency problems and dealing with latches. ([Location 2415](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=2415)) - We can batch updates to different nodes by using append-only storage, link nodes together into chains, and use an in-memory data structure that allows installing pointers between the nodes with a single compare-and-swap operation, making the tree lock-free. This approach is called a Buzzword-Tree (Bw-Tree) [LEVANDOSKI14] . ([Location 2418](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=2418)) - Having a node as a logical, rather than physical, entity is an interesting paradigm change: we do not need to pre-allocate space, require nodes to have a fixed size, or even keep them in contiguous memory segments. ([Location 2428](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=2428)) - This certainly has a downside: during a read, all deltas have to be traversed and applied to the base node to reconstruct the actual node state. ([Location 2429](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=2429)) - Delta chains can get arbitrarily long without any additional action. Since reads are getting more expensive as the delta chain gets longer, we need to try to keep the delta chain length within reasonable bounds. ([Location 2482](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=2482)) - When it reaches a configurable threshold, we rebuild the node by merging the base node contents with all of the deltas, consolidating them to one new base node. ([Location 2484](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=2484)) - Trees use a technique known as epoch-based reclamation. If some nodes and deltas are removed from the mapping table due to consolidations that replaced them during some epoch, original nodes are preserved until every reader that started during the same epoch or the earlier one is finished. ([Location 2491](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=2491)) - The Bw-Tree is an interesting B-Tree variant, making improvements on several important aspects: write amplification, nonblocking access, and cache friendliness. ([Location 2495](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=2495)) - structures [DEMAINE02] give asymptotically optimal performance regardless of the underlying memory hierarchy and a need to tune these parameters. This means that the algorithm is not required to know the sizes of the cache lines, filesystem blocks, and disk pages. ([Location 2504](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=2504)) - The two levels of this hierarchy are page cache (which is faster, but is limited in space) and disk (which is generally slower, but has a larger capacity) [AGGARWAL88]. ([Location 2509](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=2509)) - The disk is partitioned into blocks, and data is transferred between disk and cache in blocks: even when the algorithm has to locate a single item within the block, an entire block has to be loaded. This approach is cache-aware. ([Location 2512](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=2512)) - This approach allows having no platform-specific parameters, yet guarantees that the number of transfers between the two levels of the hierarchy is within a constant factor. ([Location 2520](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=2520)) - A static B-Tree is built using the van Emde Boas layout. It splits the tree at the middle level of the edges. Then each subtree is split recursively in a similar manner, resulting in subtrees of sqr(N) size. The key idea of this layout is that any recursive tree is stored in a contiguous block of memory. ([Location 2525](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=2525)) - To make the data structure dynamic (i.e., allow inserts, updates, and deletes), cache-oblivious trees use a packed array data structure, which uses contiguous memory segments for storing elements, but contains gaps reserved for future inserted elements. ([Location 2531](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=2531)) - This approach allows inserting items into the tree with fewer relocations. ([Location 2535](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=2535)) - However, as of the date of writing, I’m not aware of any nonacademic cache-oblivious B-Tree implementations. ([Location 2540](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=2540)) - A possible reason for that is an assumption that when cache loading is abstracted away, while data is loaded and written back in blocks, paging and eviction still have a negative impact on the result. ([Location 2541](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=2541)) - Another possible reason is that in terms of block transfers, the complexity of cache-oblivious B-Trees is the same as their cache-aware counterpart. ([Location 2542](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=2542)) - Immutable LSM Trees use append-only storage and merge reconciliation, and B-Trees locate data records on disk and update pages at their original offsets in the file. ([Location 2595](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=2595)) - In-place update storage structures are optimized for read performance [GRAEFE04]: after locating data on disk, the record can be returned to the client. This comes at the expense of write performance: to update the data record in place, it first has to be located on disk. On the other hand, append-only storage is optimized for write performance. Writes do not have to locate records on disk to overwrite them. However, this is done at the expense of reads, which have to retrieve multiple data record versions and reconcile them. ([Location 2597](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=2597)) - where nodes are fully occupied, optimized for sequential disk access. ([Location 2620](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=2620)) - Log-structured merge trees take their name from log-structured filesystems, which write all modifications on disk in a log-like file [ROSENBLUM92] ([Location 2621](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=2621)) - The word “merge” in LSM Trees indicates that, due to their immutability, tree contents are merged using an approach similar to merge sort. ([Location 2625](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=2625)) - LSM Trees defer data file writes and buffer changes in a memory-resident table. These changes are then propagated by writing their contents out to the immutable disk files. All data records remain accessible in memory until the files are fully persisted. ([Location 2627](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=2627)) - Immutable structures allow us to lay out data records sequentially to prevent fragmentation. ([Location 2632](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=2632)) - Since files are immutable, insert, update, and delete operations do not need to locate data records on disk, which significantly improves write performance and throughput. ([Location 2635](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=2635)) - LSM Trees are particularly useful for applications where writes are far more common than reads, which is often the case in modern data-intensive systems, given ever-growing amounts of data and ingest rates. ([Location 2636](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=2636)) - Reads and writes do not intersect by design, so data on disk can be read and written without segment locking, which significantly simplifies concurrent access. ([Location 2638](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=2638)) - To write out immutable file contents on disk, it is necessary to first buffer them in memory and sort their contents. ([Location 2651](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=2651)) - A memory-resident component (often called a memtable) is mutable: it buffers data records and serves as a target for read and write operations. ([Location 2652](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=2652)) - Disk-resident components are built by flushing contents buffered in memory to disk. Disk-resident components are used only for reads: buffered contents are persisted, and files are never modified. ([Location 2659](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=2659)) - Compaction picks several tables, reads their contents, merges them, and writes the merged result out to the new combined file. ([Location 2696](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=2696)) - Until the memtable is fully flushed, the only disk-resident version of its contents is stored in the write-ahead log. When memtable contents are fully flushed on disk, the log can be trimmed, and the log section, holding operations applied to the flushed memtable, can be discarded. ([Location 2719](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=2719)) - Because of that, deletes need to be recorded explicitly. This can be done by inserting a special delete entry (sometimes called a tombstone or a dormant certificate), indicating removal of the data record associated with a specific key: ([Location 2732](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=2732)) - Apache Cassandra implements this approach and calls it range tombstones. A range tombstone covers a range of keys rather than just a single key. ([Location 2741](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=2741)) - During lookups, more than one component is usually accessed, so their contents have to be merged and reconciled before they can be returned to the client. ([Location 2749](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=2749)) - A multiway merge-sort uses a priority queue, such as min-heap [SEDGEWICK11], that holds up to N elements (where N is the number of iterators), which sorts its contents and prepares the next-in-line smallest element to be returned. ([Location 2757](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=2757)) - In terms of complexity, merging iterators is the same as merging sorted collections. It has O(N) memory overhead, where N is the number of iterators. A sorted collection of iterator heads is maintained with O(log N) (average case) [KNUTH98] ([Location 2790](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=2790)) - In LSM Trees, insert and update operations are indistinguishable, since they do not attempt to locate data records previously associated with the key in all sources and reassign its value, so we can say that we upsert records by default. ([Location 2801](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=2801)) - To reconcile data records, we need to understand which one of them takes precedence. Data records hold metadata necessary for this, such as timestamps. ([Location 2803](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=2803)) - In LSM Trees, the number of disk-resident tables is constantly growing, but can be reduced by triggering periodic compaction. ([Location 2810](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=2810)) - Since disk-resident table contents are sorted, and because of the way merge-sort works, compaction has a theoretical memory usage upper bound, since it should only hold iterator heads in memory. ([Location 2812](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=2812)) - At any given time, multiple compactions can be executed in the system. However, these concurrent compactions usually work on nonintersecting sets of tables. ([Location 2816](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=2816)) - During compaction, tombstones are not dropped right away. They are preserved until the storage engine can be certain that no data record for the same key with a smaller timestamp is present in any other table. ([Location 2821](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=2821)) - One of the frequently implemented compaction strategies is called leveled compaction. For example, it is used by RocksDB. ([Location 2829](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=2829)) - Somewhat counterintuitively, the level with the highest index is called the bottommost level. ([Location 2831](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=2831)) - Level-0 tables are created by flushing memtable contents. ([Location 2834](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=2834)) - Key ranges for the tables on level 1 and all levels with a higher index do not overlap, so level-0 tables have to be partitioned during compaction, split into ranges, and merged with tables holding corresponding key ranges. ([Location 2835](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=2835)) - Sizes grow exponentially between the levels: tables on each next level are exponentially larger than tables on the previous one. This way, the freshest data is always on the level with the lowest index, and older data gradually migrates to the higher ones. ([Location 2847](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=2847)) - In size-tiered compaction, rather than grouping disk-resident tables based on their level, they’re grouped by size: smaller tables are grouped with smaller ones, and bigger tables are grouped with bigger ones. ([Location 2852](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=2852)) - table starvation: if compacted tables are still small enough after compaction (e.g., records were shadowed by the tombstones and did not make it to the merged table), higher levels may get starved of compaction and their tombstones will not be taken into consideration, increasing the cost of reads. ([Location 2857](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=2857)) - Apache Cassandra also implements a time window compaction strategy, which is particularly useful for time-series workloads with records for which time-to-live is set (in other words, items have to be expired after a given time period). ([Location 2863](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=2863)) - The time window compaction strategy takes write timestamps into consideration and allows dropping entire files that hold data for an already expired time range without requiring us to compact and rewrite their contents. ([Location 2864](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=2864)) - One approach is to reclaim space occupied by duplicate records and reduce space overhead, which results in higher write amplification caused by re-writing tables continuously. ([Location 2871](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=2871)) - The alternative is to avoid rewriting the data continuously, which increases read amplification (overhead from reconciling data records associated with the same key during the read), and space amplification (since redundant records are preserved for a longer time). ([Location 2872](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=2872)) - One of the big disputes in the database community is whether B-Trees or LSM Trees have lower write amplification. ([Location 2874](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=2874)) - Read amplification Resulting from a need to address multiple tables to retrieve data. Write amplification Caused by continuous rewrites by the compaction process. Space amplification Arising from storing multiple records associated with the same key. ([Location 2879](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=2879)) - Read, Update, and Memory overheads. It is called RUM Conjecture [ATHANASSOULIS16] ([Location 2885](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=2885)) - RUM Conjecture states that reducing two of these overheads inevitably leads to change for the worse in the third one, and that optimizations can be done only at the expense of one of the three parameters. ([Location 2886](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=2886)) - An ideal solution would provide the lowest read cost while maintaining low memory and write overheads, but in reality, this is not achievable, and we are presented with a trade-off. ([Location 2889](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=2889)) - B-Trees are read-optimized. ([Location 2890](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=2890)) - LSM Trees do not require locating the record on disk during write and do not reserve extra space for future writes. ([Location 2892](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=2892)) - In a default configuration, reads are more expensive, since multiple tables have to be accessed to return complete results. ([Location 2893](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=2893)) - This cost model is not perfect, as it does not take into account other important metrics such as latency, access patterns, implementation complexity, maintenance overhead, and hardware-related specifics. ([Location 2896](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=2896)) - there are some other things that many LSM Tree implementations have in common that are worth discussing: how memory- and disk-resident tables are implemented, how secondary indexes work, how to reduce the number of disk-resident tables accessed during read and, finally, new ideas related to log-structured storage. ([Location 2904](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=2904)) - Disk-resident tables are often implemented using Sorted String Tables (SSTables). ([Location 2909](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=2909)) - SSTables are sorted and laid out in key order. ([Location 2911](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=2911)) - SSTables usually consist of two components: index files and data files. ([Location 2911](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=2911)) - Index files are implemented using some structure allowing logarithmic lookups, such as B-Trees, or constant-time lookups, such as hashtables. ([Location 2911](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=2911)) - The index component holds keys and data entries (offsets in the data file where the actual data records are located). ([Location 2914](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=2914)) - The main difference here is that cells are written sequentially and are not modified during the life cycle of the SSTable. ([Location 2917](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=2917)) - Since tables merged during compaction have the same order, and merge-iteration is order-preserving, the resulting merged table is also created by writing data records sequentially in a single run. ([Location 2919](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=2919)) - As soon as the file is fully written, it is considered immutable, and its disk-resident contents are not modified. ([Location 2921](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=2921)) - One of the interesting developments in the area of LSM Tree indexing is SSTable-Attached Secondary Indexes (SASI) implemented in Apache Cassandra. ([Location 2922](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=2922)) - The source of read amplification in LSM Trees is that we have to address multiple disk-resident tables for the read operation to complete. This happens because we do not always know up front whether or not a disk-resident table contains a data record for the searched key. ([Location 2932](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=2932)) - One of the ways to prevent table lookup is to store its key range (smallest and largest keys stored in the given table) in metadata, and check if the searched key belongs to the range of that table. ([Location 2934](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=2934)) - Probabilistic data structures are generally more space efficient than their “regular” counterparts. ([Location 2939](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=2939)) - Probabilistic structures allow us to store approximate information and perform queries that yield results with an element of uncertainty. ([Location 2941](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=2941)) - Some commonly known examples of such data structures are a Bloom filter (for set membership), HyperLogLog (for cardinality estimation) [FLAJOLET12], and Count-Min Sketch (for frequency estimation) [CORMODE12]. ([Location 2942](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=2942)) - A Bloom filter, conceived by Burton Howard Bloom in 1970 [BLOOM70], is a space-efficient probabilistic data structure that can be used to test whether the element is a member of the set or not. ([Location 2944](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=2944)) - It can produce false-positive matches (say that the element is a member of the set, while it is not present there), but cannot produce false negatives (if a negative match is returned, the element is guaranteed not to be a member of the set). ([Location 2946](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=2946)) - In other words, a Bloom filter can be used to tell if the key might be in the table or is definitely not in the table. ([Location 2948](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=2948)) - A Bloom filter uses a large bit array and multiple hash functions. ([Location 2951](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=2951)) - Bits set to 1 in all positions determined by the hash functions indicate a presence of the key in the set. ([Location 2952](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=2952)) - if bits determined by all hash functions are 1, we return the positive result stating that item is a member of the set with a certain probability. If at least one of the bits is 0, we can precisely say that element is not present in the set. ([Location 2954](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=2954)) - Probability of false positives is managed by configuring the size of the bit set and the number of hash functions: in a larger bit set, there’s a smaller chance of collision; similarly, having more hash functions, we can check more bits and have a more precise outcome. ([Location 2957](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=2957)) - The larger bit set occupies more memory, and computing results of more hash functions may have a negative performance impact, so we have to find a reasonable middle ground between acceptable probability and incurred overhead. ([Location 2959](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=2959)) - Skiplist There are many different data structures for keeping sorted data in memory, and one that has been getting more popular recently because of its simplicity is called a skiplist [PUGH90b]. Implementation-wise, a skiplist is not much more complex than a singly-linked list, and its probabilistic complexity guarantees are close to those of search trees. ([Location 2973](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=2973)) - Skiplists are generally less cache-friendly than in-memory B-Trees, since skiplist nodes are small and randomly allocated in memory. ([Location 2977](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=2977)) - Apache Cassandra uses skiplists for the secondary index memtable implementation. WiredTiger uses skiplists for some in-memory operations. ([Location 3005](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3005)) - The most notable difference is that in-memory contents are immutable and therefore require no additional locks or latches for concurrent access. ([Location 3010](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3010)) - Reference counting is applied to make sure that currently accessed pages are not evicted from memory, and in-flight requests complete before underlying files are removed during compaction. ([Location 3011](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3011)) - During compaction and flush, compressed pages are appended sequentially, and compression information (the original uncompressed page offset and the actual compressed page offset) is stored in a separate file segment. ([Location 3027](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3027)) - Bitcask, one of the storage engines used in Riak, is an unordered log-structured storage engine [SHEEHY10b]. ([Location 3038](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3038)) - Unlike the log-structured storage implementations discussed so far, it does not use memtables for buffering, and stores data records directly in logfiles. ([Location 3040](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3040)) - To make values searchable, Bitcask uses a data structure called keydir, which holds references to the latest data records for the corresponding keys. ([Location 3042](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3042)) - Keydir is implemented as an in-memory hashmap and has to be rebuilt from the logfiles during startup. ([Location 3044](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3044)) - A downside of this approach is that it offers only point queries and doesn’t allow range scans, since items are unordered both in keydir and in data files. ([Location 3055](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3055)) - Advantages of this approach are simplicity and great point query performance. ([Location 3056](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3056)) - WiscKey [LU16] decouples sorting from garbage collection by keeping the keys sorted in LSM Trees, and keeping data records in unordered append-only files called vLogs (value logs). This approach can solve two problems mentioned while discussing Bitcask: a need to keep all keys in memory and to rebuild a hashtable on startup. ([Location 3063](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3063)) - The main challenge here is that because vLog data is unsorted, range scans require random I/O. ([Location 3070](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3070)) - WiscKey uses internal SSD parallelism to prefetch blocks in parallel during range scans and reduce random I/O costs. ([Location 3070](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3070)) - The main concurrency challenges in LSM Trees are related to switching table views (collections of memory- and disk-resident tables that change during flush and compaction) and ([Location 3082](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3082)) - Apache Cassandra solves these problems by using operation order barriers: all operations that were accepted for write will be waited upon prior to the memtable flush. ([Location 3090](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3090)) - In LSM Trees, we have a similar requirement: writes are buffered in a memtable, and their contents are not durable until fully flushed, so log truncation has to be coordinated with memtable flushes. ([Location 3105](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3105)) - Many modern filesystems are log structured: they buffer writes in a memory segment and flush its contents on disk when it becomes full in an append-only manner. ([Location 3110](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3110)) - SSDs use log-structured storage, too, to deal with small random writes, minimize write overhead, improve wear leveling, and increase device lifetime. ([Location 3112](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3112)) - LSM Trees and SSDs are a good match, since sequential workloads and append-only writes help to reduce amplification from in-place updates, which negatively affect performance on SSDs. ([Location 3115](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3115)) - If we stack multiple log-structured systems on top each other, we can run into several problems that we were trying to solve using LSS, including write amplification, fragmentation, and poor performance. ([Location 3117](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3117)) - Using a log-structuring mapping layer in SSDs is motivated by two factors: small random writes have to be batched together in a physical page, and the fact that SSDs work by using program/erase cycles. ([Location 3120](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3120)) - Writes can be done only into previously erased pages. This means that a page cannot be programmed (in other words, written) unless it is empty (in other words, was erased). ([Location 3123](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3123)) - A single page cannot be erased, and only groups of pages in a block (typically holding 64 to 512 pages) can be erased together. ([Location 3124](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3124)) - The flash translation layer (FTL) translates logical page addresses to their physical locations and keeps track of page states (live, discarded, or empty). When ([Location 3126](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3126)) - There are no guarantees that all pages in the block that is about to be erased are discarded. Before the block can be erased, FTL has to relocate its live pages to one of the blocks containing empty pages. ([Location 3129](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3129)) - Wear leveling distributes the load evenly across the medium, avoiding hotspots, where blocks fail prematurely because of a high number of program-erase cycles. It is required, since flash memory cells can go through only a limited number of program-erase cycles, and using memory cells evenly helps to extend the lifetime of the device. ([Location 3136](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3136)) - In summary, the motivation for using log-structured storage on SSDs is to amortize I/O costs by batching small random writes together, which generally results in a smaller number of operations and, subsequently, reduces the number of times the garbage collection is triggered. ([Location 3138](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3138)) - Log stacking manifests in a few different ways. First, each layer has to perform its own bookkeeping, and most often the underlying log does not expose the information necessary to avoid duplicating the efforts. ([Location 3143](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3143)) - Misaligned segment writes can make the situation even worse, since discarding a higher-level log segment may cause fragmentation and relocation of the neighboring segments’ parts. ([Location 3147](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3147)) - Because layers do not communicate LSS-related scheduling (for example, discarding or relocating segments), lower-level subsystems might perform redundant operations on discarded data or the data that is about to be discarded. ([Location 3150](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3150)) - Even though we say that log-structured storage is all about sequential I/O, we have to keep in mind that database systems may have multiple write streams (for example, log writes parallel to data record writes) [YANG14] ([Location 3153](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3153)) - This results in fragmentation that we tried to avoid. To reduce interleaving, some database vendors recommend keeping the log on a separate device to isolate workloads and be able to reason about their performance and access patterns independently. ([Location 3159](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3159)) - However, it is more important to keep partitions aligned to the underlying hardware [INTEL14] and keep writes aligned to page size [KIM12] ([Location 3161](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3161)) - Bw-Tree is layered on top of a latch-free, log-structured, access-method aware (LLAMA) storage subsystem. ([Location 3169](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3169)) - This layering allows Bw-Trees to grow and shrink dynamically, while leaving garbage collection and page management transparent for the tree. ([Location 3170](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3170)) - Log-structured storage buffers node updates (delta nodes) together in 4 Mb flush buffers. As soon as the page fills up, it’s flushed on disk. Periodically, garbage collection reclaims space occupied by the unused delta and base nodes, and relocates the live ones to free up fragmented pages. ([Location 3174](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3174)) - Bw-Tree awareness in LLAMA allows for the consolidation of several delta nodes into a single contiguous physical location. ([Location 3177](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3177)) - An alternative to stacking software layers is to skip all indirection layers and use the hardware directly. ([Location 3189](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3189)) - One of the implementations that uses this approach is LOCS (LSM Tree-based KV Store on Open-Channel SSD) [ZHANG13]. Another example using Open-Channel SSDs is LightNVM, implemented in the Linux kernel [BJØRLING17]. ([Location 3193](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3193)) - The flash translation layer usually handles data placement, garbage collection, and page relocation. Open-Channel SSDs expose their internals, drive management, and I/O scheduling without needing to go through the FTL. ([Location 3195](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3195)) - You can draw a parallel with using the O_DIRECT flag to bypass the kernel page cache, which gives better control, but requires manual page management. ([Location 3197](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3197)) - Log-structured storage is used everywhere: from the flash translation layer, to filesystems and database systems. It helps to reduce write amplification by batching small random writes together in memory. ([Location 3206](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3206)) - LSM Trees take some ideas from LSS and help to build index structures managed in a log-structured manner: writes are batched in memory and flushed on disk; shadowed data records are cleaned up during compaction. ([Location 3208](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3208)) - It is important to remember that many software layers use LSS, and make sure that layers are stacked optimally. ([Location 3210](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3210)) - Unfortunately, storage engine design usually involves trade-offs: you increase the cost of one operation in favor of the other. ([Location 3258](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3258)) - In a distributed system, we have several participants (sometimes called processes, nodes, or replicas). Each participant has its own local state. Participants communicate by exchanging messages using communication links between them. ([Location 3283](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3283)) - Most of the research in the distributed systems field is related to the fact that nothing is entirely reliable: communication channels may delay, reorder, or fail to deliver the messages; processes may pause, slow down, crash, go out of control, or suddenly stop responding. ([Location 3295](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3295)) - There are many themes in common in the fields of concurrent and distributed programming, since CPUs are tiny distributed systems with links, processors, and communication protocols. ([Location 3297](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3297)) - However, most of the primitives can’t be reused directly because of the costs of communication between remote parties, and the unreliability of links and processes. ([Location 3299](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3299)) - We describe algorithms in terms of state and steps (or phases), with transitions between them. Each process executes the algorithm steps locally, and a combination of local executions and process interactions constitutes a distributed algorithm. ([Location 3304](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3304)) - Consistency models describe concurrent executions and establish an order in which operations can be executed and made visible to the participants. ([Location 3341](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3341)) - When two sequences of steps execute concurrently, both of them are in progress, but only one of them is executed at any moment. ([Location 3348](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3348)) - If two sequences execute in parallel, their steps can be executed simultaneously. ([Location 3349](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3349)) - Joe Armstrong, creator of the Erlang programming language, gave an example: concurrent execution is like having two queues to a single coffee machine, while parallel execution is like having two queues to two coffee machines. ([Location 3351](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3351)) - However, what happens if one of the processes does not receive a response from the database for a longer time? To answer this question, we first have to define what longer even means. To do this, the system has to be described in terms of synchrony: whether the communication is fully asynchronous, or whether there are some timing assumptions. These timing assumptions allow us to introduce operation timeouts and retries. ([Location 3359](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3359)) - We do not know whether the database hasn’t responded because it’s overloaded, unavailable, or slow, or because of some problems with the network on the way to it. This describes a nature of a crash: ([Location 3362](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3362)) - We need to define a failure model and describe ways in which failures can occur before we decide how to treat them. ([Location 3364](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3364)) - A property that describes system reliability and whether or not it can continue operating correctly in the presence of failures is called fault tolerance. ([Location 3366](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3366)) - However, now we face a different problem: how do we keep multiple copies of shared state in sync? ([Location 3370](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3370)) - We now know that sharing state is not as simple as just introducing a database, and have to take a more granular approach and describe interactions in terms of independent processes and passing messages between them. ([Location 3371](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3371)) - We should make as few assumptions about latency as possible and never assume that latency is zero. ([Location 3385](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3385)) - Michael Lewis, in his Flash Boys book (Simon and Schuster), tells a story about companies spending millions of dollars to reduce latency by several milliseconds to able to access stock exchanges faster than the competition. This is a great example of using latency as a competitive advantage, but it’s worth mentioning that, according to some other studies, such as [BARTLETT16], the chance of stale-quote arbitrage (the ability to profit from being able to know prices and execute orders faster than the competition) doesn’t give fast traders the ability to exploit markets. ([Location 3388](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3388)) - When increasing the number, rates, and sizes of exchanged messages, or adding new processes to the existing network, we should not assume that bandwidth is infinite. ([Location 3394](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3394)) - If we have to wait for several remote servers working in parallel to respond to complete the task, the execution as a whole is as slow as the slowest remote server. ([Location 3410](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3410)) - Contrary to the widespread belief, queue capacity is not infinite and piling up more requests won’t do the system any good. ([Location 3411](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3411)) - Backpressure is a strategy that allows us to cope with producers that publish messages at a rate that is faster than the rate at which consumers can process them by slowing down the producers. ([Location 3413](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3413)) - Increasing the queue size may negatively impact latency, since changing it has no effect on the processing rate. ([Location 3417](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3417)) - Overall system latency increases because of the time spent in the queue, but this is usually still better than responding with a failure and retrying the request. ([Location 3426](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3426)) - we can size queues by measuring task processing times and the average time each task spends in the queue before it is processed, ([Location 3428](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3428)) - Assuming that clocks on remote machines run in sync can also be dangerous. Combined with latency is zero and processing is instantaneous, it leads to different idiosyncrasies, especially in time-series and real-time data processing. ([Location 3435](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3435)) - For example, when collecting and aggregating data from participants with a different perception of time, you should understand time drifts between them and normalize times accordingly, rather than relying on the source timestamp. ([Location 3437](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3437)) - Spanner (see “Distributed Transactions with Spanner”) uses a special time API that returns a timestamp and uncertainty bounds to impose a strict transaction order. Some failure-detection algorithms rely on a shared notion of time and a guarantee that the clock drift is always within allowed bounds for correctness [GUPTA01]. ([Location 3442](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3442)) - Distributed algorithms do not always guarantee strict state consistency. ([Location 3453](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3453)) - Some approaches have looser constraints and allow state divergence between replicas, and rely on conflict resolution (an ability to detect and resolve diverged states within the system) and read-time data repair (bringing replicas back in sync during reads in cases where they respond with different results). ([Location 3454](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3454)) - An eventually consistent distributed database system might have the logic to handle replica disagreement by querying a quorum of nodes during reads, ([Location 3458](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3458)) - but assume that the database schema and the view of the cluster are strongly consistent. ([Location 3459](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3459)) - one of the nodes assumes that the other node holds data records for a key, but this other node has a different view of the cluster, reading or writing the data can result in misplacing data records or getting an empty response while data records are in fact happily present on the other node. ([Location 3464](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3464)) - Understanding the process of iteration over the remote dataset is an entirely different problem: you need to understand consistency and delivery semantics, data reconciliation, paging, merges, concurrent access implications, and many other things. ([Location 3471](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3471)) - Simply hiding both behind the same interface, however useful, might be misleading. ([Location 3473](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3473)) - We should always keep in mind that local and remote execution are not the same [WALDO96]. ([Location 3474](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3474)) - The most apparent problem with hiding remote calls is latency: remote invocation is many times more costly than the local one, since it involves two-way network transport, serialization/deserialization, and many other steps. Interleaving local and blocking remote calls may lead to performance degradation and unintended side effects [VINOSKI08] ([Location 3475](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3475)) - Some distributed algorithms use heartbeat protocols and failure detectors to form a hypothesis about which participants are alive and reachable. ([Location 3485](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3485)) - When two or more servers cannot communicate with each other, we call the situation network partition. ([Location 3487](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3487)) - “Perspectives on the CAP Theorem” [GILBERT12], Seth Gilbert and Nancy Lynch draw a distinction between the case when two participants cannot communicate with each other and when several groups of participants are isolated from one another, cannot exchange messages, and proceed with the algorithm. ([Location 3489](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3489)) - Network links can also fail asymmetrically: messages can still be getting delivered from one process to the other one, but not vice versa. ([Location 3493](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3493)) - When designing highly available systems, one should always think about edge cases: what if we did replicate the data, but received no acknowledgments? Do we need to retry? Is the data still going to be available for reads on the nodes that have sent acknowledgments? ([Location 3498](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3498)) - The best way to design for failures is to test for them. ([Location 3503](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3503)) - Setting up testing harnesses that create partitions, simulate bit rot [GRAY05], increase latencies, diverge clocks, and magnify relative processing speeds is the best way to go about it. ([Location 3504](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3504)) - Over the last few years, we’ve seen a few open source projects that help to recreate different failure scenarios. Toxiproxy can help to simulate network problems: limit the bandwidth, introduce latency, timeouts, and more. Chaos Monkey takes a more radical approach and exposes engineers to production failures by randomly shutting down services. CharybdeFS helps to simulate filesystem and hardware errors and failures. You can use these tools to test your software and make sure it behaves correctly in the presence of these failures. CrashMonkey, a filesystem agnostic record-replay-and-test framework, helps test data and metadata consistency for persistent files. ([Location 3508](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3508)) - Cascading failures can propagate from one part of the system to the other, increasing the scope of the problem. ([Location 3519](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3519)) - For example, a node was offline for a while and did not receive the most recent updates. After it comes back online, helpful peers would like to help it to catch up with recent happenings and start streaming the data it’s missing over to it, exhausting network resources or causing the node to fail shortly after the startup. ([Location 3520](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3520)) - To protect a system from propagating failures and treat failure scenarios gracefully, circuit breakers can be used. ([Location 3523](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3523)) - In software development, circuit breakers monitor failures and allow fallback mechanisms that can protect the system by steering away from the failing service, giving it some time to recover, and handling failing calls gracefully. ([Location 3525](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3525)) - By that point, an overloaded server already has a hard time catching up with new connection requests, and client-side retries in a tight loop don’t help the situation. To avoid that, we can use a backoff strategy. Instead of retrying immediately, clients wait for some time. Backoff can help us to avoid amplifying problems by scheduling retries and increasing the time window between subsequent requests. ([Location 3528](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3528)) - To prevent different clients from retrying all at once after the backoff period, we can introduce jitter. Jitter adds small random time periods to backoff and reduces the probability of clients waking up and retrying at the same time. ([Location 3532](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3532)) - Without validation mechanisms in place, a system can propagate corrupted data to the other nodes, potentially overwriting noncorrupted data records. To avoid that, we should use checksumming and validation to verify the integrity of any content exchanged between the nodes. ([Location 3537](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3537)) - Instead of letting peers execute operation steps independently, we can use a coordinator that prepares an execution plan based on the available resources and predicts the load based on the past execution data available to it. ([Location 3540](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3540)) - Any communication medium is imperfect, and messages can get lost or delayed. ([Location 3560](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3560)) - Notice that the sender does not have any way to find out if the message is already delivered. In distributed systems terminology, this kind of link is called fair-loss. ([Location 3565](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3565)) - We can assume that this link is not losing messages between communicating parties systematically and doesn’t create new messages. But, at the same time, we cannot entirely rely on it. This might remind you of the User Datagram Protocol (UDP) ([Location 3573](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3573)) - To improve the situation and get more clarity in terms of message status, we can introduce acknowledgments: a way for the recipient to notify the sender that it has received the message. ([Location 3577](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3577)) - Retransmits are a way for the sender to retry a potentially failed operation. We say potentially failed, because the sender doesn’t really know whether it has failed or not, since the type of link we’re about to discuss does not use acknowledgments. ([Location 3596](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3596)) - After process A sends message M, it waits until timeout T is triggered and tries to send the same message again. ([Location 3598](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3598)) - In distributed systems terminology, this abstraction is called a stubborn link. It’s called stubborn because the sender keeps resending the message again and again indefinitely, but, since this sort of abstraction would be highly impractical, we need to combine retries with acknowledgments. ([Location 3602](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3602)) - Processing duplicates is only safe if the operation we’re about to perform is idempotent. An idempotent operation is one that can be executed multiple times, yielding the same result without producing additional side effects. For example, a server shutdown operation can be idempotent, the first call initiates the shutdown, and all subsequent calls do not produce any additional effects. ([Location 3609](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3609)) - If every operation was idempotent, we could think less about delivery semantics, ([Location 3612](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3612)) - Idempotence is particularly important in the presence of partial failures and network partitions, since we cannot always find out the exact status of a remote operation — whether it has succeeded, failed, or will be executed shortly — and we just have to wait longer. ([Location 3616](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3616)) - To achieve this, we can use deduplication and avoid processing messages more than once. ([Location 3619](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3619)) - Unreliable networks present us with two problems: messages can arrive out of order and, because of retransmits, some messages may arrive more than once. ([Location 3621](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3621)) - Deduplication works by checking if the message with a sequence number n has already been processed (passed down the stack by the receiver) and discarding already processed messages. ([Location 3633](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3633)) - In distributed systems terms, this type of link is called a perfect link, which provides the following guarantees [CACHIN11]: Reliable delivery Every message sent once by the correct process A to the correct process B, will eventually be delivered. No duplication No message is delivered more than once. No creation Same as with other types of links, it can only deliver the messages that were actually sent. ([Location 3634](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3634)) - This might remind you of the TCP4 protocol (however, reliable delivery in TCP is guaranteed only in the scope of a single session). ([Location 3642](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3642)) - In addition, TCP has selective acknowledgments, flow control, congestion control, error detection, and many other features that are out of the scope of our discussion. ([Location 3645](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3645)) - There are only two hard problems in distributed systems: 2. Exactly-once delivery 1. Guaranteed order of messages 2. Exactly-once delivery. Mathias Verraes ([Location 3647](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3647)) - at-least-once delivery, which ensures that the sender retries until it receives an acknowledgment, otherwise the message is not considered to be received. ([Location 3652](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3652)) - most-once: the sender sends the message and doesn’t expect any delivery confirmation. ([Location 3654](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3654)) - The TCP protocol works by breaking down messages into packets, transmitting them one by one, and stitching them back together on the receiving side. ([Location 3654](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3654)) - Since TCP marks each packet with a sequence number, even though some packets were transmitted more than once, it can deduplicate the packets and guarantee that the recipient will see the message and process it only once. ([Location 3656](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3656)) - This means that exactly-once processing is what’s interesting here since duplicate deliveries (or packet transmissions) have no side effects and are merely an artifact of the best effort by the link. ([Location 3660](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3660)) - For the exactly-once guarantee to hold, nodes should have a common knowledge [HALPERN90]: everyone knows about some fact, and everyone knows that everyone else also knows about that fact. In simplified terms, nodes have to agree on the state of the record: both nodes agree that it either was or was not persisted. As ([Location 3663](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3663)) - Two Generals’ Problem. This thought experiment shows that it is impossible to achieve an agreement between two parties if communication is asynchronous in the presence of link failures. ([Location 3675](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3675)) - it’s important to remember that perfect links, despite the name, do not guarantee perfect delivery. ([Location 3678](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3678)) - In a paper by Fisher, Lynch, and Paterson, the authors describe a problem famously known as the FLP Impossibility Problem [FISCHER85] (derived from the first letters of authors’ last names), wherein they discuss a form of consensus in which processes start with an initial value and attempt to agree on a new value. ([Location 3697](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3697)) - A consensus protocol describes a system that, given multiple processes starting at its initial state, brings all of the processes to the decision state. ([Location 3703](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3703)) - Agreement The decision the protocol arrives at has to be unanimous: each process decides on some value, and this has to be the same for all processes. Otherwise, we have not reached a consensus. Validity The agreed value has to be proposed by one of the participants, which means that the system should not just “come up” with the value. This also implies nontriviality of the value: processes should not always decide on some predefined default value. Termination An agreement is final only if there are no processes that did not reach the decision state. ([Location 3706](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3706)) - FISCHER85] assumes that processing is entirely asynchronous; there’s no shared notion of time between the processes. Algorithms in such systems cannot be based on timeouts, and there’s no way for a process to find out whether the other process has crashed or is simply running too slow. ([Location 3712](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3712)) - The paper shows that, given these assumptions, there exists no protocol that can guarantee consensus in a bounded time. No completely asynchronous consensus algorithm can tolerate the unannounced crash of even a single remote process. ([Location 3714](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3714)) - It only means that we cannot always reach consensus in an asynchronous system in bounded time. ([Location 3718](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3718)) - In an asynchronous system, we do not know the relative speeds of processes, and cannot guarantee message delivery in a bounded time or a particular order. ([Location 3723](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3723)) - The main criticism of asynchronous systems is that these assumptions are not realistic: processes can’t have arbitrarily different processing speeds, and links don’t take indefinitely long to deliver messages. ([Location 3725](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3725)) - under the synchronous model. It assumes that processes are progressing at comparable rates, that transmission delays are bounded, and message delivery cannot take arbitrarily long. ([Location 3731](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3731)) - A synchronous system can also be represented in terms of synchronized process-local clocks: there is an upper time bound in time difference between the two process-local time sources [CACHIN11] ([Location 3732](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3732)) - partially synchronous system exhibits some of the properties of the synchronous system, but the bounds of message delivery, clock drift, and relative processing speeds might not be exact and hold only most of the time [DWORK88] ([Location 3741](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3741)) - A failure model describes exactly how processes can crash in a distributed system, and algorithms are developed using these assumptions. ([Location 3748](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3748)) - It only means that the algorithm does not rely on recovery for correctness or liveness. Nothing prevents processes from recovering, catching up with the system state, and participating in the next instance of the algorithm. ([Location 3760](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3760)) - Failed processes are not able to continue participating in the current round of negotiations during which they failed. ([Location 3761](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3761)) - Crash-recovery is a different process abstraction, under which the process stops executing the steps required by the algorithm, but recovers at a later point and tries to execute further steps. ([Location 3764](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3764)) - omission fault. This model assumes that the process skips some of the algorithm steps, or is not able to execute them, or this execution is not visible to other participants, or it cannot send or receive messages to and from other participants. ([Location 3773](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3773)) - The hardest class of failures to overcome is arbitrary or Byzantine faults: a process continues executing the algorithm steps, but in a way that contradicts the algorithm (for example, if a process in a consensus algorithm decides on a value that no other participant has ever proposed). ([Location 3783](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3783)) - If a tree falls in a forest and no one is around to hear it, does it make a sound? ([Location 3819](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3819)) - A failure detector is a local subsystem responsible for identifying failed or unreachable processes to exclude them from the algorithm and guarantee liveness while preserving safety. ([Location 3837](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3837)) - liveness is a property that guarantees that a specific intended event must occur. ([Location 3841](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3841)) - We can think of the relationship between efficiency and accuracy as a tunable parameter: a more efficient algorithm might be less precise, and a more accurate algorithm is usually less efficient. ([Location 3852](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3852)) - Many distributed systems implement failure detectors by using heartbeats. This approach is quite popular because of its simplicity and strong completeness. ([Location 3856](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3856)) - Akka, a popular framework for building distributed systems, has an implementation of a deadline failure detector, which uses heartbeats and reports a process failure if it has failed to register within a fixed time interval. ([Location 3873](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3873)) - This approach has several potential downsides: its precision relies on the careful selection of ping frequency and timeout, ([Location 3875](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3875)) - Heartbeat, a timeout-free failure detector [AGUILERA97], is an algorithm that only counts heartbeats and allows the application to detect process failures based on the data in the heartbeat counter vectors. ([Location 3880](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3880)) - The algorithm assumes that any two correct processes are connected to each other with a fair path, which contains only fair links (i.e., if a message is sent over this link infinitely often, it is also received infinitely often), and each process is aware of the existence of all other processes in the network. ([Location 3882](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3882)) - An alternative approach, used by the Scalable Weakly Consistent Infection-style Process Group Membership Protocol (SWIM) [GUPTA01] is to use outsourced heartbeats to improve reliability using information about the process liveness from the perspective of its neighbors. ([Location 3896](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3896)) - Outsourced heartbeats allow reliable failure detection by distributing responsibility for deciding across the group of members. ([Location 3906](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3906)) - Distribution parameters are estimated from the sampling window by determining the mean and variance of samples. This information is used to compute the probability of arrival of the message within t time units after the previous one. Given this information, we compute φ, which describes how likely we are to make a correct decision about a process’s liveness. In other words, how likely it is to make a mistake and receive a heartbeat that will contradict the calculated assumptions. ([Location 3928](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3928)) - This approach was developed by researchers from the Japan Advanced Institute of Science and Technology, and is now used in many distributed systems; for example, Cassandra and Akka (along with the aforementioned deadline failure detector). ([Location 3931](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3931)) - Each member maintains a list of other members, their heartbeat counters, and timestamps, specifying when the heartbeat counter was incremented for the last time. Periodically, each member increments its heartbeat counter and distributes its list to a random neighbor. Upon the message receipt, the neighboring node merges the list with its own, updating heartbeat counters for the other neighbors. ([Location 3938](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3938)) - Nodes also periodically check the list of states and heartbeat counters. If any node did not update its counter for long enough, it is considered failed. ([Location 3941](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3941)) - Using gossip for propagating system states increases the number of messages in the system, but allows information to spread more reliably. ([Location 3951](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3951)) - To detect process failures, this approach arranges all active processes in groups. If one of the groups becomes unavailable, all participants detect the failure. In other words, every time a single process failure is detected, it is converted and propagated as a group failure. This allows detecting failures in the presence of any pattern of disconnects, partitions, and node failures. ([Location 3957](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3957)) - Failure detectors help to augment the model, allowing us to solve a consensus problem by making a trade-off between accuracy and completeness. ([Location 3976](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3976)) - Synchronization can be quite costly: if each algorithm step involves contacting each other participant, we can end up with a significant communication overhead. This is particularly true in large and geographically distributed networks. To reduce synchronization overhead and the number of message round-trips required to reach a decision, some algorithms rely on the existence of the leader (sometimes called coordinator) process, responsible for executing or coordinating steps of a distributed algorithm. ([Location 3993](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3993)) - Usually, the process remains a leader until it crashes. After the crash, any other process can start a new election round, assume leadership, if it gets elected, and continue the failed leader’s work. ([Location 3999](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=3999)) - Ideally, we’d like to assume safety, too, and guarantee there may be at most one leader at a time, and completely eliminate the possibility of a split brain situation (when two leaders serving the same purpose are elected but unaware of each other). However, in practice, many leader election algorithms violate this agreement. ([Location 4002](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4002)) - Even though leader election and distributed locking (i.e., exclusive ownership over a shared resource) might look alike from a theoretical perspective, they are slightly different. If one process holds a lock for executing a critical section, it is unimportant for other processes to know who exactly is holding a lock right now, as long as the liveness property is satisfied (i.e., the lock will be eventually released, allowing others to acquire it). In contrast, the elected process has some special properties and has to be known to all other participants, so the newly elected leader has to notify its peers about its role. ([Location 4010](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4010)) - Having a stable leader in the system helps to avoid state synchronization between remote participants, reduce the number of exchanged messages, and drive execution from a single process instead of requiring peer-to-peer coordination. ([Location 4016](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4016)) - Instead of having a single system-wide leader, each replica set has its own leader. ([Location 4020](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4020)) - bully algorithm, uses process ranks to identify the new leader. ([Location 4028](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4028)) - This algorithm is known for its simplicity. The algorithm is named bully because the highest-ranked node “bullies” other nodes into accepting it. ([Location 4030](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4030)) - It is also known as monarchial leader election: the highest-ranked sibling becomes a monarch after the previous one ceases to exist. ([Location 4031](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4031)) - One of the apparent problems with this algorithm is that it violates the safety guarantee (that at most one leader can be elected at a time) in the presence of network partitions. It is quite easy to end up in the situation where nodes get split into two or more independently functioning subsets, and each subset elects its leader. This situation is called split brain. ([Location 4045](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4045)) - Another problem with this algorithm is a strong preference toward high-ranked nodes, which becomes an issue if they are unstable and can lead to a permanent state of reelection. ([Location 4048](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4048)) - Each elected leader provides a list of failover nodes. When one of the processes detects a leader failure, it starts a new election round by sending a message to the highest-ranked alternative from the list provided by the failed leader. ([Location 4055](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4055)) - by splitting the nodes into two subsets, candidate and ordinary, ([Location 4068](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4068)) - The ordinary process initiates election by contacting candidate nodes, collecting responses from them, picking the highest-ranked alive candidate as a new leader, and then notifying the rest of the nodes about the election results. ([Location 4069](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4069)) - To solve the problem with multiple simultaneous elections, the algorithm proposes to use a tiebreaker variable δ, a process-specific delay, varying significantly between the nodes, that allows one of the nodes to initiate the election before the other ones. ([Location 4071](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4071)) - The tiebreaker time is generally greater than the message round-trip time. Nodes with higher priorities have a lower δ, and vice versa. ([Location 4073](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4073)) - Each process starts as a leader of a new group, where the only member is the process itself. Group leaders contact peers that do not belong to their groups, inviting them to join. If the peer process is a leader itself, two groups are merged. ([Location 4083](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4083)) - a leader of a larger group can become a leader for a new group. ([Location 4094](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4094)) - The invitation algorithm allows creating process groups and merging them without having to trigger a new election from scratch, reducing the number of messages required to finish the election. ([Location 4096](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4096)) - In the ring algorithm [CHANG79], all nodes in the system form a ring and are aware of the ring topology (i.e., their predecessors and successors in the ring). When the process detects the leader failure, it starts the new election. The election message is forwarded across the ring: each process contacts its successor (the next node closest to it in the ring). If this node is unavailable, the process skips the unreachable node and attempts to contact the nodes after it in the ring, until eventually one of them responds. ([Location 4098](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4098)) - The algorithm proceeds by fully traversing the ring. When the message comes back to the node that started the election, the highest-ranked node from the live set is chosen as a leader. ([Location 4105](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4105)) - Variants of this algorithm include collecting a single highest-ranked identifier instead of a set of active nodes to save space: since the max function is commutative, it is enough to know a current maximum. ([Location 4113](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4113)) - Election rounds might be costly but, since they’re infrequent, they do not have a negative impact on the overall system performance. ([Location 4121](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4121)) - Unfortunately, all the algorithms we’ve discussed in this chapter are prone to the split brain problem: we can end up with two leaders in independent subnets that are not aware of each other’s existence. To avoid split brain, we have to obtain a cluster-wide majority of votes. ([Location 4123](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4123)) - In both cases, having a leader is a way to ensure liveness (if the current leader has failed, we need a new one), and processes should not take indefinitely long to understand whether or not it has really failed. Lack of safety and allowing multiple leaders is a performance optimization: algorithms can proceed with a replication phase, and safety is guaranteed by detecting and resolving the conflicts. ([Location 4138](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4138)) - Fault tolerance is a property of a system that can continue operating correctly in the presence of failures of its components. ([Location 4155](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4155)) - The primary goal is to remove a single point of failure from the system and make sure that we have redundancy in mission-critical components. ([Location 4157](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4157)) - Data replication is a way of introducing redundancy by maintaining multiple copies of data in the system. ([Location 4162](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4162)) - Geo-replication, in this case, serves multiple purposes: it increases availability and the ability to withstand a failure of one or more datacenters by providing redundancy. ([Location 4167](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4167)) - Availability is a property that measures the ability of the system to serve a response for every request successfully. ([Location 4185](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4185)) - Consistency is defined here as atomic or linearizable consistency (see “Linearizability”). ([Location 4188](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4188)) - Availability requirement is impossible to satisfy in an asynchronous system, and we cannot implement a system that simultaneously guarantees both availability and consistency in the presence of network partitions [GILBERT02] ([Location 4196](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4196)) - We can build systems that guarantee strong consistency while providing best effort availability, or guarantee availability while providing best effort consistency [GILBERT12] ([Location 4199](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4199)) - Best effort here implies that if everything works, the system will not purposefully violate any guarantees, but guarantees are allowed to be weakened and violated in the case of network partitions. ([Location 4201](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4201)) - CP systems prefer failing requests to serving potentially inconsistent data. ([Location 4204](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4204)) - AP systems loosen the consistency requirement and allow serving potentially inconsistent values during the request. ([Location 4206](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4206)) - An example of a CP system is an implementation of a consensus algorithm, requiring a majority of nodes for progress: always consistent, but might be unavailable in the case of a network partition. ([Location 4207](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4207)) - PACELEC conjecture [ABADI12], an extension of CAP, states that in presence of network partitions there’s a choice between consistency and availability (PAC). Else (E), even if the system is running normally, we still have to make a choice between latency and consistency. ([Location 4210](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4210)) - ACID consistency describes transaction consistency: transaction brings the database from one valid state to another, maintaining all the database invariants (such as uniqueness constraints and referential integrity). In CAP, it means that operations are atomic (operations succeed or fail in their entirety) and consistent (operations never leave the data in an inconsistent state). ([Location 4223](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4223)) - Of course, there are more complicated failure scenarios and CAP conjecture is just a rule of thumb, and it doesn’t necessarily tell the whole truth.1 ([Location 4233](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4233)) - CAP conjecture discusses consistency and availability only in their strongest forms: linearizability and the ability of the system to eventually respond to every request. ([Location 4236](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4236)) - Instead of being either consistent or available, systems can provide relaxed guarantees. We can define two tunable metrics: harvest and yield, ([Location 4239](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4239)) - Harvest Defines how complete the query is: if the query has to return 100 rows, but can fetch only 99 due to unavailability of some nodes, it still can be better than failing the query completely and returning nothing. ([Location 4242](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4242)) - Yield Specifies the number of requests that were completed successfully, compared to the total number of attempted requests. Yield is different from the uptime, since, for example, a busy node is not down, but still can fail to respond to some of the requests. ([Location 4244](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4244)) - One of the ways to increase yield is to return query results only from the available partitions (see “Database Partitioning” ([Location 4248](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4248)) - A single unit of storage, accessible by read or write operations, is usually called a register. ([Location 4257](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4257)) - We can view shared memory in a distributed database as an array of such registers. ([Location 4258](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4258)) - Reads to the safe registers may return arbitrary values within the range of the register during a concurrent write operation ([Location 4275](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4275)) - For regular registers, we have slightly stronger guarantees: a read operation can return only the value written by the most recent completed write or the value written by the write operation that overlaps with the current read. ([Location 4279](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4279)) - Atomic registers guarantee linearizability: every write operation has a single moment before which every read operation returns an old value and after which every read operation returns a new one. ([Location 4284](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4284)) - To reason about the operation order and have nonambiguous descriptions of possible outcomes, we have to define consistency models. ([Location 4305](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4305)) - Even though a lot of terminology between concurrent and distributed systems overlap, we can’t directly apply most of the concurrent algorithms, because of differences in communication patterns, performance, and reliability. ([Location 4307](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4307)) - Consistency models provide different semantics and guarantees. You can think of a consistency model as a contract between the participants: what each replica has to do to satisfy the required semantics, and what users can expect when issuing read and write operations. ([Location 4313](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4313)) - helps us to distinguish between “all possible histories” of interleaving operations and “histories permissible under model X,” which significantly simplifies reasoning about the visibility of state changes. ([Location 4318](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4318)) - We can think about consistency from the perspective of state, describe which state invariants are acceptable, and establish allowable relationships between copies of the data placed onto different replicas. ([Location 4320](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4320)) - we can consider operation consistency, which provides an outside view on the data store, describes operations, and puts constraints on the order in which they occur [TANENBAUM06] [AGUILERA16] ([Location 4322](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4322)) - Without a global clock, it is difficult to give distributed operations a precise and deterministic order. ([Location 4325](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4325)) - Now we have to juggle not only consistency and availability, but also consider consistency in terms of synchronization costs [ATTIYA94]. Synchronization costs may include latency, additional CPU cycles spent executing additional operations, disk I/O used to persist recovery information, wait time, network I/O, and everything else that can be prevented by avoiding synchronization. ([Location 4329](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4329)) - Strict consistency is the equivalent of complete replication transparency: any write by any process is instantly available for the subsequent reads by any process. ([Location 4337](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4337)) - Unfortunately, this is just a theoretical model, and it’s impossible to implement, as the laws of physics and the way distributed systems work set limits on how fast things may happen [SINHA97]. ([Location 4341](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4341)) - Under this model, effects of the write become visible to all readers exactly once at some point in time between its start and end, and no client can observe state transitions or side effects of partial (i.e., unfinished, still in-flight) or incomplete (i.e., interrupted before completion) write operations [LEE15]. ([Location 4346](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4346)) - Linearizability respects both sequential process-local operation order and the order of operations running in parallel relative to other processes, and defines a total order of the events. ([Location 4356](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4356)) - This order should be consistent, which means that every read of the shared value should return the latest value written to this shared variable preceding this read, or the value of a write that overlaps with this read. ([Location 4357](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4357)) - One of the most important traits of linearizability is visibility: once the operation is complete, everyone must see it, and the system can’t “travel back in time,” reverting it or making it invisible for some participants. In other words, linearization prohibits stale reads and requires reads to be monotonic. ([Location 4373](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4373)) - Operations do not have to be instantaneous (also because there’s no such thing), but their effects have to become visible at some point in time, making an illusion that they were instantaneous. This moment is called a linearization point. ([Location 4376](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4376)) - The linearization point serves as a cutoff, after which operation effects become visible. We can implement it by using locks to guard a critical section, atomic read/write, or read-modify-write primitives. ([Location 4389](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4389)) - Many systems avoid implementing linearizability today. Even CPUs do not offer linearizability when accessing main memory by default. ([Location 4398](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4398)) - This has happened because synchronization instructions are expensive, slow, and involve cross-node CPU traffic and cache invalidations. ([Location 4399](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4399)) - In concurrent programming, you can use compare-and-swap operations to introduce linearizability. Many algorithms work by preparing results and then using CAS for swapping pointers and publishing them. For ([Location 4402](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4402)) - In distributed systems, linearizability requires coordination and ordering. ([Location 4404](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4404)) - It can be implemented using consensus: clients interact with a replicated store using messages, and the consensus module is responsible for ensuring that applied operations are consistent and identical across the cluster. ([Location 4405](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4405)) - Interestingly, linearizability in its traditional understanding is regarded as a local property and implies composition of independently implemented and verified elements. Combining linearizable histories produces a history that is also linearizable [HERLIHY90]. In other words, a system in which all objects are linearizable, is also linearizable. ([Location 4408](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4408)) - Achieving linearizability might be too expensive, but it is possible to relax the model, while still providing rather strong consistency guarantees. ([Location 4436](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4436)) - Sequential consistency allows ordering operations as if they were executed in some sequential order, while requiring operations of each individual process to be executed in the same order they were performed by the process. ([Location 4438](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4438)) - Order of execution between processes is undefined, as there’s no shared notion of time. ([Location 4441](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4441)) - Operations can be ordered in different ways (depending on the arrival order, or even arbitrarily in case two writes arrive simultaneously), but all processes observe the operations in the same order. ([Location 4446](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4446)) - Sequential consistency is often confused with linearizability since both have similar semantics. Sequential consistency, just as linearizability, requires operations to be globally ordered, but linearizability requires the local order of each process and global order to be consistent. ([Location 4451](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4451)) - In other words, linearizability respects a real-time operation order. Under sequential consistency, ordering holds only for the same-origin writes [VIOTTI16]. Another important distinction is composition: we can combine linearizable histories and still expect results to be linearizable, while sequentially consistent schedules are not composable [ATTIYA94]. ([Location 4453](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4453)) - What’s important here is that both P3 and P4 have observed values in the same order: first 2, and then 1 [TANENBAUM14]. ([Location 4460](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4460)) - Stale reads can be explained, for example, by replica divergence: even though writes propagate to different replicas in the same order, they can arrive there at different times. ([Location 4463](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4463)) - Similar to linearizability, modern CPUs do not guarantee sequential consistency by default and, since the processor can reorder instructions, we should use memory barriers (also called fences) to make sure that writes become visible to concurrently running threads in order [DREPPER07] [GEORGOPOULOS16] ([Location 4472](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4472)) - You see, there is only one constant, one universal, it is the only real truth: causality. Action. Reaction. Cause and effect. Merovingian from The Matrix Reloaded ([Location 4476](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4476)) - Under the causal consistency model, all processes have to see causally related operations in the same order. Concurrent writes with no causal relationship can be observed in a different order by different processors. ([Location 4479](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4479)) - This establishes a causal order between these operations. Even if the latter write propagates faster than the former one, it isn’t made visible until all of its dependencies arrive, and the event order is reconstructed from their logical timestamps. ([Location 4493](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4493)) - In a causally consistent system, we get session guarantees for the application, ensuring the view of the database is consistent with its own actions, even if it executes read and write requests against different, potentially inconsistent, servers [TERRY94] ([Location 4503](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4503)) - These guarantees are: monotonic reads, monotonic writes, read-your-writes, writes-follow-reads. ([Location 4505](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4505)) - Causal consistency can be implemented using logical clocks [LAMPORT78] and sending context metadata with every message, summarizing which operations logically precede the current one. When ([Location 4507](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4507)) - The two prominent and frequently cited projects implementing causal consistency are Clusters of Order-Preserving Servers (COPS) [LLOYD11] and Eiger [LLOYD13] ([Location 4510](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4510)) - Many databases, for example, Dynamo [DECANDIA07] and Riak [SHEEHY10a], use vector clocks [LAMPORT78] [MATTERN88] for establishing causal order. ([Location 4521](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4521)) - A vector clock is a structure for establishing a partial order between the events, detecting and resolving divergence between the event chains. ([Location 4524](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4524)) - Processes maintain vectors of logical clocks, with one clock per process. Every clock starts at the initial value and is incremented every time a new event arrives (for example, a write occurs). When receiving clock vectors from other processes, a process updates its local vector to the highest clock values per process from the received vectors (i.e., highest clock values the transmitting node has ever seen). ([Location 4526](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4526)) - Since we’re looking for a consistency model that would improve availability and performance, we have to allow replicas to diverge not only by serving stale reads but also by accepting potentially conflicting writes, so the system is allowed to create two independent chains of events. ([Location 4535](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4535)) - To implement causal consistency, we have to store causal history, add garbage collection, and ask the user to reconcile divergent histories in case of a conflict. Vector clocks can tell you that the conflict has occurred, but do not propose exactly how to resolve it, since resolution semantics are often application-specific. ([Location 4541](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4541)) - Session models [VIOTTI16] (also called client-centric consistency models [TANENBAUM06]) help to reason about the state of the distributed system from the client perspective: how each client observes the state of the system while issuing read and write operations. ([Location 4552](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4552)) - We still assume that each client’s operations are sequential: it has to finish one operation before it can start executing the next one. If the client crashes or loses connection to the server before its operation completes, we do not make any assumptions about the state of incomplete operations. ([Location 4557](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4557)) - In a distributed system, clients often can connect to any available replica and, if the results of the recent write against one replica did not propagate to the other one, the client might not be able to observe the state change it has made. ([Location 4559](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4559)) - This assumption holds under the read-own-writes consistency model, which states that every read operation following the write on the same or the other replica has to observe the updated value. ([Location 4562](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4562)) - The monotonic reads model restricts the value visibility and states that if the read(x) has observed the value V, the following reads have to observe a value at least as recent as V or some later value. ([Location 4565](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4565)) - The monotonic writes model assumes that values originating from the same client appear in the order this client has executed them. ([Location 4568](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4568)) - Writes-follow-reads (sometimes referred as session causality) ensures that writes are ordered after writes that were observed by previous read operations. ([Location 4572](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4572)) - Combining monotonic reads, monotonic writes, and read-own-writes gives Pipelined RAM (PRAM) consistency [LIPTON88] [BRZEZINSKI03], also known as FIFO consistency. PRAM guarantees that write operations originating from one process will propagate in the order they were executed by this process. Unlike under sequential consistency, writes from different processes can be observed in different order. ([Location 4580](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4580)) - Under eventual consistency, updates propagate through the system asynchronously. ([Location 4590](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4590)) - Formally, it states that if there are no additional updates performed against the data item, eventually all accesses return the latest written value [VOGELS09] ([Location 4590](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4590)) - case of a conflict, the notion of latest value might change, as the values from diverged replicas are reconciled using a conflict resolution strategy, such as last-write-wins or using vector clocks (see “Vector clocks”). ([Location 4592](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4592)) - Replication Factor N Number of nodes that will store a copy of data. Write Consistency W Number of nodes that have to acknowledge a write for it to succeed. Read Consistency R Number of nodes that have to respond to a read operation for it to succeed. ([Location 4602](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4602)) - Choosing consistency levels where (R + W > N), the system can guarantee returning the most recent written value, because there’s always an overlap between read and write sets. ([Location 4606](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4606)) - For example, if N = 3, W = 2, and R = 2, the system can tolerate a failure of just one node. ([Location 4608](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4608)) - During the read, two replicas out of three have to be available to serve the request for us to respond with consistent results. ([Location 4611](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4611)) - When performing a write, the coordinator should submit it to N nodes, but can wait for only W nodes before it proceeds (or W - 1 in case the coordinator is also a replica). ([Location 4613](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4613)) - The rest of the write operations can complete asynchronously or fail. ([Location 4614](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4614)) - Similarly, when performing a read, the coordinator has to collect at least R responses. Some databases use speculative execution and submit extra read requests to reduce coordinator response latency. This means if one of the originally submitted read requests fails or arrives slowly, speculative requests can be counted toward R instead. ([Location 4614](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4614)) - The same is true for the W = N, R = 1 combination: the latest value can be read from any node, as long as writes succeed only after being applied on all replicas. ([Location 4619](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4619)) - Increasing read or write consistency levels increases latencies and raises requirements for node availability during requests. Decreasing them improves system availability while sacrificing consistency. ([Location 4620](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4620)) - A consistency level that consists of ⌊N/2⌋ + 1 nodes is called a quorum, a majority of nodes. ([Location 4622](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4622)) - In other words, such systems can tolerate at most f node failures. ([Location 4626](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4626)) - For example, if there are three replicas in total, and two of them are down, read and write operations won’t be able to achieve the number of nodes necessary for read and write consistency, since only one node out of three will be able to respond to the request. ([Location 4627](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4627)) - If some write operation has failed after writing a value to one replica out of three, depending on the contacted replicas, a quorum read can return either the result of the incomplete operation, or the old value. Since subsequent same-value reads are not required to contact the same replicas, values they return can alternate. To achieve read monotonicity (at the cost of availability), we have to use blocking read-repair (see “Read Repair”). ([Location 4630](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4630)) - Using quorums for read consistency helps to improve availability: even if some of the nodes are down, a database system can still accept reads and serve writes. ([Location 4634](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4634)) - However, using replication and majorities increases storage costs: we have to store a copy of the data on each replica. If our replication factor is five, we have to store five copies. ([Location 4638](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4638)) - We can improve storage costs by using a concept called witness replicas. Instead of storing a copy of the record on each replica, we can split replicas into copy and witness subsets. ([Location 4639](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4639)) - In cases of write timeouts or copy replica failures, witness replicas can be upgraded to temporarily store the record in place of failed or timed-out copy replicas. ([Location 4643](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4643)) - Using witness replicas helps to reduce storage costs while preserving consistency invariants. There are several implementations of this approach; for example, Spanner [CORBETT12] and Apache Cassandra. ([Location 4659](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4659)) - We’ve discussed several strong consistency models, such as linearizability and serializability, and a form of weak consistency: eventual consistency. A possible middle ground between the two, offering some benefits of both models, is strong eventual consistency. ([Location 4662](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4662)) - Under this model, updates are allowed to propagate to servers late or out of order, but when all updates finally propagate to target nodes, conflicts between them can be resolved and they can be merged to produce the same valid state [GOMES17] ([Location 4665](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4665)) - One of the most prominent examples of such an approach is Conflict-Free Replicated Data Types (CRDTs, [SHAPIRO11a]) implemented, for example, in Redis [BIYIKOGLU13] ([Location 4670](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4670)) - CRDTs are specialized data structures that preclude the existence of conflict and allow operations on these data types to be applied in any order without changing the result. ([Location 4672](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4672)) - Side-effect free Their application does not change the system state. Commutative Argument order does not matter: x • y = y • x. In other words, it doesn’t matter whether x is merged with y, or y is merged with x. Causally ordered Their successful delivery depends on the precondition, which ensures that the system has reached the state the operation can be applied to. ([Location 4680](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4680)) - a larger system, to avoid propagating huge vectors, we can use super-peers. Super-peers replicate counter states and help to avoid constant peer-to-peer chatter [SHAPIRO11b]. ([Location 4700](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4700)) - To save and replicate values, we can use registers. The simplest version of the register is the last-write-wins register (LWW register), which stores a unique, globally ordered timestamp attached to each value to resolve conflicts. ([Location 4702](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4702)) - An example of a conflict-free type that combines more complex structures is a conflict-free replicated JSON data type, allowing modifications such as insertions, deletions, and assignments on deeply nested JSON documents with list and map types. This algorithm performs merge operations on the client side and does not require operations to be propagated in any specific order [KLEPPMANN14] ([Location 4712](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4712)) - Linearizability Operations appear to be applied instantaneously, and the real-time operation order is maintained. ([Location 4722](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4722)) - Sequential consistency Operation effects are propagated in some total order, and this order is consistent with the order they were executed by the individual processes. ([Location 4724](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4724)) - Causal consistency Effects of the causally related operations are visible in the same order to all processes. ([Location 4726](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4726)) - PRAM/FIFO consistency Operation effects become visible in the same order they were executed by individual processes. Writes from different processes can be observed in different orders. ([Location 4727](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4727)) - Read-own-writes Read operations reflect the previous writes. Writes propagate through the system and become available for later reads that come from the same client. ([Location 4730](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4730)) - Monotonic reads Any read that has observed a value cannot observe a value that is older that the observed one. ([Location 4732](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4732)) - Monotonic writes Writes coming from the same client propagate to other clients in the order they were made by this client. ([Location 4733](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4733)) - Writes-follow-reads Write operations are ordered after the writes whose effects were observed by the previous reads executed by the same client. ([Location 4735](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4735)) - We also discussed the concept of eventual and tunable consistency. Quorum-based systems use majorities to serve consistent data. Witness replicas can be used to reduce storage costs. ([Location 4740](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4740)) - Quick and reliable propagation may be less applicable to data records and more important for the cluster-wide metadata, such as membership information (joining and leaving nodes), node states, failures, schema changes, etc. Messages containing this information are generally infrequent and small, but have to be propagated as quickly and reliably as possible. ([Location 4759](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4759)) - The coordinator will do its best and deliver the messages to all available participants, and then anti-entropy mechanisms will bring nodes back in sync in case there were any failures. This way, the responsibility for delivering messages is shared by all nodes in the system, and is split into two steps: primary delivery and periodic sync. ([Location 4774](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4774)) - Entropy is a property that represents the measure of disorder in the system. ([Location 4776](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4776)) - a distributed system, entropy represents a degree of state divergence between the nodes. Since this property is undesired and its amount should be kept to a minimum, there are many techniques that help to deal with entropy. ([Location 4777](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4777)) - Anti-entropy is usually used to bring the nodes back up-to-date in case the primary delivery mechanism has failed. ([Location 4779](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4779)) - To keep nodes in sync, anti-entropy triggers a background or a foreground process that compares and reconciles missing or conflicting records. Background anti-entropy processes use auxiliary structures such as Merkle trees and update logs to identify divergence. Foreground anti-entropy processes piggyback read or write requests: hinted handoff, read repairs, etc. ([Location 4782](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4782)) - During read repair, the coordinator node makes a request to replicas, waits for their responses, and compares them. In case some of the replicas have missed the recent updates and their responses differ, the coordinator detects inconsistencies and sends updates back to the replicas [DECANDIA07]. ([Location 4794](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4794)) - Some Dynamo-style databases choose to lift the requirement of contacting all replicas and use tunable consistency levels instead. To return consistent results, we do not have to contact and repair all the replicas, but only the number of nodes that satisfies the consistency level. If we do quorum reads and writes, we still get consistent results, but some of the replicas still might not contain all the writes. ([Location 4796](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4796)) - Blocking read repair ensures read monotonicity (see “Session Models”) for quorum reads: as soon as the client reads a specific value, subsequent reads return the value at least as recent as the one it has seen, since replica states were repaired. If we’re ([Location 4803](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4803)) - A digest request reads the replica-local data and, instead of returning a full snapshot of the requested data, it computes a hash of this response. Now, the coordinator can compute a hash of the full read and compare it to digests from all other nodes. If all the digests match, it can be confident that the replicas are in sync. ([Location 4815](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4815)) - Digests are usually computed using a noncryptographic hash function, such as MD5, since it has to be computed quickly to make the “happy path” performant. Hash functions can have collisions, but their probability is negligible for most real-world systems. Since databases often use more than just one anti-entropy mechanism, we can expect that, even in the unlikely event of a hash collision, data will be reconciled by the different subsystem. ([Location 4821](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4821)) - Another anti-entropy approach is called hinted handoff [DECANDIA07], a write-side repair mechanism. If the target node fails to acknowledge the write, the write coordinator or one of the replicas stores a special record, called a hint, which is replayed to the target node as soon as it comes back up. ([Location 4825](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4825)) - Some databases, for example Riak, use sloppy quorums together with hinted handoff. With sloppy quorums, in case of replica failures, write operations can use additional healthy nodes from the node list, and these nodes do not have to be target replicas for the executed operations. ([Location 4832](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4832)) - Since read repair can only fix inconsistencies on the currently queried data, we should use different mechanisms to find and repair inconsistencies in the data that is not actively queried. ([Location 4844](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4844)) - finding exactly which rows have diverged between the replicas requires exchanging and comparing the data records pairwise. This is highly impractical and expensive. ([Location 4847](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4847)) - Merkle trees compose a compact hashed representation of the local data, building a tree of hashes. The lowest level of this hash tree is built by scanning an entire table holding data records, and computing hashes of record ranges. Higher tree levels contain hashes of the lower-level hashes, building a hierarchical representation that allows us to quickly detect inconsistencies by comparing the hashes, following the hash tree nodes recursively to narrow down inconsistent ranges. ([Location 4849](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4849)) - To determine whether or not there’s an inconsistency between the two replicas, we only need to compare the root-level hashes from their Merkle trees. ([Location 4857](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4857)) - Since Merkle trees are calculated recursively from the bottom to the top, a change in data triggers recomputation of the entire subtree. ([Location 4859](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4859)) - More recent research on this subject introduces bitmap version vectors [GONÇALVES15], which can be used to resolve data conflicts based on recency: each node keeps a per-peer log of operations that have occurred locally or were replicated. During anti-entropy, logs are compared, and missing data is replicated to the target node. ([Location 4862](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4862)) - To track replica states, we use node-local logical clocks. Each clock represents a set of dots, representing writes this node has seen directly (coordinated by the node itself), or transitively (coordinated by and replicated from the other ([Location 4869](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4869)) - An advantage of this approach is that it captures the causal relation between the value writes and allows nodes to precisely identify the data points missing on the other nodes. A possible downside is that, if the node was down for an extended time period, peer nodes can’t truncate the log, since data still has to be replicated to the lagging node once it comes back up. ([Location 4887](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4887)) - Masses are always breeding grounds of psychic epidemics. Carl Jung ([Location 4891](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4891)) - Gossip protocols are probabilistic communication procedures based on how rumors are spread in human society or how diseases propagate in the population. ([Location 4894](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4894)) - Rumors and epidemics provide rather illustrative ways to describe how these protocols work: rumors spread while the population still has an interest in hearing them; diseases propagate until there are no more susceptible members in the population. ([Location 4896](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4896)) - A process that holds a record that has to be spread around is said to be infective. ([Location 4900](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4900)) - Any process that hasn’t received the update yet is then susceptible. ([Location 4902](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4902)) - All processes start in a susceptible state. Whenever an update for some data record arrives, a process that received it moves to the infective state and starts disseminating the update to other random neighboring processes, infecting them. ([Location 4905](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4905)) - To avoid explicit coordination and maintaining a global list of recipients and requiring a single coordinator to broadcast messages to each other participant in the system, this class of algorithms models completeness using the loss of interest function. ([Location 4908](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4908)) - The protocol efficiency is then determined by how quickly it can infect as many nodes as possible, while keeping overhead caused by redundant messages to a minimum. ([Location 4910](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4910)) - Gossip can be used for asynchronous message delivery in homogeneous decentralized systems, where nodes may not have long-term membership or be organized in any topology. ([Location 4911](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4911)) - Message redundancy is a metric that captures the overhead incurred by repeated delivery. Redundancy is an important property, and it is crucial to how gossip works. ([Location 4921](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4921)) - The amount of time the system requires to reach convergence is called latency. ([Location 4923](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4923)) - Fanout and latency depend on the system size: in a larger system, we either have to increase the fanout to keep latency stable, or allow higher latency. ([Location 4925](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4925)) - Nonepidemic approaches can distribute the message with nonprobabilistic certainty, less redundancy, and generally in a more optimal way [BIRMAN07] ([Location 4937](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4937)) - Gossip algorithms are often praised for their scalability and the fact it is possible to distribute a message within log N message rounds (where N is the size of the cluster) [KREMARREC07], ([Location 4939](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4939)) - Selecting nodes at random greatly improves system robustness: if there is a network partition, messages will be delivered eventually if there are links that indirectly connect two processes. ([Location 4942](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4942)) - Nodes in the system can form spanning trees: unidirected, loop-free graphs with distinct edges, covering the whole network. ([Location 4947](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4947)) - Plumtrees work by creating a spanning tree overlay of nodes to actively distribute messages with the smallest overhead. ([Location 4961](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4961)) - Broadcasting messages to all known peers and maintaining a full view of the cluster can get expensive and impractical, especially if the churn (measure of the number of joining and leaving nodes in the system) is high. ([Location 4976](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4976)) - HyParView and Plumtree use a hybrid gossip approach: using a small subset of peers for broadcasting messages and falling back to a wider network of peers in case of failures and network partitions. Both systems do not rely on a global view that includes all the peers, which can be helpful not only because of a large number of nodes in the system (which is not the case most of the time), but also because of costs associated with maintaining an up-to-date list of members on every node. ([Location 4997](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=4997)) - These anti-entropy approaches optimize for one of the three parameters: scope reduction, recency, or completeness. ([Location 5013](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=5013)) - HyParView is used in Partisan, the high-performance, high-scalability distributed computing framework. ([Location 5020](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=5020)) - Plumtree was used in the Riak core for cluster-wide information. ([Location 5021](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=5021)) - The main focus of transaction processing is to determine permissible histories, to model and represent possible interleaving execution scenarios. ([Location 5041](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=5041)) - History, in this case, represents a dependency graph: which transactions have been executed prior to execution of the current transaction. History is said to be serializable if it is equivalent (i.e., has the same dependency graph) to some history that executes these transactions sequentially. ([Location 5043](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=5043)) - A transaction is a set of operations, an atomic unit of execution. Transaction atomicity implies that all its results become visible or none of them do. For example, if we modify several rows, or even tables in a single transaction, either all or none of the modifications will be applied. ([Location 5056](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=5056)) - To ensure atomicity, transactions should be recoverable. In other words, if the transaction cannot complete, is aborted, or times out, its results have to be rolled back completely. ([Location 5058](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=5058)) - Another important aspect is network partitions and node failures: nodes in the system fail and recover independently, but their states have to remain consistent. ([Location 5062](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=5062)) - Atomic commitment doesn’t allow disagreements between the participants: a transaction will not commit if even one of the participants votes against it. ([Location 5068](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=5068)) - Another important implication of this fact is that atomic commitment algorithms do not work in the presence of Byzantine failures: when the process lies about its state or decides on an arbitrary value, since it contradicts unanimity [HADZILACOS05]. ([Location 5070](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=5070)) - In databases, distributed transactions are executed by the component commonly known as a transaction manager. The transaction manager is a subsystem responsible for scheduling, coordinating, executing, and tracking transactions. ([Location 5083](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=5083)) - a distributed environment, the transaction manager is responsible for ensuring that node-local visibility guarantees are consistent with the visibility prescribed by distributed atomic operations. In other words, transactions commit in all partitions, and for all replicas. ([Location 5085](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=5085)) - 2PC executes in two phases. During the first phase, the decided value is distributed, and votes are collected. During the second phase, nodes just flip the switch, making the results of the first phase visible. ([Location 5096](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=5096)) - 2PC assumes the presence of a leader (or coordinator) that holds the state, collects votes, and is a primary point of reference for the agreement round. The rest of the nodes are called cohorts. Cohorts, in this case, are usually partitions that operate over disjoint datasets, against which transactions are performed. ([Location 5097](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=5097)) - The coordinator can be a node that received a request to execute the transaction, or it can be picked at random, using a leader-election algorithm, assigned manually, or even fixed throughout the lifetime of the system. ([Location 5103](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=5103)) - with a commit, since it requires all votes to be positive. If one of the cohorts is unavailable, the coordinator will abort the transaction. This requirement has a negative impact on availability: failure of a single node can prevent transactions from happening. Some systems, for example, Spanner (see “Distributed Transactions with Spanner”), perform 2PC over Paxos groups rather than individual nodes to improve protocol availability. ([Location 5132](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=5132)) - If one of the cohorts has failed after accepting the proposal, it has to learn about the actual outcome of the vote before it can serve values correctly, since the coordinator might have aborted the commit due to the other cohorts’ decisions. ([Location 5138](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=5138)) - When a cohort node recovers, it has to get up to speed with a final coordinator decision. Usually, this is done by persisting the decision log on the coordinator side and replicating decision values to the failed participants. Until then, the cohort cannot serve requests because it is in an inconsistent state. ([Location 5140](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=5140)) - If the coordinator does not receive a response from the replica during the propose phase, it can trigger a timeout and abort the transaction. ([Location 5144](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=5144)) - Inability of the coordinator to proceed with a commit or abort leaves the cluster in an undecided state. This means that cohorts will not be able to learn about the final decision in case of a permanent coordinator failure. Because of this property, we say that 2PC is a blocking atomic commitment algorithm. If the coordinator never recovers, its replacement has to collect votes for a given transaction again, and proceed with a final decision. ([Location 5159](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=5159)) - Many databases use 2PC: MySQL, PostgreSQL, MongoDB,2 and others. Two-phase commit is often used to implement distributed transactions because of its simplicity (it is easy to reason about, implement, and debug) and low overhead (message complexity and the number of round-trips of the protocol are low). ([Location 5162](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=5162)) - To make an atomic commitment protocol robust against coordinator failures and avoid undecided states, the three-phase commit (3PC) protocol adds an extra step, and timeouts on both sides that can allow cohorts to proceed with either commit or abort in the event of coordinator failure, depending on the system state. ([Location 5168](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=5168)) - 3PC adds a prepare phase before the commit/abort step, which communicates cohort states collected by the coordinator during the propose phase, allowing the protocol to carry on even if the coordinator fails. ([Location 5173](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=5173)) - If the coordinator crashes during this phase and the operation times out, or if one of the cohorts votes negatively, the transaction will be aborted. ([Location 5186](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=5186)) - It may happen that the coordinator cannot distribute prepare messages to all cohorts or it fails to receive their acknowledgments. In this case, cohorts may abort the transaction after timeout, since the algorithm hasn’t moved all the way to the prepared state. ([Location 5188](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=5188)) - During commit, the coordinator communicates the results of the prepare phase to all the participants, resetting their timeout counters and effectively finishing the transaction. ([Location 5192](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=5192)) - As we discussed previously, 2PC cannot recover from coordinator failures, and cohorts may get stuck in a nondeterministic state until the coordinator comes back. 3PC avoids blocking the processes in this case and allows cohorts to proceed with a deterministic decision. ([Location 5197](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=5197)) - While in theory 3PC does, to a degree, solve the problem with 2PC blocking, it has a larger message overhead, introduces potential contradictions, and does not work well in the presence of network partitions. This might be the primary reason 3PC is not widely used in practice. ([Location 5203](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=5203)) - One of the ways to do this is to let replicas agree on the execution order and transaction boundaries before acquiring locks and proceeding with execution. ([Location 5210](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=5210)) - Traditional database systems execute transactions using two-phase locking or optimistic concurrency control and have no deterministic transaction order. This means that nodes have to be coordinated to preserve order. Deterministic transaction order removes coordination overhead during the execution phase and, since all replicas get the same inputs, they also produce equivalent outputs. This approach is commonly known as Calvin, a fast distributed transaction protocol [THOMSON12]. One of the prominent examples implementing distributed transactions using Calvin is FaunaDB ([Location 5213](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=5213)) - distributed transaction management called Spanner [CORBETT12]. Its implementations (or derivatives) include several open source databases, most prominently CockroachDB and YugaByte ([Location 5245](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=5245)) - While Calvin establishes the global transaction execution order by reaching consensus on sequencers, Spanner uses two-phase commit over consensus groups per partition (in other words, per shard). ([Location 5247](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=5247)) - To achieve consistency and impose transaction order, Spanner uses TrueTime: a high-precision wall-clock API that also exposes an uncertainty bound, allowing local operations to introduce artificial slowdowns to wait for the uncertainty bound to pass. ([Location 5249](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=5249)) - Spanner offers three main operation types: read-write transactions, read-only transactions, and snapshot reads. ([Location 5252](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=5252)) - Read-write transactions require locks, pessimistic concurrency control, and presence of the leader replica. ([Location 5254](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=5254)) - Read-only transactions are lock-free and can be executed at any replica. ([Location 5255](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=5255)) - leader is required only for reads at the latest timestamp, which takes the latest committed value from the Paxos group. Reads at the specific timestamp are consistent, since values are versioned and snapshot contents can’t be changed once written. ([Location 5255](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=5255)) - Every write has to go through the Paxos group leader, while reads can be served directly from the tablet on up-to-date replicas. The leader holds a lock table that is used to implement concurrency control using the two-phase locking (see “Lock-Based Concurrency Control”) mechanism and a transaction manager that is responsible for multishard distributed transactions. Operations that require synchronization (such as writes and reads within a transaction) have to acquire the locks from the lock table, while other operations (snapshot reads) can access the data directly. ([Location 5265](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=5265)) - For multishard transactions, group leaders have to coordinate and perform a two-phase commit to ensure consistency, and use two-phase locking to ensure isolation. ([Location 5271](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=5271)) - Since the 2PC algorithm requires the presence of all participants for a successful commit, it hurts availability. Spanner solves this by using Paxos groups rather than individual nodes as cohorts. ([Location 5272](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=5272)) - Paxos groups are used to consistently replicate transaction manager states across multiple nodes. ([Location 5275](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=5275)) - To summarize, Spanner uses Paxos for consistent transaction log replication, two-phase commit for cross-shard transactions, and TrueTime for deterministic transaction ordering. ([Location 5287](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=5287)) - Since storing all database records on a single node is rather unrealistic for the majority of modern applications, many databases use partitioning: a logical division of data into smaller manageable segments. ([Location 5292](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=5292)) - The most straightforward way to partition data is by splitting it into ranges and allowing replica sets to manage only specific ranges (partitions). ([Location 5294](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=5294)) - When executing queries, clients (or query coordinators) have to route requests based on the routing key to the correct replica set for both reads and writes. This partitioning scheme is typically called sharding: every replica set acts as a single source for a subset of data. ([Location 5296](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=5296)) - To use partitions most effectively, they have to be sized, taking the load and value distribution into consideration. This means that frequently accessed, read/write heavy ranges can be split into smaller partitions to spread the load between them. ([Location 5298](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=5298)) - When nodes are added to or removed from the cluster, the database has to re-partition the data to maintain the balance. ([Location 5302](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=5302)) - Some databases perform auto-sharding and relocate the data using placement algorithms that determine optimal partitioning. These algorithms use information about read, write loads, and amounts of data in each shard. ([Location 5304](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=5304)) - To find a target node from the routing key, some database systems compute a hash of the key, and use some form of mapping from the hash value to the node ID. ([Location 5306](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=5306)) - One of the advantages of using the hash functions for determining replica placement is that it can help to reduce range hot-spotting, since hash values do not sort the same way as the original values. While two lexicographically close routing keys would be placed at the same replica set, using hashed values would place them on different ones. ([Location 5307](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=5307)) - The most straightforward way to map hash values to node IDs is by taking a remainder of the division of the hash value by the size of the cluster (modulo). If we have N nodes in the system, the target node ID is picked by computing hash(v) modulo N. The main problem with this approach is that whenever nodes are added or removed and the cluster size changes from N to N’, many values returned by hash(v) modulo N’ will differ from the original ones. This means that most of the data will have to be moved. ([Location 5309](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=5309)) - Using consistent hashing helps to reduce the number of relocations required for maintaining balance: a change in the ring affects only the immediate neighbors of the leaving or joining node, and not an entire cluster. The word consistent in the definition implies that, when the hash table is resized, if we have K possible hash keys and n nodes, on average we have to relocate only K/n keys. In other words, a consistent hash function output changes minimally as the function range changes [KARGER97] ([Location 5318](https://readwise.io/to_kindle?action=open&asin=B07XW76VHZ&location=5318))