Databases: Concurrency Control Theory

We've now covered the entire stack: Storing things on disk, buffer pool, executing operators, and doing query planning. Now we want to do 2 different components: Concurrency Control and Query Planning. We want to make sure that the database can be stored on disk safely. Again. Concurrency and control and recovery permeate throughout its entire architecture. Once we have these 2 things, we can go around and build a database system afterwards. 

Let's say you have 2 threads trying to update and same location at exactly the same time. We want to avoid race condition. Another way is you transfer $100 between bank accounts but there is a power failure. As a result, what should be the correct state of the database? The first motivation is an example of a lost update. The way that we will ensure that these things will be correct are through a concurrency control mechanism/protocol.

Concurrency control and recovery are one of the most important areas for database management systems. If you're shipping an application, what's not going to sell the product is recovering the database vs competitors, so you don't want to be in the business of writing databases yourself unless it's 100% necessary.  We want to have the idea of transactions with ACID properties. Let us first talk about transactions. 

These operations are SQL queries, or reads and writes into the database, like transferring money from my account to your account, which will be a higher-level function. No database system is going to have "move money" function, this is something you need to write up above. The key concepts of transactions is that we're not going to allow partial transactions, and these transactions are always going to be atomic, it's either all in or nothing. Even if we have a single operation transaction, all queries need to be updated, not all of them. If we have many transactions running then we just put them in a queue and pull these transactions from the queue one by one. 

Once we save a dat5abase, we flip a pointer saying that the new version of the database is the second file. Before a txn starts, copy the entire database to a new file and make all changes to that file. If txn is successful, overwrite the original file with the new one. If txn fails, just remove the dirty copy. Concurrency allows for better utilization of hardware and better throughput, and then we can do more work at the same amount of time and now I don't have to wait for queue.

Concurrency control goes back to the 1970s. A transaction can do data on disk but not on memory then we can get other transactions to run at the same time. We also would like to ensure correctness and fairness. Concurrency control is the second hardest thing to do in database systems. It's going to be super hard to guarantee correctness with transactions. However, arbitrary interleaving of operations can lead to temporary inconsistency, or permanent inconsistency (the database is damaged). For example in transferring $100, the $100 be in my account or the alternate account. Then I send an email saying the transfer succeeded, then we can get what happened to the transaction. We can only persist things that are low-level reads. A database object can be an attribute, tuple, page, database, doesn't matter. Everything works in different granularities and is based on a tuple.

The database is also a fixed size, which means that the only operations that we are going to do are reads and updates of existing things. Now we have to do a sequence of read and write operations. We can't see anything else (including the program logic) that the application did for transaction. A new transaction starts with a begin command or stops with either COMMIT or ABORT (If commit, the DBMS either saves all of the transactions changes or aborts it. If abort, changes are undone and abort can either be self-inflicted or caused by the DBMS. So the transaction either succeeded, or it failed. It's pretty self-explanatory. 

Why would you tell the data system that you want to abort? Let's say that we transfer $100, but we have an account that is considered fraud. In this case, we will abort and roll back these changes. The correctness criteria we are going to use now is defined in an ACID acronym (Atomicity, Consistency, Isolation, Durability). 

Atomicity: All actions in the txn happen, or none happen. (All or nothing) 

Consistency: If each transaction is consistent, and the database starts consistent, then it ends up consistent. (looks correct to me)
Isolation: Execution of one txn is isolated from other txns (if all alone) 

Durability: If txn commits, its effects persist.  (survive)

These factors determine the correctness criteria of a transaction. If a relational database supports transactions, this is what they mean. Atomic transactions mean that either everything happens or nothing happens. 

The most common approach is to do logging, recording our file on disk and all changes that we are making. That way if I crash I have the old value sitting around and then I can go back and put it back in place so that all the original values are still there after an abort. An example is a black box, that records what happened in an airplane the moment that it crashed. We can put the element back in the database because of this. In addition, logging is going to provide us benefits in terms of performance and high-level criteria for application and organization. 

We can turn random writes into sequential writes through a log and stuff. The approach number 2 is shadow paging. This is when the database makes copies of pages and transactions make changes to these copies, and only a few databases systems still use these methods. It's all just fragmentation, since you're copying things all the time, which eventually becomes very expensive. I would have to do a flush with every commit.  A buffer flush is the transfer of computer data from a temporary storage area to the computer's permanent memory. For instance, if we make any changes in a file, the changes we see on one computer screen are stored temporarily in a buffer.

Consistency is a term about the correctness of a database. They're all modeling many processes in the real world. If we have our database be logically correct, then any questions we ask about the database will produce correct results. The database accurately models the real world and follows integrity constraints. 

Any transaction in the future should be able to see the changes that the transaction in the past makes. This matters more in the distributed databases. Let's say I do a write and update an account and you come 1ms later and you do a read, you should be able to see my change right away. If a database is consistent before the transaction starts, it will also be consistent after. 

We also care about isolation, meaning if we have a user submitting a bunch of transactions, we want each of them to run assuming we are running them itself. Then we can just write our single threaded code and be fine. We can achieve this by strawman approach by execture transactions one by one.

Achieving parallelism can become difficult, and we can achieve this to use a concurrency control protocol, using latches to ensure the correctness of data structures. Latches are protecting internals of data structure, while locks are going to protect these database objects. A concurrency control potocol is how the DBMS decides the proper interleaving of operations

There are 2 categories of protocols. Pessimesitc require each threads to acquire locks before they're going to do anything. Optimisitic control is assuming that conflicts are rare, letting transactions run and do whatever they want. Here's an example: 

Assume at first A and B each have $1,000. T1 transfers $100 form A's account to B's and T2 credits both accounts with 6% interest. 

So T1 is as follows: 

T1

BEGIN

A = A - 100

B = B + 100

COMMIT

T2 

BEGIN

A = A * 1.06

B = B * 1.06

COMMIT

After we execute transactions for B, the order of the operations after at the end end up with 2120 (2000 * 1.06). 

There is no guarantee that T1 will execute before T2 of vice versa, if both are submitted together. But the net effect must be equivalent to those 2 transactions running serially in some order. 

Here is the serial execution example where both should have the same sum. 

2-Phase locking is a dynamic protocol when we don't know what is running. If there are no conflicts, then you can go ahead and interleave these processes any way you want. We can have one transaction stall, another transaction to keep on running and still make some good progress. 

There can be an interleaving example which isn't good, and doesn't return the correct values. For example some hacker figured out to manipulate the API and drain out account for MongoDB< so you need to do transactions.

The database doesn't do an operation, it just does reads and writes to determine whether a schedule is correct. 

Equivalency is when the object has the same values of another database state, then they are equivalent. An ordering of a schedule can be equivalent to one or more serial orderings. A schedule that is equivalent to some serial execution of transactions is a serializable schedule, if each transaction preserves consistency, then every serializable schedule preserves consistency. 

There are 3 types of anomalies we worry about: Read-Write, Write-Write, and Write-Read.

Read-Write is an unrepeatable read. After committing, we get the acknowledgement from the database system saying the transaction committed. An error can be if we're trying to read the same object and not getting the same value. 

Write-Write conflicts overwrite uncommitted data. 

Given these conflicts we can now understand what it means for a schedule to be serializable. This is to check whether schedules are correct or not.

Now we'll define a new term. 2 Schedules are said to be conflict-equivalent if they involve the same actions of the same transactions at the same time. Schedule S is conflict serializable if you are able to transform S into a serial schedule by swapping consecutive non-conflicting operations of different transactions. We can swap read on B before read on A, write on B can happen before write on A, etc, and now we end up with a serial ordering where one entire command executes before another.  Serialization is the process of converting an object into a stream of bytes to store the object or transmit it to memory, a database, or a file. Its main purpose is to save the state of an object in order to be able to recreate it when needed. In-order is ideal. The way we can do this is through a dependency Graph. 

Dependency Graph has a node for every schedule and edge between 2 transactions. We get edge from Ti to Tk if an operations Oi of Ti conflicts with an operation Oj of Tj and Oi appears earlier in the schedule than Oj. 

A write followed by a Read on a thread goes from the write thread to the read thread. Make sure there are no cycles. 

There is a way to potentially modify application to end up in a state as a serial ordering of a transaction. We can try to write a correct a result while still being not conflict serializable. 

Schedules S1 and S2 are view equivalent if:

If T1 reads initial value A in S1, then T1 also reads initial value of A in S2.

If T1 reads value of A written By T2 in S1, then T1 also reads value of A written by T2 in S2. 

If T1 writes final value of A in S1, then T1 also writes final value of A in S2. 

Sometimes, we generate a bunch of edges in a dependency graph. 

 We have a cycle here. As a result, we know that these graphs are not conflict serializable. To solve this, we make sure that teh last thread is the last write on the database. 

The way to think about these schedules is that you have this universe of any possible ordering of schedules, then you have a smaller portion of serial ordering, and then we have conflict serializable schedule, and then View Serializable orderings. The only thing I'm going to see is what the value of A is, who cares if T1 and T2 read/wrote A, since T3 is going to overwrite it?

In conclusion, concurrency control is hard, hard to get correct, and hard to get to perform well. It is also automatic, where system automatically inserts lock/unlock requests in schedules of different transactions, ensuring resulting execution is equivalent to executing transactions one after another in the same order. Transactions provide all these nice guarantees.