Notes on papers I've read
Papers
- Consistent Hashing (1997) A mechanism to redistribute hashes across a group when nodes move in or out of the group. With K keys and N Nodes, a traditional modulo N mechanism on average requires K keys to be recalculated, but with Consistent Hashing only K/N keys on average need to be updated. Key concepts introduced by Consistent Hashing:
- Disassociate hashing from the placement on nodes by using a mapping algorithm such as predecessor or successor.
- For every physical node add a virtual nodes to improve even distribution of keys across ring. Links:
- https://docs.openstack.org/swift/latest/ring_background.html
-
SWIM Failure Detector system. Heartbeat/group membership protocol, Weakly Consistent, Gossip-based (Infection) protocol. Hashicorp (Sirf, Consul)
-
The φ Accrual Failure Detector System Used by Cassandra
-
Efficient Reconciliation and Flow Control for Anti-Entropy Protocols (aka Scuttlebutt) Gossip protocol. Used by Cassandra for transmitting group/failure updates. Also by Akka (Scala).
-
Chord Distributed Hash Table (DHT) Consistent hashing for partitioning, Finger table for group membership
-
Cassandra (Facebook) DHT, Eventually Consistent, Consistent Hashing, Gossip-based (Scuttlebutt) for Group Membership, φ Accrual Failure Detector System.
-
Dynamo (Amazon) DHT, Gossip-based protocol for membership/failure detection with nodes selected at random.
-
Vivaldi Decentralized network coordinate system used to scalably map network space onto a Euclidean space. The core mechanism is (as per authors) analogous to starting with a compressed spring (all nodes starting at origin of Euclidean space) and then releasing and letting it converge. See PWL talk by Armon Dadgar for overview. Used by HashiCorp in Sirf and Consul for generating coordinates for failover to nearest neighbor, etc. The spring analogy has its own class of algorithms referred to as Force directed graphs and is used in graph visualization for creating visually pleasing graphs.
-
Network Coordinates in the Wild Builds on Vivaldi to address Drift (network coordinates drifting without limit) by using Gravity, address outliers affecting stabilization by using Low Pass Filters.