checkpoint.gno
15.34 Kb · 383 lines
1// Package checkpoint remembers what a number used to be.
2//
3// A Series is one value's history. It answers what that value held during a
4// past epoch, which is the question governance asks: voting weight has to be
5// read as of the moment a question was put, or it can be borrowed for the
6// length of one transaction and voted twice.
7//
8// It was written for a token's balances and its total supply, and there is
9// nothing about it that knows what a token is. Anything a realm wants to look
10// back at — a fee, a quorum, a member count — is a Series.
11//
12// # What it costs
13//
14// One fact about gno shapes the whole thing: storage deposit is charged per
15// OBJECT, on the DELTA of its encoded size (gnovm/pkg/gnolang/store.go,
16// LastObjectSize, at 100ugnot/byte). A field added to a record that was going
17// to be written anyway is paid for once, at creation, and costs nothing on
18// every write after. On the EVM every extra word touched is a fresh SSTORE
19// forever, which is the entire reason OpenZeppelin's ERC20Votes appends to an
20// array per block — and the reason that shape does not have to be inherited.
21//
22// So: two points inline, the rest paged into an archive. The overwhelmingly
23// common query is answered without touching the archive at all, and a value
24// that changes several times within one epoch coalesces into a single update
25// of a record already being written.
26//
27// # Epochs, not blocks
28//
29// The caller supplies the epoch and this package never asks what one is. That
30// is deliberate — the clock is policy. Quantising to something coarser than a
31// block is what makes the cost work, because a checkpoint per block maximises
32// the one thing gno charges dearly for, a brand new key.
33//
34// It also turns the anti-flash-loan property from a convention into an
35// invariant, if the caller refuses to answer for the current epoch: a
36// transaction cannot outlive its block and a block cannot outlive its epoch,
37// so a borrowed balance cannot be voted and returned. This package cannot
38// enforce that, because it does not know what time it is. It is the caller's
39// half of the bargain and worth writing down where the caller will read it.
40package checkpoint
41
42import (
43 "strings"
44
45 bptree "gno.land/p/nt/bptree/v0"
46)
47
48// Sep separates a caller's key from this package's own suffix.
49//
50// Exported because a caller sharing one Archive between several keyspaces
51// usually wants the same byte for its own compound keys, and two constants
52// with the same value in different files eventually disagree.
53//
54// A key may not contain it. That is checked rather than documented, because
55// the failure is silent: one key's range scan would reach into another's and
56// return a plausible number belonging to somebody else.
57const Sep = "\x00"
58
59// MaxKey bounds a key.
60//
61// A key is not stored once. It is the prefix of every page key this series ever
62// writes, so its length multiplies by the number of pages a long-lived value
63// accumulates — and the pages are what the design buys with the deposit it
64// saves elsewhere.
65//
66// Exported so a caller can check before calling rather than discover by
67// panicking. A hundred and twenty-eight is room for a bech32 address twice over
68// with a separator between, which is the largest sensible key the realm this
69// came out of could form.
70const MaxKey = 128
71
72// PageEpochs is how many epochs one archive page covers.
73//
74// It bounds the archive in both directions, and both matter.
75//
76// Downwards: one new key buys this many checkpoints instead of one, which is
77// what keeps the marginal cost of history near zero.
78//
79// Upwards: a page cannot grow past one bucket. Keeping every checkpoint for a
80// key in a single page would be CHEAPER in keys — one per key, forever — and
81// that is exactly its problem. Appending stays cheap, since the deposit is
82// charged on the size delta, but the whole object is deserialised to answer
83// anything about it. A key with years behind it would pay to load all of them
84// to answer about one epoch.
85const PageEpochs = uint32(32)
86
87// Archive is the shared store the older points live in.
88//
89// One Archive can hold any number of Series, told apart by key. Bounding each
90// scan to its own key's prefix is what keeps them apart, and it is the reason
91// a key may not contain Sep.
92type Archive struct {
93 t *bptree.BPTree
94}
95
96// NewArchive returns an empty archive.
97func NewArchive() *Archive { return &Archive{t: bptree.NewBPTree32()} }
98
99// Size is the number of pages stored, across every key.
100//
101// Exported for the caller that wants to assert what its own history costs —
102// the count is the number of KEYS bought, which is the expensive quantity.
103func (a *Archive) Size() int { return a.t.Size() }
104
105// page is one bucket of archived checkpoints for one key, ascending.
106//
107// One packed string, not slices: gno stores a []int64 or []uint32 as an array of
108// TypedValues at ~40 bytes an element, but a string (like a []byte) at one byte
109// each. So the entries pack big-endian into a single string — 4 bytes of epoch
110// then 8 of value, 12 bytes per entry — which is ~3x smaller than the two-slice
111// form and is what the archive's locked deposit is charged on. Appending
112// reassigns this *page's field (no tree Set), so a write still dirties exactly one
113// object.
114type page struct {
115 packed string // ascending [epoch:4 BE][value:8 BE] entries, 12 bytes each
116}
117
118// Series is one value's history: the two most recent points inline, everything
119// older in the archive.
120//
121// at >= e0 -> cur
122// e1 <= at < e0 -> prev
123// at < e1 -> the archive
124//
125// e1 == 0 means the second slot was never used, and prev is then zero, which
126// is the correct answer for every epoch below e0 — so a key that has held a
127// steady value since it was created never touches the archive at all. That
128// case is the overwhelming majority of queries.
129//
130// That sentinel is why epochs are 1-BASED and SetAt refuses zero. Zero has to
131// mean "before this series existed" and cannot also be an epoch somebody wrote
132// in, or the two readings collide: a value written at epoch 0 leaves e1 == 0
133// after the next change, the roll after that reads it as an empty slot, and the
134// point is dropped instead of archived. Silently — the archive stays empty and
135// every query below the newest two points answers zero.
136//
137// The realm this came out of never could have hit it, because its clock is
138// 1-based for exactly this reason. The assumption did not travel with the code,
139// which is the whole hazard of moving code into a package.
140//
141// Hold it as a VALUE field in whatever record the caller already persists.
142// Mutating it then dirties only that record. A pointer would make it a second
143// object, which is a second key, which is the cost this design exists to
144// avoid.
145type Series struct {
146 cur int64
147 prev int64
148 e0 uint32
149 e1 uint32
150}
151
152// Value is what the series holds now, without consulting anything.
153func (s *Series) Value() int64 { return s.cur }
154
155// Prev is the older of the two inline points: its epoch and value. A zero
156// epoch means that slot was never used (the series has at most one point).
157// Callers assembling a full history read the archive, then Prev, then
158// Since/Value — ascending by construction, since points only roll outward.
159func (s *Series) Prev() (uint32, int64) { return s.e1, s.prev }
160
161// Since is the epoch the current value has held from.
162//
163// Useful for asserting that something did NOT write — a caller that expects an
164// operation to be free can check this did not move.
165func (s *Series) Since() uint32 { return s.e0 }
166
167// SetAt records v from epoch e onward, rolling whatever falls out of the two
168// inline slots into the archive.
169//
170// e must be at least 1, and must not be below the newest epoch already
171// recorded. Callers pass a chain height quantised to an epoch, which only ever
172// increases.
173func (s *Series) SetAt(a *Archive, key string, e uint32, v int64) {
174 mustBeUsable(key)
175 if e == 0 {
176 // Refused rather than documented, because the damage is silent and
177 // arrives two changes later. See the note on Series: zero is the
178 // sentinel for an unused slot, so a real checkpoint written there is
179 // read as an empty one and dropped on the roll after next.
180 panic("checkpoint: epochs are 1-based; 0 means before the series existed")
181 }
182 if e < s.e0 {
183 // The clock went backwards. Impossible on a chain, so this means the
184 // caller is not on one — a test harness that resets the height between
185 // cases produces exactly this.
186 //
187 // Worth a panic rather than a comment because the failure it prevents
188 // is invisible: a checkpoint written below the newest one pushes a
189 // stale value into the previous slot and moves e0 backwards, and every
190 // later query returns a plausible, wrong number.
191 panic("checkpoint: the clock went backwards")
192 }
193 if e == s.e0 {
194 // The second and later change within one epoch. No new key, and the
195 // object was going to be written anyway: free, in the sense that
196 // matters.
197 s.cur = v
198 return
199 }
200 if s.e1 != 0 {
201 a.append(key, s.e1, s.prev)
202 }
203 s.prev, s.e1 = s.cur, s.e0
204 s.cur, s.e0 = v, e
205}
206
207// ValueAt answers what the series held during epoch at.
208//
209// Zero for an epoch before the series began, which is exact rather than a
210// miss: the key held nothing then.
211func (s *Series) ValueAt(a *Archive, key string, at uint32) int64 {
212 if at >= s.e0 {
213 return s.cur
214 }
215 // Covers e1 == 0 as well, where prev is zero and zero is exact.
216 if at >= s.e1 {
217 return s.prev
218 }
219 mustBeUsable(key)
220 out := int64(0)
221 // Bounded below by this key's own prefix so the descent cannot walk back
222 // into the previous key's pages. ReverseIterate is [start, end] descending
223 // with end inclusive (bptree tree.gno, "ReverseIterate calls cb"), which is
224 // the floor query — no binary search of our own.
225 a.t.ReverseIterate(key+Sep, pageKey(key, at/PageEpochs), func(_ string, pv any) bool {
226 s := pv.(*page).packed
227 for i := len(s)/12 - 1; i >= 0; i-- {
228 off := i * 12
229 if rd32(s, off) <= at {
230 out = rd64(s, off+4)
231 return true
232 }
233 }
234 // Pages bucket EPOCHS, not checkpoints, so the page a query lands in
235 // may hold only points later than the epoch being asked about. Keep
236 // walking down; the answer is in an older page.
237 return false
238 })
239 return out
240}
241
242func (a *Archive) append(key string, e uint32, v int64) {
243 pk := pageKey(key, e/PageEpochs)
244 entry := be32(e) + be64(v) // 12 bytes: epoch then value
245 if pv := a.t.Get(pk); pv != nil {
246 p := pv.(*page)
247 // Reassign the field on the pointer the tree already holds. No Set, so the
248 // leaf and its whole inner path stay clean and the write dirties only this
249 // *page. Entries arrive ascending by construction, so there is nothing to
250 // sort.
251 p.packed += entry
252 return
253 }
254 a.t.Set(pk, &page{packed: entry})
255}
256
257// mustBeUsable refuses a key that would collide with another key's pages.
258//
259// A p/ package's callers are not the people who wrote it, so this is a case
260// that can happen rather than defensive decoration. The cost is a scan of a
261// short key against the tree operations it precedes, which is nothing.
262func mustBeUsable(key string) {
263 if strings.Contains(key, Sep) {
264 panic("checkpoint: a key may not contain checkpoint.Sep")
265 }
266 if len(key) > MaxKey {
267 panic("checkpoint: that key is too long")
268 }
269 if key == "" {
270 // An empty key is not wrong so much as unusable: its page range is a
271 // prefix of every other key's, so it would scan into whatever sorts
272 // first. Refused for the same reason as one containing the separator.
273 panic("checkpoint: a key may not be empty")
274 }
275}
276
277// be32 is big-endian and fixed width, so byte order is numeric order.
278//
279// The floor query is a range scan over these keys and nothing else puts them
280// in order. Little-endian would sort pages 0, 1 and 2 correctly and come apart
281// at 256.
282func be32(u uint32) string {
283 b := [4]byte{byte(u >> 24), byte(u >> 16), byte(u >> 8), byte(u)}
284 return string(b[:])
285}
286
287// be64 packs an int64 value big-endian (via its uint64 bit pattern, so a negative
288// value round-trips through rd64). Together with be32 it forms a page's 12-byte
289// entry.
290func be64(v int64) string {
291 u := uint64(v)
292 var b [8]byte
293 for i := 7; i >= 0; i-- {
294 b[i] = byte(u & 0xff)
295 u >>= 8
296 }
297 return string(b[:])
298}
299
300// rd32 and rd64 read a packed entry's epoch and value back from a page string.
301func rd32(s string, off int) uint32 {
302 return uint32(s[off])<<24 | uint32(s[off+1])<<16 | uint32(s[off+2])<<8 | uint32(s[off+3])
303}
304
305func rd64(s string, off int) int64 {
306 var u uint64
307 for i := 0; i < 8; i++ {
308 u = (u << 8) | uint64(s[off+i])
309 }
310 return int64(u)
311}
312
313func pageKey(key string, page uint32) string { return key + Sep + be32(page) }
314
315// Trim deletes archive pages of key that lie entirely below keepFrom — except
316// the newest such page — oldest-first, at most maxPages per call. It returns
317// how many pages were removed.
318//
319// The exception is the floor-preservation invariant: a value set below the
320// horizon and unchanged since is still the correct answer for epochs INSIDE
321// the kept window, and its floor entry lives in the newest all-below page.
322// Sparing that one page keeps ValueAt exact at and above keepFrom through
323// every intermediate state of a bounded, multi-call trim. A page straddling
324// the horizon is never a candidate (it is not entirely below), so up to
325// PageEpochs-1 epochs of over-retention are kept deliberately.
326//
327// Deletion frees the page object's bytes; on chains with storage deposits the
328// locked amount is released by the same mechanism that charged it. Trim never
329// touches the two inline points — recent reads stay exact by construction.
330//
331// The walk is collect-then-remove because the tree forbids mutation from an
332// iteration callback, and it is bounded to maxPages+1 keys of collection, so
333// a call's cost is a constant of the caller's choosing.
334func (a *Archive) Trim(key string, keepFrom uint32, maxPages int) int {
335 mustBeUsable(key)
336 if maxPages <= 0 {
337 return 0
338 }
339 // Candidates are pages strictly below the horizon's own page: page P
340 // covers epochs [P*PageEpochs, P*PageEpochs+PageEpochs-1], so P <
341 // keepFrom/PageEpochs puts every epoch in P below keepFrom. Iterate is
342 // [start, end) ascending, which is exactly the candidate range.
343 end := pageKey(key, keepFrom/PageEpochs)
344 keys := []string{}
345 a.t.Iterate(key+Sep, end, func(k string, _ any) bool {
346 keys = append(keys, k)
347 return len(keys) >= maxPages+1
348 })
349 var del []string
350 if len(keys) == maxPages+1 {
351 // The budget's worth, oldest-first. The newest collected candidate —
352 // and anything beyond it the bounded walk never reached — survives,
353 // so the newest all-below page survives.
354 del = keys[:maxPages]
355 } else if len(keys) > 0 {
356 // The walk exhausted the candidates: the last one collected IS the
357 // newest all-below page. Spare it.
358 del = keys[:len(keys)-1]
359 }
360 for _, k := range del {
361 a.t.Remove(k)
362 }
363 return len(del)
364}
365
366// WalkDesc visits key's ARCHIVED checkpoints newest-first, stopping when fn
367// returns true. The two inline points are the Series' own fields and are not
368// visited — a caller assembling a history appends them itself (they are always
369// newer than anything archived, because points only ever roll OUT of the
370// inline slots). Bounded by the key's page prefix like every other walk here.
371func (a *Archive) WalkDesc(key string, fn func(e uint32, v int64) bool) {
372 mustBeUsable(key)
373 a.t.ReverseIterate(key+Sep, pageKey(key, ^uint32(0)), func(_ string, pv any) bool {
374 s := pv.(*page).packed
375 for i := len(s)/12 - 1; i >= 0; i-- {
376 off := i * 12
377 if fn(rd32(s, off), rd64(s, off+4)) {
378 return true
379 }
380 }
381 return false
382 })
383}
