arbo/addbatch.go
addbatch.goRaw
1package arbo
2
3import (
4 "bytes"
5 "fmt"
6 "sort"
7)
8
9/*
10
11AddBatch design
12===============
13
14
15CASE A: Empty Tree --> if tree is empty (root==0)
16=================================================
17- Build the full tree from bottom to top (from all the leaf to the root)
18
19
20CASE B: ALMOST CASE A, Almost empty Tree --> if Tree has numLeafs < minLeafsThreshold
21==============================================================================
22- Get the Leafs (key & value) (iterate the tree from the current root getting
23the leafs)
24- Create a new empty Tree
25- Do CASE A for the new Tree, giving the already existing key&values (leafs)
26from the original Tree + the new key&values to be added from the AddBatch call
27
28 R
29 / \
30 A *
31 / \
32 B C
33
34
35CASE C: ALMOST CASE B --> if Tree has few Leafs (but numLeafs>=minLeafsThreshold)
36==============================================================================
37- Use A, B, G, F as Roots of subtrees
38- Do CASE B for each subtree
39- Then go from L to the Root
40
41 R
42 / \
43 / \
44 / \
45 * *
46 / | / \
47 / | / \
48 / | / \
49L: A B G D
50 / \
51 / \
52 / \
53 C *
54 / \
55 / \
56 / \
57 D E
58
59
60
61CASE D: Already populated Tree
62==============================
63- Use A, B, C, D as subtree
64- Sort the Keys in Buckets that share the initial part of the path
65- For each subtree add there the new leafs
66
67 R
68 / \
69 / \
70 / \
71 * *
72 / | / \
73 / | / \
74 / | / \
75L: A B C D
76 /\ /\ / \ / \
77 ... ... ... ... ... ...
78
79
80CASE E: Already populated Tree Unbalanced
81=========================================
82- Need to fill M1 and M2, and then will be able to use CASE D
83 - Search for M1 & M2 in the inputed Keys
84 - Add M1 & M2 to the Tree
85 - From here can use CASE D
86
87 R
88 / \
89 / \
90 / \
91 * *
92 | \
93 | \
94 | \
95L: M1 * M2 * (where M1 and M2 are empty)
96 / | /
97 / | /
98 / | /
99 A * *
100 / \ | \
101 / \ | \
102 / \ | \
103 B * * C
104 / \ |\
105 ... ... | \
106 | \
107 D E
108
109
110
111Algorithm decision
112==================
113- if nLeafs==0 (root==0): CASE A
114- if nLeafs<minLeafsThreshold: CASE B
115- if nLeafs>=minLeafsThreshold && (nLeafs/nBuckets) < minLeafsThreshold: CASE C
116- else: CASE D & CASE E
117
118
119- Multiple tree.Add calls: O(n log n)
120 - Used in: cases A, B, C
121- Tree from bottom to top: O(log n)
122 - Used in: cases D, E
123
124*/
125
126// AddBatchOpt is the WIP implementation of the AddBatch method in a more
127// optimized approach.
128func (t *Tree) AddBatchOpt(keys, values [][]byte) ([]int, error) {
129 t.updateAccessTime()
130 t.Lock()
131 defer t.Unlock()
132
133 // TODO if len(keys) is not a power of 2, add padding of empty
134 // keys&values. Maybe when len(keyvalues) is not a power of 2, cut at
135 // the biggest power of 2 under the len(keys), add those 2**n key-values
136 // using the AddBatch approach, and then add the remaining key-values
137 // using tree.Add.
138
139 kvs, err := t.keysValuesToKvs(keys, values)
140 if err != nil {
141 return nil, err
142 }
143
144 t.tx, err = t.db.NewTx()
145 if err != nil {
146 return nil, err
147 }
148
149 // if nLeafs==0 (root==0): CASE A
150 if bytes.Equal(t.root, t.emptyHash) {
151 // sort keys & values by path
152 sortKvs(kvs)
153 return t.buildTreeBottomUp(kvs)
154 }
155
156 // if nLeafs<nBuckets: CASE B
157 nLeafs, err := t.GetNLeafs()
158 if err != nil {
159 return nil, err
160 }
161 minLeafsThreshold := uint64(100) // nolint:gomnd // TMP WIP
162 if nLeafs < minLeafsThreshold {
163 // get already existing keys
164 aKs, aVs, err := t.getLeafs()
165 if err != nil {
166 return nil, err
167 }
168 aKvs, err := t.keysValuesToKvs(aKs, aVs)
169 if err != nil {
170 return nil, err
171 }
172 // add already existing key-values to the inputted key-values
173 kvs = append(kvs, aKvs...)
174 // proceed with CASE A
175 sortKvs(kvs)
176 return t.buildTreeBottomUp(kvs)
177 }
178
179 return nil, fmt.Errorf("UNIMPLEMENTED")
180}
181
182type kv struct {
183 pos int // original position in the array
184 keyPath []byte
185 k []byte
186 v []byte
187}
188
189// compareBytes compares byte slices where the bytes are compared from left to
190// right and each byte is compared by bit from right to left
191func compareBytes(a, b []byte) bool {
192 // WIP
193 for i := 0; i < len(a); i++ {
194 for j := 0; j < 8; j++ {
195 aBit := a[i] & (1 << j)
196 bBit := b[i] & (1 << j)
197 if aBit > bBit {
198 return false
199 } else if aBit < bBit {
200 return true
201 }
202 }
203 }
204 return false
205}
206
207// sortKvs sorts the kv by path
208func sortKvs(kvs []kv) {
209 sort.Slice(kvs, func(i, j int) bool {
210 return compareBytes(kvs[i].keyPath, kvs[j].keyPath)
211 })
212}
213
214func (t *Tree) keysValuesToKvs(ks, vs [][]byte) ([]kv, error) {
215 if len(ks) != len(vs) {
216 return nil, fmt.Errorf("len(keys)!=len(values) (%d!=%d)",
217 len(ks), len(vs))
218 }
219 kvs := make([]kv, len(ks))
220 for i := 0; i < len(ks); i++ {
221 keyPath := make([]byte, t.hashFunction.Len())
222 copy(keyPath[:], ks[i])
223 kvs[i].pos = i
224 kvs[i].keyPath = ks[i]
225 kvs[i].k = ks[i]
226 kvs[i].v = vs[i]
227 }
228
229 return kvs, nil
230}
231
232/*
233func (t *Tree) kvsToKeysValues(kvs []kv) ([][]byte, [][]byte) {
234 ks := make([][]byte, len(kvs))
235 vs := make([][]byte, len(kvs))
236 for i := 0; i < len(kvs); i++ {
237 ks[i] = kvs[i].k
238 vs[i] = kvs[i].v
239 }
240 return ks, vs
241}
242*/
243
244// keys & values must be sorted by path, and must be length multiple of 2
245// TODO return index of failed keyvaules
246func (t *Tree) buildTreeBottomUp(kvs []kv) ([]int, error) {
247 // build the leafs
248 leafKeys := make([][]byte, len(kvs))
249 for i := 0; i < len(kvs); i++ {
250 // TODO handle the case where Key&Value == 0
251 leafKey, leafValue, err := newLeafValue(t.hashFunction, kvs[i].k, kvs[i].v)
252 if err != nil {
253 return nil, err
254 }
255 // store leafKey & leafValue to db
256 if err := t.tx.Put(leafKey, leafValue); err != nil {
257 return nil, err
258 }
259 leafKeys[i] = leafKey
260 }
261 r, err := t.upFromKeys(leafKeys)
262 if err != nil {
263 return nil, err
264 }
265 t.root = r
266 return nil, nil
267}
268
269func (t *Tree) upFromKeys(ks [][]byte) ([]byte, error) {
270 if len(ks) == 1 {
271 return ks[0], nil
272 }
273
274 var rKs [][]byte
275 for i := 0; i < len(ks); i += 2 {
276 // TODO handle the case where Key&Value == 0
277 k, v, err := newIntermediate(t.hashFunction, ks[i], ks[i+1])
278 if err != nil {
279 return nil, err
280 }
281 // store k-v to db
282 if err = t.tx.Put(k, v); err != nil {
283 return nil, err
284 }
285 rKs = append(rKs, k)
286 }
287 return t.upFromKeys(rKs)
288}
289
290func (t *Tree) getLeafs() ([][]byte, [][]byte, error) {
291 var ks, vs [][]byte
292 err := t.Iterate(func(k, v []byte) {
293 if v[0] != PrefixValueLeaf {
294 return
295 }
296 leafK, leafV := readLeafValue(v)
297 ks = append(ks, leafK)
298 vs = append(vs, leafV)
299 })
300 return ks, vs, err
301}