← Watch feed
treap, ffldb: change Put() to take in multiple key-value pairs
Public commit record
85/100 · Strong
What the developer wrote
Authored by Calvin Kim
treap, ffldb: change Put() to take in multiple key-value pairs
Previously, the Put() function took in a single key-value pair,
resulting in memory allocation overhead as the intermediary treapNodes
got allocated and immediately garbage collected, resulting in
performance loss due to the garbage collection overhead.
We're able to recycle the intermediary treapNodes allocated by taking in
multiple key-value pairs. This results in better performance of the
node especially during UTXO cache flushes.
✓ Specific, descriptive subject✓ Names a concrete action or component✓ Provides detailed explanatory context✓ Explains rationale or failure mode
What changed, and why it matters
This commit is a performance optimization, not a security fix. It changes the database cache's treap (a type of search tree) so that it can insert many key-value pairs in one batch instead of one at a time. The goal is to reduce memory allocation and garbage collection overhead when flushing the UTXO cache. There is no indication in the commit message or diff that this fixes a security vulnerability.
Recommended action
No security action required. Treat as a normal performance refactor; standard code review and regression testing are sufficient.
Security signals we found
01
No security-relevant signals detected in commit message or diff.
02
Change is purely an API/performance refactor.
03
No new imports, no cryptographic changes, no authorization or network code.
Evidence from the diff
The patch refactors Immutable.Put() in database/internal/treap/immutable.go to accept a variadic slice of KVPair structs rather than a single key/value pair. It then recycles intermediate treapNode allocations across the batch via a sync.Pool-like treapNodePool. Callers in database/ffldb/dbcache.go (commitTx) are updated to accumulate pending keys/removals into slices and call Put once per batch. Tests are updated to use the new variadic API. No bounds-checking, input-validation, or cryptographic logic changes are introduced; the functional behavior of the treap is unchanged.
Changed components
database/internal/treap/immutable.godatabase/ffldb/dbcache.godatabase/internal/treap/immutable_test.godatabase/internal/treap/treapiter_test.goInspect captured patch +210 / −86
diff --git a/database/ffldb/dbcache.go b/database/ffldb/dbcache.go
index 7e6a44d..9fe7d4d 100644
--- a/database/ffldb/dbcache.go
+++ b/database/ffldb/dbcache.go
@@ -611,19 +611,25 @@ func (c *dbCache) commitTx(tx *transaction) error {
c.cacheLock.RUnlock()
// Apply every key to add in the database transaction to the cache.
+ pendingKVs := make([]treap.KVPair, 0, tx.pendingKeys.Len())
tx.pendingKeys.ForEach(func(k, v []byte) bool {
+ pendingKVs = append(pendingKVs, treap.KVPair{Key: k, Value: v})
+
newCachedRemove = newCachedRemove.Delete(k)
- newCachedKeys = newCachedKeys.Put(k, v)
return true
})
+ newCachedKeys = newCachedKeys.Put(pendingKVs...)
tx.pendingKeys = nil
// Apply every key to remove in the database transaction to the cache.
+ pendingRemoveKVs := make([]treap.KVPair, 0, tx.pendingRemove.Len())
tx.pendingRemove.ForEach(func(k, v []byte) bool {
+ pendingRemoveKVs = append(pendingRemoveKVs, treap.KVPair{Key: k, Value: v})
+
newCachedKeys = newCachedKeys.Delete(k)
- newCachedRemove = newCachedRemove.Put(k, nil)
return true
})
+ newCachedRemove = newCachedRemove.Put(pendingRemoveKVs...)
tx.pendingRemove = nil
// Atomically replace the immutable treaps which hold the cached keys to
diff --git a/database/internal/treap/immutable.go b/database/internal/treap/immutable.go
index 84ad60b..142f4b0 100644
--- a/database/internal/treap/immutable.go
+++ b/database/internal/treap/immutable.go
@@ -105,10 +105,52 @@ func (t *Immutable) Get(key []byte) []byte {
return nil
}
-// Put inserts the passed key/value pair.
-func (t *Immutable) Put(key, value []byte) *Immutable {
- immutable, _ := t.put(key, value)
- return immutable
+// KVPair is just a helper struct for a key-value pair that's going to be
+// inserted into the treap.
+type KVPair struct {
+ Key []byte
+ Value []byte
+}
+
+// Put puts the passed in key/value pairs into the treap. For operations
+// requiring many insertions at once, Put is memory efficient as the
+// intermediary treap nodes created between each put operation is recycled
+// through an internal sync.Pool, reducing overall memory allocation.
+func (t *Immutable) Put(kvPairs ...KVPair) *Immutable {
+ treap := t
+ var prevTreapNodes [staticDepth]*treapNode
+
+ for _, kvPair := range kvPairs {
+ newTreap, newTreapNodes := treap.put(kvPair.Key, kvPair.Value)
+
+ // Loop through the prevTreapNodes and check for treapNodes that
+ // are no longer being utilized. These will be garbaged collected
+ // and they're better off being recycled in the treapNodePool.
+ for _, node := range prevTreapNodes {
+ if node == nil {
+ break
+ }
+
+ // Make sure that the node we're going to recycle isn't
+ // being used by the latest immutable treap by checking
+ // if the pointer value of the node is the same.
+ got := newTreap.get(node.key)
+ if got == node {
+ continue
+ }
+
+ // This node is only being used by the previous immutable
+ // copy and can safely be put into the treapNodePool to be
+ // recycled.
+ node.recycle()
+ }
+
+ // Replace with the latest treap and treap nodes.
+ treap = newTreap
+ prevTreapNodes = newTreapNodes
+ }
+
+ return treap
}
// put inserts the passed key/value pair and returns all the newly created
diff --git a/database/internal/treap/immutable_test.go b/database/internal/treap/immutable_test.go
index e0a1cb4..950974e 100644
--- a/database/internal/treap/immutable_test.go
+++ b/database/internal/treap/immutable_test.go
@@ -61,31 +61,43 @@ func TestImmutableSequential(t *testing.T) {
// functions work as expected.
expectedSize := uint64(0)
numItems := 1000
+ keyCount := 100
testTreap := NewImmutable()
- for i := 0; i < numItems; i++ {
- key := serializeUint32(uint32(i))
- testTreap = testTreap.Put(key, key)
+ for i := 0; i < numItems/keyCount; i++ {
+ keys := make([][]byte, 0, keyCount)
+ kvPairs := make([]KVPair, 0, keyCount)
+ for j := 0; j < keyCount; j++ {
+ n := i*keyCount + j
+ key := serializeUint32(uint32(n))
+ keys = append(keys, key)
+ kvPairs = append(kvPairs, KVPair{key, key})
+ }
+
+ testTreap = testTreap.Put(kvPairs...)
// Ensure the treap length is the expected value.
- if gotLen := testTreap.Len(); gotLen != i+1 {
+ if gotLen := testTreap.Len(); gotLen != (i+1)*keyCount {
t.Fatalf("Len #%d: unexpected length - got %d, want %d",
i, gotLen, i+1)
}
- // Ensure the treap has the key.
- if !testTreap.Has(key) {
- t.Fatalf("Has #%d: key %q is not in treap", i, key)
- }
+ for j, key := range keys {
+ // Ensure the treap has the key.
+ if !testTreap.Has(key) {
+ t.Fatalf("Has #%d#%d: key %q is not in treap", i, j, key)
+ }
- // Get the key from the treap and ensure it is the expected
- // value.
- if gotVal := testTreap.Get(key); !bytes.Equal(gotVal, key) {
- t.Fatalf("Get #%d: unexpected value - got %x, want %x",
- i, gotVal, key)
+ // Get the key from the treap and ensure it is the expected
+ // value.
+ if gotVal := testTreap.Get(key); !bytes.Equal(gotVal, key) {
+ t.Fatalf("Get #%d#%d: unexpected value - got %x, want %x",
+ i, j, gotVal, key)
+ }
+
+ expectedSize += (nodeFieldsSize + 8)
}
// Ensure the expected size is reported.
- expectedSize += (nodeFieldsSize + 8)
if gotSize := testTreap.Size(); gotSize != expectedSize {
t.Fatalf("Size #%d: unexpected byte size - got %d, "+
"want %d", i, gotSize, expectedSize)
@@ -161,31 +173,43 @@ func TestImmutableReverseSequential(t *testing.T) {
// functions work as expected.
expectedSize := uint64(0)
numItems := 1000
+ keyCount := 100
testTreap := NewImmutable()
- for i := 0; i < numItems; i++ {
- key := serializeUint32(uint32(numItems - i - 1))
- testTreap = testTreap.Put(key, key)
+ for i := 0; i < numItems/keyCount; i++ {
+ keys := make([][]byte, 0, keyCount)
+ kvPairs := make([]KVPair, 0, keyCount)
+ for j := 0; j < keyCount; j++ {
+ n := numItems - (i * keyCount) - j - 1
+ key := serializeUint32(uint32(n))
+ keys = append(keys, key)
+ kvPairs = append(kvPairs, KVPair{key, key})
+ }
+
+ testTreap = testTreap.Put(kvPairs...)
// Ensure the treap length is the expected value.
- if gotLen := testTreap.Len(); gotLen != i+1 {
+ if gotLen := testTreap.Len(); gotLen != (i+1)*keyCount {
t.Fatalf("Len #%d: unexpected length - got %d, want %d",
i, gotLen, i+1)
}
- // Ensure the treap has the key.
- if !testTreap.Has(key) {
- t.Fatalf("Has #%d: key %q is not in treap", i, key)
- }
+ for j, key := range keys {
+ // Ensure the treap has the key.
+ if !testTreap.Has(key) {
+ t.Fatalf("Has #%d#%d: key %q is not in treap", i, j, key)
+ }
- // Get the key from the treap and ensure it is the expected
- // value.
- if gotVal := testTreap.Get(key); !bytes.Equal(gotVal, key) {
- t.Fatalf("Get #%d: unexpected value - got %x, want %x",
- i, gotVal, key)
+ // Get the key from the treap and ensure it is the expected
+ // value.
+ if gotVal := testTreap.Get(key); !bytes.Equal(gotVal, key) {
+ t.Fatalf("Get #%d#%d: unexpected value - got %x, want %x",
+ i, j, gotVal, key)
+ }
+
+ expectedSize += (nodeFieldsSize + 8)
}
// Ensure the expected size is reported.
- expectedSize += (nodeFieldsSize + 8)
if gotSize := testTreap.Size(); gotSize != expectedSize {
t.Fatalf("Size #%d: unexpected byte size - got %d, "+
"want %d", i, gotSize, expectedSize)
@@ -262,33 +286,45 @@ func TestImmutableUnordered(t *testing.T) {
// treap functions work as expected.
expectedSize := uint64(0)
numItems := 1000
+ keyCount := 100
testTreap := NewImmutable()
- for i := 0; i < numItems; i++ {
+ for i := 0; i < numItems/keyCount; i++ {
// Hash the serialized int to generate out-of-order keys.
- hash := sha256.Sum256(serializeUint32(uint32(i)))
- key := hash[:]
- testTreap = testTreap.Put(key, key)
+ keys := make([][]byte, 0, keyCount)
+ kvPairs := make([]KVPair, 0, keyCount)
+ for j := 0; j < keyCount; j++ {
+ n := i*keyCount + j
+ hash := sha256.Sum256(serializeUint32(uint32(n)))
+ key := hash[:]
+ keys = append(keys, key)
+ kvPairs = append(kvPairs, KVPair{key, key})
+ }
+
+ testTreap = testTreap.Put(kvPairs...)
// Ensure the treap length is the expected value.
- if gotLen := testTreap.Len(); gotLen != i+1 {
+ if gotLen := testTreap.Len(); gotLen != (i+1)*keyCount {
t.Fatalf("Len #%d: unexpected length - got %d, want %d",
i, gotLen, i+1)
}
- // Ensure the treap has the key.
- if !testTreap.Has(key) {
- t.Fatalf("Has #%d: key %q is not in treap", i, key)
- }
+ for j, key := range keys {
+ // Ensure the treap has the key.
+ if !testTreap.Has(key) {
+ t.Fatalf("Has #%d#%d: key %q is not in treap", i, j, key)
+ }
- // Get the key from the treap and ensure it is the expected
- // value.
- if gotVal := testTreap.Get(key); !bytes.Equal(gotVal, key) {
- t.Fatalf("Get #%d: unexpected value - got %x, want %x",
- i, gotVal, key)
+ // Get the key from the treap and ensure it is the expected
+ // value.
+ if gotVal := testTreap.Get(key); !bytes.Equal(gotVal, key) {
+ t.Fatalf("Get #%d#%d: unexpected value - got %x, want %x",
+ i, j, gotVal, key)
+ }
+
+ expectedSize += nodeFieldsSize + uint64(len(key)+len(key))
}
// Ensure the expected size is reported.
- expectedSize += nodeFieldsSize + uint64(len(key)+len(key))
if gotSize := testTreap.Size(); gotSize != expectedSize {
t.Fatalf("Size #%d: unexpected byte size - got %d, "+
"want %d", i, gotSize, expectedSize)
@@ -335,31 +371,53 @@ func TestImmutableUnordered(t *testing.T) {
func TestImmutableDuplicatePut(t *testing.T) {
t.Parallel()
+ keyCount := 100
expectedVal := []byte("testval")
+
expectedSize := uint64(0)
numItems := 1000
testTreap := NewImmutable()
- for i := 0; i < numItems; i++ {
- key := serializeUint32(uint32(i))
- testTreap = testTreap.Put(key, key)
- expectedSize += nodeFieldsSize + uint64(len(key)+len(key))
+ for i := 0; i < numItems/keyCount; i++ {
+ keys := make([][]byte, 0, keyCount)
+ kvPairs := make([]KVPair, 0, keyCount)
+ for j := 0; j < keyCount; j++ {
+ n := i*keyCount + j
+ key := serializeUint32(uint32(n))
+ keys = append(keys, key)
+ kvPairs = append(kvPairs, KVPair{key, key})
+ }
- // Put a duplicate key with the expected final value.
- testTreap = testTreap.Put(key, expectedVal)
+ testTreap = testTreap.Put(kvPairs...)
- // Ensure the key still exists and is the new value.
- if gotVal := testTreap.Has(key); !gotVal {
- t.Fatalf("Has: unexpected result - got %v, want true",
- gotVal)
+ // Get expectedSize.
+ for _, key := range keys {
+ expectedSize += nodeFieldsSize + uint64(len(key)+len(key))
}
- if gotVal := testTreap.Get(key); !bytes.Equal(gotVal, expectedVal) {
- t.Fatalf("Get: unexpected result - got %x, want %x",
- gotVal, expectedVal)
+
+ // Put duplicate keys with the expected final values.
+ expectedPairs := make([]KVPair, keyCount)
+ for i := range expectedPairs {
+ expectedPairs[i] = KVPair{keys[i], expectedVal}
+ }
+
+ testTreap = testTreap.Put(expectedPairs...)
+
+ // Ensure the keys still exist and is the new value.
+ for _, key := range keys {
+ if gotVal := testTreap.Has(key); !gotVal {
+ t.Fatalf("Has: unexpected result - got %v, want true",
+ gotVal)
+ }
+ if gotVal := testTreap.Get(key); !bytes.Equal(gotVal, expectedVal) {
+ t.Fatalf("Get: unexpected result - got %x, want %x",
+ gotVal, expectedVal)
+ }
+
+ expectedSize -= uint64(len(key))
+ expectedSize += uint64(len(expectedVal))
}
// Ensure the expected size is reported.
- expectedSize -= uint64(len(key))
- expectedSize += uint64(len(expectedVal))
if gotSize := testTreap.Size(); gotSize != expectedSize {
t.Fatalf("Size: unexpected byte size - got %d, want %d",
gotSize, expectedSize)
@@ -376,7 +434,7 @@ func TestImmutableNilValue(t *testing.T) {
// Put the key with a nil value.
testTreap := NewImmutable()
- testTreap = testTreap.Put(key, nil)
+ testTreap = testTreap.Put(KVPair{key, nil})
// Ensure the key exists and is an empty byte slice.
if gotVal := testTreap.Has(key); !gotVal {
@@ -399,10 +457,12 @@ func TestImmutableForEachStopIterator(t *testing.T) {
// Insert a few keys.
numItems := 10
testTreap := NewImmutable()
+ kvPairs := make([]KVPair, 0, numItems)
for i := 0; i < numItems; i++ {
key := serializeUint32(uint32(i))
- testTreap = testTreap.Put(key, key)
+ kvPairs = append(kvPairs, KVPair{key, key})
}
+ testTreap = testTreap.Put(kvPairs...)
// Ensure ForEach exits early on false return by caller.
var numIterated int
@@ -426,38 +486,50 @@ func TestImmutableSnapshot(t *testing.T) {
// functions work as expected.
expectedSize := uint64(0)
numItems := 1000
+ keyCount := 100
testTreap := NewImmutable()
- for i := 0; i < numItems; i++ {
+ for i := 0; i < numItems/keyCount; i++ {
treapSnap := testTreap
- key := serializeUint32(uint32(i))
- testTreap = testTreap.Put(key, key)
+ keys := make([][]byte, 0, keyCount)
+ kvPairs := make([]KVPair, 0, keyCount)
+ for j := 0; j < keyCount; j++ {
+ n := i*keyCount + j
+ key := serializeUint32(uint32(n))
+ keys = append(keys, key)
+ kvPairs = append(kvPairs, KVPair{key, key})
+ }
+
+ testTreap = testTreap.Put(kvPairs...)
// Ensure the length of the treap snapshot is the expected
// value.
- if gotLen := treapSnap.Len(); gotLen != i {
+ if gotLen := treapSnap.Len(); gotLen != i*keyCount {
t.Fatalf("Len #%d: unexpected length - got %d, want %d",
i, gotLen, i)
}
- // Ensure the treap snapshot does not have the key.
- if treapSnap.Has(key) {
- t.Fatalf("Has #%d: key %q is in treap", i, key)
- }
+ for j, key := range keys {
+ // Ensure the treap snapshot does not have the key.
+ if treapSnap.Has(key) {
+ t.Fatalf("Has #%d#%d: key %q is in treap", i, j, key)
+ }
- // Get the key that doesn't exist in the treap snapshot and
- // ensure it is nil.
- if gotVal := treapSnap.Get(key); gotVal != nil {
- t.Fatalf("Get #%d: unexpected value - got %x, want nil",
- i, gotVal)
- }
+ // Get the key that doesn't exist in the treap snapshot and
+ // ensure it is nil.
+ if gotVal := treapSnap.Get(key); gotVal != nil {
+ t.Fatalf("Get #%d#%d: unexpected value - got %x, want nil",
+ i, j, gotVal)
+ }
- // Ensure the expected size is reported.
- if gotSize := treapSnap.Size(); gotSize != expectedSize {
- t.Fatalf("Size #%d: unexpected byte size - got %d, "+
- "want %d", i, gotSize, expectedSize)
+ // Ensure the expected size is reported.
+ if gotSize := treapSnap.Size(); gotSize != expectedSize {
+ t.Fatalf("Size #%d#%d: unexpected byte size - got %d, "+
+ "want %d", i, j, gotSize, expectedSize)
+ }
}
- expectedSize += (nodeFieldsSize + 8)
+
+ expectedSize += (nodeFieldsSize + 8) * uint64(keyCount)
}
// Delete the keys one-by-one while checking several of the treap
diff --git a/database/internal/treap/treapiter_test.go b/database/internal/treap/treapiter_test.go
index 08b4335..a6d12b5 100644
--- a/database/internal/treap/treapiter_test.go
+++ b/database/internal/treap/treapiter_test.go
@@ -496,10 +496,14 @@ testLoop:
for i, test := range tests {
// Insert a bunch of keys.
testTreap := NewImmutable()
+ keys := make([][]byte, 0, test.numKeys)
+ kvPairs := make([]KVPair, 0, test.numKeys)
for i := 0; i < test.numKeys; i += test.step {
key := serializeUint32(uint32(i))
- testTreap = testTreap.Put(key, key)
+ keys = append(keys, key)
+ kvPairs = append(kvPairs, KVPair{key, key})
}
+ testTreap = testTreap.Put(kvPairs...)
// Create new iterator limited by the test params.
iter := testTreap.Iterator(test.startKey, test.limitKey)
Risk score
Our methodology →Why this scored 18/100
Human-validated context
Community notes
Notes can correct, qualify, or add evidence to the AI analysis. Every note shown here has been validated by a human moderator.
No validated notes yet.
The AI analysis stands alone for now. Submit a note if you can add evidence or important context.