← Back
Home › Systems › Databases and storage engines

distributed-fs

distributed file system

HDFS, Colossus, Ceph

SystemTechniques · 9Primitives · 32 distributed-fs Chain replicationdistributed · medium: Replicas in a line: writes enter at the head and commit at the tail, reads hit the tail; f+1 nodes tolerate f failures.›Crush placementdistributed · medium: CRUSH: deterministic, hierarchy-aware pseudo-random placement of objects on devicesQuorum replicationdistributed · medium: Leaderless replication: write to W of N replicas, read from R; overlap (R + W > N) makes reads see the latest completed write.›Raftdistributed · medium: Leader-based consensus on a replicated log; one leader per term, majority commit; the default for a strongly consistent replicated state machine.›Erasure codingstorage · medium: Reed-Solomon k+m coding to survive m lost shards at lower overhead than replicationLSM-treestorage · medium: Buffer writes in memory, flush them as immutable sorted files and merge in the background; turns random writes into sequential I/O.›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.›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.›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.›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.›Fencing tokensdistributed · low: A number that grows with every lock grant and is checked by the protected resource, so a paused ex-holder's late write is rejected.›CRC32C checksumshardware-os · low: The Castagnoli CRC-32 with dedicated instructions on x86 (SSE4.2) and ARMv8. It is the standard fast integrity check for storage blocks, logs and network frames.›fsync, O_DSYNC and O_DIRECThardware-os · low: What fsync, fdatasync, O_DSYNC, O_DIRECT and F_FULLFSYNC really guarantee on Linux and macOS, and the exact call sequences for crash-safe files.›Kernel-bypass networkingnetworking · low: User space (DPDK, AF_XDP) or an in-driver eBPF hook (XDP) handles packets straight from NIC rings, skipping sockets, for 10-40 Mpps per core.›Data scrubbingstorage · low: Background re-read and checksum verification of stored data to catch latent corruptionInode file layoutstorage · low: Inodes, directory entries and block/extent maps for a file namespaceHealth checkingsystems · low: Decide per backend whether to route to it using probes and real-traffic errors, with consecutive-count hysteresis, capped ejection and a panic fallback.›Fast hash functionsdata-structures · low: Non-cryptographic hashes built from 64×64→128-bit multiplies and xor-shifts; pick by key size, trust level and whether the hash is persisted.›Rendezvous hashingdistributed · low: Score every node with hash(key, node) and pick the highest: minimal key movement and exact weights without a ring, at O(n) per lookup.›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.›Vector clocksdistributed · low: One counter per node; comparing two vectors tells whether events are ordered or concurrent, which is exactly what conflict detection needs.›Exponential backoff with jittersystems · low: Retry after delays that grow geometrically and are randomized, so failed clients spread out instead of hammering a recovering service in synchronized waves.›SIMD programminghardware-os · low: Process 4-16 lanes per instruction with AVX2, AVX-512 or NEON via Rust std::arch, with runtime dispatch and a portable fallback.›+ 2 more techniques+ 16 more primitives

Similar systems

Share the most building blocks with this one.

block-storage 41 %object-storage 29 %coordination-store 25 %event-store 23 %storage-array 21 %

In-house systems

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

ColossusAlphabetTectonicMeta PlatformsPanguAlibaba Group