Scalability of avl.Tree and Gas Limit R&D Findings & Recommendations from the dSocial Grant

[costinberty]

List of R&D Findings & Recommendations from the dSocial Grant

Following the dSocial grant, we followed 2 main R&D investigation themes:

1. resource utilization (disk/RAM) when doing various operations in the avl.Tree and
2. gas cost when doing various operations in the avl.Tree

Below we will detail our findings and recommendations for both of them.

Resource utilization for avl.Trees for large amounts of data

Objective

Test the resource utilization (storage, memory consumption, delay) when the avl.Tree has large amounts of data.

Tests Description & Results

As a general method we generated millions of posts using the code in this PR gnolang/gno#1583

We performed 3 tests using gnodev (in-memory) or gnoland (on-disk):

1. gnodev in-memory insertion time vs. avl.Tree size

   1. Decription: testing what the limits of memory consumption (to store the avl.Tree) when using gnodev. The test is described in detail in the PR 1583
   2. Test results:

      1. in a nutshell, the performance is unacceptable in gnodev above 225,000 posts on Macbook with 16GB RAM.

      2. we did not perform future tests since it was clear that the performance was unacceptable when using gnodev.
         

         Transaction time [in seconds] vs avl.Tree size [in entries]

2. gnoland on-disk insertion time vs. avl.Tree size

   1. Decription: We repeated the same test as above, but for using gnoland instead of gnodev. We tested the limits of memory consumption (to manage the avl.Tree) when using gnoland. The test is described in detail in the PR 1583
   2. Test results:
      1. the insertion time remains flat (aprox. 5 seconds for adding 500 posts) regardless of the size of the avl.Tree. (Note that 5 seconds is the configured gnoland transaction time.) During testing we used an avl.Tree of max 1M entries.
      2. No limitation was observed for using a large avl.Tree in the case of gnoland on-disk.
         

3. gnoland RAM vs. avl.Tree tree size

   1. Decription: testing how much RAM memory is needed to manage on-disk storage (for gnoland). The test is described in detail in the PR 1583
   2. Test results: starting from a baseline of 330 MB RAM for 0(zero) posts, the increase is linear up to 418 MB RAM after 1 million posts were stored on disk. That's 88 bytes per post, which is much more reasonable than 20,000 bytes per post for in-memory storage with gnodev.
      

Memory storage [in MB RAM] vs number of posts stored on disk

Conclusions & Recommendations

From the tests it is clear that the performance of gnodev is limited in the case of large avl.Trees containing more than 225,000 posts.

In contrast, in the case of using gnoland on-disk, the memory consumption and the insertion time remains acceptable even in the case of large avl.Trees at least up to 1 million posts, with no significant performance degradation expected beyond this limit.

Our recommendation is to use gnoland on-disk storage when managing large avl.Trees. When gnodev supports on-disk storage, we recommend repeating the experiments using this option.

Investigate the limits of an avl.Tree behavior with respect to queries, insertions, gas limit

Objective

The idea behind it is to see if we can determine if a certain operation (like a lookup for the posts of a user’s feed/wall) can be performed within certain gas limits. Specifically, perform a certain operation when there are millions of entries (e.g. posts on a user’s feed/wall) and keep the gas cost below a certain limit.

Tests Description & Results

We performed 3 tests:

1. on-disk storage space vs. avl.Tree tree size

   1. Description: First of all, we wanted to make sure it is possible to have gigantic avl.Trees within reasonable on-disk storage space. Using the stress-test code from PR 1583 (same as above) we inserted up to 20M posts in the avl.Tree, monitoring the total size of the gnoland-data storage folder.
   2. Test results: As expected, on-disk storage space is mostly linear with avl.Tree size. 20M posts (with negligible message text size) requires 46 GB of disk space. This is 2300 bytes for each post. Since 1 TB of disk space is common, storage space is within limits.
      

2. gas for 500 lookups vs. avl.Tree size

   1. Description: As the avl.Tree gets larger, we want to know if the gas needed to look up an entry in the large tree is acceptable. Using the same stress-testing code as above, we added up to 20M posts to the avl.Tree . At intervals of tree size, we called a realm function which does 500 entry lookups, and recorded the gas used.
   2. Test results: A tree size of 1M posts needs about 8,300,000 ugnot to do 500 lookups. At a tree size of 20M posts, this only increases to about 8,500,000 ugnot. This is reasonable. The chart’s Y axis extends to 10,000,000 ugnot which is a typical limit to the amount of gas spent on a function call, so this is within the typical limit. Most realm functions do not need to do anywhere close to 500 lookups. Furthermore, the gas needed only increases slightly due to large tree size.
      

3. gas for one insertion vs. avl.Tree size

   1. Description: As the avl.Tree gets larger, we want to know if the gas needed to insert a new entry in the large tree is acceptable. Using the same stress-testing code as above, we added up to 20M posts to the avl.Tree . At intervals of tree size, we called a realm function (CreateReply) to insert one entry, and recorded the gas used.
   2. Test results: Test results: A tree size of 1M posts needs about 2,500,000 ugnot to do one insertion (plus the other operations of the realm function). At a tree size of 20M posts, this only increases to 3,000,000 ugnot. This is reasonable. The chart’s Y axis extends to 10,000,000 ugnot which is a typical limit to the amount of gas spent on a function call, so this is well within the typical limit. Furthermore, the gas needed only increases slightly due to large tree size.
      

Conclusions & Recommendations

From the tests it is clear that if a realm needs to store millions of entries in an avl.Tree, this can be done within reasonable limits of on-disk storage space and gas needed for insertions and lookups. We recommend that developers can proceed with designing their realm without needing to worry about issues with a large avl.Tree size.

Here is a link to an xls file containing the consolidated data (including the graphs) of the tests described above
avl_gas_tests_data_updated.ods

Other findings and investigations

Beyond the scalability tests described above, below is a list of other observations worthy of consideration.

1. Stability related findings:
   1. Occasional freeze of the gnoland node was observed during testing. We created a txtar test which reproduces the problem. The Gno devs have discussed the problem, but it is still not resolved. Clearly, it’s undesirable for the gnoland node to freeze, and we recommend this issue should be resolved before deploying a public gnoland node.
   2. Except for this occasional issue, we found the gnoland node to be efficient even with large data storage.
2. Gas limit findings for the case of processing large amounts of data

Problem statement: Gno.land has a gas limit of 100,000,000 ugnot per transaction. As shown above, this is enough for many types of operations. But some operations need to process lots of data or do high-CPU operations which exceed the gas limit. For a first example, the avl.Tree can store millions of posts, but only a few hundred can be fetched in in transaction within the gas limit. For a second example, the “home feed” is the user’s own posts plus the posts of all followed users, sorted by time. There can be hundreds of followed users and hundreds of posts each to be sorted into the home feed, which is takes too much CPU for gas to do in one transaction.

For the moment, we see 3 potential solutions to address this issue:

1. Solution 1: Pagination. The solution to the first example (fetching many posts), the solution is straight-forward. The avl.Tree already supports fetching items by index. So, the function GetThreadPosts has params startIndex and endIndex so that the caller can iteratively fetch each “page” of messages.
2. Solution 2: App-specific indexer. The solution to the second example (too much CPU) uses the tx-indexer plus an application-specific indexer. The tx-indexer runs on a separate server and maintains a live database of all transactions on the blockchain. The application-specific indexer queries the tx-indexer database for specific transactions and maintains a complex in-memory data structure which is independent of the blockchain and doesn’t require gas. Finally, the user app queries the application-specific indexer, in this case to fetch IDs of the “home feed” posts. To be secure, the text of the actual posts is fetched from the blockchain which is the single source of truth.
3. Future solutions - opportunities to be developed
   • Application specific indexer framework: We plan to generalize our application-specific indexer into a framework which other projects can use in developing their app. The app needs to communicate with the API of the indexer, and we have already solved with problem using gRPC. An indexer framework relieves the developer from needing to re-implement this communication or other functionality.
   • Inter-blockchain comms (IBC): Another proposed solution for data-intensive apps is to distribute storage and computation among parallel blockchains. Gno.land was designed to work with IBC, so this can be explored in conjunction with the other solutions mentioned above.