LBADD: An experimental, distributed SQL database

LBADD

Let's build a distributed database.


LBADD is an experimental distributed SQL database, written in Go.

The goal of this project is to build a database from scratch which is well documented, fully tested, and easy to understand. Implementing as much as possible from the ground up.

It is also currently a work in progress. Feel free to follow along with the development of each component, from parser to pager.

Architecture

The database is made up of a few separate components. These handle the SQL parsing, the intermediary representation generation, the multi-node consensus, the execution of the IR, and the (persistent) storage.

For a brief overview of the purpose of each component, have a look at the overview.

Prior art

Inspiration has been taken from the brilliantly documented codebase of SQLite. However the codebase has been heavily optimized, and is difficult to follow without spending significant time.

Work has also already been done to build a distributed version of SQLite called rqlite. The project uses raft consensus in order to keep nodes consistent across the network.

LBADD aims to replicate these in a single project. LBADD doesn't aim to be nearly as performant as SQLite nor rqlite, and hopefully trades this instead for slightly more clarity and simplicity.

Contributing

Contributors are more than welcome and much appreciated. Please feel free to open a PR to improve anything you don't like, or would like to add. No PR is too small! Go check out our contributing guide for more detailed info about how to get started with a contribution.

License

This project is licensed under the MIT license.

Owner
Tom Arrell
Senior Backend Engineer @sumup — Lover of Rust and Go, hack around building keyboards when I'm bored
Tom Arrell
https://github.com/tomarrell/lbadd
Comments
  • Run tests without race detector by default

    Run tests without race detector by default

    I noticed that when running the tests with the default test command, the run would take around 45 seconds to finish. Initially I thought this was due to the fuzzing not using a build tag, however this wasn't the case.

    I noticed that when run with the race detector, the parser_test.go file in particular takes a rather absurd amount of time. In order to have a slightly tighter feedback loop on the main test command, I've removed the race detector and put it in a separate target.

    Definition of done

    • [ ] Code correctness
    • [ ] Documentation
    • [ ] Test cases
  • parser: select expression doesn't work

    parser: select expression doesn't work

    Try to parse SELECT amount * price AS total_price FROM items. This will throw a lot of errors, although the production

    SELECT result-column ...

    with result_column using the expr production, and expr using the expr binary-operator expr allows such a statement.

  • parser: parseExpr calls from other statements is broken

    parser: parseExpr calls from other statements is broken

    Describe the bug After visiting a token of a possible expr, there is no function to parse expr from that point.

    To Reproduce See #151

    Adding a helper function that takes in the first element of a possible expr and returns the parsed expr is needed.

  • Literal

    Literal "table1" erroneously recognised as keyword Table.

    Describe the bug A clear and concise description of what the bug is.

    The keyword table is being recognised by the scanner in the case of the word table1 instead of a literal table1

    To Reproduce Steps to reproduce the behavior:

    Test for the keyword table1

    Expected behavior A clear and concise description of what you expected to happen. Literal table1 instead of KeywordTable

  • nopanic: nopanic should check whether error is recovered

    nopanic: nopanic should check whether error is recovered

    Currently, the nopanic analyzer only checks if there is a panic in the codebase. If so, an error is reported, no further checks done. This analyzer shall be extended, so that it only reports the panic as disallowed, if one or more of the following rules apply:

    • the panic occurs inside the main package
    • the panic is not recovered from within the same package
    • the panic panics anything that does not implement the error interface
    • the panic panics nil

    I. e. panics are allowed, if and only if all of the following rules apply:

    • they propagate an error up the callstack in the same package
    • they are recovered from, so that it can't leave the package and can't crash the application
    • if they are recovered, it must be ensured that every path actually catches the error

    Examples

    func main() {
    defer func(){
        if err := recover(); err != nil {
            fmt.Println(err)
        }
    }()
    panic("") // allowed
}

    func main() {
    defer func(){
        if err := recover(); err != nil {
            if myErr, ok := err.(*MyErr); ok {
                fmt.Println(myErr)
            }
            panic(err) // not allowed
        }
    }()
    panic("") // allowed
}
  • executor: implement executor

    executor: implement executor

    An executor is the connection between the database input service and the database layer. Somewhere, an SQL statement is parsed and converted to the IR, which are commands that the executor can execute. The executor can then execute the appropriate methods and functions on the database in order to achieve, what the command describes.

  • staticcheck Failed

    staticcheck Failed

    ⚠ staticcheck Failed

    btree.go:187:3: empty branch (SA9003)
btree_test.go:291:3: field order is unused (U1000)
executor.go:16:6: type record is unused (U1000)
executor.go:19:6: type row is unused (U1000)
executor.go:23:2: field columns is unused (U1000)
executor.go:24:2: field rows is unused (U1000)
executor.go:25:2: field rowsAffected is unused (U1000)
query.go:6:2: field conditions is unused (U1000)
query.go:7:2: field updates is unused (U1000)
query.go:8:2: field inserts is unused (U1000)
query.go:72:6: type condition is unused (U1000)

    Checks Document

    Originally posted by @github-actions in https://github.com/tomarrell/lbadd/pull/10#issuecomment-570262390

  • Bump github.com/spf13/afero from 1.3.1 to 1.3.2

    Bump github.com/spf13/afero from 1.3.1 to 1.3.2

    Bumps github.com/spf13/afero from 1.3.1 to 1.3.2.

    Commits
    • 5d9e780 Merge pull request #249 from JohnStarich/bugfix/memfs-chmod-perm-only
    • d443df9 Fix test for Windows
    • 57ab25a Use more appropriate func name for unrestricted mode changes
    • 7b70cb1 Fix MemMapFs.Chmod changing non-perm bits
    • See full diff in compare view

    Dependabot compatibility score

    Dependabot will resolve any conflicts with this PR as long as you don't alter it yourself. You can also trigger a rebase manually by commenting @dependabot rebase.

    Dependabot commands and options

    You can trigger Dependabot actions by commenting on this PR:

    • @dependabot rebase will rebase this PR
    • @dependabot recreate will recreate this PR, overwriting any edits that have been made to it
    • @dependabot merge will merge this PR after your CI passes on it
    • @dependabot squash and merge will squash and merge this PR after your CI passes on it
    • @dependabot cancel merge will cancel a previously requested merge and block automerging
    • @dependabot reopen will reopen this PR if it is closed
    • @dependabot close will close this PR and stop Dependabot recreating it. You can achieve the same result by closing it manually
    • @dependabot ignore this major version will close this PR and stop Dependabot creating any more for this major version (unless you reopen the PR or upgrade to it yourself)
    • @dependabot ignore this minor version will close this PR and stop Dependabot creating any more for this minor version (unless you reopen the PR or upgrade to it yourself)
    • @dependabot ignore this dependency will close this PR and stop Dependabot creating any more for this dependency (unless you reopen the PR or upgrade to it yourself)
  • engine: remove leading and trailing quotes on string literals

    engine: remove leading and trailing quotes on string literals

    Describe the bug The engine does not strip leading and trailing quotes on strings. An example is internal/test/testdata/issue187/output, where the second column contains values like "2" and "5". This should be just 2 and 5, but the type should remain a string.

    To Reproduce Let the engine evaluate a command.LiteralExpression{Value: "\"1\""}. This will evaluate to a types.StringValue("1").

    Expected behavior It must evaluate to a types.StringValue(1).

  • parser: expression in VALUES must be 2D

    parser: expression in VALUES must be 2D

    Describe the bug Our ast currently has only one slice for Expressions, which is (*ast.SelectCore).Expr2. However, for the VALUES production, we would need a two-dimensional slice, since multiple values can be grouped, representing different datasets.

  • raft: implements appendEntriesResponse

    raft: implements appendEntriesResponse

    When appendEntry RPC is sent by leader to other nodes, this function generate response for the leader and handles the entries that should be stored in node logs.

  • Bump golang.org/x/text from 0.3.3 to 0.5.0

    Bump golang.org/x/text from 0.3.3 to 0.5.0

    Bumps golang.org/x/text from 0.3.3 to 0.5.0.

    Commits
    • c8236a6 unicode/bidi: remove unused global
    • ada7473 all: remove redundant type conversion
    • 1bdb400 language: remove compatibility with go < 1.2
    • 252bee0 go.mod: ignore cyclic dependency for tagging
    • ecab6e5 go.mod: ignore cyclic dependency for tagging
    • 369c86b all: fix a few function names on comments
    • 434eadc language: reject excessively large Accept-Language strings
    • 23407e7 go.mod: ignore cyclic dependency for tagging
    • b18d3dd secure/precis: replace bytes.Compare with bytes.Equal
    • 795e854 all: replace io/ioutil with io and os package
    • Additional commits viewable in compare view

    Dependabot compatibility score

    Dependabot will resolve any conflicts with this PR as long as you don't alter it yourself. You can also trigger a rebase manually by commenting @dependabot rebase.

    Dependabot commands and options

    You can trigger Dependabot actions by commenting on this PR:

    • @dependabot rebase will rebase this PR
    • @dependabot recreate will recreate this PR, overwriting any edits that have been made to it
    • @dependabot merge will merge this PR after your CI passes on it
    • @dependabot squash and merge will squash and merge this PR after your CI passes on it
    • @dependabot cancel merge will cancel a previously requested merge and block automerging
    • @dependabot reopen will reopen this PR if it is closed
    • @dependabot close will close this PR and stop Dependabot recreating it. You can achieve the same result by closing it manually
    • @dependabot ignore this major version will close this PR and stop Dependabot creating any more for this major version (unless you reopen the PR or upgrade to it yourself)
    • @dependabot ignore this minor version will close this PR and stop Dependabot creating any more for this minor version (unless you reopen the PR or upgrade to it yourself)
    • @dependabot ignore this dependency will close this PR and stop Dependabot creating any more for this dependency (unless you reopen the PR or upgrade to it yourself)
  • Bump github.com/spf13/afero from 1.4.1 to 1.9.3

    Bump github.com/spf13/afero from 1.4.1 to 1.9.3

    Bumps github.com/spf13/afero from 1.4.1 to 1.9.3.

    Release notes

    Sourced from github.com/spf13/afero's releases.

    v1.9.3

    What's Changed

    Full Changelog: https://github.com/spf13/afero/compare/v1.9.2...v1.9.3

    v1.9.2

    What's Changed

    Full Changelog: https://github.com/spf13/afero/compare/v1.9.1...v1.9.2

    v1.9.1

    What's Changed

    Full Changelog: https://github.com/spf13/afero/compare/v1.9.0...v1.9.1

    v1.9.0

    What's Changed

    New Contributors

    Full Changelog: https://github.com/spf13/afero/compare/v1.8.2...v1.9.0

    v1.8.2: RemoveAll fixes in MemMapFs and GcsFs

    v1.8.1: memfs: add modTime on folder creation

    No release notes provided.

    v1.7.1: Move GCS into its own package

    No release notes provided.

    v1.7.0: Add experimental GCS support

    Add experimental GCS support in Afero. Experimental because the CI infra of afero does not test with real GCS buckets.

    Limitations:

    • No Chmod support - The GCS ACL could probably be mapped to *nix style permissions but that would add another level of complexity and is ignored in this version.

    ... (truncated)

    Commits
    • a800a9d Fix concurrency issue in MemMapFs.Mkdir/MkdirAll
    • 2a70f2b Make mem.File implement fs.ReadDirFile
    • 0aa65ed Fix sorting in IOFS.ReadDir
    • b0a534a Update README.md
    • c92ae36 Make IOFS.ReadDir check for fs.ReadDirFile
    • 52b6417 Fix staticcheck lint errors
    • 939bf3d Fix test failures on Windows
    • 9439436 all: Run gofmt -s -w
    • 015be45 Move CI tests to GitHub Action
    • 100c9a6 Merge pull request #346 from jeffwidman/bump-minimum-go-version
    • Additional commits viewable in compare view

    Dependabot compatibility score

    Dependabot will resolve any conflicts with this PR as long as you don't alter it yourself. You can also trigger a rebase manually by commenting @dependabot rebase.

    Dependabot commands and options

    You can trigger Dependabot actions by commenting on this PR:

    • @dependabot rebase will rebase this PR
    • @dependabot recreate will recreate this PR, overwriting any edits that have been made to it
    • @dependabot merge will merge this PR after your CI passes on it
    • @dependabot squash and merge will squash and merge this PR after your CI passes on it
    • @dependabot cancel merge will cancel a previously requested merge and block automerging
    • @dependabot reopen will reopen this PR if it is closed
    • @dependabot close will close this PR and stop Dependabot recreating it. You can achieve the same result by closing it manually
    • @dependabot ignore this major version will close this PR and stop Dependabot creating any more for this major version (unless you reopen the PR or upgrade to it yourself)
    • @dependabot ignore this minor version will close this PR and stop Dependabot creating any more for this minor version (unless you reopen the PR or upgrade to it yourself)
    • @dependabot ignore this dependency will close this PR and stop Dependabot creating any more for this dependency (unless you reopen the PR or upgrade to it yourself)
  • Bump github.com/spf13/cobra from 1.0.0 to 1.6.1

    Bump github.com/spf13/cobra from 1.0.0 to 1.6.1

    Bumps github.com/spf13/cobra from 1.0.0 to 1.6.1.

    Release notes

    Sourced from github.com/spf13/cobra's releases.

    v1.6.1

    Bug fixes 🐛

    • Fixes a panic when AddGroup isn't called before AddCommand(my-sub-command) is executed. This can happen within more complex cobra file structures that have many different inits to be executed. Now, the check for groups has been moved to ExecuteC and provides more flexibility when working with grouped commands - @​marckhouzam (and shout out to @​aawsome, @​andig and @​KINGSABRI for a deep investigation into this! 👏🏼)

    v1.6.0

    Summer 2022 Release

    Some exciting changes make their way to Cobra! Command completions continue to get better and better (including adding --help and --version automatic flags to the completions list). Grouping is now possible in your help output as well! And you can now use the OnFinalize method to cleanup things when all "work" is done. Checkout the full changelog below:

    Features 🌠

    Deprecation 👎🏼

    • ExactValidArgs is deprecated (but not being removed entirely). This is abit nuanced, so checkout #1643 for further information and the updated user_guide.md on how this may affect you (and how you can take advantage of the correct behavior in the validators): @​umarcor #1643

    Bug fixes 🐛

    Dependencies 🗳️

    Testing 🤔

    Docs ✏️

    Misc 💭

    ... (truncated)

    Commits

    Dependabot compatibility score

    Dependabot will resolve any conflicts with this PR as long as you don't alter it yourself. You can also trigger a rebase manually by commenting @dependabot rebase.

    Dependabot commands and options

    You can trigger Dependabot actions by commenting on this PR:

    • @dependabot rebase will rebase this PR
    • @dependabot recreate will recreate this PR, overwriting any edits that have been made to it
    • @dependabot merge will merge this PR after your CI passes on it
    • @dependabot squash and merge will squash and merge this PR after your CI passes on it
    • @dependabot cancel merge will cancel a previously requested merge and block automerging
    • @dependabot reopen will reopen this PR if it is closed
    • @dependabot close will close this PR and stop Dependabot recreating it. You can achieve the same result by closing it manually
    • @dependabot ignore this major version will close this PR and stop Dependabot creating any more for this major version (unless you reopen the PR or upgrade to it yourself)
    • @dependabot ignore this minor version will close this PR and stop Dependabot creating any more for this minor version (unless you reopen the PR or upgrade to it yourself)
    • @dependabot ignore this dependency will close this PR and stop Dependabot creating any more for this dependency (unless you reopen the PR or upgrade to it yourself)
  • Bump github.com/google/go-cmp from 0.5.1 to 0.5.9

    Bump github.com/google/go-cmp from 0.5.1 to 0.5.9

    Bumps github.com/google/go-cmp from 0.5.1 to 0.5.9.

    Release notes

    Sourced from github.com/google/go-cmp's releases.

    v0.5.9

    Reporter changes:

    • (#299) Adjust heuristic for line-based versus byte-based diffing
    • (#306) Use value.TypeString in PathStep.String

    Code cleanup changes:

    • (#297) Use reflect.Value.IsZero
    • (#304) Format with Go 1.19 formatter
    • (#300 )Fix typo in Result documentation
    • (#302) Pre-declare global type variables
    • (#309) Run tests on Go 1.19

    v0.5.8

    Reporter changes:

    • (#293) Fix printing of types in reporter output for interface and pointer types
    • (#294) Use string formatting for slice of bytes in more circumstances

    Dependency changes:

    • (#292) Update minimum supported version to go1.13 and remove xerrors dependency

    v0.5.7

    Reporter changes:

    • (#266) Fix textual printing of byte slices
    • (#275) Reduce minimum length for specialize string diffing
    • (#276) Use any alias instead of interface{}

    Code cleanup changes:

    • (#281) Update minimum supported version to go1.11
    • (#282) Drop hacks to work around Go reflection bugs in Go1.9
    • (#285) Add //go:build lines
    • (#262) Fix staticcheck findings
    • (#263) Avoid shadowing variable
    • (#268) Use sha256 in test
    • (#271) Fix spelling mistakes
    • (#269) Change build status badge

    v0.5.6

    Reporter changes:

    • (#258) Print as text if mostly text
    • (#259) Cleanup edit groups after coalescing
    • (#260) Avoid diffing by lines if inefficient

    Minor documentation changes:

    • (#256) Fix typo in path.go

    v0.5.5

    ... (truncated)

    Commits

    Dependabot compatibility score

    Dependabot will resolve any conflicts with this PR as long as you don't alter it yourself. You can also trigger a rebase manually by commenting @dependabot rebase.

    Dependabot commands and options

    You can trigger Dependabot actions by commenting on this PR:

    • @dependabot rebase will rebase this PR
    • @dependabot recreate will recreate this PR, overwriting any edits that have been made to it
    • @dependabot merge will merge this PR after your CI passes on it
    • @dependabot squash and merge will squash and merge this PR after your CI passes on it
    • @dependabot cancel merge will cancel a previously requested merge and block automerging
    • @dependabot reopen will reopen this PR if it is closed
    • @dependabot close will close this PR and stop Dependabot recreating it. You can achieve the same result by closing it manually
    • @dependabot ignore this major version will close this PR and stop Dependabot creating any more for this major version (unless you reopen the PR or upgrade to it yourself)
    • @dependabot ignore this minor version will close this PR and stop Dependabot creating any more for this minor version (unless you reopen the PR or upgrade to it yourself)
    • @dependabot ignore this dependency will close this PR and stop Dependabot creating any more for this dependency (unless you reopen the PR or upgrade to it yourself)
  • Bump github.com/rs/zerolog from 1.19.0 to 1.28.0

    Bump github.com/rs/zerolog from 1.19.0 to 1.28.0

    Bumps github.com/rs/zerolog from 1.19.0 to 1.28.0.

    Commits

    Dependabot compatibility score

    Dependabot will resolve any conflicts with this PR as long as you don't alter it yourself. You can also trigger a rebase manually by commenting @dependabot rebase.

    Dependabot commands and options

    You can trigger Dependabot actions by commenting on this PR:

    • @dependabot rebase will rebase this PR
    • @dependabot recreate will recreate this PR, overwriting any edits that have been made to it
    • @dependabot merge will merge this PR after your CI passes on it
    • @dependabot squash and merge will squash and merge this PR after your CI passes on it
    • @dependabot cancel merge will cancel a previously requested merge and block automerging
    • @dependabot reopen will reopen this PR if it is closed
    • @dependabot close will close this PR and stop Dependabot recreating it. You can achieve the same result by closing it manually
    • @dependabot ignore this major version will close this PR and stop Dependabot creating any more for this major version (unless you reopen the PR or upgrade to it yourself)
    • @dependabot ignore this minor version will close this PR and stop Dependabot creating any more for this minor version (unless you reopen the PR or upgrade to it yourself)
    • @dependabot ignore this dependency will close this PR and stop Dependabot creating any more for this dependency (unless you reopen the PR or upgrade to it yourself)
Related tags
Database golang sql database distributed hacktoberfest
CockroachDB - the open source, cloud-native distributed SQL database.
 CockroachDB - the open source, cloud-native distributed SQL database.

CockroachDB is a cloud-native SQL database for building global, scalable cloud services that survive disasters. What is CockroachDB? Docs Quickstart C

Jan 2, 2023
A course to build the SQL layer of a distributed database.

TinySQL TinySQL is a course designed to teach you how to implement a distributed relational database in Go. TinySQL is also the name of the simplifed

Jan 8, 2023
Beerus-DB: a database operation framework, currently only supports Mysql, Use [go-sql-driver/mysql] to do database connection and basic operations

Beerus-DB · Beerus-DB is a database operation framework, currently only supports Mysql, Use [go-sql-driver/mysql] to do database connection and basic

Oct 29, 2022
A decentralized, trusted, high performance, SQL database with blockchain features
 A decentralized, trusted, high performance, SQL database with blockchain features

中文简介 CovenantSQL(CQL) is a Byzantine Fault Tolerant relational database built on SQLite: ServerLess: Free, High Availabile, Auto Sync Database Service

Jan 3, 2023
☄ The golang convenient converter supports Database to Struct, SQL to Struct, and JSON to Struct.
 ☄ The golang convenient converter supports Database to Struct, SQL to Struct, and JSON to Struct.

Gormat - Cross platform gopher tool The golang convenient converter supports Database to Struct, SQL to Struct, and JSON to Struct. 中文说明 Features Data

Dec 20, 2022
Dolt is a SQL database that you can fork, clone, branch, merge, push and pull just like a git repository.

Dolt is a SQL database that you can fork, clone, branch, merge, push and pull just like a git repository. Connect to Dolt just like any MySQL database to run queries or update the data using SQL commands. Use the command line interface to import CSV files, commit your changes, push them to a remote, or merge your teammate's changes.

Dec 31, 2022
DonutDB: A SQL database implemented on DynamoDB and SQLite

DonutDB: A SQL database implemented on DynamoDB and SQLite

Dec 21, 2022
This is a simple Golang application that executes SQL commands to clean up a mirror node's database.

This is a simple Golang application that executes SQL commands to clean up a mirror node's database.

Jan 24, 2022
Distributed reliable key-value store for the most critical data of a distributed system

etcd Note: The master branch may be in an unstable or even broken state during development. Please use releases instead of the master branch in order

Jan 9, 2023
The lightweight, distributed relational database built on SQLite.
 The lightweight, distributed relational database built on SQLite.

rqlite is a lightweight, distributed relational database, which uses SQLite as its storage engine. Forming a cluster is very straightforward, it grace

Jan 5, 2023
TiDB is an open source distributed HTAP database compatible with the MySQL protocol
TiDB is an open source distributed HTAP database compatible with the MySQL protocol

Slack Channel Twitter: @PingCAP Reddit Mailing list: lists.tidb.io For support, please contact PingCAP What is TiDB? TiDB ("Ti" stands for Titanium) i

Jan 9, 2023
TalariaDB is a distributed, highly available, and low latency time-series database for Presto
 TalariaDB is a distributed, highly available, and low latency time-series database for Presto

TalariaDB is a distributed, highly available, and low latency time-series database that stores real-time data. It's built on top of Badger DB.

Nov 16, 2022
Redwood is a highly-configurable, distributed, realtime database that manages a state tree shared among many peers

Redwood is a highly-configurable, distributed, realtime database that manages a state tree shared among many peers. Imagine something like a Redux store, but distributed across all users of an application, that offers offline editing and is resilient to poor connectivity.

Jan 8, 2023
decentralized,distributed,peer-to-peer database.

P2PDB 中文 | English 简介 P2PDB（p2p数据库），是一个去中心化、分布式、点对点数据库、P2PDB使用IPFS为其数据存储和IPFS Pubsub自动与对等方同步数据。P2PDB期望打造一个去中心化的分布式数据库，使P2PDB 成为去中心化应用程序 (dApps)、区块链应用程

Jan 1, 2023
Couchbase - distributed NoSQL cloud database

couchbase Couchbase is distributed NoSQL cloud database. create Scope CREATE SCO

Feb 16, 2022
Owl is a db manager platform,committed to standardizing the data, index in the database and operations to the database, to avoid risks and failures.

Owl is a db manager platform,committed to standardizing the data, index in the database and operations to the database, to avoid risks and failures. capabilities which owl provides include Process approval、sql Audit、sql execute and execute as crontab、data backup and recover .

Nov 9, 2022
This is a simple graph database in SQLite, inspired by "SQLite as a document database".

About This is a simple graph database in SQLite, inspired by "SQLite as a document database". Structure The schema consists of just two structures: No

Jan 3, 2023
Hard Disk Database based on a former database

Hard Disk Database based on a former database

Nov 1, 2021
Simple key value database that use json files to store the database

KValDB Simple key value database that use json files to store the database, the key and the respective value. This simple database have two gRPC metho

Nov 13, 2021