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

A new data structure for large indices

Open
#5,573 1 comment 0 reactions 0 assignees View on GitHub
Feature Enhancement P2 Performance Platform Platform Data Structures Platform Virtual Map Scalability
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

Open the contributing 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.