Luna engine

[huachaohuang]

I'd like to propose the first flagship engine for Engula here. I name it Luna, aka engula-luna-engine.

While I have some favorite ideas discussed here before, I also agree that it is more reasonable to start with simpler semantics at this moment. See also some background discussions here. So I decided to propose a more straightforward data model here.

I think the following APIs are intuitive and familiar for RocksDB users.

impl Database {
    fn open(url) -> Result<Database>;

    fn collection(&self, name) -> Result<Collection>;

    fn create_collection(&self, name) -> Result<Collection>;

    fn commit(txn: Txn) -> Result<()>;

    fn snapshot(ts: T) -> Result<Snapshot>;
}

impl Txn {
    fn put(&mut self, key: K, value: V);

    fn merge(&mut self, ...);

    fn delete(&mut self, key: K);
    
    fn assign_timestamp(&mut self, ts);
}

impl Snapshot {
    fn get(&self, key: K) -> Result<V>;

    fn iter(&self) -> Iterator;
}

Some highlights:

• Use collections instead of column families from RocksDB because I think "collection" is a more general concept than "column family".
• Both database-level and collection-level transactions and snapshots are supported.
• Things like sharding and distributed transactions (if any) should be handled inside the engine. So users can use this engine to build standalone or serverless databases in the same way. For transactions and consistency, we may also use the Ordering semantic to allow users to configure the concurrency level.
• Support user timestamps as a first-class citizen, which is a very useful feature for many databases. RocksDB is also trying to support such a feature, you can check it here.

TODO: I will add more descriptions later.

[zojw]

do we need to take care of range operation(range delete, range set, point iterator over them, compact range) as a first-class citizen in the initial phase, it's the buggy & complex feature for the previous storage engine, but sometimes it overcomes the big shortage of KV abstraction, can we do it better if we take it at init phase - -?

without range support, some situation is hard to use, e.g.

• delete/set a key range, delete from t where pk_id < 100000, update t set v = 10 where pk_id < 10000 or truncate a partition or delete a redis set
• lock a key range, select * from t pk_id < 1000 for update

maybe it will impact the impl for us - -

we also can get some input from cockroachdb/pebble#1339 and it's RFC

[huachaohuang]

Good point. Range operations are very useful in some cases. So we can start with thinking about how we can support things like range deletions better than scan + delete. RocksDB takes a very long time to get the range deletion really work. Not sure if we can do it better yet.

BTW, what do you expect the engine to do for select * from t pk_id < 1000 for update?

[zojw]

BTW, what do you expect the engine to do for select * from t pk_id < 1000 for update?

I have no very clear picture about how to impl range lock :) , maybe.... we can lay down a replicated range lock(intent) recorder like LockPrefix-startKey-endKey-ts ---> lock-meta... and let other query's scan can observe the lock recorders and wait on it - -？

[zojw]

expect range, it seems the lock record also can be optimized to the only store in memory without persisted and replicated...

it seems @sticnarf and @Little-Wallace have a great RFC about memory lock record ~ what do you think about "Does new operation supported by the engine can help users implement functions like rfcs#77?" @sticnarf @Little-Wallace , thanks 😄

[sticnarf]

To my understanding, we should be providing an optimistic transaction instead of a pessimistic transaction used in RDBMS?

I don't have a clear idea about how a user can implement something like a pessimistic transaction with the engine at first thought. Maybe providing a watch method is good for informing when a lock is released. And for in-memory locks, perhaps some options can be specified to let the engine not persist?

I don't think it a good idea to target such a complex requirement at this stage...

[huachaohuang]

We may also support something like containers. A container is a set of related key-value pairs. For example, users can store a list/dict in a container. Then the engine can provide some advanced operations to manipulate containers. For example, deleting a container all together, or keeping a container in the same thread/node to avoid distributed transactions alike.

[tisonkun]

It seems like you're defining a more general replacement than Range here that can batch arbitrary key-value pairs. I'm wondering whether it would be useful since a Range is a series of continuous key-value pairs, but manipulating arbitrary key-value pairs seems naturally by transaction. For colocating, it seems like a requirement of placement rules on scheduler that can be an orthogonal function.

[huachaohuang]

As for the thread model, I am also interested in the thread-per-core model. Each thread handles its own part of data and communicates with other threads (no matter locally or remotely) with messages. The message communication can be adjusted depending on the consistency level users require. For example, if we consider each key-value pair as an atomic variable, users can use Ordering::Relaxed to indicate a weak consistency, so that we don't need to do any synchronous message passing. This idea is similar to Anna.
Of course, thread-per-core also brings some problems like load balance. So we may try to re-schedule data shards/partitions between different threads according to some load statistics periodically.

[huachaohuang]

A thread-per-core model can make a lot of things easy. From memtable implementation to the Rust asynchronous runtime based on io uring.

[huachaohuang]

It also unified the concept of scheduling and transactions on the same node and cross nodes. Because there is no difference between a thread running locally and remotely.

[sticnarf]

Yes, I agree a thread-per-core model usually performs better and easier to develop than a SEDA model. Learnt from the experience of TiKV, the SEDA model increases the burden of the OS scheduler and brings much pain implementing necessary flow controls .

[huachaohuang]

Maybe we can consider renaming it to table-engine and set its goal to optimize for relational databases somehow. In the future, we can add something like graph-engine and stream-engine, respectively. Any thoughts?

[huachaohuang]

I think one engine can't serve all workloads, after all.

[tisonkun]

Can you outlines points about "optimize for relational databases"? I'm afraid of risks that we'll finally need a real-world relation database to scaffolding works; otherwise we're working for unreal requirements. A collection API is easier to understand and customers can start play with it without implementing a relational database.

In the other hand, if the table-engine in your mind is something provide KV API with index and transaction support, then it will be totally great to have.

While it's still optimized for relation databases, emphasizing what we'll achieve and users can play with without implying a relational database should be implemented, is a better marketing strategy. I'm afraid if you describe as if we're implementing something one should play with a by implementing a relation database, most people will simply give up to learn what it really is.

[tisonkun]

Let me give more background here:

A table-engine looks good from my perspective. The concern I speak for here is the expression, not the actually things we'll do.

So far, Engula always comes with a connection with (relational) databases. It's totally OK as a eventual goal, but people who want to implement a database today will seldom choose Engula before it's mature. At the moment, they will choose RocksDB or Pebble as a start point, and think Engula no much differences than writing their own from scratch.

However, we're still willing to get users to give feedbacks as well as contributions if they want to. With several offline discussion with potential users and contributors, they can hardly get the picture about where Engula wants to go (ref1, ref2, ref3). Even if Engula is a challenging project requiring background, this's a signal that we use unusual nouns which users cannot catch up the idea quickly.

We're not a relational database ourselves. Building a relational database is non goal of Engula. We're a storage engine. I suggest out competitors might be InnoDB, RocksDB, and even Redis. A distributed KV engine (Redis/RocksDB) with transaction and index support is easily to understand and users can later learn from how Engula is adaptive for other workload. A distributed pandas is also expressive for its table API usages.

To sum up, I agree to build a table-engine, but hesitate to emphasize "relational database" a lot. Instead, I suggest to use understandable analogies. Anyway, we don't write the relational database, and no one plans to write their database on Engula yet.

[tisonkun]

@huachaohuang thanks for starting this thread! I like the name table-engine and the API outlines above.

It looks like we're working for a (Transaction)RockDB replacement which is extended to be deployed on cloud-native environment and more elastic storage/journal implementation (besides local file sys, it can be s3, ozone, etc.). As mentioned above, still we can keep figuring out optimizing for relational database workload, but our milestone is the collection API itself.

I notice that the API of Collection is missing above, could you define it? As the naming issue of column family vs. collection, I have one concern that "collection" can be "map", "linked list", "set" from a developer perspective, while column family is key-value pairs with namespace (k-k-v). Do you consider supporting a flexible collection API like Redis?

For "container" concept, I'll comment on the subthread.

[huachaohuang]

After some offline discussions with some contributors, we agreed that we should keep the engine API simple at this stage. Here are some of our considerations:

• Talking too much about different kinds of APIs and other potential features we can do makes some users and contributors very confused about the project. So we should prioritize delivering a practically usable "thing" with some solid quality first.
• A simple API lets us focus on the underlying technical problems (reliability, scalability, ...) at the early stage, instead of keeping discussing what fancy API we can provide back and forth.
• A reliable and cost-effective key-value engine is actually good enough for a lot of applications. Considering that people have built all kinds of applications on RocksDB, we think a simple key-value API can be very competent too.

However, I think transactions are still significant to a lot of applications. So I suggest positioning the Luna engine to be a transactional key-value engine with the following features:

• Logical hierarchy like universe/database/collection (optionally, "bucket" or "container", not a priority for now)
• Hash/range partitions
• Different consistency/isolation levels
• All the serverless features inherent from Engula's architecture

If it sounds right, I may start prototyping some interfaces to bootstrap the development of v0.3. I think we don't need too many beforehand discussions, as long as we have a clear position. Things can always be improved, after all.

[JaySon-Huang]

Hi~I'm curious about the importance of the table engine (or luna engine) in engula. Would a minimal viable product of table engine be in the milestone of a more formal version like "v1.0.0" or "v2.0.0"? What else would be included in "v1.0" in your image?

[huachaohuang]

What's your expectation of a table engine?