FaRM is an RDMA-based distributed computing platform that exposes cluster memory as a shared address space with ACID transactions, achieving 10x throughput and 100x lower latency than TCP/IP via one-sided RDMA lock-free reads and RDMA-write messaging.
Main-memory distributed systems bottleneck on TCP/IP networking: a state-of-the-art key-value store (MemC3) performs 7x worse in a client-server TCP/IP setup than in a single-machine setup, despite extensive request batching. DRAM prices have dropped enough that a 100-machine cluster can hold tens of terabytes in main memory, but the network stack — not memory — is the performance ceiling.
FaRM builds three interlocking mechanisms on top of RDMA:
txAlloc place related objects on the same machine; function shipping converts distributed transactions into single-machine transactions (only a commit message to replicas, no prepare/validate round-trips).Supporting infrastructure: PhyCo kernel driver allocates physically-contiguous 2 GB regions to collapse NIC page tables from >500K entries to 1; NUMA-aware queue pair multiplexing ($q$ threads share one connection) prevents NIC cache thrashing as cluster scales.
核心技术壁垒: the cache-line versioning scheme that delivers strictly serializable lock-free reads via a single RDMA read without involving the remote CPU. Correctness relies on three non-obvious hardware properties: (a) RDMA writes are performed in increasing address order, (b) DMA is cache-coherent on x86, and (c) compiler barriers on x86 enforce sufficient ordering for DMA-visible memory writes. Replicating this on non-x86 platforms requires re-deriving the memory ordering guarantees, and achieving the same single-RDMA-read property demands per-cache-line version metadata layout with careful space/wrap-around trade-offs.
FaRM machines are both data stores and compute nodes. Each machine registers its 100 GB shared memory as 2 GB PhyCo regions with the NIC, enabling single-entry page tables. The shared address space uses a 64-bit address (32-bit region ID + 32-bit offset) resolved locally via consistent hashing on $k = 100$ virtual rings.
Two data paths serve different access patterns: lock-free one-sided RDMA reads for read-only operations (single RDMA, no remote CPU involvement), and RDMA-write messaging for transactions and function shipping. The transaction protocol uses OCC with 2PC for distributed transactions, but applications can opt into single-machine transactions when data is collocated, eliminating the prepare and validate phases.
The reader issues a single RDMA read spanning the entire object. If the header version is unlocked and its low-order $l$ bits match all cache-line versions, the snapshot is consistent. Mismatch triggers retry with randomized backoff.
无形式化作者证明 — 仅实证。The paper contains no numbered equations and no formal model; all claims are validated empirically.
Lock-free read serializability argument (§3.5): the paper argues that a lock-free read returning matching versions across all cache lines is strictly serializable with concurrent transactions.
Assumption inventory:
| # | Assumption | Where relied upon |
|---|---|---|
| 1 | RDMA writes in increasing address order | Lock-free read correctness (§3.5) |
| 2 | Cache-coherent DMA on x86 | Lock-free read correctness (§3.5) |
| 3 | Crash failures only (no Byzantine) | Transaction correctness (§3.2) |
| 4 | Bounded clock drift | ZooKeeper leases, version wrap-around safety (§3.5) |
| 5 | Bounded max simultaneous failures per replica group | Availability guarantee (§3.2) |
| 6 | Eventual synchrony | Liveness guarantee (§3.2) |
Bandwidth budget:
40 Gbps RoCE = 5 GB/s per NIC. With 16-byte keys + 32-byte values (≈128 bytes per bucket-pair RDMA read), theoretical NIC bandwidth supports $5 \times 10^9 / 128 \approx 39\text{M reads/s}$ per machine. Observed 7.3M lookups/machine (146M ÷ 20), well below this ceiling — the bottleneck is packet rate, not bandwidth, consistent with Figure 2 showing packet-rate saturation at small transfer sizes.
Scaling: throughput scales linearly with machine count for uniform workloads (near-zero coordination for lock-free reads). For skewed workloads, NIC saturation on hot-key machines limits scaling beyond ~8 machines.
RDMA vs TCP/IP throughput (Figure 2): RDMA messaging delivers 9–11x higher request rate than TCP/IP for 16–512 byte transfers. One-sided RDMA reads add another 2x for sizes ≤256 bytes (half the packets). Both saturate at ~33 Gbps for ≥2 KB sizes.
Latency (Figure 3): at peak load, TCP/IP latency is ≥145x higher than RDMA messaging across all request sizes. Unloaded RDMA read latency is ≥12x lower than TCP/IP and 3x lower than RDMA messaging.
PhyCo impact (Figure 4): without PhyCo, RDMA request rate drops 4x when registered memory exceeds 16 MB due to NIC page table cache thrashing. PhyCo sustains constant rate up to 100 GB.
Connection multiplexing (Figure 5): optimal sharing factor $q$ varies with cluster size — small $q$ provides more parallelism (better for small clusters), large $q$ reduces queue pair pressure (necessary for larger clusters).
| Metric | FaRM (20 machines) | TCP/IP baseline | Ratio |
|---|---|---|---|
| Lookup throughput (uniform) | 146M ops/s | 13.8M ops/s | 10.6x |
| Lookup throughput (YCSB) | 103M ops/s | — | — |
| Lookup latency (uniform, peak) | 35 µs | 8000+ µs | >228x |
| TCP latency at 1 ms target | — | 3.8M ops/s | FaRM 38x |
| Single-machine throughput | 26M ops/s | 40M ops/s | 0.65x |
| RDMAs per lookup (90% occ) | 1.04 | — | — |
FaRM's single-machine throughput is 35% lower than the baseline because its general lock-free read support copies objects even locally. The advantage materializes at scale.
Update workloads (5% updates, YCSB-B): FaRM with SSD replication achieves 10x higher throughput than the non-replicated TCP/IP baseline. SSD logging adds 30% overhead vs no replication. SSDs become the bottleneck at >5% update rate (215 MB/s writes + 215 MB/s cleaning reads saturate I/O bandwidth).
Optimization contribution breakdown (§4.2): low-level RDMA tuning (PhyCo + multiplexing) → 8x; lock-free one-sided reads vs messaging → 2x; hopscotch hashtable vs Pilaf's cuckoo design → 3x fewer RDMAs per lookup.
126M graph ops/s at 41 µs on 20 machines. Per-machine throughput is 10x reported Tao numbers; latency is 40–50x lower. Three dominant operations (85% of workload) each require only 1.02 RDMA reads on average via lock-free reads of collocated edge lists.
Inlining values with $H = 8$ or $H = 6$ provides good throughput/space balance for objects ≤128 bytes. $H = 2$ maximizes throughput at the cost of space utilization. Objects >320 bytes should be stored out-of-table with pointers in buckets.
| Step | Claim | Evidence | Depends on |
|---|---|---|---|
| 1 | TCP/IP is the bottleneck for main-memory distributed systems | MemC3 shows 7x single-machine vs distributed gap despite batching [16] | — |
| 2 | RDMA writes can implement high-performance messaging via circular buffers | Micro-benchmark: 9–11x throughput over TCP/IP, ≥145x lower latency at peak (Figures 2–3) | Step 1 |
| 3 | One-sided RDMA reads add 2x throughput for read-dominant workloads by halving packet count | Additional 2x for sizes ≤256 bytes (Figure 2); reads bypass remote CPU entirely | Step 2 |
| 4 | Lock-free reads via cache-line versioning are strictly serializable with transactions | Informal proof: x86 DMA cache coherence + RDMA write ordering + memory barriers guarantee consistent snapshots (§3.5) | Step 3 |
| 5 | NIC resource pressure must be actively managed at scale | PhyCo eliminates 4x degradation (Figure 4); connection multiplexing optimizes queue pair caching (Figure 5) | Steps 2–3 |
| 6 | Chained associative hopscotch hashing achieves near-single-RDMA lookups at high occupancy | 1.04 RDMA reads/lookup at 90% occupancy vs 3.2 for Pilaf (§3.6); joint versioning extends lock-free reads to bucket pairs | Steps 3–4 |
| 7 | Collocation + function shipping convert distributed transactions to single-machine transactions | Eliminates prepare/validate phases; Tao edge lists collocated with source nodes achieve 1.02 RDMA reads/op (§4.4) | Steps 4, 6 |
| 8 | End-to-end: 10x throughput and 100x lower latency vs TCP/IP | 146M lookups/s at 35 µs; 126M graph ops/s at 41 µs (Figures 12, §4.4) | Steps 2–7 |
[实现未公开] — FaRM is a Microsoft Research internal system with no public source code.
The cache-line versioning scheme (§3.5) is the hardest-to-replicate component. Reimplementation requires:
asm volatile("" ::: "memory")) provide sufficient ordering because DMA is cache-coherent.FaRM's design implicitly argues for several NIC/fabric features: