GridSync Distributed Cache

A distributed in-memory cache written in Python/Cython that achieves 12× lower p99 latency on skewed workloads compared to a Redis baseline by combining:

• Segmented LRU (SLRU) with request coalescing across 8 nodes to eliminate hot-key skew
• Cython hot-paths for hashing (FNV-1a) and eviction scoring, removing Python object overhead on the critical path
• uvloop async I/O for connection handling (2–4× faster than default asyncio event loop)
• Raft-style replication with leader election and at-least-once delivery guarantees across all nodes
• Consistent hashing ring for even key distribution with minimal key movement on node changes
• DynamoDB for Raft log persistence and cluster membership registry

Architecture

Clients
  │
  ▼
┌──────────────────────────────────────────────────┐
│             Cluster Client                        │
│  Consistent Hash Ring → route to shard owner     │
│  Leader redirect → forward SET/DEL to leader     │
└──────────────────────────┬───────────────────────┘
                           │
        ┌──────────────────┼──────────────────────┐
        ▼                  ▼                       ▼
  ┌───────────┐     ┌───────────┐           ┌───────────┐
  │  Node 0   │     │  Node 1   │    ...    │  Node 7   │
  │  (Leader) │     │(Follower) │           │(Follower) │
  │           │     │           │           │           │
  │  SLRU     │     │  SLRU     │           │  SLRU     │
  │  Cache    │     │  Cache    │           │  Cache    │
  │           │◄───►│           │◄─────────►│           │
  │  Raft     │     │  Raft     │           │  Raft     │
  │  Node     │     │  Node     │           │  Node     │
  └─────┬─────┘     └─────┬─────┘           └─────┬─────┘
        │                 │                         │
        └─────────────────┼─────────────────────────┘
                          ▼
                   ┌────────────┐
                   │  DynamoDB  │
                   │  (Raft log │
                   │  + members)│
                   └────────────┘

Quick Start

Docker (full 8-node cluster)

cd docker
docker compose up --build

This starts:

• 8 GridSync nodes on ports 7000–7007
• Local DynamoDB on port 8000
• Redis on port 6379 (for benchmark comparison)

Local development

pip install -e ".[dev]"

# Build Cython extension (optional — pure-Python fallback used otherwise)
python setup.py build_ext --inplace

# Run unit tests
pytest tests/unit/

# Run integration tests (starts in-process cluster)
pytest -m integration tests/integration/

Single node (no cluster)

GRIDSYNC_NODE_ID=node0 python -m gridsync.main

Benchmark

# Run after starting Docker cluster
bash scripts/bench_skew.sh 100000

Key Design Decisions

Segmented LRU + Request Coalescing

Standard LRU evicts hot keys when a burst of unique cold keys arrives, causing a latency spike. SLRU divides capacity into a protected segment (80%) and a probationary segment (20%). New items enter probation; a hit promotes to protected, shielding hot keys from cold eviction.

Request coalescing means that if 100 concurrent requests all miss the same key simultaneously, only one backend fetch is issued — the other 99 await the same asyncio.Future.

Cython Hot-Paths

cython_ext/hash_evict.pyx implements:

• FNV-1a 64-bit hash — branch-free, ~4× faster than Python's hash() for cache key routing
• Eviction scoring — combines frequency and recency without Python object allocation
• Shard selector — maps hash to shard index without Python modulo overhead

Falls back automatically to hash_evict_py.py if the .so is not compiled.

Raft Consensus

Full Raft implementation with:

• Randomised election timeouts (150–300 ms) to avoid split votes
• Leader-only writes: followers redirect clients to the current leader
• Log truncation on conflict detection
• At-least-once delivery: AppendEntries retried until acknowledged
• Persistent state (term, voted_for, log) stored in DynamoDB for crash recovery

uvloop

uvloop.install() replaces the default asyncio event loop with a libuv-based implementation, reducing connection handling overhead by 2–4× at the OS level.

Project Structure

gridsync/
  core/
    lru.py          Segmented LRU + coalescing cache
    router.py       Consistent hash ring
    node.py         CacheNode: ties cache + Raft + network together
  raft/
    node.py         Raft consensus implementation
    state.py        Raft persistent/volatile state
    messages.py     RequestVote / AppendEntries message types
  network/
    protocol.py     Length-prefixed msgpack framing
    server.py       uvloop TCP server (client + peer ports)
    client.py       Async client for one node
    cluster_client.py  Cluster-aware client with hash routing + redirect
  storage/
    dynamo.py       DynamoDB persistence (Raft state + membership)
  main.py           Entry point (env-var config)
cython_ext/
  hash_evict.pyx    Cython hot-paths: FNV-1a, eviction scoring
  hash_evict_py.py  Pure-Python fallback
  loader.py         Import shim (compiled → fallback)
bench/
  benchmark.py      Latency/throughput benchmark vs Redis
tests/
  unit/             Fast in-process tests (LRU, router, Raft, hash)
  integration/      In-process 3-node cluster tests
docker/
  Dockerfile
  docker-compose.yml  8-node cluster + DynamoDB Local + Redis

Performance Results

Workload: Zipfian (s=1.1), 100k requests, 1000 distinct keys, 128-byte values

Metric	GridSync	Redis	Improvement
p50	0.08 ms	0.31 ms	3.9×
p99	0.21 ms	2.54 ms	12.1×
p99.9	0.48 ms	6.1 ms	12.7×
Throughput	89k ops/s	24k ops/s	3.7×

Measured on 8× c5.xlarge EC2 instances, single-AZ, uvloop enabled.

License

MIT