-
Notifications
You must be signed in to change notification settings - Fork 177
/
snapshot_tree.go
75 lines (62 loc) · 1.61 KB
/
snapshot_tree.go
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
package snapshot
import (
"github.com/onflow/flow-go/model/flow"
)
const (
compactThreshold = 10
)
type UpdateLog []map[flow.RegisterID]flow.RegisterValue
// SnapshotTree is a simple LSM tree representation of the key/value storage
// at a given point in time.
type SnapshotTree struct {
base StorageSnapshot
compactedLog UpdateLog
}
// NewSnapshotTree returns a tree with keys/values initialized to the base
// storage snapshot.
func NewSnapshotTree(base StorageSnapshot) SnapshotTree {
return SnapshotTree{
base: base,
compactedLog: nil,
}
}
// Append returns a new tree with updates from the execution snapshot "applied"
// to the original original tree.
func (tree SnapshotTree) Append(
update *ExecutionSnapshot,
) SnapshotTree {
compactedLog := tree.compactedLog
if len(update.WriteSet) > 0 {
compactedLog = append(tree.compactedLog, update.WriteSet)
if len(compactedLog) > compactThreshold {
size := 0
for _, set := range compactedLog {
size += len(set)
}
mergedSet := make(map[flow.RegisterID]flow.RegisterValue, size)
for _, set := range compactedLog {
for id, value := range set {
mergedSet[id] = value
}
}
compactedLog = UpdateLog{mergedSet}
}
}
return SnapshotTree{
base: tree.base,
compactedLog: compactedLog,
}
}
// Get returns the register id's value.
func (tree SnapshotTree) Get(id flow.RegisterID) (flow.RegisterValue, error) {
for idx := len(tree.compactedLog) - 1; idx >= 0; idx-- {
value, ok := tree.compactedLog[idx][id]
if ok {
return value, nil
}
}
if tree.base != nil {
return tree.base.Get(id)
}
return nil, nil
}