[HN Gopher] Write a time-series database engine from scratch
___________________________________________________________________
Write a time-series database engine from scratch
Author : todsacerdoti
Score : 150 points
Date : 2021-07-04 16:31 UTC (6 hours ago)
(HTM) web link (nakabonne.dev)
(TXT) w3m dump (nakabonne.dev)
| jandrewrogers wrote:
| This is a good tutorial.
|
| The problem of out-of-order data becomes more challenging as
| ingest throughput requirements increase if your storage
| representation must guarantee a strict total order. In high-
| throughput designs this is often handled by relaxing the strict
| total ordering requirement for how the data is represented in
| storage. As long as the time-series has an _approximate_ total
| order at ingest time, there are many techniques for inexpensively
| reconstructing a strict total order at query time.
| roskilli wrote:
| Right exactly. As a point of reference, within M3DB each unique
| time series has a list of "in-order" compressed
| timestamp/float64 tuple streams. When a datapoint is written
| the series finds an encoder that it can append while keeping
| the stream in order (timestamp ascending), and if no such
| stream exists a new stream is created and becomes writeable for
| any datapoints that arrive with time stamps greater than the
| last written point.
|
| At query time these streams are read by evaluating the next
| timestamp of all written streams for a block of time and then
| taking the datapoint with the lowest timestamp of the streams.
|
| M3DB also runs a background tick that targets to complete
| within a few minutes each run to amortize CPU. During this
| process each series merges any streams that have sibling
| streams created due to out of order writes, producing one
| single in order stream. This is done by the same process used
| at query time to read the datapoints in order and they are
| consequently written to a new single compressed stream. This
| way extra computation due to our of order writes is amortized
| and only if a large percentage of series are written in time
| descending order do you end up with a significant overhead at
| write and read time. It also reduces the cost of persisting the
| current mutable data to a volume on disk (whether for snapshot
| or for persisting data for a completed time time window).
| minitoar wrote:
| For Interana I think we end up doing this by batching writes &
| sorts, and not really having a strict guarantee on when data
| imported actually shows up in query results.
| winrid wrote:
| Any cool "create a database from scratch" books? Sounds like a
| fun read. Like The Grapics Programming Black Book, but for
| databases.
|
| Of course there's plenty of literature on individual components,
| but a holistic view would be fun to read.
|
| I suppose you could read sqlite or postgres code... but that
| doesn't fit well on a Kindle. :)
| bob1029 wrote:
| You could also start from first principles and essential
| abstractions. If you build a solid key-value store, it is
| possible to construct higher-order stores on top.
|
| Once you can quickly find _a thing_ with _some key_ , any
| degree of structure and complexity is possible from that point.
| Column-based, row-based, document-based, etc. All are possible
| to build on top of K-V. Might not be the most optimal solution,
| but it is a very accessible path in my experience. You can
| start defining types like Table, Column, Row, Document, etc.
| which all leverage this idea that you can trivially refer to
| another thing by some identifier. For instance,
| Table.FirstRowId and Table.LastRowId could be used to refer to
| the logical extents of a collection of rows that might be
| linked together both ways (e.g. Row.PreviousRowId,
| Row.NextRowId).
| azhenley wrote:
| Database Design for Mere Mortals
| eatonphil wrote:
| It's not a book but I wrote a series on writing a postgres
| clone from scratch in Go.
|
| https://notes.eatonphil.com/tags/database.html
| rubyn00bie wrote:
| Yes indeed, friend! This one is a classic:
| https://cstack.github.io/db_tutorial/
|
| It's a sqlite clone from scratch.
| ddlutz wrote:
| Have you gone through it? I've seen it around for years,
| however it unfortunately looks unfinished and unmaintained. I
| think I'd be unfulfilled going through all of it just to not
| have a finished tutorial.
| ardit33 wrote:
| This is a good write up. Many years ago I decided to code/program
| a log based db, to see how far can I go. It was supposed to be
| Light-weight (Berkley DB was the inspiration). It had a working
| stream to file for all changes, and a compaction thread in the
| background.
|
| What I learned... creating the main/basic features of non-
| relational database (log based), is easy... but it is the edge
| cases that hit you hard and dealing with them creates about 90%
| of the code.
|
| It was a fun exercise from which I learned a lot.
___________________________________________________________________
(page generated 2021-07-04 23:00 UTC)