Mastering Distributed Systems: Overcoming Network Challenges and Consistency Trade‑offs

1. Challenges of Distributed Systems

What difficulties do distributed systems have compared to single‑machine systems?

Network Factors

Because services and data are spread across multiple machines, each interaction must cross machine boundaries, leading to several issues:

Network Latency: performance, timeouts

Intra‑datacenter I/O is relatively fast, but cross‑datacenter or cross‑IDC communication becomes a significant performance bottleneck. Bandwidth can be increased by upgrading hardware, but latency is a physical limit that cannot be easily reduced.

High latency reduces overall system performance, causing resource contention and forcing RPC calls to set timeout thresholds. Excessive latency introduces a third possible outcome for distributed calls—timeout—adding considerable complexity.

Typical mitigations include asynchronous processing and retry mechanisms; for cross‑IDC data distribution, solutions such as data synchronization and dedicated lines are used.

Network Failures: packet loss, reordering, jitter

These can be mitigated by using reliable transport protocols like TCP, though this introduces additional network interactions, creating a trade‑off between performance and traffic, especially critical in mobile environments.

CAP Theorem (Consistency, Availability, Partition Tolerance)

Proposed by Eric Brewer, the CAP theorem states that a distributed system can satisfy at most two of the three properties:

Consistency: strong consistency, transactional guarantees, ACID model.

Availability: redundancy to avoid single points of failure, graceful degradation.

Partition tolerance: ability to scale automatically, e.g., HBase.

Because partition tolerance is mandatory for distributed systems, designers often sacrifice consistency. Large‑scale websites typically prioritize partition tolerance and availability, leading NoSQL systems to aim for AP, while traditional databases target CA.

Scalability is a unique property of distributed systems. Scaling can be achieved by improving hardware (scale‑up) or by adding more machines (scale‑out). Linear scalability means performance grows proportionally with the number of nodes.

Availability and scalability are correlated: a well‑scaled system usually offers higher availability due to multiple nodes.

For stateless services, strong consistency is less critical; they can achieve high availability and partition tolerance with simple node addition. Stateful services must balance the three CAP dimensions based on business needs. Transactional systems often require strong consistency (ACID), sacrificing availability and scalability, whereas most other services can accept eventual consistency (BASE) to achieve high availability and scalability.

Performance is another key metric alongside CAP.

Consistency Models

Three primary models:

Strong Consistency: once data is written, all replicas return the new value immediately.

Weak Consistency: replicas may return stale values, requiring clients to perform extra work to obtain the latest data.

Eventual Consistency: replicas converge to the same value over time after updates.

Weak and eventual models usually rely on asynchronous replication, offering better performance but more complex state management; strong consistency uses synchronous replication, simplifying correctness at the cost of latency.

Other variants include:

Causal Consistency: if Process A notifies Process B of an update, B sees the new value, while unrelated processes may see eventual consistency.

Read‑Your‑Writes Consistency: a client always reads its own writes immediately, while others may see older versions.

Session Consistency: within a session, reads never return older values.

Monotonic Read Consistency: a user never reads older data than previously observed.

The most important variant for many applications is Read‑Your‑Writes, used by systems like Facebook for immediate user‑visible updates.

2. Common Distributed System Techniques and Use Cases

Consistent hashing (with virtual nodes): data distribution.

Vector clock: multi‑version data modification.

Quorum W+R>N (with vector clock): another solution for data consistency.

Merkle tree (with anti‑entropy): data replication.

MVCC: copy‑on‑write and snapshot.

2PC/3PC: distributed transactions.

Paxos: strong consistency protocol.

Symmetry and Decentralization: simplify configuration and avoid single‑master bottlenecks.

Map‑Reduce: divide‑and‑conquer; prefer moving computation to data.

Gossip protocol: node management.

Lease mechanism.

Consistent Hashing

Traditional hash mod n fails when nodes are added or removed because it requires massive reshuffling. Consistent hashing maps nodes onto a ring; each request is placed on the ring and routed to the first clockwise node, allowing seamless handling of node failures and dynamic scaling.

Consistent hashing is widely used in distributed caches (e.g., Memcached) and systems like Dynamo, which enhance the algorithm with virtual nodes to improve load balance.

Quorum W+R>N (Read/Write Quorum)

Definitions: N = number of replicas, R = minimum successful reads, W = minimum successful writes.

W+R>N ensures that a read overlaps with a write, guaranteeing consistency. Adjusting W and R lets users trade off consistency, availability, and performance.

Typical settings use N ≥ 3. For example, with N=3, W=1, a write succeeds after one replica stores the data (asynchronously replicated to others); reads may query multiple replicas to improve consistency.

Vector clocks are often combined with quorum protocols to resolve version conflicts.

Vector Clock

Used to track multiple versions of data across replicas; see referenced material for details.

Lease Mechanism

Systems like Chubby and Zookeeper grant a lease to a node, promising that its role or data remains valid for the lease duration.

Lease issuance requires only one‑way network communication; the issuer can repeatedly resend the lease.

Node crashes have limited impact: if the issuer fails, existing leases remain until expiration; after recovery, the issuer can resume honoring its leases.

Leases depend on synchronized clocks; clock skew can cause premature expiration or overlapping leases, mitigated by adding safety margins.

In practice, a lease duration of around 10 seconds is common.

Gossip Protocol

Nodes periodically exchange state information (gossip) to disseminate cluster health, load, and membership data. New nodes first contact seed nodes to obtain cluster information. Dynamo uses gossip for membership and failure detection.

2PC, 3PC, Paxos: Distributed Transaction Solutions

Distributed transactions are hard; most systems prefer eventual consistency.

Google’s Megastore (built on Bigtable) implements two‑phase locking with Chubby for coordination.

2PC

Simple but low‑throughput; all participants block, no fault tolerance—if any node fails, the whole transaction aborts.

3PC

Improves 2PC by splitting the first phase into inquiry and lock acquisition, allowing better handling of failures during the pre‑commit stage.

Paxos

Paxos achieves consensus among a majority of nodes, tolerating up to f failures in a 2f+1 cluster. It is also used for leader election and other coordination tasks.

MVCC (Multi‑Version Concurrency Control)

Key technique for high‑concurrency updates in many RDBMS storage engines; see referenced papers for details.

Map‑Reduce Concept

Divide‑and‑conquer and move computation to where data resides (locality) to reduce network transfer costs.

Classic Papers and Distributed System Learning Resources

Dynamo

HBase

LSM Tree (Log‑Structured Merge Tree) – an evolution of B+‑Tree that sacrifices some read performance for high write throughput.

LSM writes to a WAL, builds an in‑memory sorted tree (memstore), flushes to disk as immutable files, and periodically compacts them.

Lucene’s indexing mechanism follows a similar approach, writing to separate segments and merging them in the background.

References

NoSQL漫谈

多IDC的数据分布设计(一)

分布式系统的事务处理

海量存储系列之四-单机事务处理

本人一些技术方面的分享集合

Learning from google megastore (Part-1)