Hello ResilientDB community, I'm sharing PR #254 <https://github.com/apache/incubator-resilientdb/pull/254> to get feedback on the composite keys feature (Issue #180 <https://github.com/apache/incubator-resilientdb/issues/180>).
I'd like to explain the motivation and design so the community can weigh in on the approach. The deeper implementation writeup can be found in the PR description. *Background:* The KV interface within ResDB is a primary-key store. The application is exposed these methods through the client SDK to interact with the KV store (SET, GET, GETALLVALUES, GETRANGE). Their function is to persist it on disk and retrieve the keys. The two basic methods are: int Set(const std::string& key, const std::string& data); std::unique_ptr<std::string> Get(const std::string& key); ResilientDB doesn't interpret what's inside data, it is up to the application owner to decide its encoding (text record, JSON or something else). Get returns the same std::string that was passed to Set. *Problem Statement:* ResilientDB users currently have no efficient way to query by secondary attributes. In other words, the KV interface only lets you look up records by primary key. There exists no direct way to query ResDB to fetch all records where some attribute equals X. This is a common need for any application using ResilientDB as a document store (for ex: ResLens, ResCanvas). Currently, if an application needs to perform a lookup based on a secondary attribute, it requires these steps: - Scanning all N records in the database - Filtering each one in the application - O(N) cost, even if only 1% of records match The cost scales linearly with the dataset. Composite keys can help solve this by using LevelDB's sorted-key property, letting the database itself do the filtering. *Approach:* Before any implementation, I explored how similar comparable systems handle secondary lookup on top of a sorted KV store. The Hyperledger Fabric database has a similar shape <https://pkg.go.dev/github.com/hyperledger/fabric-chaincode-go/v2/shim#ChaincodeStub.CreateCompositeKey> under the hood as ResilientDB with a sorted KV store and deterministic execution on a replicated log. In their system, they encode the attribute into the key itself under a reserved region of the key space. A composite key is an index entry, i.e, a marker pointing from an attribute value back to a primary key. Since LevelDB persists keys in a lexicographically sorted order; Leveraging this property with composite keys, all matching records will end up in a small contiguous slice on disk and a subsequent prefix scan will return them directly to the application. Internally, it will use a combination of levelDB’s seek() iterator and bloom filters to achieve this. The cost is O(log N) to position the iterator at the start of the matching range (the seek) and O(M) to walk the M matching keys giving O(log N + M) total, versus O(N) for the current scan and filter approach. *What the PR does:* - Adds 4 methods to the Storage interface to enable efficient secondary indexing via composite keys: CreateCompositeKey(key), DeleteCompositeKey(key), GetByCompositeKeyPrefix(prefix), UpdateCompositeKey(old_key, new_key) - An encoder so the application doesn’t have to construct the encoded composite key themselves The format used in the PR for the encoding is as follows, inspired by the Hyperledger fabric convention: "ck" \0 index_name \0 attribute_1 \0 ... \0 primary_key \0 (null byte) is used here as the field separator because it's illegal in user-supplied attribute strings, so it can never appear inside a field. The encoder rejects inputs that contain it So, if a user with the key as their name (say “Shray”) and value as “Davis” wants to create a secondary index based on the city, it would be encoded as: ck\0byCity\0Davis\0Shray The value is empty. The key itself encodes everything (namespace, index name, attribute, primary key). The scope of this PR is intentionally narrow to include changes at the storage layer, unit testing suite for the methods added as well as a microbenchmark comparing the current method to the one using composite keys. This is my first contribution to ResilientDB and I'm genuinely excited to be part of the community and contributing. Looking forward to any feedback on the design, and happy to iterate on it. PR: https://github.com/apache/incubator-resilientdb/pull/254 Thanks, Shray Arora GGCS student at UC Davis.
