Debian Codegraph @

storage/gcp/antispam/gcp.go

raw
1 // Copyright 2024 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 gcp contains a GCP-based antispam implementation for Tessera.
16 //
17 // A Spanner database provides a mechanism for maintaining an index of
18 // hash --> log position for detecting duplicate submissions.
19 package gcp
20
21 import (
22 "bytes"
23 "compress/gzip"
24 "context"
25 "encoding/base64"
26 "errors"
27 "fmt"
28 "io"
29 "iter"
30 "os"
31 "sync/atomic"
32 "time"
33
34 "cloud.google.com/go/spanner"
35 database "cloud.google.com/go/spanner/admin/database/apiv1"
36 adminpb "cloud.google.com/go/spanner/admin/database/apiv1/databasepb"
37 "cloud.google.com/go/spanner/apiv1/spannerpb"
38
39 "github.com/transparency-dev/tessera"
40 "github.com/transparency-dev/tessera/client"
41 "google.golang.org/grpc/codes"
42 "k8s.io/klog/v2"
43 )
44
45 const (
46 DefaultMaxBatchSize = 1500
47 DefaultPushbackThreshold = 2048
48 )
49
50 // AntispamOpts allows configuration of some tunable options.
51 type AntispamOpts struct {
52 // MaxBatchSize is the largest number of mutations permitted in a single BatchWrite operation when
53 // updating the antispam index.
54 //
55 // Larger batches can enable (up to a point) higher throughput, but care should be taken not to
56 // overload the Spanner instance.
57 //
58 // During testing, we've found that 1500 appears to offer maximum throughput when using Spanner instances
59 // with 300 or more PU. Smaller deployments (e.g. 100 PU) will likely perform better with smaller batch
60 // sizes of around 64.
61 MaxBatchSize uint
62
63 // PushbackThreshold allows configuration of when to start responding to Add requests with pushback due to
64 // the antispam follower falling too far behind.
65 //
66 // When the antispam follower is at least this many entries behind the size of the locally integrated tree,
67 // the antispam decorator will return a wrapped tessera.ErrPushback for every Add request.
68 PushbackThreshold uint
69 }
70
71 // NewAntispam returns an antispam driver which uses Spanner to maintain a mapping of
72 // previously seen entries and their assigned indices.
73 //
74 // Note that the storage for this mapping is entirely separate and unconnected to the storage used for
75 // maintaining the Merkle tree.
76 //
77 // This functionality is experimental!
78 func NewAntispam(ctx context.Context, spannerDB string, opts AntispamOpts) (*AntispamStorage, error) {
79 if opts.MaxBatchSize == 0 {
80 opts.MaxBatchSize = DefaultMaxBatchSize
81 }
82 if opts.PushbackThreshold == 0 {
83 opts.PushbackThreshold = DefaultPushbackThreshold
84 }
85 if err := createAndPrepareTables(
86 ctx, spannerDB,
87 []string{
88 "CREATE TABLE IF NOT EXISTS FollowCoord (id INT64 NOT NULL, nextIdx INT64 NOT NULL) PRIMARY KEY (id)",
89 "CREATE TABLE IF NOT EXISTS IDSeq (h BYTES(32) NOT NULL, idx INT64 NOT NULL) PRIMARY KEY (h)",
90 },
91 [][]*spanner.Mutation{
92 {spanner.Insert("FollowCoord", []string{"id", "nextIdx"}, []any{0, 0})},
93 },
94 ); err != nil {
95 return nil, fmt.Errorf("failed to create tables: %v", err)
96 }
97
98 db, err := spanner.NewClient(ctx, spannerDB)
99 if err != nil {
100 return nil, fmt.Errorf("failed to connect to Spanner: %v", err)
101 }
102
103 r := &AntispamStorage{
104 opts: opts,
105 dbPool: db,
106 }
107
108 return r, nil
109 }
110
111 type AntispamStorage struct {
112 opts AntispamOpts
113
114 dbPool *spanner.Client
115
116 // pushBack is used to prevent the follower from getting too far underwater.
117 // Populate dynamically will set this to true/false based on how far behind the follower is from the
118 // currently integrated tree size.
119 // When pushBack is true, the decorator will start returning a wrapped ErrPushback to all calls.
120 pushBack atomic.Bool
121
122 numLookups atomic.Uint64
123 numWrites atomic.Uint64
124 numHits atomic.Uint64
125 }
126
127 // index returns the index (if any) previously associated with the provided hash
128 func (d *AntispamStorage) index(ctx context.Context, h []byte) (*uint64, error) {
129 ctx, span := tracer.Start(ctx, "tessera.antispam.gcp.index")
130 defer span.End()
131
132 d.numLookups.Add(1)
133 var idx int64
134 if row, err := d.dbPool.Single().ReadRow(ctx, "IDSeq", spanner.Key{h}, []string{"idx"}); err != nil {
135 if c := spanner.ErrCode(err); c == codes.NotFound {
136 span.AddEvent("tessera.miss")
137 return nil, nil
138 }
139 return nil, err
140 } else {
141 if err := row.Column(0, &idx); err != nil {
142 return nil, fmt.Errorf("failed to read antispam index: %v", err)
143 }
144 idx := uint64(idx)
145 span.AddEvent("tessera.hit")
146 d.numHits.Add(1)
147 return &idx, nil
148 }
149 }
150
151 // Decorator returns a function which will wrap an underlying Add delegate with
152 // code to dedup against the stored data.
153 func (d *AntispamStorage) Decorator() func(f tessera.AddFn) tessera.AddFn {
154 return func(delegate tessera.AddFn) tessera.AddFn {
155 return func(ctx context.Context, e *tessera.Entry) tessera.IndexFuture {
156 ctx, span := tracer.Start(ctx, "tessera.antispam.gcp.Add")
157 defer span.End()
158
159 if d.pushBack.Load() {
160 span.AddEvent("tessera.pushback")
161 // The follower is too far behind the currently integrated tree, so we're going to push back against
162 // the incoming requests.
163 // This should have two effects:
164 // 1. The tree will cease growing, giving the follower a chance to catch up, and
165 // 2. We'll stop doing lookups for each submission, freeing up Spanner CPU to focus on catching up.
166 //
167 // We may decide in the future that serving duplicate reads is more important than catching up as quickly
168 // as possible, in which case we'd move this check down below the call to index.
169 return func() (tessera.Index, error) { return tessera.Index{}, tessera.ErrPushbackAntispam }
170 }
171 idx, err := d.index(ctx, e.Identity())
172 if err != nil {
173 return func() (tessera.Index, error) { return tessera.Index{}, err }
174 }
175 if idx != nil {
176 return func() (tessera.Index, error) { return tessera.Index{Index: *idx, IsDup: true}, nil }
177 }
178
179 return delegate(ctx, e)
180 }
181 }
182 }
183
184 // Follower returns a follower which knows how to populate the antispam index.
185 //
186 // This implements tessera.Antispam.
187 func (d *AntispamStorage) Follower(b func([]byte) ([][]byte, error)) tessera.Follower {
188 f := &follower{
189 as: d,
190 bundleHasher: b,
191 }
192 // Use the "normal" BatchWrite mechanism to update the antispam index.
193 // This will be overriden by the test to use an "inline" mechanism since spannertest
194 // does not support BatchWrite :(
195 f.updateIndex = f.batchUpdateIndex
196
197 if r := os.Getenv("SPANNER_EMULATOR_HOST"); r != "" {
198 const warn = `H4sIAAAAAAAAA83VwRGAIAwEwH+qoFwrsEAr8eEDPZO7gxkcGV6G7IAJ2tr8iDp07Fs6J7BnImcK5J3EmHVIT2Dvp2YTVJMu/y1+X+jiFQ84LtK9mLHr0aqh+K15PwkWRDaPrcbU5WdMKILtCDMF5hSgQEdJlw/36D7eRYqPfsVNVBcMsNH2QQKq/p957Yr8RfWIE22t7L7ABwAA`
199 r, _ := base64.StdEncoding.DecodeString(warn)
200 gzr, _ := gzip.NewReader(bytes.NewReader([]byte(r)))
201 w, _ := io.ReadAll(gzr)
202 klog.Warningf("%s\nWarning: you're running under the Spanner emulator - this is not a supported environment!\n\n", string(w))
203
204 // Hack in a workaround for spannertest not supporting BatchWrites
205 f.updateIndex = emulatorWorkaroundUpdateIndexTx
206 }
207
208 return f
209 }
210
211 // follower is a struct which knows how to populate the antispam storage with identity hashes
212 // for entries in a log.
213 type follower struct {
214 as *AntispamStorage
215
216 // updateIndex knows how to apply the provided slice of mutations to the underlying Spanner DB.
217 //
218 // In normal operation this simply points to the batchUpdateIndex func below, but spannertest
219 // does not support either:
220 // - BatchWrite operations, or
221 // - nested transactions
222 // so we use this member as a hook to fallback to
223 // a regular transaction for tests.
224 updateIndex func(context.Context, *spanner.ReadWriteTransaction, []*spanner.Mutation) error
225
226 bundleHasher func([]byte) ([][]byte, error)
227 }
228
229 func (f *follower) Name() string {
230 return "GCP antispam"
231 }
232
233 // Follow uses entry data from the log to populate the antispam storage.
234 func (f *follower) Follow(ctx context.Context, lr tessera.LogReader) {
235 errOutOfSync := errors.New("out-of-sync")
236
237 t := time.NewTicker(time.Second)
238 var (
239 next func() (client.Entry[[]byte], error, bool)
240 stop func()
241
242 curEntries [][]byte
243 curIndex uint64
244 )
245 for {
246 select {
247 case <-ctx.Done():
248 return
249 case <-t.C:
250 }
251
252 // logSize is the latest known size of the log we're following.
253 // This will get initialised below, inside the loop.
254 var logSize uint64
255
256 // Busy loop while there are entries to be consumed from the stream
257 for streamDone := false; !streamDone; {
258 _, err := f.as.dbPool.ReadWriteTransaction(ctx, func(txctx context.Context, txn *spanner.ReadWriteTransaction) error {
259 txctx, span := tracer.Start(txctx, "tessera.antispam.gcp.FollowTxn")
260 defer span.End()
261
262 // Figure out the last entry we used to populate our antispam storage.
263 row, err := txn.ReadRowWithOptions(txctx, "FollowCoord", spanner.Key{0}, []string{"nextIdx"}, &spanner.ReadOptions{LockHint: spannerpb.ReadRequest_LOCK_HINT_EXCLUSIVE})
264 if err != nil {
265 return err
266 }
267
268 var nextIdx int64 // Spanner doesn't support uint64
269 if err := row.Columns(&nextIdx); err != nil {
270 return fmt.Errorf("failed to read follow coordination info: %v", err)
271 }
272 span.SetAttributes(followFromKey.Int64(nextIdx))
273
274 followFrom := uint64(nextIdx)
275 if followFrom >= logSize {
276 // Our view of the log is out of date, update it.
277 // We use ctx here because Cloud Spanner doesn't support nested transactions.
278 // This is okay because we're only reading the log size, not modifying anything.
279 logSize, err = lr.IntegratedSize(ctx)
280 if err != nil {
281 streamDone = true
282 return fmt.Errorf("populate: IntegratedSize(): %v", err)
283 }
284 switch {
285 case followFrom > logSize:
286 streamDone = true
287 return fmt.Errorf("followFrom %d > size %d", followFrom, logSize)
288 case followFrom == logSize:
289 // We're caught up, so unblock pushback and go back to sleep
290 streamDone = true
291 f.as.pushBack.Store(false)
292 return nil
293 default:
294 // size > followFrom, so there's more work to be done!
295 }
296 }
297
298 pushback := logSize-followFrom > uint64(f.as.opts.PushbackThreshold)
299 span.SetAttributes(pushbackKey.Bool(pushback))
300 f.as.pushBack.Store(pushback)
301
302 // 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
303 // start reading from:
304 if next == nil {
305 span.AddEvent("Start streaming entries")
306 sizeFn := func(_ context.Context) (uint64, error) {
307 return logSize, nil
308 }
309 numFetchers := uint(10)
310 next, stop = iter.Pull2(client.Entries(client.EntryBundles(txctx, numFetchers, sizeFn, lr.ReadEntryBundle, followFrom, logSize-followFrom), f.bundleHasher))
311 }
312
313 if curIndex == followFrom && curEntries != nil {
314 // Note that it's possible for Spanner to automatically retry transactions in some circumstances, when it does
315 // it'll call this function again.
316 // If the above condition holds, then we're in a retry situation and we must use the same data again rather
317 // than continue reading entries which will take us out of sync.
318 } else {
319 bs := uint64(f.as.opts.MaxBatchSize)
320 if r := logSize - followFrom; r < bs {
321 bs = r
322 }
323 batch := make([][]byte, 0, bs)
324 for i := range int(bs) {
325 e, err, ok := next()
326 if !ok {
327 // The entry stream has ended so we'll need to start a new stream next time around the loop:
328 stop()
329 next = nil
330 break
331 }
332 if err != nil {
333 return fmt.Errorf("entryReader.next: %v", err)
334 }
335 if wantIdx := followFrom + uint64(i); e.Index != wantIdx {
336 // We're out of sync
337 return errOutOfSync
338 }
339 batch = append(batch, e.Entry)
340 }
341 curEntries = batch
342 curIndex = followFrom
343 }
344
345 if len(curEntries) == 0 {
346 return nil
347 }
348
349 // Now update the index.
350 {
351 ms := make([]*spanner.Mutation, 0, len(curEntries))
352 for i, e := range curEntries {
353 ms = append(ms, spanner.Insert("IDSeq", []string{"h", "idx"}, []any{e, int64(curIndex + uint64(i))}))
354 }
355 if err := f.updateIndex(txctx, txn, ms); err != nil {
356 return err
357 }
358 }
359
360 numAdded := uint64(len(curEntries))
361 f.as.numWrites.Add(numAdded)
362
363 // Insertion of dupe entries was successful, so update our follow coordination row:
364 m := make([]*spanner.Mutation, 0)
365 m = append(m, spanner.Update("FollowCoord", []string{"id", "nextIdx"}, []any{0, int64(followFrom + numAdded)}))
366
367 return txn.BufferWrite(m)
368 })
369 if err != nil {
370 if err != errOutOfSync {
371 klog.Errorf("Failed to commit antispam population tx: %v", err)
372 }
373 stop()
374 next = nil
375 streamDone = true
376 continue
377 }
378 curEntries = nil
379 }
380 }
381 }
382
383 // batchUpdateIndex applies the provided mutations using Spanner's BatchWrite support.
384 //
385 // Note that we _do not_ use the passed in txn here - we're writing the antispam entries outside of the transaction.
386 // The reason is because we absolutely do not want the larger transaction to fail if there's already an entry for the
387 // same hash in the IDSeq table - this would cause us to get stuck retrying forever, so we use BatchWrite and ignore
388 // any AlreadyExists errors we encounter.
389 //
390 // It looks unusual, but is ok because:
391 // - individual antispam entries failing to insert because there's already an entry for that hash is perfectly ok,
392 // - we'll only continue on to update FollowCoord if no errors (other than AlreadyExists) occur while inserting entries,
393 // - similarly, if we manage to insert antispam entries here, but then fail to update FollowCoord, we'll end up
394 // retrying over the same set of log entries, and then ignoring the AlreadyExists which will occur.
395 //
396 // Alternative approaches are:
397 // - Use InsertOrUpdate, but that will keep updating the index associated with the ID hash, and we'd rather keep serving
398 // the earliest index known for that entry.
399 // - Perform reads for each of the hashes we're about to write, and use that to filter writes.
400 // This would work, but would also incur an extra round-trip of data which isn't really necessary but would
401 // slow the process down considerably and add extra load to Spanner for no benefit.
402 func (f *follower) batchUpdateIndex(ctx context.Context, _ *spanner.ReadWriteTransaction, ms []*spanner.Mutation) error {
403 ctx, span := tracer.Start(ctx, "tessera.antispam.gcp.batchUpdateIndex")
404 defer span.End()
405
406 mgs := make([]*spanner.MutationGroup, 0, len(ms))
407 for _, m := range ms {
408 mgs = append(mgs, &spanner.MutationGroup{
409 Mutations: []*spanner.Mutation{m},
410 })
411 }
412
413 i := f.as.dbPool.BatchWrite(ctx, mgs)
414 return i.Do(func(r *spannerpb.BatchWriteResponse) error {
415 s := r.GetStatus()
416 if c := codes.Code(s.Code); c != codes.OK && c != codes.AlreadyExists {
417 return fmt.Errorf("failed to write antispam record: %v (%v)", s.GetMessage(), c)
418 }
419 return nil
420 })
421 }
422
423 // EntriesProcessed returns the total number of log entries processed.
424 func (f *follower) EntriesProcessed(ctx context.Context) (uint64, error) {
425 row, err := f.as.dbPool.Single().ReadRow(ctx, "FollowCoord", spanner.Key{0}, []string{"nextIdx"})
426 if err != nil {
427 return 0, err
428 }
429
430 var nextIdx int64 // Spanner doesn't support uint64
431 if err := row.Columns(&nextIdx); err != nil {
432 return 0, fmt.Errorf("failed to read follow coordination info: %v", err)
433 }
434 return uint64(nextIdx), nil
435 }
436
437 // createAndPrepareTables applies the passed in list of DDL statements and groups of mutations.
438 //
439 // This is intended to be used to create and initialise Spanner instances on first use.
440 // DDL should likely be of the form "CREATE TABLE IF NOT EXISTS".
441 // Mutation groups should likey be one or more spanner.Insert operations - AlreadyExists errors will be silently ignored.
442 func createAndPrepareTables(ctx context.Context, spannerDB string, ddl []string, mutations [][]*spanner.Mutation) error {
443 adminClient, err := database.NewDatabaseAdminClient(ctx)
444 if err != nil {
445 return err
446 }
447 defer func() {
448 if err := adminClient.Close(); err != nil {
449 klog.Warningf("adminClient.Close(): %v", err)
450 }
451 }()
452
453 op, err := adminClient.UpdateDatabaseDdl(ctx, &adminpb.UpdateDatabaseDdlRequest{
454 Database: spannerDB,
455 Statements: ddl,
456 })
457 if err != nil {
458 return fmt.Errorf("failed to create tables: %v", err)
459 }
460 if err := op.Wait(ctx); err != nil {
461 return err
462 }
463
464 dbPool, err := spanner.NewClient(ctx, spannerDB)
465 if err != nil {
466 return fmt.Errorf("failed to connect to Spanner: %v", err)
467 }
468 defer dbPool.Close()
469
470 // Set default values for a newly initialised schema using passed in mutation groups.
471 // Note that this will only succeed if no row exists, so there's no danger of "resetting" an existing log.
472 for _, mg := range mutations {
473 if _, err := dbPool.Apply(ctx, mg); err != nil && spanner.ErrCode(err) != codes.AlreadyExists {
474 return err
475 }
476 }
477 return nil
478 }
479
480 // emulatorWorkaroundUpdateIndexTx is a workaround for spannertest not supporting BatchWrites.
481 // We use this func as a replacement for follower's updateIndex hook, and simply commit the index
482 // updates inline with the larger transaction.
483 func emulatorWorkaroundUpdateIndexTx(_ context.Context, txn *spanner.ReadWriteTransaction, ms []*spanner.Mutation) error {
484 return txn.BufferWrite(ms)
485 }