|
when you deal with concurrent updates, you deal with time, and eventually you deal with race conditions. in the systems literature, we don't tend to organize them by the type of race but by the method of avoidance: mutex/semaphore/lock free/wait free, but we really don't talk about the causes so much. meanwhile in the database literature, we talk about race conditions in terms of the isolation level: how much accidental concurrency we're willing to cope with. what follows is an overview of types of race conditions, and hopefully some of this database terminology will be useful for reasoning about your program correctness. before we talk about the 'i' in 'acid', we should talk about the 'a', atomicity: the first race condition is a dirty read, or an uncommitted read: reading data from an unfinished/uncommitted operation. people don't tend to think about this in database land, because it's generally impossible in sql. however the insides of a database will have to handle and cope with this. race conditions in databases are really about time-travel: things that can't make sense if you processed the transactions one after another. processing the transactions in order is what is called 'linearizable': the order of operations follows a timestamp, that timestamp is monotonically increasing. each transaction runs in isolation, one after another. (you can write a very simple, but slow database around this principle). seeing an incomplete transaction violates this idea. now it's time to talk about the 'i': isolation. isolation means "how much of the system can change while I am processing this". the lowest isolation level "read committed" doesn't allow dirty reads but you cannot guarantee reading the same value twice gives you the same result back each time: a read you can't rely on is often called a volatile read, or non-repeatable read. again, this is a time travelling operation: if transactions were processed one after the other, it would be impossible to see stale data — no other writer can operate. the isolation level 'read repeatable' prevents volatile reads, but you can still get stale copies back consistently, but race conditions still exist here. read-repeatable is about old values being deleted/updated after the transaction starts, but not about new records inserted after the transaction start: you can lock old values as you read them to prevent update, but it is harder to lock things that don't exist yet. these are called 'phantom reads', and mostly cause problems for scans/aggregations across tables. phantom reads are about other future or current inserts that overlap, volatile reads are about future or current updates/deletes that overlap, and dirty reads are about reading both before they are committed. you can avoid all of these race conditions by taking a snapshot of the data, working on it, and writing it back if the snapshot you read hasn't changed. (and thus 'snapshot isolation' was born) reads in the future aren't the only source of race conditions: reads in the past can be problematic too. under snapshot isolation, you can get stale reads, or read skew. a stale read, is reading committed data that's been overwritten. read skew is a little bit more special. when you have tables that depend on one another, read skew is where you take a snapshot of both but these snapshots are inconsistent with each other: one has the result of transactions the other hasn't seen yet. both snapshots are consistent internally, and expose no dirty/volatile/phantom reads, but are not consistent with each other, and you get read skew. write skew is easier to understand than read skew, don't worry about it. we've categorized the problems with reads, so we should do the same for writes. race conditions under reads are usually not-much-of-a-problem™, and writes are what cause the pain and suffering. dirty reads are caused by writes, volatile reads are caused by writes, phantom reads, stale reads, everything is caused by writes. a dirty write is doing a dirty read and updating a record based on uncommitted data. you get into a whole world of pain if the transaction aborts and you're not sure what to do with the update. once you get past atomicty and into isolation, the next type of write issue is the lost update: two transactions commit at the same time, both attempt to write to the same entry, one should win, one should lose. if both commit: then one transaction has a "lost update" - the result of it's write was overwritten. lost updates can be caused by stale writes, or what happens when you write back the data you got from a stale read. a lost update and write skew have a lot in common, like stale reads and write skew do: a lost update / stale read is about the stability of a single record, but write skew / read skew are about the stability of tables or the database. with write skew, you read from one table and update another, rather than reading to/from the same record as with a lost-update. there are other race conditions, like the aba problem, but these don't tend to appear as much in databases, but it is still possible. but anyway, i've found this sorta stuff useful for diagnosing concurrent issues. so, let's recap - dirty read: read uncommitted data - dirty write: update uncommitted data and we have this idea of stability, or a lack of time travel: a stable snapshot is one that does not change. we have the idea of stability of reads/writes across a key being violated: - volatile read: reads of committed data for a record might change - lost updates: overwriting committed data based on stale read of a record we have the idea of table stability too - phantom read: reads of committed data across a table might change and we have the idea of database stability: - read skew / write skew: working with consistent snapshots of tables but not of along with stability, we have this idea of ordering: some race conditions are about past data changing, some are about reading future data, some are about reading data that's changed as the transaction is happening so if we have a transaction processing system where each transaction is atomic, and fully isolated: each transaction works on a consistent snapshot of the database, is it the same as linearizable? (recall that linearizable means that "every transaction is run one after the other") the answer is no: there is a weaker form of transaction ordering called serializable, which is "as long as no-one else looked at what i was up to, then it's cool". with serializable, you can intermix transactions as long as they don't overlap. the moral is that transactions are about the interplay of invariants and performance: a transaction takes a world where certain properties must hold, and ensures they are true before and after the transaction runs, but doesn't enforce it as much inside. you get to do partial operations and changes no-one else gets to see. this is atomicity. isolation is about the interweaving of these atomic actions and how they compose, not just the stability of snapshots but the ordering too. transactions aren't about "doing one thing after another" they're about "hiding what i'm doing from other people until i'm done" and you get to pick and choose how stable the snapshot you work on is.
|
#
?
May 26, 2016 06:51
|
|
|
|
| # ? Apr 19, 2024 12:35 |
|
|
hey it's tef
|
|
#
?
May 26, 2016 10:03
|
|
|
|
|
#
?
May 26, 2016 11:01
|
|
|
yeah that would have been quicker
|
|
#
?
May 26, 2016 16:17
|
|
|
a fun issue is that the isolation levels were designed around single value databases and as such when you try and stick snapshot isolation in it looks messy. phantoms were discovered later which is why you get them in read committed, read repeatable but not serializable. the comic talks about 2PL/SV dbs not OCC/MVCC dbs too
|
|
#
?
May 26, 2016 16:23
|
|
|
OCC is stupid crap for naive idiots who have yet to feel the full wrath of murphy's law. "no, really, we basically don't have any contention, it's gonna be fine guys!" bullshit you need to lock everything down, make sure everything happens exactly when it should and enforce a new order upon your database with the lock manager acting as a ruthless fascist regime. if two transactions need locks owned by one another, you take one of them out back and shoot it. that's why it's called a deadlock, because one of your transactions will die
|
|
#
?
May 26, 2016 16:44
|
|
|
nah, 2pl is for olds
|
|
#
?
May 26, 2016 17:03
|
|
|
YeOldeButchere posted:if two transactions need locks owned by one another some of us prefer the world of "first commit wins" over "first transaction wins"
|
|
#
?
May 26, 2016 17:16
|
|
|
i vote equal opportunities for all transactions
|
|
#
?
May 26, 2016 17:18
|
|
|
just make sure all your data structures can be expressed as bounded semilattices
|
|
#
?
May 26, 2016 18:55
|
|
|
Cocoa Crispies posted:just make sure all your data structures can be expressed as JSON
|
|
#
?
May 26, 2016 19:02
|
|
|
tef posted:some of us prefer the world of "first commit wins" over "first transaction wins" first transaction should always win.
|
|
#
?
May 26, 2016 19:04
|
|
|
I agree that the first transaction should always win, unless the planet Mars appears between 20 and 30 degrees above the horizon on the eastern most point of America on the 5th of the month, in which case the second transaction should win
|
|
#
?
May 26, 2016 19:35
|
|
|
Shaggar posted:first transaction should always win. you have two cluster members, "piper" and "zedo" they both receive transactions "spock" and "riker" piper gets spock, then riker zedo gets riker, then spock which one wins?
|
|
#
?
May 27, 2016 00:06
|
|
|
riker. TNG supremacy
|
|
#
?
May 27, 2016 04:23
|
|
|
|
| # ? Apr 19, 2024 12:35 |
|
|
Cocoa Crispies posted:you have two cluster members, "piper" and "zedo" that's not really a transaction and 2 phase locking or optimistic concurrency control issue, though. you're asking a question about the system as a whole (which transaction is seen first by the system), but don't provide a mechanism to establish a total order for events in the system as a whole. so of course there's no valid answer
|
|
#
?
May 27, 2016 16:46
|
|