Completed: ICDevs.org - Bounty 24 - StableBtree Mokoko - up to $10k

Developers Bounties
1

Motoko StableBTree - #24

Current Status: Discussion

  • Discussion (08/14/2022)
  • Ratification
  • Open for application
  • Assigned
  • In Review
  • Closed

Official Link

Bounty Details

  • Bounty Amount: $5,000 USD of ICP at award date - $5000 USD of ICP Match Available
  • ICDevs.org DFINITY Foundation Grant Match Available: $5000 USD of ICP at award time - (For every ICP sent to 801581b2c8f3303eaeb91892784b2eac99e1128115b0fadf739576d6c94f3c8e, ICDevs.org will add $40 USD of ICP at award date to the bounty, up to the first 125 ICP donated, After 125 ICP, donations to the above address will add .25 ICP to this issue and .75 ICP to fund other ICDevs.org initiatives)
  • Project Type: Team
  • Opened: 09/02/2022
  • Time Commitment: Weeks
  • Project Type: Library
  • Experience Type: Intermediate - Motoko;

Description

This Motoko library will allow for more efficient storage and better crypt capabilities of data storage in motoko contracts.

This bounty gives the opportunity to

  • learn motoko
  • learn about merkleizaton
  • learn btrees
  • learn about stable memory

This one is pretty simple. Implement the StableBTree library found at GitHub - ielashi/stable-btreemap-example: Examples of using `StableBTreeMap` in Canisters in Motoko. Accomplishing this will award 50% of the bounty.

For the second 50%, add a mode(or an alternate library if it is more efficient), That keeps active track of a merkle hash of the root of the data set. This library will be used to calculate certified data, so the root should be compatible with including in a canister certification.

Please:

  1. Duplicate the existing functionality.

  2. Provide a set of tests.

  3. Publish as a vessel package

  4. For the merkle stretch goal, please provide tests and an example of using the tree to store certified data.

To apply for this bounty you should:

  • Include links to previous work writing tutorials and any other open-source contributions(ie. your github).
  • Include a brief overview of how you will complete the task. This can include things like which dependencies you will use, how you will make it self-contained, the sacrifices you would have to make to achieve that, or how you will make it simple. Anything that can convince us you are taking a thoughtful and expert approach to this design.
  • Give an estimated timeline on completing the task.
  • Post your application text to the Bounty Thread

Selection Process

The ICDevs.org developer’s advisors will propose a vote to award the bounty and the Developer Advisors will vote.

Bounty Completion

Please keep your ongoing code in a public repository(fork or branch is ok). Please provide regular (at least weekly) updates. Code commits count as updates if you link to your branch/fork from the bounty thread. We just need to be able to see that you are making progress.

The balance of the bounty will be paid out at completion.

Once you have finished, please alert the dev forum thread that you have completed work and where we can find that work. We will review and award the bounty reward if the terms have been met. If there is any coordination work(like a pull request) or additional documentation needed we will inform you of what is needed before we can award the reward.

Bounty Abandonment and Re-awarding

If you cease work on the bounty for a prolonged(at the Developer Advisory Board’s discretion) or if the quality of work degrades to the point that we think someone else should be working on the bounty we may re-award it. We will be transparent about this and try to work with you to push through and complete the project, but sometimes, it may be necessary to move on or to augment your contribution with another resource which would result in a split bounty.

Funding

The bounty was generously funded by the DFINITY Foundation. If you would like to turbocharge this bounty you can seed additional donations of ICP to 801581b2c8f3303eaeb91892784b2eac99e1128115b0fadf739576d6c94f3c8e. ICDevs will match the bounty $40:1 ICP for the first 125 ICP out of the DFINITY grant and then 0.25:1 after that. All donations will be tax deductible for US Citizens and Corporations. If you send a donation and need a donation receipt, please email the hash of your donation transaction, physical address, and name to donations@icdevs.org. More information about how you can contribute can be found at our donations page.

FYI: General Bounty Process

Discussion

The draft bounty is posted to the DFINITY developer’s forum for discussion

Ratification

The developer advisor’s board will propose a bounty be ratified and a vote will take place to ratify the bounty. Until a bounty is ratified by the Dev it hasn’t been officially adopted. Please take this into consideration if you are considering starting early.

Open for application

Developers can submit applications to the Dev Forum post. The council will consider these as they come in and propose a vote to award the bounty to one of the applicants. If you would like to apply anonymously you can send an email to austin at icdevs dot org or sending a PM on the dev forum.

Assigned

A developer is currently working on this bounty, you are free to contribute, but any splitting of the award will need to be discussed with the currently assigned developer.

In Review

The Dev Council is reviewing the submission

Awarded

The award has been given and the bounty is closed.

Matches

DFINITY Foundation Grant: - $5000 USD of ICP at award date

Other ICDevs.org Bounties

1 Like
2

Concerning the second part of the bounty, see Certified, scalable map. · Issue #409 · dfinity/motoko-base · GitHub

3

Agree with @domwoe
It is a better idea to implement a specialized data structure for data certification.

4

This bounty is being pursued by @sardariuss

1 Like
5

Hi, Is this bounty already closed and assigned to someone? I still this as open bounty here icdevs[.]org/news

1 Like
6

@sardariuss Are you still working on this bounty?

7

Yes I am, I’ll be able to show you some progress soon.

1 Like
8

In that case is it possible to have it assigned, and not be it in the open bounties section?

9

I’d like to be able to transform Motoko basic types (essentially the Nat16/Nat32/Nat64 and resp. Int) types into an array of bytes. In rust this is done with to_le_bytes. Also if there is something that exists to convert a struct into such an array of bytes I’m taking it too. I think rust uses the trait #[repr(packed)] that allows to peform a safe cast into a pointer of u8, then converted into a vec. But I doubt something that straightforward is possible in Motoko.

Otherwise I might continue with my tricky structures in my AlignedStruct module for now. But at some point I think I will need to be able to convert everything in a vector of bytes anyway just to be able to test with a “fake” memory (like vec_mem.rs in the Rust implementation). I was curious to test directly with ExperimentalStableMemory, but it crashes at the compilation of the tests, which probably makes sense.

10

I have that logic in candy_library/conversion.mo at main · skilesare/candy_library · GitHub. You could adapt it…probably don’t need the whole candy library as you are trying to do something fast.

1 Like
11

Hey, small update for this bounty, the code is here: GitHub - sardariuss/MotokoStableBTree: https://forum.dfinity.org/t/icdevs-org-bounty-24-stablebtree-mokoko-up-to-10k/14867

I finished the implementation of the BTreeMap itself, I’ll start on the unit tests next week.

And thank you for the candy lib that’s exactly what I needed.

2 Likes
12

Hi Skilesare,

All Rust unit tests have been implemented in Motoko. As suggested by CanScale, I’m gonna continue with these 3 tests before jumping on the merkleizaton:
1 - A test that does random key insertion for ~ 5000 values
2 - A test that is always inserting a new value which is the new highest value in the tree ~ 5000 values
3 - A test that runs an upgrade, and then show they persisted through the upgrade

I have a question though: the conversion from type to bytes are done in little endianin Rust, whereas the conversions from the candy lib are in big endian, so should I convert my types in little endian instead ?

1 Like
13

Hey @sardariuss,

Nice to meet you online! I’m on the Motoko team at DFINITY and am working on extending data structures in the base library. I was wondering if you have any interest in contributing this to the motoko-base library when it is complete (with potentially some added QOL bells and whistles to make it very user friendly).

Let me know what you think.

4 Likes
14

Hi Kentosugama,

Nice to meet you too! Yes for sure, I’d be very happy to do that.

2 Likes
15

Hi,

I’ve done the few tests I was talking about before (testing with actual stable memory), it works well, for now it’s in a separate repo here:

I’m gonna put this in the original repo soon, with CI on top.

@kentosugama I’ve been thinking a bit on how to improve the public interface to make it more user friendly. As an example the current BTreeMap.init method looks like this:

/// Initializes a BTreeMap.
///
/// If the memory provided already contains a BTreeMap, then that
/// map is loaded. Otherwise, a new BTreeMap instance is created.
public func init<K, V>(
memory : Memory,
max_key_size : Nat32,
max_value_size : Nat32,
key_converter: BytesConverter,
value_converter: BytesConverter
) : BTreeMap<K, V> {

First, I could wrap the current BTreeMap class into a new StableBTreeMap (or just StableBTree?) that uses the stable memory as memory. This would remove the memory parameter from the init method. And we could only expose a few methods (e.g. insert, get, remove, size). I want to keep the rest public in the original BTreeMap so I can do unit tests.

Second, it would be great if the key_converter and value_converter could directly be deduced from the type of K and V. But AFAIK it’s not possible to do such thing in Motoko. I’m forced to have a method to convert types in bytes because the ExperimentalStableMemory has a specific method for each type. I guess I could create a StableBTreeVK class for each combination of K and V I want to support but this is super ugly. Note that converting in bytes also makes my life way easier to be able to test the BTreeMap with my VecMemory that is a buffer of bytes.
One alternative could be to not template any of this and use always use [Nat8] for keys and values, forcing the user to do the conversion beforehand and afterwards. But IMO I’d rather just have to give the converters in the init method.

What do you think? Is this some of the improvements you were thinking when talking about “QOL bells and whistles” ?

2 Likes
16

Hey!

This sounds great.

As a general point, I think it makes sense to fully complete the ICDevs bounty first, and then we can worry about merging into base.

By QOL, I mainly mean adding extra utility functions (e.g. motoko-base/Buffer.mo at master · dfinity/motoko-base · GitHub). I don’t think there will be as many functions for maps, but things like finding max value, min value, folding over maps, mapping a higher order function over the kv pairs, producing a text representation of the current entries, etc.

Serialization seems to be the most thorny problem. Right off the bat, do you think there’s a good way to have a non-stable version, where the user doesn’t have to pass in a memory (since it’s just stored in the normal heap), and there’s no max sizes or converters since serialization is not necessary?

As for the stable use case, I agree that having the users pass in the converters is the best approach at the moment. I would definitely not implement every combination of serializer by type :slight_smile:

A possible alternative: Not sure if you’ve considered using to_candid and from_candid primitives? These are Motoko operators that let you serialize any shareable type to Blobs and back. Could be useful as an out of box serializer, except for the fact that you need to convince the compiler that the generic types are shared. As far as I can tell, this is a bit tricky at the moment. Motoko Sharable Generics.

3 Likes
17

Hi guys,

Last updates:

  • The MemoryManager has been added to be able to use many btrees in stable memory. All tests pass, but it seems that using the MemoryManager significantly slows down the execution of the BTree functions. I haven’t done any investigation yet.
  • A version of the Btree using the heap instead of the stable memory is now available on the branch “heap_version”.
  • Kentosugama will start PRs to gradually put the code (both stable and heap versions) into the motoko-base library. @skilesare Could somebody from ICDevs be involved in the reviews ? That could be a way to validate the first part of the bounty.
4 Likes
18

Awesome! I’ll take a look early next week. We’ll get the bounty closed out. Great Job!

19

Hey, icme made me realize I missed a few things: for the stable implementation, I missed a few recent commits from the rust repo, I’m gonna check that out. For example chore: Enhancements to the StableBTreeMap API. (#17) · dfinity/stable-structures@53d4f93 · GitHub I could do something similar in the motoko version, adding the max_size function in the BytesConverter, and probably exposing the bytesConverter for every common type (Nat8, Nat32, etc.).

Also for the heap_version, I need to use a buffer of the real K, V types instead of bytes, there is no need to convert in bytes indeed.

@kentosugama I will create new branches in my repo to do this to not impact the PR if that’s correct with you

1 Like
20

Small update: I implemented the max_size() function in the BytesConverter on the main branch and the K, V template arguments for the heap version.

@kentosugama I tried to understand what’s happening with the MemoryManager today.

First I noticed that the execution slows down or crashes:

  • around 5k entries when using the MemoryManager (with stable memory)
  • around 25k entries when using directly the stable memory

When it slows down or crashes, I usually have these messages in the console:

Nov 23 18:36:15.524 WARN s:za6i6-rsijm-wkhfy-76yge-w72zd-2mbch-4hjg5-6ieqy-alrnx-azwgk-iqe/n:evshh-lrotb-t5oeu-psqm7-fqz5h-zfyun-r5wdr-u5ugs-zqhrz-wc7rw-uae/ic_execution_environment/scheduler Finished executing message type “Ingress, method name insertMany,” on canister CanisterId(rrkah-fqaaa-aaaaa-aaaaq-cai) after 7.2521542 seconds, messaging: {“round”:41,“canister_id”:“rrkah-fqaaa-aaaaa-aaaaq-cai”,“message_id”:null}
Nov 23 18:36:32.719 WARN s:za6i6-rsijm-wkhfy-76yge-w72zd-2mbch-4hjg5-6ieqy-alrnx-azwgk-iqe/n:evshh-lrotb-t5oeu-psqm7-fqz5h-zfyun-r5wdr-u5ugs-zqhrz-wc7rw-uae/ic_consensus/consensus starvation detected: Notary has not been invoked for 4.1307306s

Also when I monitor the RAM, I see some spikes that seem to coincide with the moment these messages are emited. That RAM far exceeds the memory required for my entries to be stored in the btree.

My naïve guess is that the query/update methods I call take too much time (because I call a single canister method insert that inserts 5k entries at once in a motoko loop to reduce test time). This creates problems with the simulated consensus, which then requires more cpu and memory to perform, and ultimatly leads to the crash. But in my tests, when I tried to call the query/updates in 10 batches of 500 entries, it doesn’t quite solve the problem.

I’ll continue investigate tomorrow, but any feedback will be appreciated!