Hi, good library, I’ve been working on something similar like 2 months ago: GitHub - hissssst/nanolsm: Tiny Elixir LSM KV implementation. I love how in the recent months there have been like 4 new embedded Elixir DB projects published. Maybe we should start a discord server about it, hehe

I’ve read your code and I have these questions and notes:

1. What’s your plan for the library? Do you have any new planned features in mind?
2. What’s the point of write lock on the sst? SST is written once, by a single process, during compaction and is never accessed before the compaction finishes
3. What’s the point of read lock on the sst? Every access to SST is opening a new file descriptor and SSTs are immutable (in a sense that files are only written once, and deleted)
4. Do you plan to have block cache?
5. It seems that read path calls singleton (per Goblin instance, not global) Goblin.Store genserver. Why? I’d suggest to use the ets with the names of opened files and key ranges
6. You use :file module which spawns a process with a new file descriptor on every read call and essentially introduces a copy (while message passing) on every read. You don’t share the descriptor between processes, so I’d just suggest to use a :prim_file instead, to avoid copying or use opened :file descriptors and store them in ets (from the point 1)
7. I see you also implemented memtable as a map which is stored in singleton genserver. Why? I’d suggest to use ets too
8. As far as I can see, if a process dies during transaction, Writer will have the copies of the old memtables forever in it’s state. This sounds like a bug
9. In writer, has_conflict checks are performed against state.transactions[pid].commit which is always an empty list, and it looks like these conflict checks must be implemented against current memtables in the writer. Looks like a bug
10. Looks like WAL is not writing to disk on every call which can result in data losses. This design choice must be reflected in the doc about the DB.
11. WAL does full flush of the state on the disk periodically, but I’d suggest to just append new entries for the performance and clean the state when these entries are appended to the log.

Right now the implementation has bottlenecks in reads and writes, since all reads and writes are genserver calls to the singletones (Store and Writer), has problems with WAL durability and overall performance. I would be happy to share the knowledge about implementing parallel reads and writes, improving WAL and performance

This is great, super interesting! Happy to see that CubDB is providing some inspiration, and that the ecosystem is growing Looking forward to find some time to delve into this and try it out. LSM trees definitely provide some interesting possibilities and optimizations.

If you’re talking about O_DIRECT, I agree, but such block caching is useless, since values and keys are not decoded in it and it still needs to be marshalled. I was thinking about decoded values cache with index or at least binsearch tuple, not just a “block as bytes cache”

But yeah, prim_file has other issues too. I was talking about with erlang core team about it on erlangforum and they said that they are planning to rewrite the fs modules, but they don’t have a deadlines, estimate or plan for it, and the strangest part is that I asked if I can contribute and work on the impl and they declined saying that they are unwilling to accept contributions. That was strange

Yeah. Goblin does a very interesting trick where it’s implementation of transactions uses snapshots, and these snapshots cost nothing to create when you use maps as memtables, since they are immutable by default. Very nice trick, but it bottlenecks the performance since it requires a singleton

It’s not a dark magic, enterprise databases in Erlang are using it directly. It is a NIF which wraps libc calls like pread, fopen and such. But it comes with limitations which can break the VM. One of the limitations is that it must always be uses only by a single process. It uses NIF resource mechanism which works in a way where if some process dies (or is killed) while using the resource, it will close the file descriptor. So if you share the prim_file descriptor (which just holds an integer libc file descriptor) and it gets closed in one process, other process will continue using it and when somewhere a new file descriptor is created, it will be the same number as this closed one and the process will accidentally read from the new one, breaking a lot of internal VM assumptions and potentially crashing the VM.

But if you open descriptor, never share it and use it in the process it was opened in, you’re all good

@Asd Thanks for your questions and bug finds! nanoLSM looks good and seems interesting as well, I will look more into it. I will try to answer all your questions.

1. This started as a fun project to learn about LSM databases, but the end goal is to have a generic database than can be used in some projects, either in some IoT nerves device or some mix project where necessary. It will not be as feature complete as other production LSM databases, therefore block caches will probably not be implemented at first hand unless really necessary for read performance.
2. You’re right about the SST files, the locks are completely unnecessary and can be removed altogether, which I am working on.
3. The writer and store module implementations will be changed to ets tables, good insight!
4. I use :file which normally spawns a pid for the file descriptor, but I use the :raw mode when opening a file, which opens a :prim_file descriptor instead, which you suggested, so I believe this is the same.
5. That’s a legit bug that will be fixed, processes that start a transaction should be monitored so that the Writer can clean up after the process dies during the transaction.
6. The commit list for a transaction is updated when a transaction completes while another transaction is ongoing. I’ll double-check this to make sure it is still correct.
7. Yep, I should definitely add to the docs that the WAL does periodical syncs and that this can potentially cause data loss if it crashes before a sync, good catch!

Please do share how you would implement parallel reads and writes, sounds interesting!

@garrison Thanks for the insights, that clears up the transaction handling. With the read/commit number, do you mean a sequence number is given to the transaction when it starts and reads for that transaction can only read below this seq no? And write/write conflicts are between the start seq no and the latest seq no in the writer then? En ets table in the writer makes a lot of sense, clearing up some of the bottleneck performances @Asd mentioned as well. I will fix the transaction handling to allow snapshot isolation and disregard serializability. Blocking flushes until there are no ongoing transactions seems like a natural implementation then.

It would be much better to actually sync before returning from transaction commit(). You should always default to proper durability guarantees. If users want to turn them off that’s their own business, but it’s best not to hand footguns to unsuspecting devs.

Generally you want to bunch a number of transactions together before syncing the WAL. This optimization is known as “group commit”. After the batch is committed you then unblock the clients’ commit calls.