hiero-ledger / hiero-ledger/hiero-consensus-node
A new data structure for large indices
- Dominant language
- Java
- Stars
- 406
- Forks
- 226
- Avg merge
- 3d 4h
- Merged PRs (30d)
- 210
Description
### Problem
Today VirtualMap works in one of the following two modes for virtual keys:
* long keys: LongListOffHeap is used as an index
* object keys: HalfDiskHashMap is used as an index
HalfDiskHashMap is generic, but is slow. LongListOffHeap is fast, but it has a limitation that keys must be longs (or mapped to longs), and these longs should be relatively low and sequential.
At some point, we will need to support non-sequential long keys, which are distributed evenly over the whole long range, -2^63 to 2^63-1. LongListOffHeap can't be used in this case as it stores chunks of longs from 0 to max value, even if many values within aren't used. Even for sequential long keys, at some point there will be so many entities that long lists won't fit into Java heap.
There is another LongList implementation, LongListDisk, which stores everything in a file. It's slow (random reads), it was never designed to be used in production, and it's still has the same architectural flaw that it stores everything from 0 to max value.
### Solution
This feature request is to implement a new data structure, which can store long values and can be used as an index for long-based keys. It should be more efficient than HalfDiskHashMap and need less memory than LongListOffHeap.
### Alternatives
_No response_
Contributor guide
Research direction
No source file or test is named. Start by reading VirtualMap and the existing LongListOffHeap, HalfDiskHashMap, and LongListDisk implementations to understand their index behavior and limitations. Done means a production-suitable long-value index that handles non-sequential long-based keys with less memory than LongListOffHeap and better efficiency than HalfDiskHashMap.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- java
- Domain
- backend
- Issue type
- Feature
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Stale
- Clarity
- Needs clarification
- Newbie friendliness
- 25/100