crypto-org-chain / crypto-org-chain/cronos
Problem: memiavl snapshot don't have any compression
- 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
Assessment
This issue has not been assessed yet.