Debian Codegraph @

storage/posix/antispam/badger.go

raw
1 // Copyright 2025 The Tessera authors. All Rights Reserved.
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 // http://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS IS" BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14
15 // Package badger provides a Tessera persistent antispam driver based on
16 // BadgerDB (https://github.com/hypermodeinc/badger), a high-performance
17 // pure-go DB with KV support.
18 package badger
19
20 import (
21 "context"
22 "encoding/binary"
23 "errors"
24 "fmt"
25 "iter"
26 "os"
27 "sync/atomic"
28 "time"
29
30 "github.com/dgraph-io/badger/v4"
31 "github.com/transparency-dev/tessera"
32 "github.com/transparency-dev/tessera/client"
33 "github.com/transparency-dev/tessera/internal/otel"
34 "k8s.io/klog/v2"
35 )
36
37 const (
38 DefaultMaxBatchSize = 1500
39 DefaultPushbackThreshold = 2048
40 )
41
42 var (
43 nextKey = []byte("@nextIdx")
44 )
45
46 // AntispamOpts allows configuration of some tunable options.
47 type AntispamOpts struct {
48 // MaxBatchSize is the largest number of mutations permitted in a single BatchWrite operation when
49 // updating the antispam index.
50 //
51 // Larger batches can enable (up to a point) higher throughput, but care should be taken not to
52 // overload the Spanner instance.
53 //
54 // During testing, we've found that 1500 appears to offer maximum throughput when using Spanner instances
55 // with 300 or more PU. Smaller deployments (e.g. 100 PU) will likely perform better with smaller batch
56 // sizes of around 64.
57 MaxBatchSize uint
58
59 // PushbackThreshold allows configuration of when to start responding to Add requests with pushback due to
60 // the antispam follower falling too far behind.
61 //
62 // When the antispam follower is at least this many entries behind the size of the locally integrated tree,
63 // the antispam decorator will return tessera.ErrPushback for every Add request.
64 PushbackThreshold uint
65 }
66
67 // NewAntispam returns an antispam driver which uses Badger to maintain a mapping between
68 // previously seen entries and their assigned indices.
69 //
70 // Note that the storage for this mapping is entirely separate and unconnected to the storage used for
71 // maintaining the Merkle tree.
72 //
73 // This functionality is experimental!
74 func NewAntispam(ctx context.Context, badgerPath string, opts AntispamOpts) (*AntispamStorage, error) {
75 if opts.MaxBatchSize == 0 {
76 opts.MaxBatchSize = DefaultMaxBatchSize
77 }
78 if opts.PushbackThreshold == 0 {
79 opts.PushbackThreshold = DefaultPushbackThreshold
80 }
81
82 // Open the Badger database located at badgerPath, it will be created if it doesn't exist.
83 db, err := badger.Open(badger.DefaultOptions(badgerPath))
84 if err != nil {
85 return nil, fmt.Errorf("failed to open badger: %v", err)
86 }
87
88 r := &AntispamStorage{
89 opts: opts,
90 db: db,
91 }
92
93 go func() {
94 ticker := time.NewTicker(1 * time.Minute)
95 defer ticker.Stop()
96 for {
97 select {
98 case <-ctx.Done():
99 return
100 case <-ticker.C:
101 }
102
103 again:
104 err := db.RunValueLogGC(0.7)
105 if err == nil {
106 goto again
107 }
108 }
109 }()
110
111 return r, nil
112 }
113
114 type AntispamStorage struct {
115 opts AntispamOpts
116
117 db *badger.DB
118
119 // pushBack is used to prevent the follower from getting too far underwater.
120 // Populate dynamically will set this to true/false based on how far behind the follower is from the
121 // currently integrated tree size.
122 // When pushBack is true, the decorator will start returning ErrPushback to all calls.
123 pushBack atomic.Bool
124
125 numLookups atomic.Uint64
126 numWrites atomic.Uint64
127 numHits atomic.Uint64
128 }
129
130 // index returns the index (if any) previously associated with the provided hash
131 func (d *AntispamStorage) index(ctx context.Context, h []byte) (*uint64, error) {
132 _, span := tracer.Start(ctx, "tessera.antispam.badger.index")
133 defer span.End()
134
135 d.numLookups.Add(1)
136 var idx *uint64
137 err := d.db.View(func(txn *badger.Txn) error {
138 item, err := txn.Get(h)
139 if err == badger.ErrKeyNotFound {
140 span.AddEvent("tessera.miss")
141 return nil
142 }
143 span.AddEvent("tessera.hit")
144 d.numHits.Add(1)
145
146 return item.Value(func(v []byte) error {
147 i := binary.BigEndian.Uint64(v)
148 idx = &i
149 return nil
150 })
151 })
152 return idx, err
153 }
154
155 // Decorator returns a function which will wrap an underlying Add delegate with
156 // code to dedup against the stored data.
157 func (d *AntispamStorage) Decorator() func(f tessera.AddFn) tessera.AddFn {
158 return func(delegate tessera.AddFn) tessera.AddFn {
159 return func(ctx context.Context, e *tessera.Entry) tessera.IndexFuture {
160 ctx, span := tracer.Start(ctx, "tessera.antispam.badger.Add")
161 defer span.End()
162
163 if d.pushBack.Load() {
164 span.AddEvent("tessera.pushback")
165 // The follower is too far behind the currently integrated tree, so we're going to push back against
166 // the incoming requests.
167 // This should have two effects:
168 // 1. The tree will cease growing, giving the follower a chance to catch up, and
169 // 2. We'll stop doing lookups for each submission, freeing up Spanner CPU to focus on catching up.
170 //
171 // We may decide in the future that serving duplicate reads is more important than catching up as quickly
172 // as possible, in which case we'd move this check down below the call to index.
173 return func() (tessera.Index, error) { return tessera.Index{}, tessera.ErrPushbackAntispam }
174 }
175 idx, err := d.index(ctx, e.Identity())
176 if err != nil {
177 return func() (tessera.Index, error) { return tessera.Index{}, err }
178 }
179 if idx != nil {
180 return func() (tessera.Index, error) { return tessera.Index{Index: *idx, IsDup: true}, nil }
181 }
182
183 return delegate(ctx, e)
184 }
185 }
186 }
187
188 // Follower returns a follower which knows how to populate the antispam index.
189 //
190 // This implements tessera.Antispam.
191 func (d *AntispamStorage) Follower(b func([]byte) ([][]byte, error)) tessera.Follower {
192 f := &follower{
193 as: d,
194 bundleHasher: b,
195 }
196
197 return f
198 }
199
200 // follower is a struct which knows how to populate the antispam storage with identity hashes
201 // for entries in a log.
202 type follower struct {
203 as *AntispamStorage
204
205 bundleHasher func([]byte) ([][]byte, error)
206 }
207
208 func (f *follower) Name() string {
209 return "Badger antispam"
210 }
211
212 // Follow uses entry data from the log to populate the antispam storage.
213 func (f *follower) Follow(ctx context.Context, lr tessera.LogReader) {
214 errOutOfSync := errors.New("out-of-sync")
215
216 t := time.NewTicker(time.Second)
217 var (
218 next func() (client.Entry[[]byte], error, bool)
219 stop func()
220
221 curEntries [][]byte
222 curIndex uint64
223 )
224 for {
225 select {
226 case <-ctx.Done():
227 return
228 case <-t.C:
229 }
230
231 // logSize is the latest known size of the log we're following.
232 // This will get initialised below, inside the loop.
233 var logSize uint64
234
235 // Busy loop while there's work to be done
236 for moreWork := true; moreWork; {
237 err := f.as.db.Update(func(txn *badger.Txn) error {
238 ctx, span := tracer.Start(ctx, "tessera.antispam.badger.FollowTxn")
239 defer span.End()
240
241 // Figure out the last entry we used to populate our antispam storage.
242 var followFrom uint64
243
244 switch row, err := txn.Get(nextKey); {
245 case errors.Is(err, badger.ErrKeyNotFound):
246 // Ignore this as we're probably just running for the first time on a new DB.
247 case err != nil:
248 return fmt.Errorf("failed to get nextIdx: %v", err)
249 default:
250 if err := row.Value(func(val []byte) error {
251 followFrom = binary.BigEndian.Uint64(val)
252 return nil
253 }); err != nil {
254 return fmt.Errorf("failed to get nextIdx value: %v", err)
255 }
256 }
257
258 span.SetAttributes(followFromKey.Int64(otel.Clamp64(followFrom)))
259
260 var err error
261 if followFrom >= logSize {
262 // Our view of the log is out of date, update it
263 logSize, err = lr.IntegratedSize(ctx)
264 if err != nil {
265 if errors.Is(err, os.ErrNotExist) {
266 // The log probably just hasn't completed its first integration yet, so break out of here
267 // and go back to sleep for a bit to avoid spamming errors into the log and scaring operators.
268 moreWork = false
269 return nil
270 }
271 return fmt.Errorf("populate: IntegratedSize(): %v", err)
272 }
273 switch {
274 case followFrom > logSize:
275 // Since we've got a stale view, there could be more work to do - loop and check without sleeping.
276 moreWork = true
277 return fmt.Errorf("followFrom %d > size %d", followFrom, logSize)
278 case followFrom == logSize:
279 // We're caught up, so unblock pushback and go back to sleep
280 moreWork = false
281 f.as.pushBack.Store(false)
282 return nil
283 default:
284 // size > followFrom, so there's more work to be done!
285 }
286 }
287
288 pushback := logSize-followFrom > uint64(f.as.opts.PushbackThreshold)
289 span.SetAttributes(pushbackKey.Bool(pushback))
290 f.as.pushBack.Store(pushback)
291
292 // If this is the first time around the loop we need to start the stream of entries now that we know where we want to
293 // start reading from:
294 if next == nil {
295 span.AddEvent("Start streaming entries")
296 sizeFn := func(_ context.Context) (uint64, error) {
297 return logSize, nil
298 }
299 numFetchers := uint(10)
300 next, stop = iter.Pull2(client.Entries(client.EntryBundles(ctx, numFetchers, sizeFn, lr.ReadEntryBundle, followFrom, logSize-followFrom), f.bundleHasher))
301 }
302
303 if curIndex == followFrom && curEntries != nil {
304 // Note that it's possible for Spanner to automatically retry transactions in some circumstances, when it does
305 // it'll call this function again.
306 // If the above condition holds, then we're in a retry situation and we must use the same data again rather
307 // than continue reading entries which will take us out of sync.
308 } else {
309 bs := uint64(f.as.opts.MaxBatchSize)
310 if r := logSize - followFrom; r < bs {
311 bs = r
312 }
313 batch := make([][]byte, 0, bs)
314 for i := range int(bs) {
315 e, err, ok := next()
316 if !ok {
317 // The entry stream has ended so we'll need to start a new stream next time around the loop:
318 next = nil
319 break
320 }
321 if err != nil {
322 return fmt.Errorf("entryReader.next: %v", err)
323 }
324 if wantIdx := followFrom + uint64(i); e.Index != wantIdx {
325 klog.Infof("at %d, expected %d - out of sync", e.Index, wantIdx)
326 // We're out of sync
327 return errOutOfSync
328 }
329 batch = append(batch, e.Entry)
330 }
331 curEntries = batch
332 curIndex = followFrom
333 }
334
335 // Now update the index.
336 {
337 for i, e := range curEntries {
338 if _, err := txn.Get(e); err == badger.ErrKeyNotFound {
339 b := make([]byte, 8)
340 binary.BigEndian.PutUint64(b, curIndex+uint64(i))
341 if err := txn.Set(e, b); err != nil {
342 return err
343 }
344 }
345 }
346 }
347
348 numAdded := uint64(len(curEntries))
349 f.as.numWrites.Add(numAdded)
350
351 // and update the follower state
352 b := make([]byte, 8)
353 binary.BigEndian.PutUint64(b, curIndex+numAdded)
354 if err := txn.Set(nextKey, b); err != nil {
355 return fmt.Errorf("failed to update follower state: %v", err)
356 }
357
358 return nil
359 })
360 if err != nil {
361 if err != errOutOfSync {
362 klog.Errorf("Failed to commit antispam population tx: %v", err)
363 }
364 stop()
365 next = nil
366 continue
367 }
368 curEntries = nil
369 }
370 }
371 }
372
373 // EntriesProcessed returns the total number of log entries processed.
374 func (f *follower) EntriesProcessed(ctx context.Context) (uint64, error) {
375 var nextIdx uint64
376 err := f.as.db.View(func(txn *badger.Txn) error {
377 switch item, err := txn.Get(nextKey); {
378 case errors.Is(err, badger.ErrKeyNotFound):
379 // Ignore this, we've just not done any following yet.
380 return nil
381 case err != nil:
382 return fmt.Errorf("failed to read nextKey: %v", err)
383 default:
384 return item.Value(func(val []byte) error {
385 nextIdx = binary.BigEndian.Uint64(val)
386 return nil
387 })
388 }
389 })
390
391 return nextIdx, err
392 }