Comment by bob1029 | Hacker News Reader

Comment by bob1029 | Hacker News Reader

Parent Full thread

We have a new business system we are trying to build that has a lot of very granular auditing and versioning requirements throughout, and this is where I started looking.

After a while of screwing with this kind of approach, I realized that the number of different types of objects involved was going to cause an explosion in the number of related auditing and versioning tables. Keeping track of not only who changed something but also the exact facts they changed (such that you could revert as needed) requires a lot of additional boilerplate in each instance.

So, I made a pretty big gamble and went all-in on an event-sourced abstraction where everything is written to 1 gigantic append-only log of events. Turns out, this was worth it in our case. As long as everything has a timestamp and you have a way to refer to specific log entries (i.e. by offset), you basically have a complete solution. The hard parts are handled by a JSON serializer and gzip. We use in-memory indexes that are simply long/long dictionaries that map an object identity to a physical log offset.

The only downside with what I have proposed is that there is no garbage collection or cleanup possible. At this time, this is actually a highly-desirable property of the system. Disk space is cheap. Losing 3 weeks of work to an accidental button click is not.

> The only downside with what I have proposed is that there is no garbage collection or cleanup possible.

If you are using Kafka, you can use log compaction[0] to achieve this. It's also possible to delete individual entries with tombstone records, assuming your objects have a "key" attribute.

[0]https://kafka.apache.org/20/documentation.html#compaction

In mysql parlance, I think it is pretty common to run a replicated server where you save a copy of the binlogs, which are the replication messages that the primary sends to the secondary to keep the secondary in sync. That supposedly lets you reconstruct every state that the db has been in. It would depend on implementation details that I haven't checked though: it doesn't follow automatically from replication. But I know of some sites that do it that way.

There is also a concept of "purely functional data structures" used for example by Happstack. Those are data structures where you never mutate anything, but instead do updates by allocating new nodes and pointers, so an update takes O(log n) operations since you have to reallocate the path to the root of a b-tree like structure, instead of just overwriting a cell. In principle that should still not be too bad, if the amount of data isn't huge. For whatever reason, though, happstack's performance is apparently disappointing even when you take its design into account.

This is precisely what https://github.com/sirixdb/sirix does. A resource in a database is stored in a huge persistent structure of index pages.

The main index is a trie, which indexes revision numbers. The leaf nodes of this trie are "RevisionRootPages". Under each RevisionRootPage another trie indexes the main data. Data is addressed through dense unique and stable 64bit int nodeKeys. Furthermore, the user-defined secondary indexes currently are also stored as further tries under a RevisionRootPage.

The last layer of inner pages in a trie adds references to a predefined maximum number of data page fragments. The copy-on-write architecture does not simply copy whole data pages, but it depends on the versioning algorithm. The default is a sliding snapshot algorithm, which copies changed/inserted/deleted nodes plus nodes, which fall out of a predefined window (usually the size is low, as the page fragments have to be read from random locations in parallel to reconstruct a full page). This reduces the amount of data to store for each new revision. The inner pages of the trie (as well as the data pages) are not page-aligned, thus they might be small. Furthermore, they are compressed before writing to persistent storage.

Currently, it offers a single read-write transaction on a resource plus read-only transactions without any locks.

Those logs though are at the lower Db level of abstraction (using them requires getting out of the database proper).

What the parent is referring to is the actual database schema itself. It’s a giant versioned log essentially.

Presumably there is some sort of ‘key frame’ however, or you’d need to go all the way back however many years ago to start rebuilding the objects current state?

> Presumably there is some sort of ‘key frame’ however, or you’d need to go all the way back however many years ago to start rebuilding the objects current state?

Correct. My criteria for the snapshot feature becoming a priority will be when log recovery takes longer than 5 minutes. I cannot see that occurring anytime soon based on current figures.

That event architecture also sounds like it has to be serialized, right? But, the idea of database is concurrent operations. Is there a conflict?

Everything in my solution is serialized through a LMAX Disruptor ringbuffer to ensure single writer and sequential processing of events.

As posted in another comment that's basically what https://github.com/sirixdb/sirix supports along with easily reconstructing former revisions of a JSON document (or any node therein), sophisticated secondary (also versioned) indexes, querying with JSONiq and optimizations at query compile time as for joins and aggregates....

In our case we opted for three types of secondary user-defined indexes (besides the main document trie index to find unique, stable nodes by their 64bit ID), namely

1. field indexes

2. path indexes

3. content-and-structure indexes which index paths and their typed values

Furthermore a path summary keeps track of all distinct paths in the JSON resource.

I like your event sourcing approach. I was recently looking into YugabyteDB changde data capture and it quickly became apparent that cdc can be used for exactly that. I wrote about It here: https://gruchalski.com/posts/2022-02-23-yugabytedb-change-da....

One problem with the cdc approach is not having a way to monitor ddl operations. However, at least in any Postgres capable database with extensions support, it’s pretty easy to either: use pg_audit or write a rudimentary extension for ddl streaming.

DDL transactions should be committed orders of magnitude less frequently than data transactions, so it’s reasonable to separate their logging.

Interestingly enough, the new CDC SDK in YugabyteDB 2.13 supports DDL statements as well: https://github.com/yugabyte/yugabyte-db/blob/398a2b1a460ed8f....

I've done this before on smaller scales. Writing a set of table-valued functions that expose the event data in relational form "as of date given by param X", and views on top of that where X is set to getdate(), you get a very ergonomic way to consume "current" & "historical" data. Materialized views can make querying these more natural relations very cheap if your engine supports them.

Can you explain how you "go back" to an earlier state? I assume your event stream writes into a database, and that database is then used by the front end. Do you replay the entire stream up until date/time x into a separate database to restore or check out the state up to then?

Usually you make heavy use of SELECT DISTINCT ON (…) FROM … ORDER BY ts DESC and you can use WHERE ts < ts_0 to recreate until ts_0. Liberal use of MATERIALIZED VIEWs.

> everything is written to 1 gigantic append-only log of events

Do you replicate that stream to avoid SPOF?

I am currently investigating synchronous replication of each compressed log batch to a 2nd host. We are totally fine with availability issues (i.e. system down because log replication broken). Availability problems are far preferable to consistency and other nasty bugs.

Reply on news.ycombinator.com