Show HN: A Database Written in C | Hacker News Reader

Show HN: A Database Written in C

github.com

9 pointsalexpadula22 comments

Hey hackernews! I'd like to share a hobby and passion project I've been working on for almost a year now. It's an open-source storage engine (underlying component of a database(s)) similar to that of LevelDB/RocksDB but written entirely in C.

The storage engine is called TidesDB.

TidesDB is written entirely in C. It's designed as a fast, transactional key-value storage engine built on a log-structured merge-tree (LSM-tree) architecture.

My journey with TidesDB began nearly 2 years ago whilst I was experimenting with various data structures and databases in Go. When I encountered the log-structured merge tree concept, I was initially overwhelmed by its complexity after reviewing other implementations.

However, after studying the original paper, I realized I could potentially simplify the design by focusing on just a 2-level approach(memory level and a disk level). This was challenging at first, and I scrapped many ideas along the way, but over time I discovered how powerful this design could potentially be.

The beauty of this design/architecture is its extensibility. Since the disk level contains many SSTables (Sorted String Tables), we can efficiently pair and merge them in various ways - whether in parallel for speed or incrementally to minimize resource impact.

What began as a challenging learning process has I believed evolved into a unique engine design and library.

You can check out TidesDB code here: https://github.com/tidesdb/tidesdb

Website here (Architecture-design, documentation and more): https://tidesdb.com

There are a variety of FFI libraries in the works for C++, GO, Python, Lua and more!

Currently TidesDB is nearing its first major release, we are still in beta development.

I'd love to get your thoughts, questions and all :)

Open articleView on HN

That's a cool project, thanks for sharing! Does string sorting also consider unicode (or did I get SSTables wrong)?

Hey! Thank you very much for the kind words.

The system currently sorts comparing raw byte values directly. So if I'm understanding correctly, no it doesn't handle unicode sorting. If key's were stored as strings and compared that way, yes. :)

Ok, I see. I implemented an object database based on the Sqlite backend some time ago for CrossLine and other applications, which includes ideas of MUMPS and also uses unicode collating algorithms implemented in Qt, but it's c++, see e.g. https://github.com/rochus-keller/Udb/blob/master/Idx.cpp.

If you wanna know why I chose binary keys - I wanted the user to be able to use any data type, cross language support, also I believe the way we have it now is faster for comparisons I believe. I overall think this a bit more efficient than storing a string key.

That's a sensible approach, and Sqlite does it that way too. But unicode becomes an issue at the latest when you want to implement text indices. Based on your description, I assumed that your database already offers something like this up front. But of course you can also do this in higher layers.

Oh yes indeed!

I must say just off the bat and a few minutes reviewing, I'm extremely impressed. I stared the repository to play with it further later.

I have been considering for some time whether I should change the backend. LSM trees and a much simpler implementation than, for example, RocksDb seem attractive.

Yeah RocksDB is amazing so is LevelDB but there are tradeoff's with every design. LevelDB and RocksDB are very similar in design, RocksDB is a fork of LevelDB. The code bases are very large, especially RocksDB and that specific LSM tree design is pretty standardized now. TidesDB is I'd dare to almost say newer generation :)

Do you have applications which use the concurrency feature of your database?

In what way?

There are examples with integration tests currently.

The website explains some tadbits regarding concurrency quite well.

I'd need to better understand what you mean.

I am interested in your overarching objective for the database. For example, my Udb was only a means to an end, so that I could equip my applications such as CrossLine, WorkTree, FlowLine, or Herald with incremental persistence. I had considered concurrency, but never needed it. However, I had looked at various larger libraries (such as RocksDb) for a multi-user version of Crossline, for example. With RocksDb, there are numerous applications that can be studied and which demonstrate the robustness and scalability of the database. A much leaner solution with concurrency and transaction properties seems attractive, but would of course have to prove itself first.

Very cool.

I do agree, much to prove still.

If you want feel free to join the Discord and we can talk in real-time. Could be a diverse and interesting conversation.

Just discovered that you're requiring C23 which I don't have on my development machine. Actually one of the reasons I didn't continue with RocksDb yet is that they moved to a pretty recent c++ version, which I neither have. I think for infrastructure code (such as a database) it is better to take a very conservative approach to language versions (to avoid dependency domino effects).

Oh noo.

I've thought about this more than I'd like to admit. I'd need to review if it's possible to refactor a bit to work with C99+. I don't believe there would be many changes but it's been awhile writing the entire code base as it is.

Because TidesDB is in BETA v0.8.0 currently we can definitely do this. I'm curious do you use CMake? I will create an issue.

https://github.com/tidesdb/tidesdb/issues/356

I don't want to burden you with work, so don't feel obliged in any way. This is simply my opinion (there are also good reasons for newer C versions). In all my personal projects, I don't have any newer versions than C99 or C++11 (most are even C++98/03). I recently even migrated a compiler backend framework from C++17 to C++11 to use it: https://github.com/rochus-keller/eigen/. I could do the same with your code if I would use it, but first I have to move forward in other projects.

Concerning cmake: I only use it if unavoidable; instead I implemented my own build system (https://github.com/rochus-keller/busy/) some years ago which I now use for most of my personal projects.

Oh no burdens here. Would take a lot to burden me with something I love to do!

You are quite the master I'm very similar to you in that I gotta get my hands on everything haha.

I tagged yeah on the issue. I will after work have a look at the changes required to make backwards compatible. If not much, why not. I'll weigh the possible negatives if any.

Things build rather well with C99 actually. I am setting it as the default.

Ou!! really checking it out.

tried tidesdb with python and it's really fast. a transactional key-value database written in c with a modern lsm-tree architecture. worth checking out

Thank you for the kind words Ivan and your work on the Python FFI.

Reply on news.ycombinator.com