[RFC] Custom Storage Engine for SeriousDB

SeriousDB's Storage Engine

SeriousDB has grown from a simple proof of concept into a project with real community interest. The current implementation stores all data in a single serialized file (.sdb) which works well for early-stage use but does not scale very well. Our goal is to make a DB that will serve 100 concurrent operations at any given moment. This issue is an open RFC to discuss and define the requirements for a custom storage engine that will serve as the foundation for SeriousDB's next phase.
We would love input from the community before any implementation work begins.

I was thinking of moving from a single .sdb file to a directory-based layout that separates raw data, B-tree indexes, and WAL segments into their own folders. This would make concurrent access safer and each component easier to manage independently, but we want to hear from people who have worked with embedded storage engines before we commit to anything. If you have opinions on the layout, the concurrency model, the indexing strategy, or anything else engine-related. Please share your opinions and thoughts below.

I’d suggest starting with two ideas:

B+ tree for disk-based storage/indexing, so the database doesn't need to keep the entire dataset in memory.
Many readers / one writer for concurrency. This could allow reads to happen in parallel while keeping writes serialized initially, which should be simpler and safer to implement.

A rough architecture could be:

        SeriousDB API
               │
        Storage Engine
       ┌──────┼──────┐
       ▼      ▼       ▼
   B+ Tree    Buffer    WAL
               Pool
                │
               Disk

And the concurrency model:

Reader ──┐
Reader ──┤
Reader ──┼──> Storage Engine
Reader ──┤
Reader ──┘          ▲
                     │
                    Writer
              (one at a time)

For example, the storage layer could eventually expose something as simple as:

db.set("key", "value")
value = db.get("key")
db.delete("key")

while the B+ tree, buffer pool, and WAL remain internal implementation details.

I think this gives us a relatively simple first step toward the 100-concurrent-operation goal without trying to solve multiple concurrent writers and transactions immediately.

I was also leaning in towards the same idea

@danieldeer

@danieldeer can we get your thoughts on this as well?

@danieldeer

I was also leaning in towards the same idea

This will probably take a lot of work but if we can get a plan in place we can have multiple people working on different parts.
This have to wait till @danieldeer gives his thoughts though

can i join you guys as well?

@VihaanReddyM

@VihaanReddyM and @mohammedFawzy0111 I think those will make scaling a lot better for the end user.
Im open to work on some parts on this too, if we divide the work, I would like to also work on some parts.

One question for @mohammedFawzy0111 I just wondered how you did those graphs, they look a bit AI generated... No offense

@VihaanReddyM

@VihaanReddyM and @mohammedFawzy0111 I think those will make scaling a lot better for the end user.
Im open to work on some parts on this too, if we divide the work, I would like to also work on some parts.

One question for @mohammedFawzy0111 I just wondered how you did those graphs, they look a bit AI generated... No offense

Yea I think we should split the work but before that let's make a solid plan on what all needs to be implemented for this and from there we can split it and go from there.

@VihaanReddyM and @mohammedFawzy0111 I think those will make scaling a lot better for the end user. Im open to work on some parts on this too, if we divide the work, I would like to also work on some parts.

One question for @mohammedFawzy0111 I just wondered how you did those graphs, they look a bit AI generated... No offense

The image one IS AI. I fed it the idea and how I want it to work I wasn't at my pc then but I reviewed it. The text ones I did myself though.

@VihaanReddyM and @mohammedFawzy0111 I think those will make scaling a lot better for the end user.
Im open to work on some parts on this too, if we divide the work, I would like to also work on some parts.
One question for @mohammedFawzy0111 I just wondered how you did those graphs, they look a bit AI generated... No offense

Yea I think we should split the work but before that let's make a solid plan on what all needs to be implemented for this and from there we can split it and go from there.

I can work on a plan but it will take some time because I am currently at a 12 hours shift

@VihaanReddyM

Okay I will start by explaining my idea @VihaanReddyM @mattsva @IndicKangaroo @danieldeer

So the idea is as follows:

We have a B+ tree that manages our data into leaf and internal nodes. It's responsible for insertion, deletion, search, splitting, etc. but doesn't necessarily have anything to do with disk I/O.

We need a simple DiskManager that has only two basic responsibilities: reading raw bytes from the ".sdb" file and writing raw bytes to it. It shouldn't know anything about B+ trees or keys and values.

Then we need a bridge between those raw bytes and Python objects — a Serializer.

A leaf in the B+ tree represents a page.

What is a page? It's simply the fixed-size block of data that we read from or write to disk at once. A size such as 4096 bytes (4 KiB) is a reasonable starting point since it gives us a predictable fixed-size unit for disk I/O.

That means our ".sdb" file is made up of pages:

.sdb

│ Page 0       │ 4096 bytes
──────────────
│ Page 1       │ 4096 bytes
──────────────
│ Page 2       │ 4096 bytes
──────────────
│ ...          │

So, ideally:

file_size % 4096 == 0

Each page contains a header followed by its actual data. The header tells us things such as:

What type of page this is (leaf or internal)
The page's ID
How many keys are currently stored
For a leaf, the ID of the next leaf
Other metadata we may need later

After the fixed-size header comes the page's payload.

For a leaf page, this could look roughly like:


│ Header        │
──────────────
│ Keys          │
───────────────
│ Values        │
───────────────
│ Free space    │

      4096 bytes

For an internal page, instead of values we store child page IDs:

│ Header        │
───────────────
│ Keys          │
───────────────
│ Child IDs     │
───────────────
│ Free space    │

      4096 bytes

The important part is that the page has a fixed size. If a page contains fewer keys than its maximum capacity, the remaining space is simply unused/padded for now.

The number of key/value pairs we can fit into a page depends on the representation we choose for keys and values. For example, if both are fixed-size 8-byte integers, each pair needs 16 bytes, plus the header and any other metadata.

This is also why the serializer needs to know the exact binary representation we're using. It is responsible for turning something like:

_Node(
    keys=[10, 20, 30],
    values=[...],
)

into exactly 4096 bytes, and doing the reverse when we read that page back from disk.

The B+ tree therefore doesn't need to know whether a node came from memory or from disk. It just works with nodes/page IDs, while the lower layers deal with turning those nodes into persistent pages.

Eventually the flow becomes roughly:

             B+ Tree
                │
                ▼
        │ Python _Node  │
                │
           Serializer
                │
                ▼
        │ 4096 raw bytes│
                │
           DiskManager
                │
                ▼
             .sdb file

The key idea is that the B+ tree deals with structure, the serializer deals with representation, and the DiskManager deals with persistence.

We can build these pieces independently and then connect them together.

I am bad at explaining things so if you don't get anything feel free to ask

I do understand the concept and I actually know what a B+ tree is. We have a large amount of data, and the B+ tree keeps the keys sorted in big nodes, so we don't have to search through everything (that would be too slow). We only look at one node per level and follow the separator keys down until we reach the exact leaf where the key should be. The leaves hold the actual data and are linked together, so range scans are fast too.
Am I about correct?

@VihaanReddyM and @mohammedFawzy0111 I think those will make scaling a lot better for the end user.
Im open to work on some parts on this too, if we divide the work, I would like to also work on some parts.
One question for @mohammedFawzy0111 I just wondered how you did those graphs, they look a bit AI generated... No offense

Yea I think we should split the work but before that let's make a solid plan on what all needs to be implemented for this and from there we can split it and go from there.

I can work on a plan but it will take some time because I am currently at a 12 hours shift

Take your time

I do understand the concept and I actually know what a B+ tree is. We have a large amount of data, and the B+ tree keeps the keys sorted in big nodes, so we don't have to search through everything (that would be too slow). We only look at one node per level and follow the separator keys down until we reach the exact leaf where the key should be. The leaves hold the actual data and are linked together, so range scans are fast too.
Am I about correct?

That sounds about right. I also wanted to ask about write operations. Since Python can handle concurrent reads during I/O, how does it manage writes? Is there any way we can make the write process faster or concurrent?

I will open 3 sub issues for the following

B+ Tree Implementation

Disk Manager Implementation

Linking the Tree and the Manager together

If you want to work on any of these pls make sure to read the plan we have already (it was discussed earlier in this issue) and you can give description of how you will implement, from there if there are multiple people interested I will choose one if not I will give it to the only one interested.

You all ok with this?

Sounds like a good plan. There is a lot who want to contribute so any of them can comment their plan to implement the corresponding features.

@VihaanReddyM

Hi @VihaanReddyM, I'd like to take the Disk Manager sub-issue. I've read the plan in this thread and the db-engine branch (storage_format.py, serializer.py, types.py, exceptions.py) and tried to match what's already there.

Scope

Raw fixed-size page I/O on the .sdb file and nothing else. It knows nothing about B+ trees, keys or records, and it doesn't call PageSerializer. The file offset of a page is page_id * PAGE_SIZE, which fits the serializer taking the page ID as an argument.

API (new `disk_manager.py`)

DiskManager(path), usable as a context manager, plus close()
read_page(page_id) -> bytes: exactly PAGE_SIZE bytes, ready for deserialize() / deserialize_metadata()
write_page(page_id, data): takes the output of serialize() / serialize_metadata()
allocate_page() -> UInt32
page_count
sync()

Behavior

Open: creates the file if missing. If it exists, file_size % PAGE_SIZE == 0 is required, otherwise it raises. It never reads page 0 or checks the magic number (deserialize_metadata does that), and unlike Cache.load it never renames or replaces a bad file. The layer above decides what to do.
Reads: out-of-range IDs raise. Partial reads are retried, and EOF before a full page is an error.
Writes: len(data) == PAGE_SIZE and an existing page are required. Only allocate_page grows the file.
Allocation: appends one zero-filled page and returns its ID, raising if the ID would exceed the UInt32 limit. On a new file the first call returns 0, so the upper layer must allocate and write page 0 before anything else. I'll document this in the docstring.
Durability: write_page doesn't fsync. sync() calls os.fsync, like WriteAheadLog.append, so the WAL-before-data ordering can be decided later.
Threading: use os.pread / os.pwrite where available, so concurrent reads don't share a file offset. Fall back to a lock around seek + read/write on Windows. Reader/writer and cross-process locking stay in the concurrency manager.
Errors: OS failures propagate as OSError, as in the existing code. Invariant violations (bad page ID, wrong size, misaligned file) raise a new DiskManagerError(ApplicationError) in exceptions.py.

Questions

Page 0: who writes the initial page 0 for a new database? I'd suggest the DiskManager stays dumb and the layer that owns SdbMetadata writes it right after open.
Page count: SdbMetadata.total_page_count and the file size can disagree, for example after a crash between allocating and updating metadata. I'd treat the file size as the DiskManager's truth and let the higher layer detect a mismatch. page_count would be re-read from the file when an ID looks out of range, so a reader doesn't reject pages another process just allocated. Free-list reuse stays above the DiskManager.
Torn last page: a crash during allocate_page can leave a partial last page, which "raise on misalignment" would turn into an unopenable database. I'd raise by default and add an explicit repair option (truncate to the last whole page) for recovery, similar to WriteAheadLog._repair_torn_tail. Is that acceptable?
Target branch: contributing.md says PRs target main, but this work lives on db-engine. I'll target db-engine unless you say otherwise.

Tests (pytest, `tmp_path`)

allocate, write and read round trips; reopen and read back
misaligned file rejected; wrong-size write rejected
out-of-range read and write; write to an unallocated page rejected
a freshly allocated page reads as zeros, which deserialize rejects
a short read is retried and EOF raises
use after close() raises
page 0 can be allocated and written first
page_count and file size stay aligned
concurrent readers and writers never interleave pages

I'll keep the PR focused on this, in Draft until ready, and follow the repo conventions (ruff, ty, NumPy docstrings, Conventional Commits, regenerated docs/reference/ for exceptions.py). Engine benchmarks for these operations could be a follow-up on top of #212.

@VihaanReddyM

looks solid to me. as for your questions:

I think the disk manager responsblity is data I/O so it should dump and only know how to write or read a page or allocate an empty one.
I agree to let page count determined throught file size and when detecting mismatch we update or make some kind of a check using a hash checksum or something.
torn pages indeed could be a problem I would go with a recovey method as you suggested and leave the decision to the caller.
yes push to db-engine so we don't pollute main with unfinished features or files.

waiting for @VihaanReddyM opinion on this.

@mohammedFawzy0111

thanks @mohammedFawzy0111 for proposal review, i agree the DiskManager stays dumb, and page checksums and the total_page_count mismatch check belong in the serializer/metadata layer. I'll hold off until @VihaanReddyM confirms the scope and assigns the sub-issue.

Hi @VihaanReddyM, I'd like to take the Disk Manager sub-issue. I've read the plan in this thread and the db-engine branch (storage_format.py, serializer.py, types.py, exceptions.py) and tried to match what's already there.

Scope

Raw fixed-size page I/O on the .sdb file and nothing else. It knows nothing about B+ trees, keys or records, and it doesn't call PageSerializer. The file offset of a page is page_id * PAGE_SIZE, which fits the serializer taking the page ID as an argument.

API (new disk_manager.py)

DiskManager(path), usable as a context manager, plus close()

read_page(page_id) -> bytes: exactly PAGE_SIZE bytes, ready for deserialize() / deserialize_metadata()

write_page(page_id, data): takes the output of serialize() / serialize_metadata()

allocate_page() -> UInt32

page_count

sync()

Behavior

Open: creates the file if missing. If it exists, file_size % PAGE_SIZE == 0 is required, otherwise it raises. It never reads page 0 or checks the magic number (deserialize_metadata does that), and unlike Cache.load it never renames or replaces a bad file. The layer above decides what to do.

Reads: out-of-range IDs raise. Partial reads are retried, and EOF before a full page is an error.

Writes: len(data) == PAGE_SIZE and an existing page are required. Only allocate_page grows the file.

Allocation: appends one zero-filled page and returns its ID, raising if the ID would exceed the UInt32 limit. On a new file the first call returns 0, so the upper layer must allocate and write page 0 before anything else. I'll document this in the docstring.

Durability: write_page doesn't fsync. sync() calls os.fsync, like WriteAheadLog.append, so the WAL-before-data ordering can be decided later.

Threading: use os.pread / os.pwrite where available, so concurrent reads don't share a file offset. Fall back to a lock around seek + read/write on Windows. Reader/writer and cross-process locking stay in the concurrency manager.

Errors: OS failures propagate as OSError, as in the existing code. Invariant violations (bad page ID, wrong size, misaligned file) raise a new DiskManagerError(ApplicationError) in exceptions.py.

Questions

Page 0: who writes the initial page 0 for a new database? I'd suggest the DiskManager stays dumb and the layer that owns SdbMetadata writes it right after open.

Page count: SdbMetadata.total_page_count and the file size can disagree, for example after a crash between allocating and updating metadata. I'd treat the file size as the DiskManager's truth and let the higher layer detect a mismatch. page_count would be re-read from the file when an ID looks out of range, so a reader doesn't reject pages another process just allocated. Free-list reuse stays above the DiskManager.

Torn last page: a crash during allocate_page can leave a partial last page, which "raise on misalignment" would turn into an unopenable database. I'd raise by default and add an explicit repair option (truncate to the last whole page) for recovery, similar to WriteAheadLog._repair_torn_tail. Is that acceptable?

Target branch: contributing.md says PRs target main, but this work lives on db-engine. I'll target db-engine unless you say otherwise.

Tests (pytest, tmp_path)

allocate, write and read round trips; reopen and read back

misaligned file rejected; wrong-size write rejected

out-of-range read and write; write to an unallocated page rejected

a freshly allocated page reads as zeros, which deserialize rejects

a short read is retried and EOF raises

use after close() raises

page 0 can be allocated and written first

page_count and file size stay aligned

concurrent readers and writers never interleave pages

I'll keep the PR focused on this, in Draft until ready, and follow the repo conventions (ruff, ty, NumPy docstrings, Conventional Commits, regenerated docs/reference/ for exceptions.py). Engine benchmarks for these operations could be a follow-up on top of #212.

Hey so I have just read through this and I would be happy to assign you for this feature but Daniel gave a strict warning about AI generated content (I also mentioned, let’s discuss without AI). This wall of text looks and is formatted like something AI would write. Please don’t use AI for any of your following messages and if I find any signs of AI In the PR I will close it.

Keeping that in mind you can go ahead and start work on the disk manager and open a PR to the DB Engine branch.

One more thing, lets move all discussions about B+ Trees and Disk Manager to their Respective issue.

@VihaanReddyM

@VihaanReddyM I have a suggestion. we can work on the key/value codec layer I metioned before so the one designing B+ tree know what to expect.
it is basically a lyaer sitting between the public API and the sotrage engine we are desgining.

import seriousdb as sdb

sdb.set("key", {"value1": 1, "value2": ['a','b','c']})

in this example code we have avalue of a dict type and the design I mentioned before we can have value of any of python's datatypes.

the codec layer is reposible of encoding the keys and values into uniform format that we can pass to B+ tree without worrying about its pythonic type.

Keys should support reasonable scalar/ comparable types:

str
int
float
bytes
bool

the encoding must perserve the expected ordering of the key type so our B+ tree can compare encoded keys correctly.

Values should support arbitrary Python data types and provide reliable round-tripping.

I am asking for your opinion on this. if you agree either you or me could work on this.

Guys we need to discuss the checksum and codec. Should the checksum be implemented in the file manager or should it be its own thing?

Let's also discuss what specs the codec should have since we will be needing it.

@VihaanReddyM

Guys we need to discuss the checksum and codec. Should the checksum be implemented in the file manager or should it be its own thing?

Let's also discuss what specs the codec should have since we will be needing it.

@VihaanReddyM I don't think the checksum should be implemented directly into DiskManager.
DiskManager should stay responsible for reading/writing raw pages. A checksum is about validating the contents/format of a page, not performing I/O.
I'd make it part of the serialization/page layer,
The serializer already knows the page layout and we already have reserved space in the page header for future checksum data. That seems to me like the natural place to calculate and verify it.
One thing we should decide is what the checksum covers. I'd say the whole page except the checksum field itself. The exact algorithm can be decided separately;
I would suggest CRC32 . It would probably be sufficient for detecting accidental corruption.

As for the codec lauer I sent two messages discussing them before but my rough idea is that
I'd make the codec a separate layer from both the serializer and B+ tree.

The main requirements I'd suggest are:

For Keys

It should Support reasonable built-in types initially: str, bytes, int, float, bool, etc.
Encoding must be deterministic.
Encoded keys must preserve the intended ordering of the original values.
The encoding needs to be produce differently for similar values, so e.g. 1 and "1" don't collide.
encode() / decode() should round-trip the supported types.

For Values

Values Should support arbitrary Python objects.
encode() / decode() must round-trip the object.
Values can be variable-sized because the storage layer already has the overflow-page design.

I'd also keep the key codec and value codec conceptually separate, even if they initially share an implementation.

The important part is that the B+ tree should only see bytes. My first thought was pickle but I wouldn't decide on it yet. Since values are allowed to be arbitrary Python objects, it's one possible implementation, but we should first define the codec's guarantees and then choose the encoding format based on those requirements.

Sounds good let's try and merge the B+ Tree implementation and then we can move forward from there.

Navigation Menu

Repository navigation

[RFC] Custom Storage Engine for SeriousDB #290

SeriousDB's Storage Engine

35 remaining items

Scope

API (new `disk_manager.py`)

Behavior

Questions

Tests (pytest, `tmp_path`)

Scope

API (new `disk_manager.py`)

Behavior

Questions

Tests (pytest, `tmp_path`)

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

[RFC] Custom Storage Engine for SeriousDB #290

Description

SeriousDB's Storage Engine

Activity

mohammedFawzy0111 commented on Sep 25, 2026

VihaanReddyM commented on Sep 25, 2026

VihaanReddyM commented on Sep 25, 2026

mohammedFawzy0111 commented on Sep 27, 2026

IndicKangaroo commented on Sep 27, 2026

mattsva commented on Sep 28, 2026

VihaanReddyM commented on Sep 28, 2026

mohammedFawzy0111 commented on Sep 28, 2026

mohammedFawzy0111 commented on Sep 28, 2026

mohammedFawzy0111 commented on Sep 28, 2026

mohammedFawzy0111 commented on Sep 28, 2026

mattsva commented on Sep 28, 2026

mattsva commented on Sep 28, 2026

VihaanReddyM commented on Sep 29, 2026

35 remaining items

mohammedFawzy0111 commented on Oct 4, 2026

IndicKangaroo commented on Oct 4, 2026

Scope

API (new disk_manager.py)

Behavior

Questions

Tests (pytest, tmp_path)

mohammedFawzy0111 commented on Oct 4, 2026

IndicKangaroo commented on Oct 5, 2026

VihaanReddyM commented on Oct 5, 2026

Scope

API (new disk_manager.py)

Behavior

Questions

Tests (pytest, tmp_path)

VihaanReddyM commented on Oct 5, 2026

mohammedFawzy0111 commented on Oct 5, 2026

VihaanReddyM commented on Oct 7, 2026

mohammedFawzy0111 commented on Oct 8, 2026

mohammedFawzy0111 commented on Oct 8, 2026

VihaanReddyM commented on Oct 18, 2026

Metadata

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

Issue actions

API (new `disk_manager.py`)

Tests (pytest, `tmp_path`)

API (new `disk_manager.py`)

Tests (pytest, `tmp_path`)