Zhang Yanpo (drdr.xp)

Zhang Yanpo (drdr.xp)

I write codes, by hands

Build a Distributed Timestamp Oracle with EzRaft

46 分钟阅读

本文链接: https://blog.openacid.com/algo/ez-ts-oracle/

A timestamp oracle issues one globally increasing sequence. Transaction systems built on MVCC consume two of those values on every commit, so the oracle sits on the critical path of every write. The naive way to keep the sequence safe is one Raft commit per request. That design is correct. It is also too slow.

This article builds the other design: reserve a range with one Raft write, then allocate from memory. The service is timestamp_oracle, about 200 lines on EzRaft. It runs as a three-node cluster, stays available after any one node fails, and answers next_timestamp without waiting for a Raft commit.

EzRaft, from the previous article, is a small Rust API over OpenRaft. It hides the Raft, networking, and storage machinery, so you can start with the service itself.

Three calls carry the design:

  • EzRaft::write() commits the upper bound of a reserved range and applies it to the state machine.
  • EzRaft::wait_metrics() lets a background task sleep until its node becomes the leader.
  • EzRaft::linearizable(ReadPolicy::LeaseRead) checks the leader lease and returns the current term, so each cached range is bound to one term.

The idea underneath those calls is simple. Raft owns a ceiling. The leader spends from below that ceiling in memory. A lease and a term tag decide whether it is still allowed to spend.

Architecture overview: `next_timestamp` requests allocate timestamps from the leader's memory, while the reservation task connects the in-memory cache to a three-node EzRaft cluster

What a Timestamp Oracle Must Guarantee

The interface is one call: a client sends next_timestamp, and the service returns a timestamp.

Those values usually order distributed transactions. Models such as Percolator give each transaction a start timestamp and a commit timestamp. Those two numbers decide which transaction came first. TiDB’s TSO (Timestamp Oracle) is the same component.

The service has three hard requirements:

  1. Monotonicity. Timestamps increase in the order requests reach the oracle, and they never go backward after a failover. Every timestamp from the new leader must be greater than every timestamp the old leader already returned.

  2. Fault tolerance. The service stays available while a majority of the cluster is alive. OpenRaft already provides that, so a three-node cluster can lose any one node and keep issuing timestamps.

  3. Low latency. next_timestamp sits on the critical path of every operation that needs an ordering point, so each request has to be cheap.

There is a softer requirement as well. The values should stay close to wall-clock time. Correctness only requires the sequence to increase. Closeness to wall-clock time is a quality goal, not a safety property.

Safe Baseline: One Raft Write per Timestamp

The cluster only has to agree on one durable value: reserved_end, the exclusive end of all timestamp space reserved so far. Every value below reserved_end is permanently consumed, whether or not a client ever received it.

The obvious safe design writes one Raft log entry for every next_timestamp request. Once that entry is replicated and applied, the state machine returns the timestamp it claimed. Every leader walks the same log, so a failover cannot reuse an earlier value.

The state machine is correspondingly small:

struct Reserve {
    reserve_upto_us: u64,
}

struct Interval {
    start: u64,
    end: u64,
}

struct TimeState {
    reserved_end: u64,
}

impl EzApp for TimeState {
    type Request = Reserve;
    type Response = Interval;

    async fn apply(&mut self, req: Reserve) -> Interval {
        let start = self.reserved_end;
        let end = start.max(req.reserve_upto_us);
        self.reserved_end = end;
        Interval { start, end }
    }
}

Reserve asks the state machine to move reserved_end to at least reserve_upto_us. The response is the newly claimed half-open interval [start, end). Those types and apply() are all that [EzApp][docs-ezraft-ezapp] needs. See timestamp_oracle.rs:66-112.

The max in apply() makes the transition idempotent. Applying the same upper bound again leaves reserved_end unchanged, so a timed-out reservation can be retried safely.

This design is safe. It is also slow: every request pays for Raft replication and state-machine application. The rest of the article takes both of those costs off the request path.

Fast Path: Reserve Timestamps in Batches

One Raft entry can reserve a wide range instead of a single value. By default the service reserves one second of timestamp space, then the leader hands out individual values from that range in memory.

reserved_end is durable. The leader’s position inside the reserved range is not: it lives only in memory. If the leader fails, its successor skips the unused suffix and reserves a new range. The sequence may contain gaps. It never goes backward.

A background reservation task keeps the leader’s cache filled. Each successful reservation is stored in a Reserved value with three fields: the term that owns the range, the next available timestamp, and the exclusive upper bound.

struct Reserved {
    term: u64,
    next: u64,
    end: u64,
}

run_reserver() uses wait_metrics() to wait until the node becomes the leader. Once it is, the task calls refill() and repeats every half-reservation interval. See timestamp_oracle.rs:170-186:

struct TimeService {
    // ...
    reserved: Mutex<Reserved>,
}

impl TimeService {
    async fn run_reserver(&self) {
        let refresh_interval = Duration::from_micros(self.reservation_width.get() / 2);
        loop {
            let leads = self.raft.wait_metrics(None, |m| m.state == ServerState::Leader, "reserve timestamps");
            if let Err(error) = leads.await {
                return;
            }
            if let Err(error) = self.refill().await {
                warn!("{error}");
            }
            tokio::time::sleep(refresh_interval).await;
        }
    }
}

refill() first obtains a valid leader term. It then computes now + width, commits that upper bound through Raft, and stores the returned interval in TimeService.reserved. See timestamp_oracle.rs:188-205:

async fn refill(&self) -> io::Result<()> {
    // ensure leader lease and get leader term.
    let term = self.leader_term().await?;
    let now = unix_timestamp_micros();
    let width = self.reservation_width.get();
    let upto = now.saturating_add(width);

    let interval = self.raft.write(Reserve { reserve_upto_us: upto }).await?;

    self.reserved.lock().await.install(term, interval);
    Ok(())
}

The Raft write rate is now independent of the request rate. For a reservation width of width, the task writes once every width / 2. A single distributed commit can serve 100,000 next_timestamp requests.

Preserve Monotonicity Across Leader Failover

Batch allocation stays safe because the committed upper bound, not the in-memory cursor, is the handoff point. When a new leader is elected, it already has the log. After it applies those entries, reserved_end is at least as large as anything the old leader reserved. The new leader never starts from the old leader’s in-memory cursor, because that cursor was never replicated.

Three-node leader failover: Raft log replication and state-machine replay keep `reserved_end` consistent across nodes, so the new leader begins from a safe timestamp range

That committed bound protects the new leader. It does not stop the old one. A network partition can isolate the old leader long enough for the other nodes to elect a replacement, while the old leader still believes it owns the cluster.

Once the new leader issues a timestamp from a later range, any later allocation from the old leader’s range would move time backward. The old leader must refuse requests as soon as it can no longer prove that it still holds leadership.

Reject a Stale Leader with a Lease

A lease is a time-bounded promise: as long as the leader has heard from a quorum recently, no other node can win an election. Checking that promise is a local read of heartbeat state, so it adds no network round trip to a timestamp request. timestamp_oracle performs that check with a linearizable read using ReadPolicy::LeaseRead.

OpenRaft refreshes the lease from heartbeat acknowledgments. A recent acknowledgment from a quorum opens a window during which another leader cannot be elected. The current leader can allocate timestamps for the length of that window.

Once the latest quorum acknowledgment is older than the lease timeout, the node can no longer prove it is the only leader. linearizable() returns an error, and next_timestamp() stops before it touches the cache.

Three-node timeline: heartbeat acknowledgments keep the old leader's lease valid; after the lease expires, a local check rejects `next_timestamp` requests, and the cluster then elects a new leader

[EzRaft::linearizable(ReadPolicy::LeaseRead)][code-ezraft-linearizable] reads the most recent heartbeat state in memory. It does not contact the quorum again. Internally it calls OpenRaft’s [Raft::ensure_linearizable()][docs-openraft-ensure-linearizable] and returns (term, index). The term identifies the current leadership; the allocator uses it to validate the cached range:

async fn leader_term(&self) -> io::Result<u64> {
    let (term, _index) = self.raft.linearizable(ReadPolicy::LeaseRead).await?;
    Ok(term)
}

Serve

next_timestamp from Memory

With a reserved range in place, the request path has three steps:

  • Call leader_term() to validate the lease and obtain the current term.
  • Allocate one timestamp from the cache and advance the cursor.
  • Return the timestamp to the client.

The HTTP handler, the request path, and the cache allocation fit in a few lines. See timestamp_oracle.rs:124-133 and timestamp_oracle.rs:162-168:

async fn get_time(service: web::Data<TimeService>) -> Result<web::Json<String>, actix_web::Error> {
    let micros = service.next_timestamp().await.map_err(actix_web::error::ErrorServiceUnavailable)?;
    Ok(web::Json(format_timestamp(micros)))
}

async fn next_timestamp(&self) -> io::Result<u64> {
    let mut reserved = self.reserved.lock().await;
    let term = self.leader_term().await?;
    let timestamp = reserved.take(term, unix_timestamp_micros());
    timestamp.ok_or_else(|| io::Error::other("no reserved timestamp is currently available"))
}

fn take(&mut self, leader_term: u64, now: u64) -> Option<u64> {
    let timestamp = now.max(self.next);
    if self.term != leader_term || timestamp >= self.end {
        return None;
    }
    self.next = timestamp + 1;
    Some(timestamp)
}

now.max(self.next) keeps timestamps close to wall-clock time while preserving local monotonicity. If the clock advances, the allocator follows it. If several requests arrive in the same microsecond—or the wall clock steps backward—self.next keeps every result unique and increasing.

The term comparison in take() is not part of the lease check. The next section is why that field exists. leader_term() keeps the term and discards the log index; see timestamp_oracle.rs:207-210. The OpenRaft documentation describes the other ReadPolicy options. The underlying read optimization is covered in How OpenRaft Optimizes ReadIndex.

Bind Cached Ranges to a Leader Term

A valid lease proves that this node is the leader now. It does not prove that the cached range belongs to the current term.

Suppose node A reserved a range in term 1, lost leadership, and won it back in term 3. The leftover cache is still in the same process, so a restart is not there to wipe it. In between, node B may have been the leader in term 2 and may already have issued later timestamps. Node A’s leftover cache now sits behind time. Using it would go backward.

That is why Reserved stores the term next to next and end. A range reserved in term 1 is valid only in term 1. The term-3 leader must commit a new reservation before it can serve requests again.

Cross-term timeline for three nodes: node A is the leader in terms 1 and 3, but its old reservation cache is invalidated; `next_timestamp` succeeds only after `refill` installs a new range for term 3

take() enforces both cache invariants in one guard. A term mismatch rejects a range from an earlier leadership. timestamp >= self.end rejects an exhausted range. Later requests succeed only after the background task installs a valid range.

if self.term != leader_term || timestamp >= self.end {
    return None;
}

With the lease check and the term check in place, the in-memory path is safe across leader changes.

Run the Service

Start a Three-Node Cluster

Open three terminals and start one node in each. The first command creates the cluster; the other two use --seed to find the first node and join it:

cargo run --example timestamp_oracle -- --addr 127.0.0.1:8090
cargo run --example timestamp_oracle -- --addr 127.0.0.1:8091 --seed 127.0.0.1:8090
cargo run --example timestamp_oracle -- --addr 127.0.0.1:8092 --seed 127.0.0.1:8090

The cluster assigns node IDs automatically. When a node joins, EzRaft writes a blank log entry and uses its index as the new node’s ID. Other log entries may be committed between two joins, so IDs such as 0, 8, and 17 are expected. /api/metrics now shows three voters with node 0 as the leader:

{"id":0,"current_term":1,"state":"Leader","current_leader":0,
 "membership_config":{"membership":{"configs":[[0,8,17]], ...}}}

Request Timestamps

curl -X POST 127.0.0.1:8090/time

Run the command three times. Each request returns an RFC 3339 timestamp as a JSON string:

"2026-08-11T14:43:16.966734Z"
"2026-08-11T14:43:16.973216Z"
"2026-08-11T14:43:16.979556Z"

The six-to-seven-millisecond gaps come from starting a new curl process for each request. The timestamp allocation itself stays entirely in the leader’s memory.

A follower rejects /time and names the current leader in its response:

$ curl -s -X POST 127.0.0.1:8091/time
has to forward request to: Some(0), Some(BasicNode { addr: "127.0.0.1:8090" })   [HTTP 503]

Stop the Leader

Press Ctrl-C in the terminal running node 0, then keep sending next_timestamp requests to the two remaining nodes:

14:43:28.998  curl 8090  ->  "2026-08-11T14:43:28.998630Z"                        [200]
14:43:29      kill node 0
14:43:29.3    curl 8091  ->  has to forward request to: Some(0), ...:8090          [503]
   ...        (for about five seconds, both 8091 and 8092 return the same 503)
14:43:34.8    curl 8091  ->  has to forward request to: Some(17), ...:8092         [503]
14:43:34.8    curl 8092  ->  no reserved timestamp is currently available          [503]
14:43:35.169  curl 8092  ->  "2026-08-11T14:43:35.169756Z"                        [200]

The timeline shows two stages of recovery. At first the followers still point clients at node 0. Node 17 is then elected leader, but its first Reserve entry has not committed, so its in-memory cache is still empty. As soon as that reservation commits, the service resumes.

The timestamps stay monotonic. The first value from the new leader, 14:43:35.169756, is greater than the last value from the old leader, 14:43:28.998630. The unused interval between them is a harmless gap. /api/metrics confirms that the cluster has advanced from term 1 to term 2:

{"id":17,"current_term":2,"state":"Leader","current_leader":17}
{"id":8,"current_term":2,"state":"Follower","current_leader":17}

What Raft Owns

The consensus layer does not need to see every timestamp. It needs to see the ceiling, and it needs to say who may spend below that ceiling. Once those two facts are durable and current, next_timestamp is a local increment.

That split is the whole service. EzRaft handles replication, election, and failover. The application code persists the reservation boundary, tags each cached range with a term, and advances a cursor.

Reference:

本文链接: https://blog.openacid.com/algo/ez-ts-oracle/

openacid

留下评论

猜您还喜欢