Bedrock

Bedrock is a networking and distributed transaction layer built on top of SQLite. It is a distributed relational database management system designed for geo-replication. It was initially made for (and is owned by) Expensify, the expense management company.

History

BedRock is the system that backs Expensify, the expense management company. It had been used for 8 years prior to being launched. It was originally created as an in house solution to the strict database constraints of financial institutions - response time within milliseconds, transaction logging and authentication, and replication of multiple servers.

Query Interface

SQL Command-line / Shell

Bedrock queries can be any SQLite compatible query. The result is returned in an HTTP-like / JSON format, as per user request. It also support the MySQL protocol, and hence the user can continue using the MySQL client of their choice. It also provides a PHP binding that one can use to work with it from the shell itself.

Query Execution

Tuple-at-a-Time Model

Bedrock uses the same query execution model as used by SQLite. The Squery method in Bedrock calls the sqlite3_exec method, which is a one step query execution interface.

Views

Virtual Views

Bedrock inherits view support from SQLite. SQLite supports virtual views. Whether SQLite supprots Materialized views is a topic of debate - while the official documentation claims it supports materialized views, the definition of materialized as used by SQLite seemed to vary.

Foreign Keys

Supported

Bedrock inherits foreign key support from SQLite. To enable foreign key support, SQLITE_OMIT_FOREIGN_KEY and SQLITE_OMIT_TRIGGER must not be defined at runtime.

Indexes

B+Tree R-Tree

Bedrock inherits index support from SQLite. The default index is a B Tree. There is an option to use an R Tree for range queries, in which case SQLITE_ENABLE_RTREE needs to be defined.

Hardware Acceleration

Custom

Bedrock is written for modern hardware with SSD-backed RAID drives and RAM file caches. It was made to be "simple", not requiring any esoteric hardware hacks as done by other systems. Hence, there is no standard hardware acceleration option.

Data Model

Relational

Bedrock inherits the data model from SQLite, which supports a relational data model.

Storage Model

N-ary Storage Model (Row/Record)

Bedrock stores data in a SQLite database. This stores data in a row-wise, where each row is referred to as a tuple. The tuples are stored contiguously on each page, and can be stored across multiple pages.

Storage Architecture

Disk-oriented

Bedrock is an embedded SQLite engine, and reads / writes to ordinary disk files.

Concurrency Control

Multi-version Concurrency Control (MVCC) Two-Phase Locking (Deadlock Prevention) Two-Phase Locking (Deadlock Detection)

Bedrock inherits concurrency control from SQLite. SQLite maintains page locks using Two-Phase Locking.

However, Bedrock has its own proprietary synchronization engine to support concurrency over multiple servers.

Bedrock's synchronization engine is a private distributed general ledger, i.e, a private blockchain. Each thread has an internal table called journal, which has 3 columns called id, query, hash. Each time a query is committed to the database, a new row is inserted into the journal. The new row records the query, and calculates the new incremental hash based on the previous row. When a server connects to a cluster, the most recent id and hash are broadcasted. If two servers disagree on the the hash corresponding to the id, then they know that they have "forked" at some point and stop communicating with each other. A Paxos-based election scheme decides which fork stands up to the new master.

Since Bedrock supports multi-threaded writes, it is prone to write conflicts. This is addressed by "sharding" the table, and querying all the journal tables in a UNION whenever the database is to be viewed as one.

Query Compilation

Code Generation

Bedrock data is stored in SQLite databases. The compilation is hence the same as in SQLite. To execute a SQL statement, it is first compiled into a byte-code program using one of the sqlite3_prepare% methods. Once the code has been generated, it is run by a virtual machine.

Checkpoints

Non-Blocking Blocking

Bedrock inherits checkpoint support from SQLite, hence supports blocking and non-blocking checkpoints.

Joins

Nested Loop Join Sort-Merge Join

Bedrock inherits join support from SQLite. SQLite uses nested loop joins, and has been criticised previously for its slow performance. SQLite supports Sort-Merge joins over unique keys.

Bedrock Logo
Website

http://bedrockdb.com/

Source Code

https://github.com/Expensify/Bedrock

Tech Docs

https://github.com/Expensify/Bedrock/tree/master/docs

Developer

Expensify

Country of Origin

US

Start Year

2016

Project Type

Open Source

Written in

C++

Supported languages

C++

Embeds / Uses

SQLite

Inspired By

SQLite

Compatible With

MySQL

Operating Systems

Linux, OS X

Licenses

LGPL v3