crypto-org-chain / crypto-org-chain/cronos

Problem: memiavl snapshot don't have any compression

Open
#827 4 comments 0 reactions 1 assignee Claimed by @yihuang View on GitHub
Dominant language
Go
Stars
336
Forks
299
Avg merge
2d 17h
Merged PRs (30d)
4

Description

Currently for simplicity, the [snapshot format](https://github.com/crypto-org-chain/cronos/blob/06af6fa6d6d11ff3348e4143920d82977f538e53/versiondb/memiavl/README.md#iavl-snapshot) is plain data without any compression, compression is important to reduce the size.
- `nodes`, each node is just a bunch of integers together with 32bytes hash, there are lots of zero bytes to compress, we can compress each node independently and add 1 byte length prefix, nodes are referenced by file offset, candidates:
- ~~[RLE](https://aquarchitect.github.io/swift-algorithm-club/Run-Length%20Encoding/)~~
- ~~[Cap'n Proto packing schema](https://capnproto.org/encoding.html#packing)~~
- simply concatenated varint, although not strictly random accessing, but skipping varint seems fast enough:
```python
def skipVarInt(buf, n):
'skip n varint encoded integers in buffer'
for offset, b in enumerate(buf):
if b>>7 == 0:
n -= 1
if n == 0:
break
else:
raise Exception('buffer exhausted')
return offset
```
- [stream vbyte](https://github.com/lemire/streamvbyte)
- `keys`, a bunch of short and ordered bytes, frequent access, delta encoding should be efficient here, then we need to organize the data in small fixed size chunk, and support looking up the key by index, rather than uncompressed file offset.
- `values`, unordered, less frequent access, can apply some generic random accessible compression like [zstd seektable format](https://github.com/facebook/zstd/blob/dev/contrib/seekable_format/zstd_seekable_compression_format.md), still support look up by uncompressed file offset.
- In IAVL modify operations, the values in snapshot are not used at all, if the query is taken over by versiondb, then the values are rarely needed (maybe need in proof generation?), we can even look up the value field from versiondb using `(node.key, node.version)`, if versiondb is integrated with IAVL tree closely.

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.