# flint
A *lighter* SQL database
## Use case
Use Flint if you need: OLTP with low-latency writes of a single-writer SQL
database, high-availability, and read replication.
Use something like Cassandra or ScyllaDB if you need maximum write *throughput*
and single denormalized tables (no JOINs) with sharding across nodes.
If you do not fall within these two categories you may need to reconsider your
schema requirements. Or, your usecase may fall into a specialized category with
specific requirements. Geographic writes: Cockroach or Yubabyte, Analytics:
Clickhouse, or Flexible schema: MongoDB. There are many more application
specific databases, and you will likely know which to choose from if your
requirements necessitate them.
## Architecture
Flint follows a variation of the heap disk format that I've dubbed Log-structured
Segmented Heap (LSH). The heap is split into segments (each segment corresponds
to only one table) of 2MB. Our writes first go to an in-memory table + write-ahead
log (WAL). In high-throughput scenarios where we have a growing queue of
in-memory tables, we append new segments to the heap file, permanently growing
the file. In all other cases we have a background vacuum process that queues up
segments sorted by recency of last write (for temporal locality) and the amount
of free slots in a segment. We can then perform insertions of inserts and updates
of tuples to the "old" segment reclaiming dead tuple slots. Additionally,
between segments (2MB) and pages (4KB), segments are split into *blocks* (64KB).
This is the compressible unit and the unit of writes from the flushed in-memory
tables. For point inserts and updates we also are able to do single page writes
for uncompressed pages.
This architecture hopes to take advantage of the write-throughput of LSM
designs utilizing in-memory tables + WAL, while avoiding the write-amplification
induced by leveling and compaction of sstables. This design also maintains the
advantage of traditional heap structure's superior point queries. We also leave
room for optimizations such as compression and Postgres' HOT tuple locality.
### Indexes
Indexing follows the MySQL primary-key indirection approach instead of updating
every index for every tuple update. At the *slight* cost of read latency, we
can maintain our higher write throughput we gained through the LSH architecture.
### MVCC
Similarly to Postgres, Flint performs tuple level MVCC. All tuples are immutable
once written, until they are automatically vacuumed.
### Compression
Flint (will) implements LZ4 and Zstd compression at the 64KB block level. Blocks
go through two phases when compression is enabled. Phase 1: an uncompressed
block fills to 64KB. At which point this block is eligible for compression in
future writes. We assume that if an entire block is written at once that there
is a large sum of writes at the time and that we want to defer compression to a
later time. Phase 2: compression of the block with inserts. The block is filled
up to a set maximum that gives enough buffer space for future updates. Updates
can have the same uncompressed size, but differing compression ratios so space
is sacrificed to avoid overwrites that go beyond a block's fixed 64KB size (note:
blocks are always padded to 64KB length whether compressed or not).
Phase 1 and 2 make up the transition phase of a block. Once compressed a block
stays compressed (hot blocks defer compression for this reason). Operations on
the block are now always in at block-level granularity; reads and writes. A
compressed block maintains the buffer space so it can continue to be mutable.
Its dead slots and vacuumed and reused for new point updates.
### Replication (future improvements)
Standard deployment model is a single writer database with optional read replicas.
This follows the common practice (used by Postgres) of streaming WAL changes to
read replicas. This requires zero HA infrastructure and is the default solution
for multi-instance deployments.
#### Failover and HA
Optionally, failover with a lease-based, single writer deployment is available.
With a single writer, Flint maintains the low-latency writes of the single-writer
model while having the HA benefits of multi-master deployments. The cost is a
brief amount of downtime and dropped queries (still much shorter of than
alternatives such as Postgres + Patroni). This designates 3-5 nodes in a
membership Raft quorum, and it elects a primary write instance. (*MAYBE*) Each
database (logical) is assigned a Raft group and can assign any of the nodes as
the primary write instance. This distributes logical databases among the Flint
instances for best write-throughput.
What Flint is not. An "infinitely" scaling multi-master database. This meets
the 95% of use-cases where you have single-node writing and storage scale, but
want the option for simple to manage HA and read replication to meet read
throughput demands. You get fast writes, HA, read scaling, and operational sanity
at the cost of geographically dispersed local writes and storage scaling for
single deployments.
#### Heterogeneous Deployments (Advanced)
Each logical database can be configured to a different replica failover (RF)
count. For a 5 node deployment, you can have your primary database as an RF of 5.
So that it has 4 read replicas and failover nodes at any given time. Another
logical database may not have the same read or failover requirements (RF 1), but
it may require greater storage scaling. You can deploy 5 nodes, 4 of which meet
the storage capacity needs of the primary database, and 1 that meets the storage
capacity needs of the primary + secondary logical database. Thus, you have two
logical databases within the same control plane with different HA, read replica,
and capacity constraints.
Example:
```
You don't buy hardware then figure out where databases go. You decide:
db_users: 10TB, RF=3
db_analytics: 5TB, RF=1
db_events: 2TB, RF=2
Then compute required nodes:
db_users needs 3 nodes of at least 10TB each
db_analytics needs 1 node of at least 5TB
db_events needs 2 nodes of at least 2TB
Overlap these assignments:
Node 1: 10TB (db_users primary) + 2TB (db_events primary) = 12TB minimum
Node 2: 10TB (db_users replica) + 2TB (db_events replica) = 12TB minimum
Node 3: 10TB (db_users replica) = 10TB minimum
Node 4: 5TB (db_analytics) = 5TB minimum
```
This requires upfront planning, but has the benefit of deterministic hardware
procurement. Any future "scaling" is vertical scaling of nodes following this
calculation.
## Source Layout
```
Server
└─> Handler
└─> Executor
├─> Parser (SQL → AST)
├─> Planner (AST → Plan)
├─> Storage Engine (data)
└─> execute_plan(Plan, Storage) → Response
```
## Todo
- [ ] Support for variable length primary and secondary keys on indexes, currently
flint currently only supports fixed-length values.
- [ ] Proper serialization of segments/blocks
- [ ] Hash indexes
- [ ] MVCC for indexes (once UPDATE and DELETE are implemented)