Spaces:
Running
Running
File size: 3,386 Bytes
b110593 |
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 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 |
// _ _
// __ _____ __ ___ ___ __ _| |_ ___
// \ \ /\ / / _ \/ _` \ \ / / |/ _` | __/ _ \
// \ V V / __/ (_| |\ V /| | (_| | || __/
// \_/\_/ \___|\__,_| \_/ |_|\__,_|\__\___|
//
// Copyright © 2016 - 2024 Weaviate B.V. All rights reserved.
//
// CONTACT: [email protected]
//
package lsmkv
import (
"crypto/rand"
"testing"
"github.com/google/uuid"
"github.com/stretchr/testify/require"
)
// This test asserts that the *binarySearchTree.insert
// method properly calculates the net additions of a
// new node into the tree
func TestInsertNetAdditions_Replace(t *testing.T) {
t.Run("single node entry", func(t *testing.T) {
tree := &binarySearchTree{}
key := make([]byte, 8)
val := make([]byte, 8)
rand.Read(key)
rand.Read(val)
n, _ := tree.insert(key, val, nil)
require.Equal(t, len(key)+len(val), n)
})
t.Run("multiple unique node entries", func(t *testing.T) {
tree := &binarySearchTree{}
amount := 100
size := 8
var n int
for i := 0; i < amount; i++ {
key := make([]byte, size)
val := make([]byte, size)
rand.Read(key)
rand.Read(val)
newAdditions, _ := tree.insert(key, val, nil)
n += newAdditions
}
require.Equal(t, amount*size*2, n)
})
t.Run("multiple non-unique node entries", func(t *testing.T) {
tree := &binarySearchTree{}
var (
amount = 100
keySize = 100
origValSize = 100
newValSize = origValSize * 100
keys = make([][]byte, amount)
vals = make([][]byte, amount)
netAdditions int
)
// write the keys and original values
for i := range keys {
key := make([]byte, keySize)
rand.Read(key)
val := make([]byte, origValSize)
rand.Read(val)
keys[i], vals[i] = key, val
}
// make initial inserts
for i := range keys {
currentNetAddition, _ := tree.insert(keys[i], vals[i], nil)
netAdditions += currentNetAddition
}
// change the values of the existing keys
// with new values of different length
for i := 0; i < amount; i++ {
val := make([]byte, newValSize)
rand.Read(val)
vals[i] = val
}
for i := 0; i < amount; i++ {
currentNetAddition, _ := tree.insert(keys[i], vals[i], nil)
netAdditions += currentNetAddition
}
// Formulas for calculating the total net additions after
// updating the keys with differently sized values
expectedFirstNetAdd := amount * (keySize + origValSize)
expectedSecondNetAdd := (amount * (keySize + newValSize)) - (amount * keySize) - (amount * origValSize)
expectedNetAdditions := expectedFirstNetAdd + expectedSecondNetAdd
require.Equal(t, expectedNetAdditions, netAdditions)
})
// test to assure multiple tombstone nodes are not created when same value is added and deleted multiple times
// https://semi-technology.atlassian.net/browse/WEAVIATE-31
t.Run("consecutive adding and deleting value does not multiply nodes", func(t *testing.T) {
tree := &binarySearchTree{}
key := []byte(uuid.New().String())
value := make([]byte, 100)
rand.Read(value)
for i := 0; i < 10; i++ {
tree.insert(key, value, nil)
tree.setTombstone(key, nil)
}
flat := tree.flattenInOrder()
require.Equal(t, 1, len(flat))
require.True(t, flat[0].tombstone)
})
}
|