timestamp.go

package yin

// Timestamp identifies and orders CRDT updates.
//
// The current representation is a Lamport logical counter plus the ReplicaID
// that issued the timestamp. The fields are intentionally unexported so a
// future HLC implementation can replace or extend the representation while
// preserving the comparison and advance contracts. Timestamp never consults
// wall-clock time, keeping generated histories deterministic and reproducible.
type Timestamp struct {
	counter uint64
	replica ReplicaID
}

// NewTimestamp constructs a Timestamp from an explicit Lamport counter and
// issuing ReplicaID.
func NewTimestamp(counter uint64, replica ReplicaID) Timestamp {
	return Timestamp{counter: counter, replica: replica}
}

// Counter returns the Lamport logical counter currently carried by ts.
func (ts Timestamp) Counter() uint64 {
	return ts.counter
}

// ReplicaID returns the replica that issued ts.
func (ts Timestamp) ReplicaID() ReplicaID {
	return ts.replica
}

// Compare orders timestamps by Lamport counter, then by ReplicaID as a
// deterministic tie-breaker. It returns -1 when ts sorts before other, 1 when it
// sorts after other, and 0 when both components are equal.
func (ts Timestamp) Compare(other Timestamp) int {
	if ts.counter < other.counter {
		return -1
	}
	if ts.counter > other.counter {
		return 1
	}
	return ts.replica.Compare(other.replica)
}

// Advance returns the next local timestamp for replica after observing seen.
// The returned Lamport counter is max(ts.counter, seen.counter)+1; no
// wall-clock input is used. Advance panics if the next counter would overflow;
// silently wrapping would violate Lamport monotonicity.
func (ts Timestamp) Advance(seen Timestamp, replica ReplicaID) Timestamp {
	next := ts.counter
	if seen.counter > next {
		next = seen.counter
	}
	if next == ^uint64(0) {
		panic("yin: timestamp counter overflow")
	}
	return Timestamp{counter: next + 1, replica: replica}
}

// nextLocalTimestamp issues the timestamp for replica's next local write given
// the causal state it has observed. The returned Lamport counter is one past
// the maximum counter in observed, from any replica, so the local write orders
// after every update already incorporated. CRDTs that track causal state as a
// VersionVector should issue every local timestamp through this helper.
func nextLocalTimestamp(observed VersionVector, replica ReplicaID) Timestamp {
	seen := NewTimestamp(observed.maxCounter(), replica)
	return seen.Advance(seen, replica)
}

// lwwVersion returns the causal coverage of a single-write timestamp: the
// version vector holding just the writer's counter. A zero-counter timestamp
// means "no write yet" and maps to the empty vector.
func lwwVersion(timestamp Timestamp) VersionVector {
	if timestamp.Counter() == 0 {
		return VersionVector{}
	}
	return NewVersionVector(map[ReplicaID]uint64{timestamp.ReplicaID(): timestamp.Counter()})
}