10

Description:

RocksDB is a key-value storage so we can simply serialise the list of objects & store the value corresponding to a key. This would be ok if the data in the list is small enough.

But if the list is large and ever increasing in size then we would need the data paginated. So in this case storing the entire serialised list data corresponding to a single key would not be a good idea; as there would be a performance issue since every time a new data is inserted into the list this very large value would need to be read & updated also during read time when showing list to user entire value would be retrieved while only a part of it was needed by the user.

Ex: Let’s say we want to store orders placed by user in rocksDB. Then we could store this order data in following way in RockDB “u:1:li:o” : Serialised([O1{}, O2{},….On{}]). But if there are thousands of orders placed by user and we would like to retrieve the orders in form of pages (10 or 20 records at a time). So storing thousands of order in same key and retrieving entire data from that key & then giving required 10-20 records won’t be a good idea. Also adding new order by user to same key will affect the performance as described above.

So I am working to design schema for efficiently storing and retrieving such large lists in RocksDB.

If you can give your suggestions on schema design that would be great & very much helpful.

1
  • Will you only add to the end of the list or will there be new items added to the middle of the list? Will any list item ever be updated? Commented Jun 10, 2020 at 4:21

1 Answer 1

2

you need to split your "large list" into a set of nodes of a "Segment B-Tree" and then store each node one as a RocksDB record.

Each node will need to store it's Height in the "Segment B-Tree" and it's left child ID.

This have a number of benefit

  1. This will let you find if one entry is inside the list without having to scan the whole list.

  2. Scanning all the leaf node would be fast because leaf node have contiguous ID

  3. This let you easily fetch any subset of the list using offset.

See : https://www.sqlite.org/fts3.html for more detail.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.