Efficiently store large list structure in RocksDB so that the data can be retrieved in pages

Question

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.

Martines

@Pinank What is the programming language that you use? – Trichomonad

@Trichomonad Golang – Martines

Does this answer your question? store list in key value database – Trichomonad

I'm not familiar with RocksDB, but a relational database could implement next page fetching efficiently via so called "keyset pagination" (aka. "index method") - take a look at the graph at the bottom of this article. Perhaps you can do something similar? – Gerik

Answer 1

The trick is to flatten/explode the list into many keys. So instead of a giant list in a single key you want to spread it across many keys. A 10 item list would have 10 key/value pairs

The key would be structured as schema#primarykey#listname#index

Then you can paginate the list by doing a prefix scan from schema#primarykey#listname#fromIndex to schema#primarykey#listname#toIndex

Menu