The Jepsen description of strict serializability is exactly what FoundationDB offers: linearizability with a real time constraint. All transactions are observed to have happened at a single point in time and a transaction observes the effects of all previously committed transactions.
It seems like it should be able to offer strict, but the official docs suggest otherwise and clearly distinguish it as different than serializable:
“FoundationDB provides the strongest possible consistency model, sequential consistency (closely related to serializability from the database literature), providing the greatest possible ease of development.”
In other places it says “serializable” but not strict.
Also, read conflicts are not added automatically on dependent reads of conflict-free operations, violating serializability of conflict-full operations.
Finally, if you query range offsets, is the entire prior range locked with a read conflict or just the key at the offset? My understanding is the latter which allows phantoms.
There’s a lot going on here and I would appreciate any clarification you can offer.
Range reads do create conflict ranges for the entire range even if you use offsets. Not only does it create the conflict range, I think it actually does the work of reading the data, it just isn’t returned to you. This is why it is an O(N) operation with the size of the offset.
Not sure of the exact scenario you’re envisioning with atomic ops, but they’re essentially blind writes from what I understand. I don’t know how blind writes relate to transaction isolation, but I’m sure someone can fill in the details.
>Not only does it create the conflict range, I think it actually does the work of reading the data, it just isn’t returned to you. This is why it is an O(N) operation with the size of the offset.
This is true. The data is never returned to the client or anything, it's just that on the server the b-tree data structures are not augmented with the necessary information to do log(n) offset seeks so they have to scan. This is an orthogonal issue to all of the conflict stuff.
FoundationDB provides strict serializability for all types of operations, no exceptions. You have to deliberately ask for lower (e.g. snapshot) levels.
>Read conflicts are not added automatically on dependent reads of conflict-free operations, violating serializability of conflict-full operations.
"Conflict-free operations" presumably refer to the atomic ops. "dependent reads" of such operations are simply not possible because these ops return no data. From the docs: "Atomic operations do not expose the current value of the key to the client..." Hence no serializability violation is possible.
>Finally, if you query range offsets, is the entire prior range locked with a read conflict or just the key at the offset? My understanding is the latter which allows phantoms.
Nope. There are no locks anyway (optimistic concurrency), but KeySelectors (i.e. offsets), range reads, and any and all combinations thereof account for all necessary transaction read dependencies. No phantoms possible.
To clarify: if you read a range, even if it is totally empty (returns 0 records), FoundationDB still ensures strict serializability against any other transactions that touch that range.
They also say that "ranges need to be manually locked to avoid phantoms" which is not true. Range reads, deletes, etc. in FDB are all strictly serializable with respect to other operations.
Finally, they describe FoundationDB as "modified percolator". There may be some similarities I guess, but FoundationDB was architected without knowledge Percolator and they are very different. In particular, Percolator is a batch system and FoundationDB is designed for OLTP workloads.
Just because Percolator was implemented to provide transactional isolation in an OLAP system doesn’t mean that the algorithm doesn’t apply to OLTP contexts.
FoundationDB and Percolator were developed independently, but the fundamental principal is the same.
8 comments
[ 2.5 ms ] story [ 33.0 ms ] threadSee 12:10 of this video from the FoundationDB Summit: https://youtu.be/EMwhsGsxfPU
The Jepsen description of strict serializability is exactly what FoundationDB offers: linearizability with a real time constraint. All transactions are observed to have happened at a single point in time and a transaction observes the effects of all previously committed transactions.
“FoundationDB provides the strongest possible consistency model, sequential consistency (closely related to serializability from the database literature), providing the greatest possible ease of development.”
https://apple.github.io/foundationdb/consistency.html
In other places it says “serializable” but not strict.
Also, read conflicts are not added automatically on dependent reads of conflict-free operations, violating serializability of conflict-full operations.
Finally, if you query range offsets, is the entire prior range locked with a read conflict or just the key at the offset? My understanding is the latter which allows phantoms.
There’s a lot going on here and I would appreciate any clarification you can offer.
Not sure of the exact scenario you’re envisioning with atomic ops, but they’re essentially blind writes from what I understand. I don’t know how blind writes relate to transaction isolation, but I’m sure someone can fill in the details.
This is true. The data is never returned to the client or anything, it's just that on the server the b-tree data structures are not augmented with the necessary information to do log(n) offset seeks so they have to scan. This is an orthogonal issue to all of the conflict stuff.
>Read conflicts are not added automatically on dependent reads of conflict-free operations, violating serializability of conflict-full operations.
"Conflict-free operations" presumably refer to the atomic ops. "dependent reads" of such operations are simply not possible because these ops return no data. From the docs: "Atomic operations do not expose the current value of the key to the client..." Hence no serializability violation is possible.
>Finally, if you query range offsets, is the entire prior range locked with a read conflict or just the key at the offset? My understanding is the latter which allows phantoms.
Nope. There are no locks anyway (optimistic concurrency), but KeySelectors (i.e. offsets), range reads, and any and all combinations thereof account for all necessary transaction read dependencies. No phantoms possible.
To clarify: if you read a range, even if it is totally empty (returns 0 records), FoundationDB still ensures strict serializability against any other transactions that touch that range.
suggests that serializability is violated when atomic ops are mixed with regular ops on the same key.
Note that transaction pipelining in Calvin does not have this issue.
They also say that "ranges need to be manually locked to avoid phantoms" which is not true. Range reads, deletes, etc. in FDB are all strictly serializable with respect to other operations.
Finally, they describe FoundationDB as "modified percolator". There may be some similarities I guess, but FoundationDB was architected without knowledge Percolator and they are very different. In particular, Percolator is a batch system and FoundationDB is designed for OLTP workloads.
FoundationDB and Percolator were developed independently, but the fundamental principal is the same.
See other comment re. phantoms.