rystsov

Yep, I still consider them to be cutting edge. Paxos was written in 1990 but the industry adopted it only in 2010s. For example I've looked through pBFT and it doesn't mention reconfiguration protocol which is essential for industry use. I've found one from 2012 so it should be getting ripe by now.

We can't ignore or pretend that network partitioning doesn't happen. When people talk about choosing two out of CAP the real question is C or A because P is out of our control.

When we combine network partitioning with single local data suffix loss it either leads to a consistency violation or to a system being unavailable desperate the majority of the nodes being are up. At the moment Kafka chooses availability over consistency.

Also I read Kafka source and the role of network partitioning doesn't seem to be crucial. I suspect that it's also possible to cause similar problem with a single node power-outage https://twitter.com/rystsov/status/1641166637356417027 and unfortunate timing

Strongly consistent protocols such as a Paxos and Raft always choose consistency over availability and when consistency isn't certain they refuse to answer.

Raft & Paxos: any number of nodes may be down, as soon as the majority is available a replicated system is available and doesn't lie.

Kafka as it's described in the post(): any number of nodes may be down, at most one power outage is allowed (loss of unsynced data), as soon as the majority is available a replicated system is available and doesn't lie.

The counter-example simulates a single power outage

() https://jack-vanlightly.com/blog/2023/4/24/why-apache-kafka-...

I was following Jepsen results since Kyle's first post and it's amazing that the blog post series became a well respected company

The report revealed the following unknown consistency issues which we had to fix:

  - duplicated writes by default
  - aborted read with InvalidTxnState
  - lost transactional writes

The first issue was caused by a client: starting with recent versions the client has idempotency on by default but when the server-side doesn’t support it (we had idempotency behind a feature flag) the client doesn’t complain. We will enable idempotency by default in 21.1.1 so it shouldn't be an issue. Also it's possible to turn the feature flag on for the older versions.

The other two issues were related to the transactions; we haven’t chaos tested the abort operation since it’s very similar to commit but even the tiny difference in logic was enough to hide the bug. It’s fixed now too.

Hey folks, I wrote this post and I'm happy to answer questions

Cool! What did you test? I've played with Jepsen and Cosmos DB when I was at Microsoft but we had to ditch ssh, write custom agent and inject faults with PowerShell command lets.

Can you clarify what you mean? AFAIK with manual commit you have the most control over when the commit happens

Look at this blog post describing a data loss caused by auto-commit: https://newrelic.com/blog/best-practices/kafka-consumer-conf...

Also there also may be more subtle issues with auto-commit: https://github.com/edenhill/librdkafka/issues/2782

Documentation is a bit confusing: the protocol was evolved over time (new KIPs) and there is mismatch between the database model and kafka model. But we see a lot of potential in the Kafka transactional protocol.

At Redpanda we were able to push to 5k distributed transactions cross replicated shard. It's a mind-blowing for a database to achieve the same result.

Also Kafka transactional protocol works at low level it's very easy to build systems on top of it. For example, it's very easy to build a Calvin inspired system http://cs.yale.edu/homes/thomson/publications/calvin-sigmod1...

It wasn't a big surprise for us. Redpanda is a complex distributed system with multiple components even at the core level: consensus, idmepotency, transactions so we were ready that something might be off (but we were pleased to find that all the safety issues were with the things which were behind the feature flags at the time).

Also we have internal chaos test and by the time partnership with Kyle started we already identified half of the consistency issues and sent PRs with fixes. The issues got in the report because by the time we started the changes weren't released yet. But it is acknowledged in the report

> The Redpanda team already had an extensive test suite— including fault injection—prior to our collaboration. Their work found several serious issues including duplicate writes (#3039), inconsistent offsets (#3003), and aborted reads/circular information flow (#3036) before Jepsen encountered them

We missed other issues because haven't exercised some scenario. As soon as Kyle found the issues we were able to reproduce them with the in-house chaos tests and fix. This dual testing (jepsen + existing chaos harness) approach was very beneficial. We were able to check the results and give feedback to Kyle if he found a real thing or if it looks more like an expected behavior.

We fixed all the consistency (safety) issues, but there are several unresolved availability dips. We'll stick with Jepsen (the framework) until we're sure we fixed then too. But then we probably rely just on the in house tests.

Clojure is very powerful language and I was truly amazed how fast Kyle for able to adjust his tests to new information but we don't have clojure expertise and even simple tasks take time. So it's probably wiser to use what we already know even it it a bit more verbose.

I've created this list a while ago https://github.com/redpanda-data/awesome-distributed-transac.... Maybe it's time to update it.

Usually I start with a couple of seed papers then follow the references, look at the other papers the authors wrote. When a phd student explores an area they write several paper on the topic so there is a lot material to read. But the real gem is the thesis, it has depth, context and a lot of links to other work in the area.

The mess is mostly the result of the mismatch between the classic database transactional model and kafka transactional model (G0 anomaly). If you read the documentation without the database background it seems ok, but when you notice the differences between the models it becomes hard to understand if it's a bug or property of the Kafka protocol.

There is a lot of research happening around this area even in the database world. The list of the isolation levels isn't final and some of the recent developments include PC-PSI and NMSI which also seem to "violate" the order. I hope one day we get the formal academic description of the Kafka model. It looks very promising.

Different systems solve different problems and have different functional characteristics. Actually one of the thing which Kyle highlighted in his report is write cycles (G0 anomaly), it isn't a problem of the Redpanda implementation but a fundamental property of the Kafka protocol. Records in Kafka protocol don't have preconditions and they don't overwrite each other (unlike the database operations) so it doesn't make sense to enforce order on the transactions and it's possible to run them in parallel. It gives enormous performance benefits and doesn't compromise safety.

Hey folks, I was working with Kyle Kingsbury on this report from the Redpanda side and I'm happy to help if you have questions

Yes and no, we do both. For ack=-1 we wait for fsync & replication confirmation but for other modes we relaxed the behavior.

Author is here AMA :)

Hi Kyle, thanks for the Elle :) I want to use Elle to check long histories of transactions over small set of keys with read dominant workload, the paper recommends to use lists over registers but when the history becomes long on the one hand it becomes too wasteful to read the register's history on each request on the other hand the Elle's input becomes very large. E.g. when each read should return the whole register's history the size of history grows O(n^2) compared to the case when the reads return just the head.

So I'm curios how would you have described the ability of finding violations with Elle using read-write registers with unique values vs the append-only lists?

I agree it's hard for me too to be precise about naming in academic sense. But this published paper "Writes: the dirty secret of causal consistency" says that both Cosmos DB and MongoDB have causal consistency so I don't know.. At least Cosmos DB and MongoDB provide the same guarantees for session/causal.

It's off-topic. But yes, Cosmos DB has rigorous tests[1] including Jepsen (a tool).

[1] https://twitter.com/dharmashukla/status/869104163510034432

> Thus far, causal consistency has generally been limited to research projects ... MongoDB is one of the first commercial databases we know of which provides an implementation.

Cosmos DB provides session consistency (looks like an another name for causal consistency) at least since 2014 [1].

Cosmos DB's session guarantees [2]: consistent prefix, monotonic reads, monotonic writes, read-your-writes, write-follows-reads.

Mongo DB's causal consistency guarantees [3]: monotonic reads, monotonic writes, read-your-writes, write-follows-reads.

Doubt that four years later still qualities as one of the first.

[1] https://www.infoq.com/news/2014/08/microsoft-azure-documentd...

[2] https://docs.microsoft.com/en-us/azure/cosmos-db/consistency...

[3] https://docs.mongodb.com/manual/core/read-isolation-consiste...

I agree that CRDT don't help with data-scalability (eventually all data converge on a single node), just wanted to comment on the following phrase

> CRDTs don't help in the case that you don't want to deliver wrong answers

Usually when people talk about CRDT they assume that a client talks to a single node and then a background process replicate data to others node. Before this replication is done, if a client contact the other node they get "wrong answers". But nothing prevent a client always talk with quorum of nodes and do replication on its own, in this case we'll get always only right answers :)

However we still need to merge if we do quorum-ing. Paxos/Raft-based systems basically take optimistic lock then they quorum (see prepare phase) so they suffer from contention and need a leader to serialize requests (leader in paxos/raft is for liveness not safety). But with CRDT we always can merge so concurrent requests are not a problem and we can achieve better level of parallelism (request-scalability).

CRDT may help: if you read from quorum, merge(+modify) and write back to quorum for read (write) then you'll always get right answers.

"unlike Google Percolator, FoundationDB, or similar systems, FaunaDB places no constraints on replica distance and is practical to deploy at global internet latencies"

"For each batch of parallel transactions, they are inserted into a distributed, write-ahead transaction log"

"Replicas must achieve consensus for how to insert new transactions into the log. FaunaDB uses an optimized Raft implementation to achieve consensus."

There are constrains on running consensus across the world (Raft), it adds at least 200 ms to serialize txs. Also higher latency means longer interval between hearbeats and hence longer downtime if leader is isolated - known issue of leader based consensus protocols (see "There Is More Consensus in Egalitarian Parliaments" paper[1] or "In search of a simple consensus algorithm" post[2])

Google's Percolator doesn't depend on global consensus but just on global TSO (timestamp oracle) which is possible to implement in a way:

- it doesn't suffer from leader isolation (no leader)

- doesn't have bottleneck (each node handles requests)

- doesn't touch disk on each request

details in the "Quorum clock: leaderless distributed clock" post[3].

[1] https://www.cs.cmu.edu/~dga/papers/epaxos-sosp2013.pdf

[2] http://rystsov.info/2017/02/15/simple-consensus.html

[3] http://rystsov.info/2018/10/01/tso.html

Roaring 20s were pretty liberal in USSR too - https://en.wikipedia.org/wiki/LGBT_history_in_Russia#LGBT_Hi...

It would be interesting to repeat the research in St.Petersburg, the siege during the WW2 lasted more than 2 year and there were 642,000 casualties among civilians.

https://en.wikipedia.org/wiki/Siege_of_Leningrad

Some update on Gryadka - Tobias Schottdorf and Greg Rogers independently explored it with TLA+ and didn't find any issues: - https://tschottdorf.github.io/single-decree-paxos-tla-compar... - https://medium.com/@grogepodge/tla-specification-for-gryadka...

I responded in the comments: http://tschottdorf.github.io/if-its-not-paxos-its-probably-w... the analysis is based on a false assumption about the read operation

I don't know TLA+ yet but I'll assist anybody with an explanation on how Gryadka works.

It's good but wrong because it's based on a false assumption about how the read operation works. I explained it in the comments.