FeOphant - A SQL database server written in Rust and inspired by PostreSQL.

Overview

FeOphant

A SQL database server written in Rust and inspired by PostreSQL.

We now have support for persistent storage! Not crash safe but I'm getting there!

Latest Build codecov

Website

Launch

Launch the server ./feophant

Lauch a postgres client application to test ./pgbench -h 127.0.0.1 -p 50000 ./psql -h 127.0.0.1 -p 50000

Benchmark to aid in profiling cargo instruments --bench feophant_benchmark -t time

What works user facing

  • Connecting unauthenticated using a postgres client/driver.
  • You can create tables, insert data and query single tables.
  • Data is persisted to disk, not crash safe and the on disk format is NOT stable.

Postgres Divergance

Its kinda pointless to blindly reproduce what has already been done so I'm making the following changes to the db server design vs Postgres.

  • Rust's memory safety and strong type system.

  • Multi-threaded async design based on Tokio instead of Postgres's multi-process design.

    • Perk of this is not needing to manage SYSV shared memory. (Postgres largely fixed this but I think its still worth noting).
  • Want to avoid vaccuum for transaction wrap around. Will try 64-bit transaction IDs but might go to 128-bit.

    • I can avoid the need to freeze Transaction IDs however the hint bits will need scanning to ensure that they are updated.
  • Replacing OIDs with UUIDv4s.

  • I think I've figured out what the core divergeance from Postgres that I'm interested in. I love Postgres's transactional DDLs but version controlling a schema is awful. What if I make the database server a library and your schema is code? You supply a new binary that runs as the database server and if you need to change it you just deploy the binary instead? Then the compiler can optimize out anything you don't need to run the system in your use case. The hardest part is dealing with schema changes that affect your on disk format.

Rust Notes

How to setup modules sanely: https://dev.to/stevepryde/intro-to-rust-modules-3g8k

Reasonable application error type creation: https://github.com/dtolnay/anyhow

Library Errors: https://github.com/dtolnay/thiserror

Rust's inability to treat enum variants as a type is a HUGE pain. I end up having an enum to hold data and another enum to validate and match the sub type. The RFC to fix this was postponed indefinately.

Legal Stuff (Note I'm not a lawyer!)

I am explicitly striving for SQL+Driver compatibility with PostgreSQL so things such as system tables and code that handles them will be named the same. I don't think this violates their trademark policy but if I am please just reach out to me! I have also gone with a pretty restrictive license but I'm not tied to it if that is causing an issue for others who are using the code.

Comments
  • Improve how page handling is done

    Improve how page handling is done

    Currently all pages in the system are being handled via Tokio's BytesMut struct and related traits. This struct is awesome for giving me easy read/write methods on an underlying set of pointers.

    However I have discovered a critical issue that I am uncertain how to solve effectively.

    So right now I have a combination of features in my lock/cache system:

    • Reader/Writer locks for a given page
    • A least recently used cache of pages
    • A way to check out pages and if discarded a way to purge the cache.

    The issue I am facing is as follows:

    1. A page is is checked out for read or write.
    2. Read/writes are done to it but are discarded for any number of reasons.
    3. The next process checks out the same page.
    4. The process will not see the entire page since it has been consumed partially. This leads to interesting and painful bugs as I discovered in my index work.
    opened by chotchki 1
  • Implement page level locks that are ordered to avoid deadlocking.

    Implement page level locks that are ordered to avoid deadlocking.

    Acceptance Criteria:

    • Should be able to update a row either inside a page or not without loosing commits.
    • This is independent of transaction control so I think this sits below/in row manager.
    opened by chotchki 1
  • The number of managers in io is excessive

    The number of managers in io is excessive

    I've been using a series of layered providers I've been calling managers and its gotten overly complex.

    I need a better naming convention and package organization structure.

    opened by chotchki 0
  • Extract the creation of new page offsets

    Extract the creation of new page offsets

    Currently page offsets are generated as part of the insertion into the file system. However this results in a bad assumption in a couple layers of the stack.

    My issue is that the code ends up assuming when a new page is inserted that it will result in the logical next page.

    If I can avoid the extraction I would prefer it, we'll see.

    opened by chotchki 0
  • Implement Page Level Locking

    Implement Page Level Locking

    So I have a fully ready free space map but I can't avoid the locking issue anymore despite it also being the next item on the todo list.

    So I started trying to bake in locks and I've hit my normal do I go for a read or write lock approach? I think I may have screwed up the lock manager design, oops too much in silos!

    So what I really need in a lock manager is this:

    • multi-threaded access
    • ability to read page
    • ability to write a page without causing collisions

    I'm debating do I need to put a check-in / check-out layer on top of file manager. So I could expose an api for the following: Read - Easy ReadForUpdate - This is the hard part Ideally Append - Needs to be serialized //Ignoring Delete/shrink for now

    I should treat this as a lesson for not implementing something outside the greater system and realizing I can't integrate it.

    opened by chotchki 0
  • Implement Free Space Maps so mutation of data doesn't need a linear scan/parse non stop.

    Implement Free Space Maps so mutation of data doesn't need a linear scan/parse non stop.

    Did more thinking, I should implement postgres's streams concept so that I don't need to do lookups to find associated metadata on an object. I thought I was going to get to use Uuid+page offset. I think its now going to be uuid+page offset+ type.

    struct PageId + enum PageType should do it (done).

    opened by chotchki 0
  • Add support for defining a primary key on a table.

    Add support for defining a primary key on a table.

    This implies the following functionality:

    • Index support through the stack down to the page level.
    • The concept of unique indexes.
    • Transactional support for indexes.
    • Failure of a statement on constraint violation. Unsure if I'll end up with a general constraint system from this.

    Based on reading this really means implementing Btree indexes. They don't seem to be that bad to understand/implement.

    First and most important question, how should the index layers work? Are they transactional? (I don't think so until I implement a visability map) How should the low level layer function? Should I have an Index config struct I pass around or just a table + columns + unique or not + type Index Config it is

    Index Manager -> for a given table IO Manager -> Handle Page Load / Store / Update

    Implemented the formats but I think I need to add locking to the I/O manager. At a minimum I need to support a get for update, update and release lock. I'm not sure I understand how this should work :(. I think need to commit to another layer.

    Back to indexes for now. I need to make a decision on how to handle them hitting the file system. Postgres uses a series of OIDs to map onto disk.

    I've been using uuids, I think I'm going to continue that. That would also solve the postgres fork approach.
    

    Next up implementing the index manager to add entries to the index.

    I'm having a hard time figuring this out, I might work to do the operations on the tree before I keep messing with the serialization protocols. I'm just worries they are directly linked.

    Got further into the index manager. Unfortunately I need a lock manager to let it even pass the smell test. Time to go on a wild goose chase again! (This project is great for someone with ADHD to have fun on!)

    The lock manager design/code is done but I'm not happy with using a rwlock to protect a tag. I really want to have the lock protect the content but that needs a way for me to support writeback. I think I need to build out two more things, a WAL mechanism and a buffer manager.

    I guess I need to commit to doing this for reals. However I am worried about reaching a point of partially working for a while like when I did the type fixing. We'll see how this goes.

    For now, the index implementation is now on hold until I get an integrated I/O subsystem and a stubbed out WAL.

    opened by chotchki 0
  • Implement the numeric type

    Implement the numeric type

    Postgres has arbitrary precision types that are critical for financial applications.

    Implementing them will require a picking up a rust arbitrary precision library such as https://www.postgresql.org/docs/current/datatype-numeric.html

    Right now the most reasonable library seems to have major limitations https://github.com/alkis/decimal and is basically a wrapper of the C library http://speleotrove.com/decimal/.

    opened by chotchki 1
  • Implement the ability to drop tables

    Implement the ability to drop tables

    Right now pgbench fails on an initial attempt to drop the tables. We should add drop support.

    drop table if exists pgbench_accounts, pgbench_branches, pgbench_history, pgbench_tellers

    opened by chotchki 1
  • Implement Fossa Cleanup

    Implement Fossa Cleanup

    Right now I have licensing issues as identified by Fossa. These are not due to the code but the various support tools around the code.

    To fix this I will need to restructure the project to separate testing tools from the core code. They are already separated but its hard for Fossa to tell. However since I'm not selling presenting this code as production ready, meh, I'll fix it later.

    opened by chotchki 0
  • Implement index pointer validation

    Implement index pointer validation

    The BTreeLeafs have a doubly linked list to scan back and forth once you reach the bottom.

    They are stored in multiple pages so if the database crashes they could be corrupted.

    To work around this until I figure out a better way I can scan each leaf on database startup.

    Will need to determine if the database shuts down unclean or not.

    opened by chotchki 0
  • Switch from next_free_offset to free space based

    Switch from next_free_offset to free space based

    Currently new pages are selected based on appending to the end instead of based on pages being in use or not.

    Switch this to using just the free space map.

    Row manager will make use of the free/full markings. Index manager will make use of them as inuse/not used.

    opened by chotchki 0
  • Figure out how to test multithreaded code

    Figure out how to test multithreaded code

    A lot of my low level code is very heavy and sensitive to locks. The Tokio project has a library called loom that seems to offer a reasonable way to test this type of code for correctness.

    I suspect I'll have to move away from Github based runners once I do so.

    https://github.com/tokio-rs/loom

    opened by chotchki 0
Releases(v0.9.0)
  • v0.9.0(Oct 10, 2021)

    This release has some major changes under the hood which enabled the headline features!

    • FileManager was re-written to FileManager2. This allowed the streaming of the code base while also eliminating the lost write problem.
      • FileManager2 has the added benefit of integrated caching and locking. All in less code thanks to the Moka library!
    • Indexes were integrated into the codebase (these are not crash safe yet!)
    • A free space manager was integrated that enables the marking of full/not full pages. More changes will be coming to improve this.
    Source code(tar.gz)
    Source code(zip)
  • v0.8.0(Aug 15, 2021)

    This release is a grab bag of support technologies to enable the underlying goal of enforced unique indexes.

    • Switched from IOManager to FileManager which means all storage is persisted now. This is not crash safe. File interactions are designed to scale to a fixed maximum file handle count.
    • Decided the primary key for storage is a Uuid, this will be the basic differentiator to route storage requests. At this time I'm not planning on supporting real tablespaces. If I change my mind, I'll have to plumb it in to this infrastructure.
    • Have real integration tests using a non-feophant Postgres driver.
    • Have the ability to profile the code and already found two places that were unneeded hot spots. "vec![]" is a code smell! You should be able to make a moderate guess on how big it will get.

    Implemented but unintegrated code (which means I'll change it like crazy as I integrate):

    • A lock manager based on weak refs
    • BTree indexes
    Source code(tar.gz)
    Source code(zip)
  • v0.7.1(Aug 1, 2021)

    This release marks the major enhancement of the internal type system.

    • The structs were moved into a better place that aligns with the rest of the code.
    • The serialization process now uses a unified buffer instead of concatenating many small buffers.
    • I can support complex AND array types.
    • There is now a split between table and type which will make transformations easier in queries.
    • I have a strong definition of what each layer should be doing.

    Known design issues.

    • I still have not addressed the lack of well done locking.
    • The state of the client is not tracked in regards to in progress transactions.
    Source code(tar.gz)
    Source code(zip)
  • v0.7.0(Jul 19, 2021)

  • v0.6.0(Jul 14, 2021)

    FeOphant now supports the concept of nullable columns.

    I'll note this was mainly ensuring the parser could support it, the underlying infrastructure was built with null in mind from the beginning.

    Source code(tar.gz)
    Source code(zip)
  • v0.5.0(Jul 14, 2021)

  • v0.4.0(Jul 10, 2021)

    FeOphant now supports a simple SQL insert of values.

    A basic pipeline for query execution has been built based on the Postgres model.

    • Query String -> sql_parser -> ParseTree
    • ParseTree -> analyzer -> QueryTree
    • QueryTree -> rewriter -> QueryTree
    • QueryTree -> planner -> PlannedStatement
    • PlannedStatement -> executer -> do stuff
    Source code(tar.gz)
    Source code(zip)
Owner
Christopher Hotchkiss
Christopher Hotchkiss
šŸ§° The Rust SQL Toolkit. An async, pure Rust SQL crate featuring compile-time checked queries without a DSL. Supports PostgreSQL, MySQL, SQLite, and MSSQL.

SQLx ?? The Rust SQL Toolkit Install | Usage | Docs Built with ā¤ļø by The LaunchBadge team SQLx is an async, pure Rustā€  SQL crate featuring compile-tim

launchbadge 7.6k Dec 31, 2022
ReefDB is a minimalistic, in-memory and on-disk database management system written in Rust, implementing basic SQL query capabilities and full-text search.

ReefDB ReefDB is a minimalistic, in-memory and on-disk database management system written in Rust, implementing basic SQL query capabilities and full-

Sacha Arbonel 75 Jun 12, 2023
A Rust SQL query builder with a pleasant fluent API closely imitating actual SQL

Scooby An SQL query builder with a pleasant fluent API closely imitating actual SQL. Meant to comfortably build dynamic queries with a little bit of s

Aleksei Voronov 100 Nov 11, 2022
Gh-sql - Query GitHub Projects (beta) with SQL

gh-sql: Query GitHub Projects (beta) with SQL Installation gh extension install KOBA789/gh-sql Features SELECT items DELETE items UPDATE item fields

Hidekazu Kobayashi 108 Dec 7, 2022
SQL validator tool for BigQuery standard SQL.

bqvalid What bqvalid does bqvalid is the SQL validator tool for BigQuery standard SQL. bqvalid fails with error message if there's the expression that

null 10 Dec 25, 2022
GlueSQL is a SQL database library written in Rust

GlueSQL is a SQL database library written in Rust. It provides a parser (sqlparser-rs), execution layer, and optional storage (sled) packaged into a single library.

GlueSQL 2.1k Jan 8, 2023
Distributed SQL database in Rust, written as a learning project

toyDB Distributed SQL database in Rust, written as a learning project. Most components are built from scratch, including: Raft-based distributed conse

Erik Grinaker 4.6k Jan 8, 2023
Distributed, version controlled, SQL database with cryptographically verifiable storage, queries and results. Think git for postgres.

SDB - SignatureDB Distributed, version controlled, SQL database with cryptographically verifiable storage, queries and results. Think git for postgres

Fremantle Industries 5 Apr 26, 2022
SQL database to read and write "discord"

GlueSQL Discord Storage After discussing how CI testing will be managed, we plan to move it upstream. Precautions for use discord ToS https://discord.

Jiseok CHOI 9 Feb 28, 2023
A programmable document database inspired by CouchDB written in Rust

PliantDB PliantDB aims to be a Rust-written, ACID-compliant, document-database inspired by CouchDB. While it is inspired by CouchDB, this project will

Khonsu Labs 718 Dec 31, 2022
A programmable document database inspired by CouchDB written in Rust

BonsaiDb Formerly known as PliantDb. Not yet released on crates.io as BonsaiDb. BonsaiDb aims to be a Rust-written, ACID-compliant, document-database

Khonsu Labs 721 Jan 2, 2023
RisingWave is a cloud-native streaming database that uses SQL as the interface language.

RisingWave is a cloud-native streaming database that uses SQL as the interface language. It is designed to reduce the complexity and cost of building real-time applications. RisingWave consumes streaming data, performs continuous queries, and updates results dynamically. As a database system, RisingWave maintains results inside its own storage and allows users to access data efficiently.

Singularity Data 3.7k Jan 2, 2023
An explorer for the DeArrow database as a web application. Inspired by Lartza's SBrowser

DeArrow Browser An explorer for the DeArrow database as a web application. Inspired by Lartza's SBbrowser. Public instance available at dearrow.minibo

null 3 Aug 10, 2023
TDS 7.2+ (mssql / Microsoft SQL Server) async driver for rust

Tiberius A native Microsoft SQL Server (TDS) client for Rust. Supported SQL Server versions Version Support level Notes 2019 Tested on CI 2017 Tested

Prisma 189 Dec 25, 2022
ReadySet is a lightweight SQL caching engine written in Rust that helps developers enhance the performance and scalability of existing applications.

ReadySet is a SQL caching engine designed to help developers enhance the performance and scalability of their existing database-backed applications. W

ReadySet 1.7k Jan 8, 2023
rust_arango enables you to connect with ArangoDB server, access to database, execute AQL query, manage ArangoDB in an easy and intuitive way, both async and plain synchronous code with any HTTP ecosystem you love.

rust_arango enables you to connect with ArangoDB server, access to database, execute AQL query, manage ArangoDB in an easy and intuitive way, both async and plain synchronous code with any HTTP ecosystem you love.

Foretag 3 Mar 24, 2022
SubZero - a standalone web server that turns your database directly into a REST/GraphQL api

What is this? This is a demo repository for the new subzero codebase implemented in Rust. subZero is a standalone web server that turns your database

subZero 82 Jan 1, 2023
Rust library to parse, deparse and normalize SQL queries using the PostgreSQL query parser

This Rust library uses the actual PostgreSQL server source to parse SQL queries and return the internal PostgreSQL parse tree.

pganalyze 37 Dec 18, 2022
Rust client for Timeplus Proton, a fast and lightweight streaming SQL engine

Rust Client for Timeplus Proton Rust client for Timeplus Proton. Proton is a streaming SQL engine, a fast and lightweight alternative to Apache Flink,

Timeplus 4 Feb 27, 2024