hiero-ledger / hiero-ledger/hiero-consensus-node

Enable performance testing with 10B accounts preserving in-memory indexes

Open
#24,953 1 comment 0 reactions 0 assignees View on GitHub
Epic Performance Platform Platform Virtual Map Scalability
Dominant language
Java
Stars
406
Forks
226
Avg merge
3d 4h
Merged PRs (30d)
210

Description

Full longevity testing with 10B accounts assumes 60B VirtualMap key-value pairs (10B accounts, 10B aliases, 10B NFTs, 20B token relations, 10B smart contract memory slots). To maintain `MemoryIndexDiskKeyValueStore` index, we would need 60B * 8 ~= 480 GB of RAM. We could decrease the size of the index by implementing chunks for stored key-value pairs but prototyping has showed that performance impact is going to be significant. A new proposal is presented here that is believed to be able to achieve smaller index size without sacrificing performance.

- Move path-key-value records (`VirtualLeafBytes`) to `HalfDiskHashMap`: each bucket contains complete records for all keys mapping into it. A possible implementation would contain a key-to-dataOffset map followed by actual records. Data offsets are within the bucket.
- Replace `MemoryIndexDiskKeyValueStore` with a path-to-key map and "chunkify" it.

Essential operations:
- `loadLeafRecord(key)` maps `key` to bucket index, reads bucket's map, finds `key` and determines record `offset` in the bucket, reads the record.
- `loadLeafRecord(path)` reads the chunk containing `path`, determines its `key`, calls `loadLeafRecord(key)`.
- `findKey(key)` calls `loadLeafRecord(key)`, returns `path` from the record.
- `flush` maps dirty leaves to buckets, reads and updates buckets with new records, writes updated buckets to a new file and updates bucket index. Updating the path-to-key map can be done in a separate pass from a dirty paths list or simultaneously with processing dirty/deleted leaves.
- `compaction` works without change on both data file collections.
- `reconnect` is functionally unchanged but may have performance consequences of the new design.
- state validator will need to be significantly reworked to match the new data structures and their relations.

Performance considerations:
- Implementing chunk id index for the path-to-key map may significantly reduce its size.
- Reading/updating a value from `VirtualMap` goes from two random disk reads to one or two [nearly] sequential disk reads.
- Adding multiple new keys will ideally touch two path-to-key chunks (one at the first leaf path and one beyond the last leaf path) with much lower amortized cost.
- Deleting multiple keys will touch one path-to-key chunk per deletion and ideally two chunks for the whole bunch, still lower amortized cost.

Index memory usage per 1B keys:
- hash index: `1B * 2 / 128 * 8 = 0.125 GB` (already implemented)
- path-to-key index : `1B / 64 * 8 = 0.125 GB` (assuming 64 entries per chunk)
- bucket index : `1B / 32 * 8 = 0.25 GB` (assuming 32 records per bucket)

totaling 0.5 GB / 1B keys.
A 60B-key VirtualMap would require only 30 GB for all indexes thus allowing to continue using in-memory index implementation without changing the current memory configuration.

Contributor guide

Open the contributing guide

Research direction

Start by reviewing VirtualLeafBytes, HalfDiskHashMap, and MemoryIndexDiskKeyValueStore, then trace the loadLeafRecord, findKey, flush, compaction, reconnect, and state-validator entry points. Done means the proposed bucket and chunked path-to-key design is implemented, preserves required operations, and supports the stated 60B-key index-memory target without unacceptable performance loss.

Written by the indexing model from the issue text.

Assessment

Tech stack
java
Domain
databases, performance
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Quiet
Clarity
Needs clarification
Newbie friendliness
30/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.