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
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)
Command line tool to generate idiomatic Go code for SQL databases supporting PostgreSQL, MySQL, SQLite, Oracle, and Microsoft SQL Server

About xo xo is a command-line tool to generate Go code based on a database schema or a custom query. xo works by using database metadata and SQL intro

Jan 8, 2023
Go fearless SQL. Sqlvet performs static analysis on raw SQL queries in your Go code base.

Sqlvet Sqlvet performs static analysis on raw SQL queries in your Go code base to surface potential runtime errors at build time. Feature highlights:

Dec 19, 2022
Database Abstraction Layer (dbal) for Go. Support SQL builder and get result easily (now only support mysql)

godbal Database Abstraction Layer (dbal) for go (now only support mysql) Motivation I wanted a DBAL that No ORM、No Reflect、Concurrency Save, support S

Nov 17, 2022
A Go (golang) package that enhances the standard database/sql package by providing powerful data retrieval methods as well as DB-agnostic query building capabilities.

ozzo-dbx Summary Description Requirements Installation Supported Databases Getting Started Connecting to Database Executing Queries Binding Parameters

Dec 31, 2022
Mocking your SQL database in Go tests has never been easier.

copyist Mocking your SQL database in Go tests has never been easier. The copyist library automatically records low-level SQL calls made during your te

Dec 19, 2022
Additions to Go's database/sql for super fast performance and convenience. (fork of gocraft/dbr)

dbr (fork of gocraft/dbr) provides additions to Go's database/sql for super fast performance and convenience. Getting Started // create a connection (

Dec 31, 2022
Go library for accessing multi-host SQL database installations

hasql hasql provides simple and reliable way to access high-availability database setups with multiple hosts. Status hasql is production-ready and is

Dec 28, 2022
Document-oriented, embedded SQL database

Genji Document-oriented, embedded, SQL database Table of contents Table of contents Introduction Features Installation Usage Using Genji's API Using d

Jan 1, 2023
A Golang library for using SQL.

dotsql A Golang library for using SQL. It is not an ORM, it is not a query builder. Dotsql is a library that helps you keep sql files in one place and

Dec 27, 2022
a golang library for sql builder

Gendry gendry is a Go library that helps you operate database. Based on go-sql-driver/mysql, it provides a series of simple but useful tools to prepar

Dec 26, 2022
SQL builder and query library for golang

__ _ ___ __ _ _ _ / _` |/ _ \ / _` | | | | | (_| | (_) | (_| | |_| | \__, |\___/ \__, |\__,_| |___/ |_| goqu is an expressive SQL bu

Dec 30, 2022
SQL query builder for Go

GoSQL Query builder with some handy utility functions. Documentation For full documentation see the pkg.go.dev or GitBook. Examples // Open database a

Dec 12, 2022
Type safe SQL builder with code generation and automatic query result data mapping
Type safe SQL builder with code generation and automatic query result data mapping

Jet Jet is a complete solution for efficient and high performance database access, consisting of type-safe SQL builder with code generation and automa

Jan 6, 2023
Write your SQL queries in raw files with all benefits of modern IDEs, use them in an easy way inside your application with all the profit of compile time constants

About qry is a general purpose library for storing your raw database queries in .sql files with all benefits of modern IDEs, instead of strings and co

Dec 25, 2022
Type safe SQL query builder and struct mapper for Go

sq (Structured Query) ?? ?? sq is a code-generated, type safe query builder and struct mapper for Go. ?? ?? Documentation • Reference • Examples This

Dec 19, 2022
Fast SQL query builder for Go

sqlf A fast SQL query builder for Go. sqlf statement builder provides a way to: Combine SQL statements from fragments of raw SQL and arguments that ma

Dec 23, 2022
💥 A lightweight DSL & ORM which helps you to write SQL in Go.
💥 A lightweight DSL & ORM which helps you to write SQL in Go.

sqlingo is a SQL DSL (a.k.a. SQL Builder or ORM) library in Go. It generates code from the database and lets you write SQL queries in an elegant way.

Jan 2, 2023
Fluent SQL generation for golang

sqrl - fat-free version of squirrel - fluent SQL generator for Go Non thread safe fork of squirrel. The same handy fluffy helper, but with extra lette

Dec 16, 2022
Fluent SQL generation for golang

Squirrel is "complete". Bug fixes will still be merged (slowly). Bug reports are welcome, but I will not necessarily respond to them. If another fork

Jan 6, 2023