← Back
Home › Systems › Databases and storage engines

distributed-kv

partitioned, replicated key-value store

DynamoDB, Cassandra

SystemTechniques · 10Primitives · 23 distributed-kv Anti-entropy repairdistributed · medium: Replicas compare hash trees of a key range, descend only into differing subtrees and stream just those ranges, healing silent divergence in the background.›CRDTsdistributed · medium: Data types whose replicas accept writes independently and always converge by merging, with no coordination: counters, sets, maps, registers, text.›Hinted handoffdistributed · medium: Park a write meant for a down replica as a tagged hint on a healthy node, replay it when the replica returns, and count it toward the write quorum only if availability matters more than consistency.›Multi-Paxosdistributed · medium: Paxos run once per log slot with a stable leader that skips phase 1; the foundation of Chubby, Spanner and much production consensus.›Quorum replicationdistributed · medium: Leaderless replication: write to W of N replicas, read from R; overlap (R + W > N) makes reads see the latest completed write.›SWIM gossip membershipdistributed · medium: Each node probes one random peer per period, asks k others on timeout, and piggybacks membership updates; constant load per node at any cluster size.›LSM compactionstorage · medium: Compaction policies (leveled, tiered, time-window, FIFO) decide which sorted files to merge and when, trading write, read and space amplification and purging tombstones.›Merkle treedata-structures · low: Hash tree for verifying and diffing large datasets with logarithmic proofsRange partitioningdistributed · low: Cut the sorted key space into contiguous half-open ranges kept in a boundary map; split hot or big ranges, merge small ones, move ranges between nodes.›Token bucketsystems · low: A bucket of up to b tokens refilled at rate r; requests spend tokens, enforcing an average rate while allowing bursts of b.›Vector clocksdistributed · low: One counter per node; comparing two vectors tells whether events are ordered or concurrent, which is exactly what conflict detection needs.›Consistent hashingdistributed · low: Hash nodes and keys onto a ring; each key belongs to the next node clockwise, so membership changes move only about 1/n of keys.›Phi accrual failure detectordistributed · low: Instead of a fixed heartbeat timeout, output a continuous suspicion level φ from the observed heartbeat interval distribution; adapts to each link's jitter.›Write-ahead logstorage · low: Append each change to a checksummed sequential log and fsync it before touching data pages; the basis of crash durability in nearly every database.›Bloom filterdata-structures · low: Bit array answering "definitely not present" or "probably present" in about 10 bits per key for 1 % false positives; inserts are cheap, deletes impossible.›Fractional indexingdistributed · low: Give every list item a sortable string key and generate a new key strictly between its neighbours, so a move or insert writes one row.›Lamport clocksdistributed · low: One integer per process, max-plus-one on receive; gives a total order consistent with causality using 8 bytes per timestamp.›Leasesdistributed · low: A lock that expires on its own: bounded-time ownership that survives crashes and partitions, given bounded clock drift and fencing tokens on writes.›Reliable UDPgame-networking · low: Transport over UDP: each packet carries a sequence number, an ack and a 32-bit ack history; only chosen messages are made reliable.›K way mergesearch-sort · low: Merge k sorted streams with a heap or loser tree (merging iterators)Sstablestorage · low: Sorted string table: data blocks with restart points, index, filter and footerEvent deduplication windowdistributed · low: Keep the ids of recently accepted events for a time window and drop repeats; memory stays bounded by rotating time buckets instead of per-entry timers.›Message sequence numbersdistributed · low: A per-stream counter on every message lets the receiver detect loss, duplicates and reordering, ack cheaply and resume after reconnect with "send from N".›+ 3 more techniques+ 7 more primitives

Similar systems

Share the most building blocks with this one.

wide-column 25 %lsm-engine 17 %event-store 17 %

In-house systems

Named systems of this kind at large companies, with their paper or write-up.

DynamoAmazonDynamoDBAmazonZippyDBMeta PlatformsPaxosStoreTencent Holdings