- Updated: March 18, 2026
- 3 min read
Design and Implementation of a Conflict‑Free Replicated Token Bucket for OpenClaw Rating API Edge
# Design and Implementation of a Conflict‑Free Replicated Token Bucket for OpenClaw Rating API Edge
## Introduction
The OpenClaw Rating API Edge requires a highly‑available, low‑latency rate‑limiting mechanism that works across multiple data‑centers. To meet this need we built a **conflict‑free replicated token bucket** (CR‑TB) using CRDT techniques. This article walks through the design, the CRDT data model, step‑by‑step implementation, and operational best‑practices. It also references the earlier *Cross‑Region Consistency Guide* and the *Redis‑Cluster Implementation* for context.
—
## Design Overview
– **Goal:** Provide deterministic rate‑limiting while allowing writes in any region without coordination.
– **Approach:** Model the token bucket as a **PN‑Counter CRDT** that tracks tokens added and tokens consumed separately. The net token count is the difference between the two counters.
– **Key properties:**
1. **Eventual consistency** – all replicas converge to the same token count.
2. **Monotonicity** – counters only increase, preventing lost updates.
3. **Idempotent merges** – safe to replay operations.
—
## CRDT Data Model
{
“bucket_id”: “string”, // unique identifier for the bucket
“capacity”: “integer”, // max tokens the bucket can hold
“added”: { “replica_id”: “int” }, // PN‑Counter for tokens added
“consumed”: { “replica_id”: “int” } // PN‑Counter for tokens consumed
}
– **Added Counter:** Incremented when tokens are refilled (e.g., every second).
– **Consumed Counter:** Incremented when a request is allowed.
– **Current Tokens:** `capacity + sum(added) – sum(consumed)` (clamped to `[0, capacity]`).
—
## Implementation Steps
1. **Choose a CRDT library** – UBOS provides a lightweight PN‑Counter implementation that can be persisted in Redis or RocksDB.
2. **Create bucket metadata** – store `bucket_id`, `capacity`, and initial counters (`added=0`, `consumed=0`).
3. **Refill job** (run per replica):
python
def refill(bucket):
bucket.added[replica_id] += refill_rate
4. **Consume token** (when a request arrives):
python
def try_consume(bucket):
if bucket.current_tokens > 0:
bucket.consumed[replica_id] += 1
return True
return False
5. **Merge replicas** – on replication sync, merge the two PN‑Counters by taking the element‑wise maximum.
6. **Persist state** – after each operation, write the bucket state to the chosen store (Redis cluster for low latency, RocksDB for durability).
7. **Expose API** – a thin HTTP layer (`/rate-limit/:bucket_id`) that calls `try_consume` and returns `200 OK` or `429 Too Many Requests`.
—
## Operational Best‑Practices
| Practice | Why it matters |
|———-|—————-|
| **Separate write‑region** for each replica | Guarantees monotonic counter increments without cross‑region locks. |
| **Periodic state snapshots** (e.g., every minute) | Reduces merge cost and provides a recovery point. |
| **Bounded replication lag** – monitor with Prometheus alerts | Ensures the token count does not drift beyond acceptable limits. |
| **Use Redis‑Cluster for hot buckets** – low‑latency reads/writes | Aligns with the *Redis‑cluster implementation* described in the consistency guide. |
| **Graceful degradation** – fallback to a static rate limit if CR‑TB sync fails | Keeps the API functional during network partitions. |
—
## References
– **Cross‑Region Consistency Guide** – explains the underlying CRDT theory and replication patterns used here.
– **Redis‑Cluster Implementation** – details how we store PN‑Counters in a sharded Redis cluster for high throughput.
For a deeper dive into hosting OpenClaw on UBOS, see the internal documentation: [Host OpenClaw](/host-openclaw/).
—
## Conclusion
By leveraging a PN‑Counter CRDT, the OpenClaw Rating API Edge gains a conflict‑free, globally consistent rate‑limiting mechanism that scales across regions without sacrificing latency. The design aligns with UBOS best‑practice guidelines and integrates cleanly with existing Redis‑cluster deployments.
*Published by the UBOS Team*