losfair / mvsqlite Goto Github PK

View Code? Open in Web Editor NEW

1.4K 24.0 39.0 514 KB

Distributed, MVCC SQLite that runs on FoundationDB.

Home Page: https://github.com/losfair/mvsqlite/wiki

License: Apache License 2.0

Rust 99.07% Shell 0.28% Makefile 0.12% C 0.52%

database rust

mvsqlite's Introduction

mvSQLite

Distributed, MVCC SQLite that runs on top of FoundationDB.

Documentation

mvSQLite

Features

Full feature-set from SQLite: mvSQLite integrates with SQLite as a custom VFS layer. It is a layer "below" SQLite, and all of SQLite's features are available.
Time travel: Checkout the snapshot of your database at any point of time in the past.
Lock-free, scalable reads and writes: Optimistic fine-grained concurrency with BEGIN CONCURRENT-like semantics. mvSQLite inherits FoundationDB's lock-free property - not a single distributed lock is acquired during data plane operation.
Get the nice properties from FoundationDB, without its limits: Correctness, really fast and scalable distributed transactions, synchronous and asynchronous replication, integrated backup and restore. Meanwhile, there's no five-second transaction limit any more, and a SQLite transaction can be ~39x larger than FDB's native transaction.
Drop-in addition: Use LD_PRELOAD or a patched libsqlite3.so to plug mvSQLite into your existing apps. Read the docs

Releases

Grab the latest binaries from the Releases page. You can also build your own binaries to run on a platform other than x86-64.

Quick reference

Check the single-page mvSQLite Quick Reference for common operations with mvSQLite.

Try it

Install FoundationDB:

wget https://github.com/apple/foundationdb/releases/download/7.1.15/foundationdb-clients_7.1.15-1_amd64.deb
sudo dpkg -i foundationdb-clients_7.1.15-1_amd64.deb
wget https://github.com/apple/foundationdb/releases/download/7.1.15/foundationdb-server_7.1.15-1_amd64.deb
sudo dpkg -i foundationdb-server_7.1.15-1_amd64.deb

Download the binaries:

curl -L -o ./libmvsqlite_preload.so https://github.com/losfair/mvsqlite/releases/download/v0.2.1/libmvsqlite_preload.so
curl -L -o ./mvstore https://github.com/losfair/mvsqlite/releases/download/v0.2.1/mvstore
chmod +x ./mvstore

Run mvstore, the server-side half that should be colocated with the FoundationDB cluster in production:

RUST_LOG=info ./mvstore \
  --data-plane 127.0.0.1:7000 \
  --admin-api 127.0.0.1:7001 \
  --metadata-prefix mvstore \
  --raw-data-prefix m

Create a namespace with the admin API:

curl http://localhost:7001/api/create_namespace -i -d '{"key":"test"}'

Build libsqlite3 and the sqlite3 CLI: (note that a custom build is only needed here because the sqlite3 binary shipped on most systems are statically linked to libsqlite3 and LD_PRELOAD don't work)

wget https://www.sqlite.org/2023/sqlite-amalgamation-3410000.zip
unzip sqlite-amalgamation-3410000.zip
cd sqlite-amalgamation-3410000
gcc -O2 -fPIC --shared -o libsqlite3.so ./sqlite3.c -lpthread -ldl -lm
gcc -O2 -o sqlite3 ./shell.c -L. -lsqlite3

Set environment variables, and run the shell:

export RUST_LOG=info MVSQLITE_DATA_PLANE="http://localhost:7000"

# "test" is the key of the namespace we created earlier
LD_PRELOAD=../libmvsqlite_preload.so LD_LIBRARY_PATH=. ./sqlite3 test

You should see the sqlite shell now :) Try creating a table and play with it.

Contributing

mvsqlite can be built with the standard Rust toolchain:

cargo build --release -p mvstore
cargo build --release -p mvsqlite
make -C mvsqlite-preload

Internals are documented in the wiki.

mvsqlite's People

Contributors

Stargazers

Watchers

mvsqlite's Issues

Read-write transactions with unbounded size

Currently there is a 50,000 pages (390 MiB) total write size limit on transactions, but larger transactions can be useful in scenarios like schema change.

It is possible to provide an option to trade write concurrency for unbounded read-write transactions by implementing commit locks. I did some work on this in #49, but closed the PR due to the complexity - maybe we should re-consider in the future.

Dependency Dashboard

This issue lists Renovate updates and detected dependencies. Read the Dependency Dashboard docs to learn more.

Rate-Limited

These updates are currently rate-limited. Click on a checkbox below to force their creation now.

Open

These updates have all been created already. Click a checkbox below to force a retry/rebase of any.

Detected dependencies

cargo

mvclient/Cargo.toml

anyhow 1

thiserror 1

tokio 1

log 0.4

tracing 0.1

rand 0.8.5

url 2.3.1

hex 0.4.3

serde 1

rmp-serde 1.1.0

bytes 1.4.0

tokio-util 0.7.3

futures 0.3

serde_json 1

reqwest 0.11.11

byteorder 1.4.3

serde_bytes 0.11

blake3 1.3.1

zstd 0.11.2

mvfs/Cargo.toml

anyhow 1

thiserror 1

tokio 1

tracing 0.1

serde 1

serde_json 1

lazy_static 1.4.0

reqwest 0.11.11

moka 0.9.4

bytes 1.4.0

mvsqlite-fuse/Cargo.toml

anyhow 1

thiserror 1

tokio 1

log 0.4

rand 0.8.5

tracing 0.1

tracing-subscriber 0.3.16

libc 0.2

backtrace 0.3.66

serde 1

serde_json 1

lazy_static 1.4.0

reqwest 0.11.11

fuser 0.11.0

structopt 0.3.26

indexmap 1.9.1

slab 0.4.7

regex 1.6

mvsqlite/Cargo.toml

anyhow 1

thiserror 1

tokio 1

log 0.4

rand 0.8.5

stackful 0.1.5

tracing 0.1

ctor 0.1.22

tracing-subscriber 0.3.16

libc 0.2

backtrace 0.3.66

serde 1

serde_json 1

lazy_static 1.4.0

reqwest 0.11.11

mvstore-stress/Cargo.toml

anyhow 1

thiserror 1

tokio 1

log 0.4

tracing 0.1

rand 0.8.5

url 2.3.1

hex 0.4.3

serde 1

rmp-serde 1.1.0

bytes 1.4.0

tokio-util 0.7.3

futures 0.3

serde_json 1

reqwest 0.11.11

tracing-subscriber 0.3.16

structopt 0.3.26

blake3 1.3.1

rpds 0.12.0

backtrace 0.3.66

mvstore/Cargo.toml

anyhow 1

thiserror 1

tokio 1

log 0.4

tracing 0.1

rand 0.8.5

tracing-subscriber 0.3.16

foundationdb 0.7.0

structopt 0.3.26

hyper 0.14.20

url 2.3.1

hex 0.4.3

serde 1

rmp-serde 1.1.0

bytes 1.4.0

tokio-util 0.7.3

futures 0.3

blake3 1.3.1

serde_json 1

serde_bytes 0.11

zstd 0.11.2

moka 0.9.4

bloom 0.3.2

constant_time_eq 0.2.4

heapless 0.7

lmdb-rkv 0.14.0

bumpalo 3.11.1

itertools 0.10.5

github-actions

.github/workflows/ci.yml

actions/checkout v3

actions-rs/toolchain v1

Swatinem/rust-cache v2

actions/upload-artifact v3

actions/checkout v3

actions-rs/toolchain v1

actions/upload-artifact v3

actions/checkout v3

actions/download-artifact v3

actions/checkout v3

actions/download-artifact v3

actions/checkout v3

actions/download-artifact v3

actions/checkout v3

actions/download-artifact v3

actions/checkout v3

actions/download-artifact v3

actions/checkout v3

actions/download-artifact v3

actions/checkout v3

actions/download-artifact v3

actions/checkout v3

actions/download-artifact v3

actions/checkout v3

actions/download-artifact v3

actions/checkout v3

actions/download-artifact v3

actions/checkout v2

actions/upload-artifact v3

actions/checkout v2

actions/download-artifact v2

actions/download-artifact v2

actions/download-artifact v3

actions/download-artifact v3

softprops/action-gh-release v1

ubuntu 20.04

ubuntu 20.04

ubuntu 20.04

ubuntu 20.04

ubuntu 20.04

ubuntu 20.04

ubuntu 20.04

ubuntu 20.04

ubuntu 20.04

ubuntu 20.04

ubuntu 20.04

ubuntu 20.04

ubuntu 20.04

ubuntu 20.04

ubuntu 20.04

Check this box to trigger a request for Renovate to run again on this repository

Usage with node.js - dynamic linking

Hi @losfair, thank you for what seems to be a monumental work!

I scoured the internet for examples of dynamic linking mvSQLite but found nothing useful.

I did try to modify better-sqlite3/binding.gyp in multiple ways, but without the relevant knowledge it feels like shooting in the dark.

I was hoping you could post some guide, or the patch you've mentioned here WiseLibs/better-sqlite3#855 for everyone's convenient access.

Thank you for your time! :)

Commit group rollback does not release lock

sqlite> begin;
sqlite> create table some_db.t1 (k text, v text);
sqlite> select mv_commitgroup_begin();
sqlite> commit;
sqlite> select mv_commitgroup_rollback();
sqlite> begin;
sqlite> create table some_db.t1 (k text, v text);
  2022-08-05T16:12:38.530509Z ERROR mvsqlite::vfs: failed to acquire lock: hold by another connection
    at mvsqlite/src/vfs.rs:383

Error: database is locked

Compress database pages with zstd

See https://github.com/mlin/sqlite_zstd_vfs to reduce disk space of pages in the foundationdb and to improve performance

`truncate_namespace` should do a range delete on the changelog subspace

Monotonic commit group transactions

Within a commit group, no new transaction should be allowed to start after a transaction has been committed, because the effect of the previous commit is not visible yet and this can cause database corruption.
No two transactions on the same namespace should be allowed in the same commit group. Otherwise there can also be database corruption, in the following case:
1. Two transactions on the same database are started in the same commit group.
2. Both transactions are committed.
3. The commit group is committed. The mutation history is no longer linear, and the database is now corrupt. last_write_version check isn't sufficient here, because the commit itself is atomic.

Dirty pages not cleared from the cache after commit failure

Versions >= v0.1.18-9 && <= v0.2.0-1 contain a correctness issue where dirty pages are not cleared from the cache after a transaction failed to commit. This has been fixed in cb6f3f8.

DO NOT USE releases in this version range.

Online schema change

Stage 1: Writer lock - block concurrent read-write DMLs (#80)
Stage 2: Log replay - fully concurrent

Please update the Cargo.lock for moka cache to v0.9.8

Hi. Currently, moka cache version is pinned to v0.9.4 by the Cargo.lock file:

mvsqlite/Cargo.lock

Lines 1178 to 1179 in f2117d3

 name = "moka" 

 version = "0.9.4"

Please upgrade it to v0.9.8 or the latest v0.11.2.

We found a critical bug that will cause a segfault in a corner case: moka-rs/moka#281 (comment). It is fixed for v0.11.0 and then backported to v0.9.8 and v0.10.3.

Evaluate Profile-Guided Optimization (PGO) applicability

Hi!

Recently I benchmarked a lot of software (including many databases) with PGO and got some interesting results (they are available here).

I think it could be interesting to apply PGO to the project too, since SQLite got measurable improvements from PGO. FoundationDB also gets performance improvements from PGO.

is this used in production?

as titled. any case studies?

Use from Python `sqlite` / creating a standalone `libsqlite3.so`

This is a very exciting project! sqlite is a great interface, and FoundationDB is a great DB.

I'd like to use mvsqlite from Python; it doesn't have to be via the stdlib's import sqlite (i.e. if a different 3rd-party library makes the integration easier), but FUSE is not an option in the context I am using (a unikernel). In fact, even if the LD_PRELOAD approach was usable by Python libraries, this unikernel context does not support that. For my use-case, I'd only be using mvsqlite and I'd be OK if the default sqlite library was overridden so that all sqlite connections use mvsqlite and the regular FS-based sqlite was not available.

So, I'm thinking I'd need a different integration method, which would be along the lines of creating a standalone libsqlite3.so which can override the default system lib. I'm not quite sure how to build something like that, but I could also see it being helpful for other use-cases which are mvsqlite-only and want to avoid LD_PRELOAD.

Does this make sense as a supported use-case? I'm not sure how to do it; I can poke around at modifying the mvsqlite-preload/Makefile for my own purposes, but it could be nice to have support for such an integration method in the repo.

Safety of `journal_mode=off`

mvSQLite does not need SQLite's journaling mechanism. Currently we emulate an in-memory journal to make applications happy, but this is a waste of memory. We need to figure out a way to disable journaling, safely.

There is journal_mode=off, but SQLite's documentation states:

The OFF journaling mode disables the atomic commit and rollback capabilities of SQLite. The ROLLBACK command no longer works; it behaves in an undefined way.

So a questions is that... how undefined is ROLLBACK with journal_mode=off? If it just corrupts the "disk" image, it's fine. We listen on the SQLITE_FCNTL_COMMIT_PHASETWO fcntl callback so we know whether a transaction is really committed. However, if it also corrupts memory, that would be very bad.

mvstore: Cache and reuse FDB transactions

Within the 5-sec limit, reuse the same FDB transaction for multiple mvstore transactions with the same read version.

This reduces the FDB get-read-version overhead.

Commit path: Concurrent commits after snapshot LWV should be observed

In the commit path, previously mvstore returned last-write-version (LWV) to the client, and the client then checks whether LWV matches the local last known version. If so, changelog-based cache invalidation is skipped.

This is not correct with PLCC, since LWV is now a snapshot read. Concurrent commits started after FDB transaction read version will not be observed, and will not conflict on FDB commit.

Consider the following order:

        mvSQLite RV                                       [commit] FDB RV     [commit] FDB Commit
            |                                                   |                   |
Txn 1   -----------------------------------------------------------------------------------------

               mvSQLite RV    [commit] FDB RV     [commit] FDB Commit
                   |                |                   |
Txn 2a  -----------------------------------------------------------------------------------------

               mvSQLite RV                      [commit] FDB RV   [commit] FDB Commit
                   |                                  |                 |
Txn 2b  -----------------------------------------------------------------------------------------

In the Txn1 + Txn2a case, Txn1 will see LWV == Txn2 commit version and return that to the client. This is correct. But in the Txn1 + Txn2b case, Txn1 will see LWV == Txn1 mvSQLite RV, and the client will think nothing has happened during Txn1's execution. This is incorrect.

To fix this, the client needs to check whether the changelog is empty instead.

Executing mvstore for Windows

C:\Users\elee\Downloads\mvsqlite\target\release>set RUST_LOG=info

C:\Users\elee\Downloads\mvsqlite\target\release>mvstore --data-plane 127.0.0.1:7000  --admin-api 127.0.0.1:7001 --metada
ta-prefix mvstore --raw-data-prefix m
Error: failed to initialize server

Caused by:
    0: cannot open fdb cluster
    1: No cluster file found in current directory or default location

MacOS support

I had some trouble trying this on MacOS. Creating a namespace would hang (not sure if this is MacOS specific). Running sqlite3 with DYLD_INSERT_LIBRARIES didn't seem to interpose correctly, sqlite3 would still operate on the local file test. There are some tweaks to compiler and linker flags in spots that were necessary, I can contribute some of those back if it's of interest.

In-memory content cache decreases performance on YCSB workloadc

Related: #92

It is strange that enabling content cache causes performance decrease over time: (this is with a hot cache that has almost all pages)

READ   - Takes(s): 10.0, Count: 103349, OPS: 10344.3, Avg(us): 6159, Min(us): 1108, Max(us): 51167, 99th(us): 11775, 99.9th(us): 48703, 99.99th(us): 50719
...
READ   - Takes(s): 160.0, Count: 1057188, OPS: 6607.8, Avg(us): 9661, Min(us): 797, Max(us): 55519, 99th(us): 50719, 99.9th(us): 53823, 99.99th(us): 55199

while on the same cluster, with content cache disabled:

READ   - Takes(s): 190.0, Count: 1730079, OPS: 9106.2, Avg(us): 7006, Min(us): 809, Max(us): 51423, 99th(us): 12815, 99.9th(us): 47007, 99.99th(us): 50847

Run stress tests without rowid

Run stress tests without rowid. According to the documentation this has some benefits. Your blog posts state that rowid was harming concurrency.

https://univalence.me/posts/mvsqlite-bench-20220930

https://www.sqlite.org/withoutrowid.html

Database corruption with FUSE mode

Found by running ycsb on FUSE:

Preload mode is not affected.

Related: #38

Publish client crates to crates.io

The client crates (mvclient, mvfs) should be available on crates.io.

Specify and verify the system with TLA+

mvSQLite has stacked a lot of logic on top of FoundationDB. The design of these logic should be verified for correctness.

Some specific subsystems that would benefit from verification:

The commit path
Garbage collection

Instructions on how to build mvsqlite for ARM64 architecture

I would like to use mvsqlite but I have a Mac M1 computer (ARM64)
The preload library and the patched libsqlite3.so are only available for AMD64

Do you have detailed instructions on how to build mvsqlite from source? I couldn't find one.

What are the benefits of using an intermediate server mvstore with Foundationdb?

What's the role and benefits of mvstore server?

Is it possible to make mvsqlite client side library connect to Foundation db cluster directly?

Incorrect page-level conflict check logic in `commit()`

This was fixed in 365bb6b. Opened a issue just as a record of reasoning.

PLCC commit works in 4 steps:

Check the existence of the requested page hashes.
Read last-write-version, check for idempotent commits, and write a new last-write-version. This read is a snapshot read, because the transaction flow is not affected by the value.
Read the current latest version of all the pages in the read set. If any of the versions are newer than client_assumed_version, it is a conflict.
Write new hashes to the page index, and write a new changelog entry.

Previously, step 3 incorrectly only added a read conflict range on the current latest version itself. This only protects against truncate_namespace, but not a concurrent commit that adds a newer version of an overlapping page. The fix is to add a entire read conflict range of key..=range_end instead, so concurrent conflicting commits will abort our transaction.

vfs: Commit hook

Transaction commit is done in the xUnlock VFS method currently. When concurrent read-write transactions happen on the same DB, all except one writer process is abort()-ed so the application doesn't wrongfully think its transaction was committed. This behavior is not optimal.

A better option is to use commit hooks.

Invalid link to blog

https://wiki.univalence.me/s/ec5c295b-e8f7-4fcd-aa20-9babe51784b7 gives an invalid link

Design: Consistent mesh for page-level mutation logs

Currently the cache invalidation logic depends on FoundationDB. After each call to /batch/commit, we store the set of pages mutated by the transaction into a special keyspace in FDB, keyed by the commit versionstamp. When a later request to /stat comes in, keys in the range (client_last_known_commit_version, current_read_version) are scanned and returned to the client so that they can invalidate their caches.

This results in a lot of temporary data that is written once and read a few times. It is a waste to let these data go through the entire FDB transaction & storage systems, and a better design is possible.

Import and export databases

Import from and export to SQLite database files.

Target features for v0.3

Online schema change (restricted: database will be read-only to non-migration clients)
- #80
- #99
Overlay databases: create writable snapshots as new "overlay" databases from a version of an existing database
- #84

automatic creation of namespaces

Hi, it would be nice to have away to make the client automatically create a namespace if it doesn't exist.

Is there a way currently to do this?

Jepsen tests

It would be nice to run Jepsen tests on mvsqlite to verify its correctness.

Docker image on docker hub

Hello, thanks for your very interesting work!
It would be really nice to have a public docker image to be able to try it in few seconds

I'm pretty sure this will boost interest and usage as well

Missing causality tracking in `read_page_hash`

Currently we are missing a conflict range in read_page_hash when the version range is empty. This does not cause data corruption yet since SQLite never reads uninitialized pages, but theoretically this is not correct.

Instructions on how to build sqlite3.exe for windows

Windows support with sqlite3.exe

cmd
scoop install llvm openssl-mingw llvm-mingw
cargo build --release -p mvsqlite` Works on Windows 11.
cd mvsqlite/mvsqlite
# Tinkering with shims see zip.
gcc -O2 -o sqlite3 sqlite3.c shell.c shim.c preload.c -L../target/release -LC:/Users/elee/scoop/apps/openssl-mingw/current/lib64 -lmvsqlite -lssl -lcrypto -lWs2_32 -lbcrypt -lUserenv -lntdll
set RUST_LOG=info
set MVSQLITE_DATA_PLANE=http://localhost:7000
sqlite3.exe test
.vfslist
  2022-10-19T05:05:35.621924Z  INFO mvsqlite: mvsqlite initialized, default_sector_size: 8192
    at mvsqlite\src\lib.rs:174

SQLite version 3.39.3 2022-09-05 11:02:23
Enter ".help" for usage hints.
sqlite> .vfslist
vfs.zName      = "mvsqlite"  <--- CURRENT
[...]

mvsqlite.zip

We are assuming that the fdb and mvstore is in an ubuntu os. That they've been started and the admin interface has been used to create a test database.

Other notes

The dependencies openssl-devel are required for ssl and crypto. Might be able to use mbedtls.

Provide a single archive for executing mvsqlite

Describe the project you are working on

I am working on a virtual worlds game that balancing creating and adventuring.

Describe the problem or limitation you are having in your project

There is no single package that provides everything needed to execute mvsqlite.

Describe the feature / enhancement and how it helps to overcome the problem or limitation

Collect mvsqlite console shell
Collect mvsqlite shared library
Collect a tested version of foundation db
Provide a single archive for setup

Describe how your proposal will work, with code, pseudo-code, mock-ups, and/or diagrams

Pick one platform and make sure the package contains everything needed to run mvsqlite.

If this enhancement will not be used often, can it be worked around with a few lines of script?

This is a long series of steps I have documented.

Is there a reason why this should be core?

I want to collaborate rather than work alone.

Add back commit groups

The commit group feature that allows multi-database transactions is removed from the latest version, because an elegant API design is not found. SQLite doesn't give us a way to associate a VFS with its database connection, so we had to use thread-local state. This causes confusion for the user, and does not work with languages that aggressively reschedules coroutines like Go.

Custom freelist handling

SQLite manages an on-disk data structure called "freelist". The freelist is used to track free pages in the database.

The head of the freelist is stored in page 0. Each page allocation/release will write to page 0, and conflict with every other concurrent transaction. This is not good for concurrency.

We should emulate a freelist instead.

Change notification for queries

The current primitives provided by mvstore/mvsqlite is enough to implement efficient change notification for queries: notify the app when the result of running a query may change.

The mechanisms involved are read_set and the interval field provided by the /stat endpoint. Pages read by a transaction can be recorded, and later checked against /stat response.

However, exposing this would either need modification to SQLite itself, or the use of thread-local state.