compact.gno
8.88 Kb · 221 lines
1// Package compact makes fragmentation a number you can act on.
2//
3// A soft delete does not free anything. It clears the element and leaves the
4// tree node behind, so the bytes stay locked and every read still walks past
5// them. Compacting drops those nodes and the chain refunds their deposit to
6// whoever signed the transaction. So compaction is paid work, and the only
7// real question is WHEN: too early and you free too few nodes to cover the
8// gas, too late and every read has been paying for the holes in between.
9//
10// This realm refuses to answer that question, on purpose. It publishes the
11// two integers the answer is made of and lets whoever is watching decide,
12// because the realm cannot see the gas price of the day and the caller can.
13//
14// - Fragmentation() is live vs allocated, the free read a bot polls.
15// - Reclaimable() is what a Compact would actually free, right now.
16// - Quote() prices it at the floor gas price, as an advertisement.
17//
18// The arithmetic is gno.land/p/moul/x/storagecost and the container is
19// gno.land/p/moul/ulist, whose Compact drops dead nodes without moving a live
20// index, so an index is stable for the life of the realm.
21//
22// # Why this quote is trustworthy where a reaper's is not
23//
24// A reaper advertises what deleting entries will refund, and to do that it has
25// to guess how much state an entry occupies from its payload length. That
26// guess is bad: a per-entry floor dominates at the small end, and one realm
27// under-advertised by 25x on chain because of it.
28//
29// Compaction has no such problem. What it frees is a COUNT of dead nodes, and
30// the container already reports that count exactly. Every node costs the same
31// whatever it carried. So the number on this page is a measured constant times
32// an exact integer, not a ratio applied to a guess, which is why this is the
33// half of the mechanism worth showing first.
34package compact
35
36import (
37 "strings"
38
39 "chain/runtime"
40
41 "gno.land/p/moul/kit/ui/v0"
42 "gno.land/p/moul/md/v0"
43 "gno.land/p/moul/ulist/v1"
44 "gno.land/p/moul/x/storagecost/v1"
45 "gno.land/p/nt/ufmt/v0"
46)
47
48// gasWantedCompact is the gas ceiling a compacting transaction is assumed to
49// ask for, used only to price the advertised bounty. A caller compacting an
50// unusually large number of nodes should re-price with
51// storagecost.EvaluateAtFloor directly rather than trust this.
52const gasWantedCompact int64 = 5_000_000
53
54// maxText caps an entry so one caller cannot lock an unbounded deposit in a
55// single call. Small on purpose: this realm is about the NODES, and a fat
56// payload would only hide the thing it exists to show.
57const maxText = 256
58
59// Entry is one element. Author is kept so a drop can be refused to anyone
60// else: soft-deleting a stranger's entry would be vandalism, and the holes
61// this realm studies should come from ordinary use.
62type Entry struct {
63 Text string
64 Author address
65 Added int64 // block height
66}
67
68var entries = ulist.New()
69
70// Add appends an entry and locks its storage deposit against the caller.
71func Add(cur realm, text string) int {
72 if text == "" {
73 panic("compact: empty entry")
74 }
75 if len(text) > maxText {
76 panic(ufmt.Sprintf("compact: entry too long, %d bytes against a %d cap", len(text), maxText))
77 }
78 entries.Append(&Entry{
79 Text: text,
80 Author: cur.Previous().Address(),
81 Added: runtime.ChainHeight(),
82 })
83 return entries.TotalSize() - 1
84}
85
86// Drop soft-deletes your own entry, which is what creates a hole.
87//
88// It frees nothing on its own, and that is the point of the realm: the bytes
89// stay locked until somebody compacts. Only the author may drop, so the
90// fragmentation on this page is the honest kind that ordinary use produces.
91func Drop(cur realm, index int) {
92 e, ok := entryAt(index)
93 if !ok {
94 panic(ufmt.Sprintf("compact: no live entry at %d", index))
95 }
96 if e.Author != cur.Previous().Address() {
97 panic("compact: only the author may drop an entry")
98 }
99 entries.MustDelete(index)
100}
101
102// Compact frees the dead tree nodes and returns how many it freed.
103//
104// Permissionless by design, and the refund goes to whoever signs this
105// transaction rather than to the realm or to the authors: the chain pays the
106// signer directly, so there is nothing here to distribute and nothing to
107// steal. The worst a caller can do is waste their own gas compacting a board
108// that had no holes.
109func Compact(cur realm) int {
110 return entries.Compact()
111}
112
113// Fragmentation reports live elements against allocated indices.
114//
115// The gap between them is what a compaction has to work with. It is a free
116// read so a bot can poll it and decide for itself, which is the whole design:
117// the realm publishes, the caller times.
118func Fragmentation() (live, allocated int) {
119 return entries.Size(), entries.TotalSize()
120}
121
122// Reclaimable is how many dead nodes a Compact would free right now.
123//
124// It is NOT the same as allocated minus live. A dead element only becomes a
125// reclaimable node once every element under it is also dead, so a board with
126// many scattered holes can report a large gap and nothing to reclaim. That
127// difference is exactly what makes the timing a decision instead of a rule.
128func Reclaimable() int { return entries.Compactable() }
129
130// Quote prices what a Compact would return, at the default storage price and
131// the floor gas price.
132//
133// Unlike a payload-derived bounty this is a counted quantity: Reclaimable is
134// exact, and storagecost.EstimateNodes multiplies it by a measured per-node
135// constant. Treat it as an advertisement all the same. The authoritative
136// numbers are the chain's, in the StorageUnlockEvent the transaction emits.
137func Quote() storagecost.Quote {
138 return storagecost.EvaluateAtFloor(
139 storagecost.EstimateNodes(int64(Reclaimable())), gasWantedCompact)
140}
141
142// entryAt reads index i, reporting whether a live entry is there.
143func entryAt(i int) (*Entry, bool) {
144 v := entries.Get(i)
145 if v == nil {
146 return nil, false
147 }
148 e, ok := v.(*Entry)
149 return e, ok
150}
151
152func Render(path string) string {
153 var b strings.Builder
154
155 b.WriteString(md.H1("Compact"))
156 b.WriteString("\nSoft-deleting an entry frees nothing: the tree node stays, the bytes stay locked, and every read still walks past the hole. Compacting drops those nodes and the chain refunds their deposit **to whoever signs the transaction**. The only question is when.\n\n")
157
158 live, allocated := Fragmentation()
159 dead := Reclaimable()
160 q := Quote()
161
162 b.WriteString(md.H2("The two integers"))
163 b.WriteString("\n")
164 b.WriteString(md.BulletList([]string{
165 ufmt.Sprintf("**%d live** of **%d allocated** indices%s", live, allocated, ratioSuffix(live, allocated)),
166 ufmt.Sprintf("**%d reclaimable nodes**, about %d bytes of state", dead, q.Bytes),
167 ufmt.Sprintf("refunds roughly **%s** to whoever compacts", storagecost.FormatGNOT(q.Refund)),
168 ufmt.Sprintf("against **%s** of gas at the floor price, break-even at %d bytes", storagecost.FormatGNOT(q.Fee), q.BreakEven),
169 ufmt.Sprintf("verdict: **%s**", verdict(q, dead)),
170 }))
171 b.WriteString("\n")
172
173 if dead > 0 {
174 b.WriteString(ui.Action("Compact it", "Compact") + "\n\n")
175 }
176
177 b.WriteString(md.H2("Why allocated minus live is not the answer"))
178 b.WriteString(ufmt.Sprintf("\nThis board has **%d** unused indices and **%d** reclaimable nodes. A dead element only becomes a reclaimable node once everything under it is dead too, so scattered holes free nothing while a dead tail frees a lot. That is why nobody can write down a rule for when to compact, and why the realm publishes the numbers instead of a schedule.\n\n", allocated-live, dead))
179
180 b.WriteString(md.H2("Board"))
181 b.WriteString("\n")
182 if live == 0 {
183 b.WriteString("Empty. " + ui.Action("Add the first entry", "Add", "text", "hello") + "\n\n")
184 } else {
185 rows := []string{}
186 for i := 0; i < allocated; i++ {
187 e, ok := entryAt(i)
188 if !ok {
189 continue
190 }
191 rows = append(rows, ufmt.Sprintf("`#%d` %s | by %s at height %d",
192 i, ui.Excerpt(strings.ReplaceAll(e.Text, "|", " "), 48), ui.Addr(e.Author), e.Added))
193 }
194 b.WriteString(md.BulletList(rows))
195 b.WriteString("\n")
196 }
197
198 b.WriteString(md.HorizontalRule())
199 b.WriteString("\nThe arithmetic is [p/moul/x/storagecost](/p/moul/x/storagecost/v1); the container is [p/moul/ulist](/p/moul/ulist/v1), whose `Compact` drops dead nodes without moving a live index. The byte figure is an exact node count times a measured per-node constant, which is why it is sounder than a payload-derived bounty, but it is still an estimate: the chain's `StorageUnlockEvent` is the settlement.\n")
200
201 return b.String()
202}
203
204// ratioSuffix adds the fragmentation percentage, and says nothing at all when
205// the board is empty rather than dividing by zero.
206func ratioSuffix(live, allocated int) string {
207 if allocated <= 0 || live == allocated {
208 return ""
209 }
210 return ufmt.Sprintf(", %d%% of indices are holes", (allocated-live)*100/allocated)
211}
212
213func verdict(q storagecost.Quote, dead int) string {
214 if dead == 0 {
215 return "nothing to reclaim, compacting would only burn gas"
216 }
217 if q.Worth() {
218 return "worth " + storagecost.FormatGNOT(q.Net)
219 }
220 return "not worth the gas yet"
221}
