- The order of log entries does not matter.
- Users of the log are peers. No client / server distinction.
- When appending a log entry, you can send a copy of the append to all your peers.
- You can ask your peers to refresh the latest log entries.
- When creating a new entry, it is a very good idea to have a nonce field. (I use nano IDs for this purpose along with a timestamp, which is probabilistically unique.)
- If you want to do database style queries of the data, load all the log entries into an in memory database and query away.
- You can append a log entry containing a summary of all log entries you have so far. For example: you’ve been given 10 new customer entries. You can create a log entry of “We have 10 customers as of this date.”
- When creating new entries, prepare the entry or list of entries in memory, allow the user to edit/revise them as a draft, then when they click “Save”, they are in the permanent record.
- To fix a mistake in an entry, create a new entry that “negates” that entry.
A lot of parallelism / concurrency problems just go away with this design.
I.e. "we have 10 customers as of this date" can become immediately invalid if a new entry is appended afterwards with a date before that summary entry (i.e. because it was on a peer which hadn't yet sent it)
For example, we had a 28-day reconciliation period at one company I worked at (and handled over 120 million events per day). If you appended an event earlier than 28 days prior, it was simply ignored. This very rarely happened, but allowed us to fix bugs with events for up to 28 days.
Yes you may be changing history and you may have a business reason not to address that revision immediately (you've already billed them?) - but the system can still learn it made a mistake and fix it (add activity from Jan 30 evening that comes in late to the Feb bill?)
This is surprising, Kafka-like logs are all strictly ordered.
The log entries do have timestamps on them. You can sort by timestamp, but a peer has the right to append an new entry that’s older than the latest timestamp.
When it’s time to have identical replicas, a log entry must be appended that says the log is closed. Once all peers have this, the log is now immutable and can be treated as such. An example of this (for a payroll system) is a collection of entries for time clock in and outs, payroll taxes withheld, direct deposits to employees, etc when it’s time to do a payroll. The log is closed and that data can never be altered, but now the data can be relied on by someone else.
Conceptually this is surprisingly similar to the type of internal logs a typical database like PostgreSQL keeps.
If you want to get rid of an entry, you create a new entry that negates the existing entry.
Synchronization is called "reconcilation" in accounting terminology.
The computer concept is that we have a current state, and changes to it come in. The database with the current state is authoritative. This is not suitable for handling money.
The real question is, do you really care what happened last month? Last year? If yes, a log-based approach is appropriate.
It’s curious that over those projections, we then build event stores for CQRS/ES systems, ledgers etc, with their own projections mediated by application code.
But look underneath too. The journaled filesystem on which the database resides also has a log representation, and under that, a modern SSD is using an adaptive log structure to balance block writes.
It’s been a long time since we wrote an application event stream linearly straight to media, and although I appreciate the separate concerns that each of these layers addresses, I’d probably struggle to justify them all from first principles to even a slightly more Socratic version of myself.
The database only supports CRUD. So while the CDC stream is the truth, it's very low level. We build higher-level event types (as in event sourcing) for the same reason we build any higher-level abstraction: it gives us a language in which to talk about business rules. Kleppmann makes this point in his book and it was something of an aha moment for me.
I'm pretty sure journalled filesystem recycle the journal. There are log-structured filesystem but they aren't used much beyond low-level flash.
- General legers are formed by way of transactions recorded as journal entries. Journal entries are where two or more accounts from the general ledger are debited & credited such that total debits equals total credits. For example, a sale will involve a journal entry which debits cash or accounts receivable, and credits revenue.
- The concept of the debits always needing to equal credits is the most important and fundamental control in accounting. It's is the core idea around which all of double entry bookkeeping is built.
- temporally ordered Journal entries are what form a log from which a general ledger can be derived. That log of journal entries is append-only and immutable. If you make an mistake with a journal entry, you typically don't delete it, you just make another adjusting (i.e. correcting) entry.
Having a traditional background in accounting as a CPA, as a programmer I have written systems that are built around a log of temporally ordered transactions that can be used to construct state across time. To my colleagues that didn't have that background they found it interesting but very strange as an idea (led to a lot of really interesting discussions!). It was totally strange to me that they found it odd because it was the most comfortable & natural way for me to think about many problems.
It was interesting to learn how Restate links events for a key, with key-level logical logs multiplexed over partitioned physical logs. I imagine this is implemented with a leader per physical log, so you can consistently maintain an index. A log service supporting conditional appends allows such a leader to act like the log is local to it, despite offering replicated durability.
Leadership can be an important optimization for most systems, but shared logs also allow for multi-writer systems pretty easily. We blogged about this pattern https://s2.dev/blog/kv-store
There are several services like that, but they are mostly kept behind the scene as a competitive advantage when building distributed systems. AWS uses it behind the scene for many services, as mentioned here by Marc Brooker https://brooker.co.za/blog/2024/04/25/memorydb.html. Facebook has similar systems like LogDevice https://logdevice.io/, and recently Delos https://research.facebook.com/publications/log-structured-pr...
very exciting. this is the future. i am working on a very similar concept. every database is a log at its core, so the log, which is the highest performance part of the system, is buried behind many layers of much lower performing cruft. edge persistence with log-per-user application patterns opens up so many possibilities.
Using a standard format, converting things into logical data, would be significantly slower. It is important that WAL be fast because it is the bottleneck in transactions. It would make more sense to have a separate change streaming service.
> It was strange to me that there was no log-as-service...
Any blockchain that is built upon PBFT derivative is such a system.
Well, yes, but then you've backed into CAP again because you only have one log.
The application state is defined by the log here, and the log drives retries/recovery, so it doesn't much matter if the process that executes the app code splits off. The log would hydrate another one.
Also the one log is at the granularity of a single key or handler execution. More of a logical log, than a physical log or even partition.
In Restate, we implement a logical log-per-key, backed by a partitioned physical log.
For something that is trying to solve the general problem of consistent single ground-truth log, you can't really do much better than Spanner.
https://www.npmjs.com/package/@canvas-js/gossiplog
Joel Gustafson started this stuff at MIT and used to work at Protocol Labs. It’s very straightforward. By any chance sewen do you know him?
I first became aware of this guy’s work when he posted “merklizing the key value store for fun and profit” or something like that. Afterwards I looked at log protocols, including SLEEP protocol for Dat/Hypercore/ pear and time-travel DBs that track diffs, including including Dolt and even Quadrable.
https://news.ycombinator.com/item?id=36265429
Gossiplog’s README says exactly what this article says— everything is a log underneath and if you can sync that (using prolly tree techniques) people can just focus on business logic and get sync for free!
I think they are trying to solve a related problem. "We can consolidate the work by making a generic log that has networking and syncing built-in. This can be used by developers to make automatically-decentralized apps without writing a single line of networking code."
At a first glance, I would say that Gossiplog is a bit more low level, targeting developers of databases and queues, to save them from re-building a log every time. But then there are elements of sharing the log between components. Worth a deeper look, but seems a bit lower level abstraction.
Check this out: https://joelgustafson.com/posts/2024-09-30/introduction-to-c...
And this: https://github.com/canvasxyz/canvas
You might like this interview: https://www.youtube.com/watch?v=JWrRqUkJpMQ
This is what I’m working on now: https://intercoin.org/intercloud.pdf
I learned about distributed incrementally -monotonic logs back at the late 90s, with many other ways to do guaranteed transactional database actions. And I'm quite certain these must have been invented in the 50s or 60s, as these are the problems that early business computer users had: banking software. These are the techniques that were buried in legacy COBOL routines, and needed to be slowly replaced by robust Java core services.
I'm sure the Restate designers will have learned terribly useful insights in how to translate these basic principles into a working system with the complexities of today's hardware/software ecosystem.
Yet it makes me wonder if young programmers are only being taught the "build fast-break things" mentality and there are no longer SW engineers able to insert these guarantees into their systems from the beginning, by standing on the shoulders of the ancients that invented our discipline, so that their lore is actually used in practice? Or am I just missing something new in the article that describes some novel twist?
So I took distributed computing. Which ended up being one of the four classes that satisfied the 80/20 rule for my college education.
Quite recently I started asking coworkers if they took such a class and was shocked to learn how many not only didn’t take it, but could not even recall it being an option at their school. What?
I can understand it being rare in the 90’s but the 00’s and on were paying attention to horizontal scaling, and the 2020’s are rotten with it distributed computing concerns. How… why… I don’t understand how we got here.
The article is well written, but they still have a lot of problems to solve.
Here's a follow-up thought: to what extent did the grey-beards let us juniors down by steering us down a different path? A few instances:
DB creators knew about replicated logs, but we got given DBs, not replicated log products.
The Java creators knew about immutability: "I would use an immutable whenever I can." [James Gosling, 1] but it was years later when someone else provided us with pcollections/javaslang/vavr. And they're still far from widespread, and nowhere near the standard library.
Brendan Eich supposedly wanted to put Scheme into browsers, but his superiors had him make JS instead.
What other stuff have we been missing out on?
[1] https://www.artima.com/articles/james-gosling-on-java-may-20...
I wish James had been in favor of immutability in designing java.util.Date!
And yes, there are moment where you go "oh, we implicitly gave up xyz (i.e., causal order across steps) when we started adopting architecture pqr (microservices). But here is a thought on how to bring that back without breaking the benefits of pqr".
If you want, you can think of this as one of these cases. I would argue that there is tremendous practical value in that (I found that to be the case throughout my career).
And technology advances in zig zag lines. You add capability x but lose y on the way and later someone finds a way to have x and y together. That's progress.
On the contrary. Everything becomes coordinated.
The entire "log" becomes a giant ass mutex lock. Good luck scaling it.
That has been proven to scale well - the way we implement that in Restate is classical shared nothing physical partitioning, with indexing on a key granularity.
So nothing like a shared mutex unless you want to access the same key, which otherwise your database synchronizes, if you want any reasonable level of consistency.
Literally one log - which does indeed reduce your coordination headache, but is susceptible to your "giant ass mutex" comment, and
One log per ... - which brings the coordination problems right back into existence.
- We mean using one log across different concerns like state a, communication with b, lock c. Often that is in the scope of a single entity (payment, user, session, etc.) and thus the scope for the one log is still small, and it reduces coordination headache for coordinating between the systems. You would have a lot of independent logs still, for separate payments.
- It does _not_ mean that one should share the same log (and partition) for all the entities in your app, like necessarily funneling all users, payments, etc. through the same log. What would be needed if you try and do some multi-key-distributed transaction processing. That goes actually beyond the proposal here, and has some benefits of its own, but have a hard time scaling.
"ATProto for Distributed Systems Engineers" describes how updates from the users end up in their own small databases (called PDS) and then a replicated log. What we traditionally think of as an API server (called a view server in ATProto) is simply one among the many materializations of this log.
I personally find this model of thinking about dataflow in large-scale apps pretty neat and easy to understand. The parallels are unsurprising since both the Restate blog and ATProto docs link to the same blog post by Martin Kleppmann.
This arch seems to be working really well for Bluesky, as they clearly aced through multiple 10x events very recently.
[1]: https://atproto.com/articles/atproto-for-distsys-engineers
In a way this article here suggests to extend that
(1) from a log that represents data (upserts, cdc, etc.) to a log of coordination commands (update this, acquire that log, journal that steo)
(2) have a way to link the events related to a broader operation (handler execution) together
(3) make the log aware of handler execution (better yet, put it in charge), so you can automatically fence outdated executions
[1] https://engineering.linkedin.com/distributed-systems/log-wha...
https://engineering.linkedin.com/distributed-systems/log-wha...
If everything’s in one log, there’s nothing to coordinate
Separate logical logs with no need for coordination can only work if they are truly independent systems - no causality between them.
The way our open source project implements that is with a partitioned log and indexes at key-granularity, so it is like virtually a log per key.
This is lovely and I'm itching to try it. One question:
We have a use case where a location gets cut off completely from the internet at large. In that case, it makes sense for the local hardware (typically Android and/or iOS tablets or equivalent) to take over as a log owner: even though you're cut off, if you're willing to swallow the risk (and hence cost) of offline payments, you should be able to create orders, fulfill them, pay for them, close them out, send tickets to the kitchen to cook the food or to the warehouse to fetch the tractor, etc.
Does restate include something that covers that use-case? In the noodling/daydreaming a colleague and I have done, we ended up with something very close to restate (I imagined just using Kafka), except that additionally many operations would have a CRDT nature: eg. you should _always_ be allowed to add a payment to an order, because presumably a real-life payment happened.
I've also noodled with the idea of logs whose canonical ownership can be transferred. That covers cases where you start offline and then reconnect, but doesn't work so well for transactions that start out connected (and thus owned in the datacenter) and need to continue offline.
One could also imagine ensuring that > n/2 consensus members are always located inside the restaurant/hardware store/etc., so if you go offline, you can still proceed. It might even be possible to recognize disconnection and then take one full vote to further subdivide that pool of consensus members so if one dies it doesn't halt progress. This feels like it would be getting very tricksy…
It's mostly based on wpaxos (wide-area consensus), spaxos, fpaxos and pretty neat. The repo above is a productionization of several proof of concepts to get there.
> One could also imagine ensuring that > n/2 consensus members are always located inside the restaurant/hardware store/etc., so if you go offline, you can still proceed.
This is what annoys me to no end about RAFT. It's a great protocol, don't get me wrong, but its too simple for these types of problems. RAFT fails when it doesn't have consensus and because the consensus is non-deterministic, it must have an odd number of nodes. PAXOS, while far more complex than RAFT in terms of "grok", is deterministic so you don't need an odd number of nodes.
If you throw in some flexible quorums, you can do some really neat stuff, like how Atlas handles a "region" (ie, areas connected via the internet instead of the same network) becoming disconnected; but I'm not ready yet. There's still a long way to go!
I wonder why you want to designate the local device as "owner". The devices could simply keep the (closed) payments in a local outbox, and send them to the server when it comes back online. If there is no way for syncing the local changes to the server to fail, you've essentially created a CRDT (at least the "conflict-free" part).
Of course that means you cannot have any server side validation at all (maybe this is what you mean by "owner"?). Because that would mean closed out payments would be rejected by the server and you'd end up in an inconsistent state. A consequence of this is that there could be no balance checking (as an example). Payments in a ledger are inherently a CRDT!
The consensus part is interesting. Would you really need it? Wouldn't one device be sufficient to validate a transaction? And would consensus really even mean something within a small building? If the restaurant catches on fire the data would be lost anyway, so if you don't achieve "high-availability", why bother?
If the simple-majority is inside the restaurant, then the restaurant is online and the rest of the world is offline.
Complex distributed coordination and orchestration is at the root of what makes many apps brittle and prone to inconsistencies.
But we can mitigate much of complexity with a neat trick, building on the fact that every system (database, queue, state machine) is effectively a log underneath the hood. By implementing interaction with those systems as (conditional) events on a shared log, we can build amazingly robust apps.
If you have come across “Turning the Database Inside Out” (https://martin.kleppmann.com/2015/11/05/database-inside-out-...), you can think of this a bit like “Turning the Microservice Inside Out”
The post also looks at how this can be used in practice, given that our DBs and queues aren't built like this, and how to strike a sweet-spot balance between this model with its great consistency, and maintaining healthy decoupling and separation of concerns.
- It means using one log across different concerns like state a, communication with b, lock c. Often that is in the scope of a single entity (payment, user, session, etc.) and thus the scope for the one log is still small. You would have a lot of independent logs still, for separate payments.
- It does _not_ mean that one should share the same log (and partition) for all the entities in your app, like necessarily funneling all users, payments, etc. through the same log. That goes actually beyond the proposal here - has some benefits of its own, but have a hard time scaling.
In your Restate example of the "processPayment" function, how do you handle errors of the "accountService" call? Like, what if it times out or returns a server error?
Do you store the error result and the caller of "processPayment" has to re-trigger the payment, in order to generate a new log?
We, too, are weighed down by how much space AI-focused companies are taking.
The next step is the, how do you make this usable in practice...
Though to be fair I've only read Temporal docs, and this Restate blog post, without much experience in either. Temporal may not have as much on the distributed locking (or concept of) side of things that Restate does, in this post.
If you only consider appending results of steps of a handler, then you have something like Temporal.
This here uses the log also for RPC between services, for state that outlives an individual handler execution (state that outlives a workflow, in Temporal's terms).
[1]: https://engineering.linkedin.com/distributed-systems/log-wha...
Things like types that encode what events are legal in a log, first class support for data versions, fast file read and writes, etc
I think the monospaced font is Comic Mono.[3]
[1] https://plus.excalidraw.com/virgil
When you build stateful handlers, the state per key is in the internal DB, and that get's you a similar effect to log compaction, i.e., retain one value per key.
We then copy the summary transactions to a new log, and compress and archive the old log.
You can identify high throughput and low throughput types of log entries and segregate them into different log streams. For example, the “new customer/change customer info” stream probably gets way less traffic than the “customer has logged in” stream. The former is also harder to summarise. Put the hard to summarise but low volume stuff in its own log.
https://github.com/restatedev/restate/blob/main/LICENSE#L1
> Business Source License 1.1
https://spdx.org/licenses/BUSL-1.1.html
> The Business Source License (this document, or the “License”) is not an Open Source license.
Suggest exploring e.g. https://github.com/dbos-inc/dbos-transact-py
That said - the Additional Use Grant for Restate is fairly ambiguous:
> Additional Use Grant: You may make use of the Licensed Work, provided that you may not use the Licensed Work for an Application Platform Service.
> An “Application Platform Service” is a commercial offering that allows third parties (other than your employees and contractors) to access the functionality of the Licensed Work by registering new services (directly or indirectly) with the Licensed Work for the purpose of invoking such services through the Licensed Work.
What does it mean to "access the functionality"? What does it mean to "register [a] new service" ? How do you determine the "purpose" of invoking such services?
I understand that the intent is to prevent someone from launching a competing "Restate-as-a-Service" business; but broadly written clauses like this scare me off. If I want to build a totally different kind of business that heavily _relies_ on Restate, I would worry that these ambiguous, broad definitions could easily be used against me.
I really wish that companies adopting the BSL would put much more clarity into the license text. I know there's likely very good business reasons not to - you may constrain yourself in the future by doing so - but in my mind it would be the "right" thing to do. You'd get people actually using and contributing back to your software, much like they would under a more permissive license.
But DTs have a huge problem: What happens if the owner of the lock netsplits?
Either the DTC waits (potentially forever?) for the owner of the lock to get back in touch and release the lock, or a timeout is applied and now the owner of the lock (who may be unaware of the netsplit) will be out of sync with the system.
The Virtual Objects in Restate are much like actors. They are somewhat inspired by Orleans [1], and you could call them virtual stateful actors. They blend with the durable execution for processing messages with multiple durable steps.
Regarding temporal, check also this question: https://news.ycombinator.com/item?id=42815318
Interesting analogy - in a way it is doing something CSP-like in a distributed app/service architecture with the all the different processes and components that are there. The shared log (or a partition of that) being a way to establish a sequential order.
The end result is https://pipe.pico.sh which is an authenticated, networked *nix pipes over SSH. Since it relies on stdin/stdout via SSH it's one of the easiest pubsub systems we've used and we keep finding its ergonomics powerful. We have a centralized log-drain, metric-drain, and cache-clearing-drain all using `pipe`.