Status Updates before 21.8.2022

[koculu]

ZoneTree Roadmap

1. Replace in memory SkipList with lock-free B+Tree or B-link tree. (Done)

Several successful LSM tree products use SkipLists in-memory tables. ZoneTree is no exception at the moment.
However, the overhead of SkipList in Managed Environment is much more than C++ libraries. That includes both speed and memory consumption.
Initial experiments show that it is possible to speed up ZoneTree by using B+Tree by a factor of up to 🏃 10 🏃 and reduce memory consumption by 90%. 😮
B+Tree & B-Link tree is under construction at the moment.

2. Introduce sequence numbers in WAL entries. (Done)

Current WAL entries have no sequence numbers. ZoneTree requires locking of inserts and updates along with WAL writes. It is crucial to eliminate the need for locking of WAL writes. The change will not be compatible with existing WAL records.

3. Introduce ZoneTree library version information in the tree meta file. (Done)

It is necessary to leave a version footprint in the database file to enable the planning and implementation of database migrations to preserve backward compatibility.

[koculu]

Status Update

Roadmap items #1 and #2 are done with https://github.com/koculu/ZoneTree/releases/tag/release-v1.2.4
The performance improvement is on track.
Lock-free B+Tree is not implemented. Because it is too complicated and we don't need that much complication for small performance gain in memory. ZoneTree's performance bottleneck is disk writes but not memory operation.
100M inserts in 20 seconds is possible now.

Planned Feature List

• Add snapshot iterator support. (Done)
• Add Db Version information for backward compatibility. (Done)
• Improve crash resilience of human-readable database meta file. (Done)

[koculu]

Status Update

Starting with Release version 1.3.2,
ZoneTree is capable of doing automatic performance tuning.
See below how ZoneTree adjusts the cache capacity when 1000 parallel threads read 1 million keys and values from start to end.
1 billion read in total in 48 seconds.

[tekr]

This looks useful in many scenarios if it is able to live up to the claims under real-world use. Nice work.

One suggestion - as a new visitor, the posts above are a bit confusing since they mix project work items with state in non-chronological order. E.g. item 1 says '(Done)', but underneath says that Zonetree uses LSM 'at the moment'. And then further down says that B+tree/B-link work 'under construction'.

I suggest you use Github's issue tracking to make this clearer. I.e. create an issue for every new work item, and link to the relevant ones from this roadmap. The linked issues will show their status, making it easy for viewers to see current overall status as well as for you or anyone else to track, comment on, or contribute to individual items.

Looking forward to seeing this project develop further.

[koculu]

Thank you for the suggestions @tekr

I will remove the roadmap after I complete the documentation site. I am working on it now.

The chronological order of development is here: https://github.com/koculu/ZoneTree/releases

ZoneTree is an LSM tree since the beginning. There is no change on that.
LSM Tree is a data structure that contains multiple data structures in it.
The in-memory table was initially SkipList. Then it is replaced with B+Tree for performance reasons.

Anyway, it is an implementation detail and not so important for consumers.

[tekr]

Typo on my part, sorry - I meant 'uses SkipList..' not 'uses LSM..'.

Fair enough. I'm sure documentation will help a lot, though it's rarely fun for the developer writing it! It just wasn't 100% clear to me from reading the roadmap posts as a newbie whether the mentioned performance improvement work was all complete and released or still ongoing in some form, given the differing definitions of 'now' in places.

Anyway, very impressive work!

[tcsaddul]

Been monitoring this project since the start. I am quite amazed with the super fast evolution and updates. So I checked the profile of the author has done other genuinely hard projects.

Doing everything the github way for every item is impractical for FAST updates espcially if there is LONE author where he does all the push, approval, commits, etc would be unrealistic. Maybe when some other contributors come in and help, that github thing is recommended.

I have high hopes for this project because the author seems to be working full time.

[tekr]

I was thinking more for the large roadmap items rather than every minor change. And having issues linked to commits can help potential contributors grok the project direction and codebase more quickly, as well as see what items are outstanding (assuming that OP is open to additional contributors).

Certainly agree that this looks promising!