Comments (6)
With support for linearizable reads in go-dqlite, we could add this Jepsen test to our current battery:
http://jepsen-io.github.io/jepsen/jepsen.tests.linearizable-register.html
from go-dqlite.
My understanding is that linearizability applies naturally to atomic/single operations (like reading a register). The SQL model actually has transactional/multi operations, where usually the most you can have is serializability.
In particular SQLite in WAL mode uses snapshot isolation. I'm not sure how can you avoid stale reads with snapshot isolation: it's always possible to start a read transaction and read a stale value that was overwritten by a write transaction just after the read transaction started. I don't think there's any raft modification that can avoid that, since it's a property of the SQL/snapshot-isolation mode.
For example, if you use the sqlite3
command line to create a database like:
sqlite3 foo "pragma journal_mode=WAL; begin; create table foo(a text, b int); insert into foo (a,b) values ('a', 1); insert into foo (a,b) values ('b', 2); commit;"
then in 2 separate shells you start 2 sqlite3 shells and run these commands in the following order:
# shell 1
sqlite> begin;
sqlite> select * from foo where a='a';
a|1
this starts a read transaction on shell 1, then:
# shell 2
sqlite> begin;
sqlite> update foo set b=3 where a='b';
sqlite> begin;
this overwrites the value 'b', which transaction 1 still has to read. Now:
# shell 1
sqlite> select * from foo where a='b';
b|2
which is a stale read. This is kind of non-linearizable "by design", in the sense that the snapshot isolation transaction model is serializable but not linearizable (and indeed in the SQL standard there's no isolation mode guarantees linearizability, because it doesn't quite match with multi-operation transactions).
I've used the sqlite3
command line, but with dqlite is the same.
from go-dqlite.
My understanding is that linearizability applies naturally to atomic/single operations (like reading a register). The SQL model actually has transactional/multi operations, where usually the most you can have is serializability.
But as far as dqlite is concerned, the whole database is one big piece of state, right? Is the inclusion of transactions in the SQL model relevant when all query/exec operations are atomic and opaque to raft (i.e. they might as well be modifying and reading a single register)?
I'm not sure how can you avoid stale reads with snapshot isolation: it's always possible to start a read transaction and read a stale value that was overwritten by a write transaction just after the read transaction started.
I don't think the situation you describe is a stale read, is it? It's consistent with a sequencing of transactions where the read happens before the right, and linearizability (or strict serializability, I guess, since we're talking about transactions) isn't violated because each transaction appears to execute atomically at some point between invocation and return.
from go-dqlite.
My understanding is that linearizability applies naturally to atomic/single operations (like reading a register). The SQL model actually has transactional/multi operations, where usually the most you can have is serializability.
But as far as dqlite is concerned, the whole database is one big piece of state, right? Is the inclusion of transactions in the SQL model relevant when all query/exec operations are atomic and opaque to raft (i.e. they might as well be modifying and reading a single register)?
It is relevant because a dqlite SQL transaction can't be quite mapped to a raft operation, because it's not atomic in terms of client interactions. Typically the client starts the transaction, sends SQL commands, gets back results, possibly sends other SQL commands, until commit. It's only at commit time that we can possibly start a raft operation. However, precisely because they involve multiple client interactions, transactions can interleave. And if a write and read transaction interleave you might get the effect described in the example, without any possibility of resolving it with raft.
I believe the only way would be to allow either N concurrent read transactions OR one single write transaction. At the moment rN ead transactions can proceed concurrently with one single write transactions thanks to the WAL and its snapshot isolation.
Another way to see it, is that although the whole database is one big piece of state as you say, the operations that are run through raft are not the SQL transactions, but rather the result of the SQL transactions (i.e. the WAL pages that get added to the WAL).
Not sure how well I've articulated this, if it's confusing I'm happy to elaborate further.
I'm not sure how can you avoid stale reads with snapshot isolation: it's always possible to start a read transaction and read a stale value that was overwritten by a write transaction just after the read transaction started.
I don't think the situation you describe is a stale read, is it? It's consistent with a sequencing of transactions where the read happens before the right, and linearizability (or strict serializability, I guess, since we're talking about transactions) isn't violated because each transaction appears to execute atomically at some point between invocation and return.
The thing is that the definition of linearizable refers to single objects. If you take just that definition and apply it to the single object "second row of table foo", then this is a stale read because it violates real-time ordering. Likewise if you take the stronger multi-object version of linearizability, called strict serializability, this example is still a stale read since it violates real-time ordering.
As you point, these two transactions can be logically sequenced (i.e. serialized). However real-time ordering is violated, which is the key of linearizability (or actually strict serializability for transactions) vs serializability.
from go-dqlite.
As you point, these two transactions can be logically sequenced (i.e. serialized). However real-time ordering is violated, which is the key of linearizability (or actually strict serializability for transactions) vs serializability.
Hmm, I'm looking at this part from the jepsen.io page about strict serializability that you linked:
When Herlihy and Wing introduced linearizability, they defined strict serializability in terms of a serializable system which is compatible with real-time order.
A history is serializable if it is equivalent to one in which transactions appear to execute sequentially, i.e., without interleaving. A (partial) precedence order can be defined on non-overlapping pairs of transactions in the obvious way. A history is strictly serializable if the transactions’ order in the sequential history is compatible with their precedence order.
“The obvious way” means that transaction A precedes transaction B if A completes before B begins; this is the real-time constraint from linearizability.
Under that partial precedence order, the two transactions in your example wouldn't even be comparable, hence strict serializability doesn't impose any requirement on the order they should be applied -- right?
from go-dqlite.
As you point, these two transactions can be logically sequenced (i.e. serialized). However real-time ordering is violated, which is the key of linearizability (or actually strict serializability for transactions) vs serializability.
Hmm, I'm looking at this part from the jepsen.io page about strict serializability that you linked:
When Herlihy and Wing introduced linearizability, they defined strict serializability in terms of a serializable system which is compatible with real-time order.
A history is serializable if it is equivalent to one in which transactions appear to execute sequentially, i.e., without interleaving. A (partial) precedence order can be defined on non-overlapping pairs of transactions in the obvious way. A history is strictly serializable if the transactions’ order in the sequential history is compatible with their precedence order.
“The obvious way” means that transaction A precedes transaction B if A completes before B begins; this is the real-time constraint from linearizability.
Under that partial precedence order, the two transactions in your example wouldn't even be comparable, hence strict serializability doesn't impose any requirement on the order they should be applied -- right?
If you call the read transaction in the example "A" and the write transaction "B", you have B completing before A in real-time ordering but the serialization (logical) ordering needs to be that A completes before B (because it does not see the modifications made by B). This violates strict linearizability.
The ordering between these 2 specific transactions can't be partial, because they operate on the same data.
In case you aren't yet convinced, it might be worth writing to jepsen's author Kyle Kingsbury (aphyr at jepsen.io) to confirm or provide more details. Canonical had paid for training/consulting from him back then, so I believe he will be happy to reply. I'm not nearly as expert as him.
from go-dqlite.
Related Issues (20)
- Log Start and End of requests
- Handover tests are flaky
- Segfault on s390x inside yaml.v3 HOT 2
- sql.DB instances hang forever when database is unreachable HOT 20
- TestParallelNewApp: inconsistent cluster.yaml and info.yaml
- Allow WithExternalConn use any net.Conn instance HOT 4
- Shell: Support for WITH clauses (or more complex queries) HOT 7
- Shell: Provide .help
- Expose WithTracing option in app options HOT 3
- Expose an operation to remove a node from the cluster HOT 2
- RowsAffected not returning correct value for UPDATE HOT 4
- Upgrade from yaml.v2 to yaml.v3
- Issues with sharing a connection between statements (?) HOT 4
- Client Error Handling needs improvement HOT 10
- Jepsen failure: EOF when calling Open HOT 1
- Return error in driver.BeginTx if options aren't used/required or incorrect.
- Role re-shuffling for failure domains
- Shortcomings of sortCandidates
- TestIntegration_LeadershipTransfer CI failures HOT 2
- restore dqlite state from snapshot HOT 1
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from go-dqlite.