《后端架构设计·分布式与数据一致性》2.3 混合逻辑时钟与版本向量在 arch-lab 的落地

// file: internal/platform/hlc/hlc.go
// tier: L1
// verify: go test ./internal/platform/hlc/ -count=1
package hlc

import (
	"fmt"
	"sync"
	"time"
)

// Timestamp is a hybrid logical clock reading: physical milliseconds plus a
// logical counter that breaks ties and covers clock regression.
type Timestamp struct {
	Wall    int64
	Logical uint32
}

// Compare returns -1, 0 or 1 in lexicographic (Wall, Logical) order.
func (t Timestamp) Compare(other Timestamp) int {
	switch {
	case t.Wall < other.Wall:
		return -1
	case t.Wall > other.Wall:
		return 1
	case t.Logical < other.Logical:
		return -1
	case t.Logical > other.Logical:
		return 1
	default:
		return 0
	}
}

// Before reports whether t is strictly older than other.
func (t Timestamp) Before(other Timestamp) bool { return t.Compare(other) < 0 }

// String renders a timestamp for logs.
func (t Timestamp) String() string { return fmt.Sprintf("%d.%d", t.Wall, t.Logical) }

// Clock is a hybrid logical clock. It never returns a timestamp smaller than
// one it has already returned, even when the wall clock moves backwards.
type Clock struct {
	mu   sync.Mutex
	last Timestamp
	wall func() time.Time
}

// NewClock builds a clock from a wall-time source. A nil source uses time.Now.
func NewClock(wall func() time.Time) *Clock {
	if wall == nil {
		wall = time.Now
	}
	return &Clock{wall: wall}
}

// Now records a local event and returns its timestamp.
func (c *Clock) Now() Timestamp { return c.observe(Timestamp{}) }

// Send records a send event. It is separate from Now only for readability at
// call sites.
func (c *Clock) Send() Timestamp { return c.Now() }

// Receive merges a remote timestamp and records the receive event.
func (c *Clock) Receive(remote Timestamp) Timestamp { return c.observe(remote) }

// Last returns the most recent timestamp without advancing the clock.
func (c *Clock) Last() Timestamp {
	c.mu.Lock()
	defer c.mu.Unlock()
	return c.last
}

func (c *Clock) observe(remote Timestamp) Timestamp {
	c.mu.Lock()
	defer c.mu.Unlock()

	now := c.wall().UnixMilli()
	wall := max(c.last.Wall, remote.Wall, now)

	var logical uint32
	switch {
	case wall == c.last.Wall && wall == remote.Wall:
		logical = max(c.last.Logical, remote.Logical) + 1
	case wall == c.last.Wall:
		logical = c.last.Logical + 1
	case wall == remote.Wall:
		logical = remote.Logical + 1
	default:
		logical = 0
	}
	c.last = Timestamp{Wall: wall, Logical: logical}
	return c.last
}

=== RUN   TestClockMonotonicUnderWallRollback
    hlc_test.go:24: timestamps: 1000.0 1000.1 1000.2
=== RUN   TestReceivePreservesCausality
    hlc_test.go:46: sent=1000.0 received=1001.0 local=1001.1
=== RUN   TestSameWallConcurrentEventsTie
    hlc_test.go:62: node-a=1000.0 node-b=1000.0 equal=true
--- PASS   (all three)

// file: internal/platform/hlc/vv.go
// tier: L1
// verify: go test ./internal/platform/hlc/ -run TestMerge -count=1
package hlc

// VersionVector counts mutations per writer node.
type VersionVector map[string]uint64

func (v VersionVector) Clone() VersionVector {
	out := make(VersionVector, len(v))
	for node, counter := range v {
		out[node] = counter
	}
	return out
}

func (v VersionVector) Increment(node string) uint64 {
	v[node]++
	return v[node]
}

// Merge takes the pointwise maximum of two vectors.
func (v VersionVector) Merge(other VersionVector) {
	for node, counter := range other {
		if counter > v[node] {
			v[node] = counter
		}
	}
}

// Equal reports whether two vectors describe the same mutations.
func (v VersionVector) Equal(other VersionVector) bool {
	for node, counter := range v {
		if other[node] != counter {
			return false
		}
	}
	for node, counter := range other {
		if v[node] != counter {
			return false
		}
	}
	return true
}

// VersionRelation classifies two version vectors.
type VersionRelation int

const (
	VersionEqual VersionRelation = iota
	VersionBefore
	VersionAfter
	VersionConcurrent
)

// Compare classifies two vectors using the same component-wise order as a
// vector clock.
func (v VersionVector) Compare(other VersionVector) VersionRelation {
	lessOrEqual, greaterOrEqual := true, true
	for node, a := range v {
		b := other[node]
		if a > b {
			lessOrEqual = false
		}
		if a < b {
			greaterOrEqual = false
		}
	}
	for node, b := range other {
		a := v[node]
		if a > b {
			lessOrEqual = false
		}
		if a < b {
			greaterOrEqual = false
		}
	}
	switch {
	case lessOrEqual && greaterOrEqual:
		return VersionEqual
	case lessOrEqual:
		return VersionBefore
	case greaterOrEqual:
		return VersionAfter
	default:
		return VersionConcurrent
	}
}

$ go test ./internal/platform/hlc/ -run 'TestOrderUpdate|TestMerge' -v -count=1
    hlc_test.go:76: after reserve: version=map[node-a:1]
    hlc_test.go:86: after pay: version=map[node-a:1 node-b:1]
    hlc_test.go:106: conflict=true status=CANCELLED version=map[node-a:1 node-b:1]
    hlc_test.go:124: conflict=false status=INVENTORY_RESERVED version=map[node-a:1]
--- PASS