Repository navigation
Expand file tree
/
Copy pathengine.go
More file actions
230 lines (212 loc) · 5.96 KB
/
Copy pathengine.go
File metadata and controls
230 lines (212 loc) · 5.96 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
package lockd
import (
"context"
"errors"
"hash/fnv"
"time"
"github.com/imharjot/lockd/clock"
"github.com/imharjot/lockd/lease"
)
// Engine is the in-process reservation engine. It hashes keys across a fixed
// set of shards; within a shard each active key is driven by its own actor
// goroutine. The public surface is deliberately tight: Acquire, Renew, Release
// and Fence. It is not a general key-value store.
type Engine struct {
shards []*shard
clk clock.Clock
wal *walSink
obs Observer
}
// Config tunes engine construction. Zero values fall back to sensible
// defaults.
type Config struct {
// Shards is the number of independent key shards. Defaults to 16.
Shards int
// Clock is the time source. Defaults to the real wall clock.
Clock clock.Clock
// Tick is the timing-wheel granularity. Defaults to 50ms.
Tick time.Duration
// WheelSlots is the number of wheel buckets per shard. Defaults to 512.
WheelSlots int
// WAL, if non-nil, receives durable records for crash recovery.
WAL Journal
// ManualTick disables the background wheel goroutine so a test can drive
// expiry deterministically with Tick() after advancing a fake clock.
ManualTick bool
// Observer, if non-nil, receives metrics events.
Observer Observer
}
// Grant is what a successful Acquire or Renew returns to a caller. The Token is
// the fencing token the caller must present on later renew/release.
type Grant struct {
Key string
Holder string
Token lease.Token
ExpiresAt time.Time
}
// Errors surfaced by the engine. The lease-domain errors are re-exported so
// callers can match on them without importing the lease package.
var (
ErrHeld = lease.ErrHeld
ErrNotHeld = lease.ErrNotHeld
ErrWrongHolder = lease.ErrWrongHolder
ErrFenced = lease.ErrFenced
ErrBadTTL = lease.ErrBadTTL
ErrClosed = errors.New("lockd: engine closed")
)
// New builds an engine from cfg and starts its shard goroutines.
func New(cfg Config) *Engine {
if cfg.Shards <= 0 {
cfg.Shards = 16
}
if cfg.Clock == nil {
cfg.Clock = clock.NewReal()
}
if cfg.Tick <= 0 {
cfg.Tick = 50 * time.Millisecond
}
if cfg.WheelSlots <= 0 {
cfg.WheelSlots = 512
}
e := &Engine{clk: cfg.Clock, obs: cfg.Observer}
if e.obs == nil {
e.obs = nopObserver{}
}
if cfg.WAL != nil {
e.wal = &walSink{j: cfg.WAL}
}
e.shards = make([]*shard, cfg.Shards)
for i := range e.shards {
e.shards[i] = newShard(i, e, cfg.Clock, cfg.Tick, cfg.WheelSlots, cfg.ManualTick)
}
return e
}
func (e *Engine) shardFor(key string) *shard {
h := fnv.New32a()
_, _ = h.Write([]byte(key))
return e.shards[int(h.Sum32())%len(e.shards)]
}
// Acquire reserves key for holder for ttl. If the key is already held, the
// call blocks in a fair FIFO queue until the key frees or ctx is cancelled.
// On success it returns a Grant carrying a fresh fencing token.
func (e *Engine) Acquire(ctx context.Context, key, holder string, ttl time.Duration) (Grant, error) {
start := e.clk.Now()
g, err := e.acquire(ctx, key, holder, ttl)
e.obs.AcquireDone(err == nil, e.clk.Now().Sub(start))
return g, err
}
func (e *Engine) acquire(ctx context.Context, key, holder string, ttl time.Duration) (Grant, error) {
if ttl <= 0 {
return Grant{}, ErrBadTTL
}
sh := e.shardFor(key)
a := sh.actorFor(key)
cmd := newCommand(opAcquire)
cmd.holder = holder
cmd.ttl = ttl
cmd.ctx = ctx
if !a.submit(cmd) {
// actor shut down between lookup and submit; retry once with a fresh
// actor.
a = sh.actorFor(key)
if !a.submit(cmd) {
return Grant{}, ErrClosed
}
}
select {
case res := <-cmd.reply:
if res.err != nil {
return Grant{}, res.err
}
return grantFrom(res.lease), nil
case <-ctx.Done():
// Tell the actor to prune our slot if we are still queued.
a.drainCancelled()
select {
case res := <-cmd.reply:
if res.err != nil {
return Grant{}, res.err
}
return grantFrom(res.lease), nil
default:
return Grant{}, ctx.Err()
}
}
}
// Renew extends holder's grant on key by ttl. The caller must present the
// fencing token from the original grant.
func (e *Engine) Renew(key, holder string, token lease.Token, ttl time.Duration) (Grant, error) {
if ttl <= 0 {
return Grant{}, ErrBadTTL
}
sh := e.shardFor(key)
a, ok := sh.lookupActor(key)
if !ok {
return Grant{}, ErrNotHeld
}
cmd := newCommand(opRenew)
cmd.holder = holder
cmd.token = token
cmd.ttl = ttl
if !a.submit(cmd) {
return Grant{}, ErrNotHeld
}
res := <-cmd.reply
if res.err != nil {
return Grant{}, res.err
}
return grantFrom(res.lease), nil
}
// Release frees holder's grant on key. The fencing token guards against a
// stale client releasing a lease that has since been re-granted.
func (e *Engine) Release(key, holder string, token lease.Token) error {
sh := e.shardFor(key)
a, ok := sh.lookupActor(key)
if !ok {
return ErrNotHeld
}
cmd := newCommand(opRelease)
cmd.holder = holder
cmd.token = token
if !a.submit(cmd) {
return ErrNotHeld
}
return (<-cmd.reply).err
}
// Fence returns the current fencing token for key and whether it is held. A
// writer downstream of the lock can compare this against the token it was
// granted to detect that it has been superseded.
func (e *Engine) Fence(key string) (lease.Token, bool) {
sh := e.shardFor(key)
a, ok := sh.lookupActor(key)
if !ok {
return 0, false
}
cmd := newCommand(opSnapshot)
if !a.submit(cmd) {
return 0, false
}
res := <-cmd.reply
if !res.held {
return 0, false
}
return res.lease.Token, true
}
// Close stops every shard and its actors. After Close the engine must not be
// used.
func (e *Engine) Close() {
for _, sh := range e.shards {
sh.stop()
}
}
// Tick drives every shard's wheel once. It is meant for tests and tools using
// a fake clock in ManualTick mode; advance the clock, then call Tick to flush
// any leases that have expired.
func (e *Engine) Tick() {
for _, sh := range e.shards {
sh.tickOnce()
}
}
func grantFrom(l lease.Lease) Grant {
return Grant{Key: l.Key, Holder: l.Holder, Token: l.Token, ExpiresAt: l.ExpiresAt}
}