Skip to content

Commit 5007716

Browse files
awskiiawskii
authored
Merge 45b649f into 71ce2d1 
2 parents 71ce2d1 + 45b649f commit 5007716

File tree

7 files changed

+206
-14
lines changed

7 files changed

+206
-14
lines changed

‎erigon-lib/state/bps_tree.go‎

Lines changed: 62 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -186,6 +186,68 @@ func (b *BpsTree) bs(x []byte) (n Node, dl, dr uint64) {
186186
return n, dl, dr
187187
}
188188

189+
func (b *BpsTree) LookAround(g ArchiveGetter, ci uint64, key []byte) (skey []byte, di uint64, found bool, err error) {
190+
if b.offt == nil || b.offt.Count() == 0 {
191+
return nil, 0, false, nil
192+
}
193+
var cmp int
194+
cmp, skey, err = b.keyCmpFunc(key, ci, g)
195+
if err != nil {
196+
return nil, 0, false, err
197+
}
198+
199+
l, r := uint64(0), b.offt.Count()
200+
switch cmp {
201+
case 0:
202+
return skey, ci, true, nil
203+
case 1:
204+
r = ci
205+
case -1:
206+
l = ci
207+
}
208+
209+
if b.trace {
210+
fmt.Printf("lookAround [ci=%d] %x [%d %d]\n", ci, key, l, r)
211+
}
212+
defer func() {
213+
if b.trace {
214+
fmt.Printf("found %x [%d %d]\n", key, l, r)
215+
}
216+
}()
217+
218+
var m uint64
219+
for l < r {
220+
m = (l + r) >> 1
221+
cmp, skey, err = b.keyCmpFunc(key, m, g)
222+
if err != nil {
223+
return nil, 0, false, err
224+
}
225+
if b.trace {
226+
fmt.Printf("lr %x [%d %d]\n", skey, l, r)
227+
}
228+
229+
switch cmp {
230+
case 0:
231+
return skey, m, true, nil
232+
//return &BpsTreeIterator{t: b, i: m}, nil
233+
case 1:
234+
r = m
235+
case -1:
236+
l = m + 1
237+
}
238+
}
239+
if l == r {
240+
m = l
241+
//return &BpsTreeIterator{t: b, i: l}, nil
242+
}
243+
244+
cmp, skey, err = b.keyCmpFunc(key, m, g)
245+
if err != nil {
246+
return nil, 0, false, err
247+
}
248+
return skey, m, cmp == 0, nil
249+
}
250+
189251
// Seek returns first key which is >= key.
190252
// Found is true iff exact key match is found.
191253
// If key is nil, returns first key and found=true

‎erigon-lib/state/btree_index.go‎

Lines changed: 44 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -94,6 +94,10 @@ func (c *Cursor) Value() []byte {
9494
return c.value
9595
}
9696

97+
func (c *Cursor) LookAround(key []byte) (found bool, err error) {
98+
return c.btt.LookAround(c, key)
99+
}
100+
97101
func (c *Cursor) Next() bool {
98102
if !c.next() {
99103
return false
@@ -103,7 +107,8 @@ func (c *Cursor) Next() bool {
103107
if err != nil {
104108
return false
105109
}
106-
c.key, c.value = key, value
110+
c.key = append(c.key[:0], key...)
111+
c.value = append(c.value[:0], value...)
107112
return true
108113
}
109114

@@ -866,6 +871,7 @@ func (b *BtIndex) dataLookup(di uint64, g ArchiveGetter) ([]byte, []byte, error)
866871
}
867872

868873
// comparing `k` with item of index `di`. using buffer `kBuf` to avoid allocations
874+
// resulting int is 1 when key[di] > k; -1 when key[di] < k
869875
func (b *BtIndex) keyCmp(k []byte, di uint64, g ArchiveGetter) (int, []byte, error) {
870876
if di >= b.ef.Count() {
871877
return 0, nil, fmt.Errorf("%w: keyCount=%d, but key %d requested. file: %s", ErrBtIndexLookupBounds, b.ef.Count(), di+1, b.FileName())
@@ -1028,6 +1034,43 @@ func (b *BtIndex) Seek(g ArchiveGetter, x []byte) (*Cursor, error) {
10281034
return b.newCursor(context.Background(), k, v, dt, g), nil
10291035
}
10301036

1037+
func (b *BtIndex) LookAround(c *Cursor, x []byte) (found bool, err error) {
1038+
if b.Empty() || c.d >= b.ef.Count() {
1039+
return false, nil
1040+
}
1041+
1042+
// defer func() {
1043+
// fmt.Printf("[Bindex][%s] seekInFiles '%x' -> '%x' di=%d\n", b.FileName(), x, cursor.Value(), cursor.d)
1044+
// }()
1045+
var dt uint64
1046+
if UseBpsTree {
1047+
_, dt, found, err = b.bplus.LookAround(c.getter, c.d, x)
1048+
} else {
1049+
_, dt, found, err = b.alloc.Seek(c.getter, x)
1050+
}
1051+
_ = found
1052+
if err != nil /*|| !found*/ {
1053+
if errors.Is(err, ErrBtIndexLookupBounds) {
1054+
return false, nil
1055+
}
1056+
return false, err
1057+
}
1058+
1059+
k, v, err := b.dataLookup(dt, c.getter)
1060+
if err != nil {
1061+
if errors.Is(err, ErrBtIndexLookupBounds) {
1062+
return false, nil
1063+
}
1064+
return false, err
1065+
}
1066+
if !bytes.Equal(k, x) {
1067+
return false, nil
1068+
}
1069+
c.key = append(c.key[:0], k...)
1070+
c.value = append(c.value[:0], v...)
1071+
c.d = dt
1072+
return true, nil
1073+
}
10311074
func (b *BtIndex) OrdinalLookup(getter ArchiveGetter, i uint64) *Cursor {
10321075
k, v, err := b.dataLookup(i, getter)
10331076
if err != nil {

‎erigon-lib/state/domain.go‎

Lines changed: 84 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -608,6 +608,7 @@ type DomainRoTx struct {
608608
ht *HistoryRoTx
609609
d *Domain
610610
files []ctxItem
611+
btcursors []*Cursor
611612
getters []ArchiveGetter
612613
readers []*BtIndex
613614
idxReaders []*recsplit.IndexReader
@@ -620,6 +621,23 @@ type DomainRoTx struct {
620621
valsC kv.Cursor
621622
}
622623

624+
func (dt *DomainRoTx) getCursorFromFile(i int, filekey []byte) ([]byte, bool, error) {
625+
if !(UseBtree || UseBpsTree) {
626+
panic("not implemented")
627+
}
628+
629+
cur := dt.statefulBtree(i)
630+
cur.getter = dt.statelessGetter(i)
631+
found, err := cur.LookAround(filekey)
632+
if err != nil {
633+
return nil, false, err
634+
}
635+
if found {
636+
return cur.Value(), true, nil
637+
}
638+
return nil, false, nil
639+
}
640+
623641
func (dt *DomainRoTx) getFromFile(i int, filekey []byte) ([]byte, bool, error) {
624642
g := dt.statelessGetter(i)
625643
if !(UseBtree || UseBpsTree) {
@@ -1281,6 +1299,58 @@ var (
12811299
UseBtree = true // if true, will use btree for all files
12821300
)
12831301

1302+
func (dt *DomainRoTx) getFromFilesCursor(filekey []byte) (v []byte, found bool, fileStartTxNum uint64, fileEndTxNum uint64, err error) {
1303+
hi, _ := dt.ht.iit.hashKey(filekey)
1304+
1305+
for i := len(dt.files) - 1; i >= 0; i-- {
1306+
if dt.d.indexList&withExistence != 0 {
1307+
//if dt.files[i].src.existence == nil {
1308+
// panic(dt.files[i].src.decompressor.FileName())
1309+
//}
1310+
if dt.files[i].src.existence != nil {
1311+
if !dt.files[i].src.existence.ContainsHash(hi) {
1312+
if traceGetLatest == dt.d.filenameBase {
1313+
fmt.Printf("GetLatest(%s, %x) -> existence index %s -> false\n", dt.d.filenameBase, filekey, dt.files[i].src.existence.FileName)
1314+
}
1315+
continue
1316+
} else {
1317+
if traceGetLatest == dt.d.filenameBase {
1318+
fmt.Printf("GetLatest(%s, %x) -> existence index %s -> true\n", dt.d.filenameBase, filekey, dt.files[i].src.existence.FileName)
1319+
}
1320+
}
1321+
} else {
1322+
if traceGetLatest == dt.d.filenameBase {
1323+
fmt.Printf("GetLatest(%s, %x) -> existence index is nil %s\n", dt.d.filenameBase, filekey, dt.files[i].src.decompressor.FileName())
1324+
}
1325+
}
1326+
}
1327+
1328+
//t := time.Now()
1329+
v, found, err = dt.getCursorFromFile(i, filekey)
1330+
// v, found, err = dt.getFromFile(i, filekey)
1331+
if err != nil {
1332+
return nil, false, 0, 0, err
1333+
}
1334+
if !found {
1335+
if traceGetLatest == dt.d.filenameBase {
1336+
fmt.Printf("GetLatest(%s, %x) -> not found in file %s\n", dt.d.filenameBase, filekey, dt.files[i].src.decompressor.FileName())
1337+
}
1338+
// LatestStateReadGrindNotFound.ObserveDuration(t)
1339+
continue
1340+
}
1341+
if traceGetLatest == dt.d.filenameBase {
1342+
fmt.Printf("GetLatest(%s, %x) -> found in file %s\n", dt.d.filenameBase, filekey, dt.files[i].src.decompressor.FileName())
1343+
}
1344+
//LatestStateReadGrind.ObserveDuration(t)
1345+
return v, true, dt.files[i].startTxNum, dt.files[i].endTxNum, nil
1346+
}
1347+
if traceGetLatest == dt.d.filenameBase {
1348+
fmt.Printf("GetLatest(%s, %x) -> not found in %d files\n", dt.d.filenameBase, filekey, len(dt.files))
1349+
}
1350+
1351+
return nil, false, 0, 0, nil
1352+
}
1353+
12841354
func (dt *DomainRoTx) getFromFiles(filekey []byte) (v []byte, found bool, fileStartTxNum uint64, fileEndTxNum uint64, err error) {
12851355
hi, _ := dt.ht.iit.hashKey(filekey)
12861356

@@ -1308,7 +1378,8 @@ func (dt *DomainRoTx) getFromFiles(filekey []byte) (v []byte, found bool, fileSt
13081378
}
13091379

13101380
//t := time.Now()
1311-
v, found, err = dt.getFromFile(i, filekey)
1381+
v, found, err = dt.getCursorFromFile(i, filekey)
1382+
// v, found, err = dt.getFromFile(i, filekey)
13121383
if err != nil {
13131384
return nil, false, 0, 0, err
13141385
}
@@ -1391,6 +1462,18 @@ func (dt *DomainRoTx) statelessGetter(i int) ArchiveGetter {
13911462
return r
13921463
}
13931464

1465+
func (dt *DomainRoTx) statefulBtree(i int) *Cursor {
1466+
if dt.btcursors == nil {
1467+
dt.btcursors = make([]*Cursor, len(dt.files))
1468+
}
1469+
r := dt.btcursors[i]
1470+
if r == nil {
1471+
r = dt.statelessBtree(i).newCursor(context.Background(), nil, nil, 0, dt.statelessGetter(i))
1472+
dt.btcursors[i] = r
1473+
}
1474+
return r
1475+
}
1476+
13941477
func (dt *DomainRoTx) statelessIdxReader(i int) *recsplit.IndexReader {
13951478
if dt.idxReaders == nil {
13961479
dt.idxReaders = make([]*recsplit.IndexReader, len(dt.files))

‎erigon-lib/state/domain_shared.go‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -305,7 +305,7 @@ func (sd *SharedDomains) LatestCommitment(prefix []byte) ([]byte, uint64, error)
305305

306306
// GetfromFiles doesn't provide same semantics as getLatestFromDB - it returns start/end tx
307307
// of file where the value is stored (not exact step when kv has been set)
308-
v, _, startTx, endTx, err := sd.aggTx.d[kv.CommitmentDomain].getFromFiles(prefix)
308+
v, _, startTx, endTx, err := sd.aggTx.d[kv.CommitmentDomain].getFromFilesCursor(prefix)
309309
if err != nil {
310310
return nil, 0, fmt.Errorf("commitment prefix %x read error: %w", prefix, err)
311311
}

‎erigon-lib/state/domain_shared_test.go‎

Lines changed: 9 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -4,17 +4,17 @@ import (
44
"context"
55
"encoding/binary"
66
"fmt"
7-
"github.com/holiman/uint256"
8-
"github.com/ledgerwatch/erigon-lib/kv"
9-
"github.com/ledgerwatch/erigon-lib/kv/rawdbv3"
10-
"github.com/ledgerwatch/log/v3"
11-
"github.com/stretchr/testify/require"
127
"math/rand"
138
"testing"
149
"time"
1510

11+
"github.com/holiman/uint256"
1612
"github.com/ledgerwatch/erigon-lib/common/length"
13+
"github.com/ledgerwatch/erigon-lib/kv"
14+
"github.com/ledgerwatch/erigon-lib/kv/rawdbv3"
1715
"github.com/ledgerwatch/erigon-lib/types"
16+
"github.com/ledgerwatch/log/v3"
17+
"github.com/stretchr/testify/require"
1818
)
1919

2020
func TestSharedDomain_CommitmentKeyReplacement(t *testing.T) {
@@ -455,13 +455,17 @@ func TestSharedDomain_StorageIter(t *testing.T) {
455455
require.NoError(t, err)
456456

457457
missed := 0
458+
checked := false
458459
err = domains.IterateStoragePrefix(k0, func(k []byte, v []byte, step uint64) error {
460+
checked = true
461+
//fmt.Printf("checking %x\n", k)
459462
if _, been := existed[string(k)]; !been {
460463
missed++
461464
}
462465
return nil
463466
})
464467
require.NoError(t, err)
468+
require.True(t, checked)
465469
require.Zero(t, missed)
466470

467471
err = domains.deleteAccount(k0, pv, step)

‎go.mod‎

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -276,8 +276,8 @@ require (
276276
golang.org/x/mod v0.17.0 // indirect
277277
golang.org/x/text v0.15.0 // indirect
278278
golang.org/x/tools v0.21.0 // indirect
279-
google.golang.org/genproto/googleapis/api v0.0.0-20240515191416-fc5f0ca64291 // indirect
280-
google.golang.org/genproto/googleapis/rpc v0.0.0-20240515191416-fc5f0ca64291 // indirect
279+
google.golang.org/genproto/googleapis/api v0.0.0-20240521202816-d264139d666e // indirect
280+
google.golang.org/genproto/googleapis/rpc v0.0.0-20240521202816-d264139d666e // indirect
281281
gopkg.in/cenkalti/backoff.v1 v1.1.0 // indirect
282282
gopkg.in/tomb.v1 v1.0.0-20141024135613-dd632973f1e7 // indirect
283283
gotest.tools/v3 v3.5.1 // indirect

‎go.sum‎

Lines changed: 4 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -1359,10 +1359,10 @@ google.golang.org/genproto v0.0.0-20201210142538-e3217bee35cc/go.mod h1:FWY/as6D
13591359
google.golang.org/genproto v0.0.0-20201214200347-8c77b98c765d/go.mod h1:FWY/as6DDZQgahTzZj3fqbO1CbirC29ZNUFHwi0/+no=
13601360
google.golang.org/genproto v0.0.0-20210108203827-ffc7fda8c3d7/go.mod h1:FWY/as6DDZQgahTzZj3fqbO1CbirC29ZNUFHwi0/+no=
13611361
google.golang.org/genproto v0.0.0-20210226172003-ab064af71705/go.mod h1:FWY/as6DDZQgahTzZj3fqbO1CbirC29ZNUFHwi0/+no=
1362-
google.golang.org/genproto/googleapis/api v0.0.0-20240515191416-fc5f0ca64291 h1:4HZJ3Xv1cmrJ+0aFo304Zn79ur1HMxptAE7aCPNLSqc=
1363-
google.golang.org/genproto/googleapis/api v0.0.0-20240515191416-fc5f0ca64291/go.mod h1:RGnPtTG7r4i8sPlNyDeikXF99hMM+hN6QMm4ooG9g2g=
1364-
google.golang.org/genproto/googleapis/rpc v0.0.0-20240515191416-fc5f0ca64291 h1:AgADTJarZTBqgjiUzRgfaBchgYB3/WFTC80GPwsMcRI=
1365-
google.golang.org/genproto/googleapis/rpc v0.0.0-20240515191416-fc5f0ca64291/go.mod h1:EfXuqaE1J41VCDicxHzUDm+8rk+7ZdXzHV0IhO/I6s0=
1362+
google.golang.org/genproto/googleapis/api v0.0.0-20240521202816-d264139d666e h1:SkdGTrROJl2jRGT/Fxv5QUf9jtdKCQh4KQJXbXVLAi0=
1363+
google.golang.org/genproto/googleapis/api v0.0.0-20240521202816-d264139d666e/go.mod h1:LweJcLbyVij6rCex8YunD8DYR5VDonap/jYl3ZRxcIU=
1364+
google.golang.org/genproto/googleapis/rpc v0.0.0-20240521202816-d264139d666e h1:Elxv5MwEkCI9f5SkoL6afed6NTdxaGoAo39eANBwHL8=
1365+
google.golang.org/genproto/googleapis/rpc v0.0.0-20240521202816-d264139d666e/go.mod h1:EfXuqaE1J41VCDicxHzUDm+8rk+7ZdXzHV0IhO/I6s0=
13661366
google.golang.org/grpc v1.14.0/go.mod h1:yo6s7OP7yaDglbqo1J04qKzAhqBH6lvTonzMVmEdcZw=
13671367
google.golang.org/grpc v1.16.0/go.mod h1:0JHn/cJsOMiMfNA9+DeHDlAU7KAAB5GDlYFpa9MZMio=
13681368
google.golang.org/grpc v1.17.0/go.mod h1:6QZJwpn2B+Zp71q/5VxRsJ6NXXVCE5NRUHRo+f3cWCs=

0 commit comments

Comments
 (0)