3 ms·

Thank you for sharing your strategy for concurrent transactions. It's a very interesting topic :) I see however some possible pain points in this strategy. My

Thank you for sharing your strategy for concurrent transactions. It's a very interesting topic :) I see however some possible pain points in this strategy. My main concerns are: * This looks to me a lot like some poor (no pun intended) form of MVCC (https://en.wikipedia.org/wiki/Multiversion_concurrency_control https://en.wikipedia.org/wiki/Multiversion_concurrency_contr...). Basically, it supports only two "V"s, the "on" and "off", while "normal" MVCC implementations support as many as required. * Related to the above, I don't see how you can support more than one overlapping tx with this strategy. Sure, I'll keep tuned for the next post on this topic, but I fail to see how --without exclusive locking-- it could be done based on these principles. * Every read seems like it needs to check the switch. I understand this might be expensive, specially if there is a concurrent modification in progress. Keys are co-located in the node, but they still require random access. * It looks like even aborted transactions require writes to the database. And every transaction requires at least two writes (the write intent and its consolidation to the key). I don't expect good performance here. Please help me clarify these questions, specially if I'm missing something. Hope it helps anyway. Thanks!

wicknicks 11y ago
Yeah, I am not sure how multiple queries will co-exist in this strategy. Especially, if you have two queries which are not commutative (say, one which increments a column and the other one which replaces the column with its square root). Also, how does this work in the presence of replicas? Does every replica go through the strategy? What if one or more replicas go down during a transaction?
saganus 11y ago
Excellent questions! thanks for this, I Was too lazy to lay them down like this. I hope they get an answer!
openasocket 11y ago
I'm not at all associated with the Cockroach folks, but I'm pretty sure they actually do use MVCC, and the description they gave in this post is a simplification of the actual implementation. At least, there are a bunch of references to MVCC in their codebase: https://github.com/cockroachdb/cockroach/tree/master/storage/engine https://github.com/cockroachdb/cockroach/tree/master/storage...
patrickaljord 11y ago
> It looks like even aborted transactions require writes to the database. And every transaction requires at least two writes (the write intent and its consolidation to the key). I don't expect good performance here. Isn't this kind of needed in case of unexpected network partitions? I'm thinking of tests like Jespen (https://aphyr.com/tags/jepsen https://aphyr.com/tags/jepsen), if you want to retain full ACID and consistency in worst case scenarios, you'll need these kind of slower transactions checks, I may be wrong though.
mrtracy 11y ago
Hi there, blog author here! This blog post is not a full description of CockroachDB's transaction strategy. If you're interested, you can find a complete rundown of our strategy here: (https://github.com/cockroachdb/cockroach/blob/master/docs/design.md#lock-free-distributed-transactions https://github.com/cockroachdb/cockroach/blob/master/docs/de...). However, that is a very terse document: this blog post was an attempt to expand on one of the basic ideas behind our design. My goal to clearly explain how we approach atomicity, without broaching the complicated topic of Isolation. That said, I will attempt to address some of the pain points you raised: * Cockroach does use a full MVCC system; writes are "append-only" and we keep the full history of values for each key. Keys can be queried at a timestamp, and every write explicitly specifies a timestamp as well (each transaction is assigned a timestamp, all writes will use the same timestamp). With this system, each transaction operates on a snapshot of the database. * Our strategy for overlapping transactions is straightforward: if two concurrent transactions have a conflict, one of them will be aborted and retried. Write intents (in combination with another component, the "read timestamp cache") are used by conflicting transactions to discover each other. Once discovered, the decision of which in-progress transaction gets aborted is deterministic - each transaction is assigned a random integer "priority", and the transaction with the highest priority always wins the conflict (unless one of the transactions has already committed). * Every read does need to check the switch if the key being read has a write intent; reads of plain values (with no in-progress transaction) do not need to check a switch. * Yes, aborted transactions can write intents to the database in our current system. However, the second "write" (consolidation) happens asynchronously, and is not required for the transaction to function correctly. It should only be noticed if the key is accessed again by another transaction before it is consolidated. For committed transactions, I don't believe this is a particularly high price to pay. A system that doesn't write aborted transactions to disk would be considerably more complex; I think it would involve two commit phases (I. The transaction has been "committed" in memory, and can no longer be aborted by other transactions II. The transaction must successfully commit all changes to disk in an atomic fashion). You likely could get some additional performance (if disk latency is a sufficient bottleneck), but it would be hard won in terms of complexity.
- ahachete 11y ago
  Hi, thanks for the reply! I will read the more detailed document. It would probably make more sense to me. From the description of MVCC that you say, it looks like you're storing the whole replicated state machine that you have via the Raft protocol. If txs are assigned such a timestamp, I agree that could operate as a full MVCC system. Good. Regarding the overlapping txs, it makes sense once you say you're aborting txs. Without that, it sounded really difficult to achieve without locking. When you say reads only check the switch if there is a write intent, where is exactly that "switch"? I understood it's not with the key, but rather at some other random location. If that's the case, I insist that you require two reads: one for the key, the other one for the switch. Os is the switch co-located with every key? Regarding the aborted txs, I can't argue without numbers, but I'd like to see those. I mean: you may abort txs voluntarily (I want to ROLLBACK) or involuntary (there's a concurrent conflict). That may or may not be a high number. But all of those would be written to disk, so it might become a high price.

wicknicks 11y ago

Yeah, I am not sure how multiple queries will co-exist in this strategy. Especially, if you have two queries which are not commutative (say, one which increments a column and the other one which replaces the column with its square root). Also, how does this work in the presence of replicas? Does every replica go through the strategy? What if one or more replicas go down during a transaction?

saganus 11y ago

Excellent questions! thanks for this, I Was too lazy to lay them down like this. I hope they get an answer!

openasocket 11y ago

I'm not at all associated with the Cockroach folks, but I'm pretty sure they actually do use MVCC, and the description they gave in this post is a simplification of the actual implementation. At least, there are a bunch of references to MVCC in their codebase: https://github.com/cockroachdb/cockroach/tree/master/storage/engine https://github.com/cockroachdb/cockroach/tree/master/storage...

patrickaljord 11y ago

> It looks like even aborted transactions require writes to the database. And every transaction requires at least two writes (the write intent and its consolidation to the key). I don't expect good performance here. Isn't this kind of needed in case of unexpected network partitions? I'm thinking of tests like Jespen (https://aphyr.com/tags/jepsen https://aphyr.com/tags/jepsen), if you want to retain full ACID and consistency in worst case scenarios, you'll need these kind of slower transactions checks, I may be wrong though.

mrtracy 11y ago

Hi there, blog author here! This blog post is not a full description of CockroachDB's transaction strategy. If you're interested, you can find a complete rundown of our strategy here: (https://github.com/cockroachdb/cockroach/blob/master/docs/design.md#lock-free-distributed-transactions https://github.com/cockroachdb/cockroach/blob/master/docs/de...). However, that is a very terse document: this blog post was an attempt to expand on one of the basic ideas behind our design. My goal to clearly explain how we approach atomicity, without broaching the complicated topic of Isolation. That said, I will attempt to address some of the pain points you raised: * Cockroach does use a full MVCC system; writes are "append-only" and we keep the full history of values for each key. Keys can be queried at a timestamp, and every write explicitly specifies a timestamp as well (each transaction is assigned a timestamp, all writes will use the same timestamp). With this system, each transaction operates on a snapshot of the database. * Our strategy for overlapping transactions is straightforward: if two concurrent transactions have a conflict, one of them will be aborted and retried. Write intents (in combination with another component, the "read timestamp cache") are used by conflicting transactions to discover each other. Once discovered, the decision of which in-progress transaction gets aborted is deterministic - each transaction is assigned a random integer "priority", and the transaction with the highest priority always wins the conflict (unless one of the transactions has already committed). * Every read does need to check the switch if the key being read has a write intent; reads of plain values (with no in-progress transaction) do not need to check a switch. * Yes, aborted transactions can write intents to the database in our current system. However, the second "write" (consolidation) happens asynchronously, and is not required for the transaction to function correctly. It should only be noticed if the key is accessed again by another transaction before it is consolidated. For committed transactions, I don't believe this is a particularly high price to pay. A system that doesn't write aborted transactions to disk would be considerably more complex; I think it would involve two commit phases (I. The transaction has been "committed" in memory, and can no longer be aborted by other transactions II. The transaction must successfully commit all changes to disk in an atomic fashion). You likely could get some additional performance (if disk latency is a sufficient bottleneck), but it would be hard won in terms of complexity.

ahachete 11y ago
Hi, thanks for the reply! I will read the more detailed document. It would probably make more sense to me. From the description of MVCC that you say, it looks like you're storing the whole replicated state machine that you have via the Raft protocol. If txs are assigned such a timestamp, I agree that could operate as a full MVCC system. Good. Regarding the overlapping txs, it makes sense once you say you're aborting txs. Without that, it sounded really difficult to achieve without locking. When you say reads only check the switch if there is a write intent, where is exactly that "switch"? I understood it's not with the key, but rather at some other random location. If that's the case, I insist that you require two reads: one for the key, the other one for the switch. Os is the switch co-located with every key? Regarding the aborted txs, I can't argue without numbers, but I'd like to see those. I mean: you may abort txs voluntarily (I want to ROLLBACK) or involuntary (there's a concurrent conflict). That may or may not be a high number. But all of those would be written to disk, so it might become a high price.