Skip to content

PROJECT_BRIEF.md

Latest commit

 

History

History
153 lines (108 loc) · 6.12 KB

PROJECT_BRIEF.md

File metadata and controls

153 lines (108 loc) · 6.12 KB

Project Brief: TQCache

TQCache is a high-performance, persistent caching system implemented in Go. It allows usage both as an embeddable Go library and as a standalone server application (CLI). The server application behaves like Memcached, accepting a configuration file (defaulting to tqcache.conf) for easy deployment. It allows configurable persistence guarantees (e.g., FSYNC on every write, periodic sync, or OS-buffered) to balance durability vs. performance. It implements both the Memcached text protocol and the Binary Protocol, ensuring compatibility with standard clients.

Architecture

Concurrency Model

Uses a lock-free, worker-based architecture with one goroutine per shard:

Component Description
ShardedCache Routes keys to shards via FNV-1a hash
Worker Single goroutine processing requests via channel
Storage Per-shard files (no locks needed)
Sync Worker Periodic fsync across all shards (configurable)

How it works:

  1. Each shard has a dedicated Worker goroutine that owns all shard state
  2. Requests are sent via buffered channels (1000 capacity by default)
  3. Worker processes requests sequentially - no locks needed within a shard
  4. GOMAXPROCS = max(min(cpu_count, shards/4), 1) for optimal parallelism

Benefits:

  • Lock-free: No mutexes, no lock contention within shards
  • Predictable latency: Sequential processing, no lock waiting
  • Simple reasoning: Each shard is single-threaded, no race conditions

On-Disk Storage System

Uses fixed-size records with fseek for random access (not append-only).

File Purpose
keys Fixed-size key records (1049 bytes each)
data Variable-size value records

Keys File Format (keys)

Each record is exactly 1051 bytes at offset keyId * 1051:

┌──────────┬──────────────┬─────────┬──────────┬────────┬─────────┐
│  keyLen  │     key      │   cas   │  expiry  │ bucket │ slotIdx │
│ 2 bytes  │  1024 bytes  │ 8 bytes │ 8 bytes  │ 1 byte │ 8 bytes │
└──────────┴──────────────┴─────────┴──────────┴────────┴─────────┘
         Total: 1051 bytes per record
Field Size Description
keyLen 2 bytes Actual key length (uint16, 0-1024)
key 1024 bytes Key string, null-padded
cas 8 bytes CAS token (uint64)
expiry 8 bytes Unix timestamp in milliseconds (int64), 0 = no expiry
bucket 1 byte Data bucket index (0-15)
slotIdx 8 bytes Slot index within the bucket (int64)

keyId = record index = file offset / 1051

Data File Format (data)

Create 16 data files each holding a different size bucket. Bucket size starts at 1024 bytes and double the size for each file.

┌──────────┬────────────────────┐
│  length  │        data        │
│ 4 bytes  │ [bucketSize] bytes │
└──────────┴────────────────────┘
Field Size Description
length 4 bytes Actual data length (uint32, 0-64MB)
data bucketSize bytes Raw value bytes, null padded

Bucket sizes: 1KB, 2KB, 4KB, ..., 64MB.

Slot sizes: Total slot = 4 + bucketSize bytes.

In-Memory Structures

1. B-Tree Index (Fast Read Access)

  • In-memory only: Built on startup by scanning keys file
  • Lookup: key string → keyId (record index)
  • Stores: { key, keyId, bucket, slotIdx, length, expiry, cas }

2. Expiry Min-Heap (TTL Invalidation Without Scanning)

  • Structure: Binary min-heap ordered by expiry field
  • In-memory only: Built on startup from keys file
  • Entries: (expiry, keyId) — pointers into keys file

Operations:

Operation Complexity Description
PeekMin() O(1) Check if root is expired
Insert() O(log n) Add new item with TTL
Remove(keyId) O(log n) Remove by keyId (with index map)

Invalidation Flow (no scanning required):

  1. Background ticker calls PeekMin() every 100ms
  2. If root.expiry <= now: call Remove(keyId), compact file slots
  3. Repeat until root is not expired or heap is empty

3. Continuous Defragmentation (Always Compact Files)

Instead of free lists, uses continuous defragmentation:

On delete/expiry:

  1. Move tail slot data to freed slot position
  2. Update the moved entry's index to point to new slot
  3. Truncate file by one slot

Benefits:

  • Files are always compact, no wasted space
  • O(1) allocation (always append to end)
  • No fragmentation over time

Success Criteria

  1. Persistence: Data survives process restarts
  2. Performance: Fast lookups via B-Tree, 100k+ RPS SET/GET with sharding
  3. Protocol: Compatible with Memcached clients (Text and Binary protocols)
  4. Simplicity: Easy to understand and maintain, small code base
  5. Compatibility: Works with PHP Memcached session handler

Files: Each shard has its own folder (shard_00/ to shard_15/) containing keys and data_* files.