s-tree-sharding

a distributed database that splits data across multiple servers using consistent hashing and a gossip protocol. each server runs a segment tree for range queries and handles locking to prevent conflicts.

what it does:

• auto-rebalances shards when load gets uneven (3-second broadcast)
• handles range queries in log time using segment trees
• prevents write conflicts with interval locking
• runs 8 shards in docker, tests with a client

how it works

network

8 shards connected in a ring. a test client sends requests to them over grpc.

  [ client ]
    |||||
    ▼▼▼▼▼
[1] ←→ [2] ←→ [3] ←→ ... ←→ [8]
  └─────────────────────────────┘
     gossip network (every 3s)

shard internals

when data comes in, the shard:

1. routes based on action type (query / lock / insert)
2. stores data in a binary tree
3. checks tree for conflicts on locks
4. broadcasts current size to other shards

consistent hashing

each key gets hashed to a shard. each shard owns 160 virtual points on the ring to spread load evenly.

key 42500
  → hash_key(42500)
  → find in sorted hashes
  → return shard id

segment tree

data stored as a binary interval tree. each node tracks the min/max values in its range. queries walk the tree in log time.

---

how rebalancing works

every 500ms, each shard checks if it has too much data (default: > 100 items).

if it does, and 5 seconds have passed since the last rebalance:

1. find the midpoint of the data range
2. extract all data above the midpoint
3. send it to the right neighbor
4. shrink own range to below midpoint
5. neighbor expands its range to accept new data

this keeps shards balanced without a central coordinator.

how queries work

client sends request like "give me all keys from 10 to 100".

shard checks if this range overlaps with what it owns. if not, send a redirect (301) to the next shard. if yes, walk the tree and return results.

when multiple shards own parts of the range, the client gets redirected in a chain until all data is collected.

how locking works

client requests a lock on range [10, 50].

server walks the tree and checks if any node in that range is already locked. if yes, return conflict (409). if no, mark all overlapping nodes as locked and return success (200).

to unlock, send same range with empty data packet.

prevents two clients from writing to overlapping ranges at the same time.

---

files

---

cmd/
  client/
    client.go          - test suite, 5 phases
    listener.go        - listens to shard responses
  server/
    main.go            - startup, goroutine orchestration
    handlers.go        - request routing
    migration.go       - 500ms rebalance monitor
    storage/
      engine.go        - tree operations, locks
      tree.go          - binary tree implementation
      hash_ring.go     - consistent hashing
proto/
  service.proto        - message definitions
docker-compose.yml     - 8 shard cluster setup

running it

compile protobuf

go install google.golang.org/protobuf/cmd/protoc-gen-go@latest
go install google.golang.org/grpc/cmd/protoc-gen-go-grpc@latest

protoc --go_out=. --go-grpc_out=. proto/service.proto proto/metadata.proto

start cluster

docker compose down && docker compose up --build

waits 10s for shards to start, then test client runs 5 phases:

1. basic distribution - 100 points
2. heavy load - 5 waves of 500 points each
3. query correctness - full range queries
4. locking - concurrent lock tests
5. cluster consistency - shard state checks