1CS514: Intermediate Course in Operating SystemsProfessor Ken BirmanVivek Vishnumurthy: TATransactionsn The most important reliability technology for client-server systemsn Now start an in-depth examination of the topicn How transactional systems really workn Implementation considerationsn Limitations and performance challengesn Scalability of transactional systemsn This will span several lecturesTransactionsn There are several perspectives on how to achieve reliabilityn One approach focuses on reliability of communication channels and leaves application-oriented issues to the client or server – “stateless”n Major alternative is to focus on the data managed by a system. Stateful version yields transactional systemn A third option exploits non-transactional replication. We’ll look at it laterTransactions on a single database:n In a client/server architecture,n A transaction is an execution of a single program of the application(client) at the server.n Seen at the server as a series of reads and writes.n We want this setup to work whenn There are multiple simultaneous client transactions running at the server.n Client/Server could fail at any time.Transactions –The ACID Propertiesn Are the four desirable properties for reliable handling of concurrent transactions.n Atomicityn The “All or Nothing” behavior.n Consistencyn Each transaction must preserve consistency.n Isolation (Serializability)n Concurrent transaction execution should be equivalent (in effect) to a serialized execution.n Durabilityn Once a transaction is done, it stays done.Transactions in the real worldn In cs514 lectures, transactions are treated at the same level as other techniquesn But in the real world, transactions represent a huge chunk (in $ value) of the existing market for distributed systems!n The web is gradually starting to shift the balance (not by reducing the size of the transaction market but by growing so fast that it is catching up)n But even on the web, we use transactions when we buy products2The transactional modeln Applications are coded in a stylized way:n begin transactionn Perform a series of read, update operationsn Terminate by commit or abort. n Terminologyn The application is the transaction managern The data manageris presented with operations from concurrently active transactionsn It schedules them in an interleaved but serializableorderA side remarkn Each transaction is built up incrementallyn Application runsn And as it runs, it issues operationsn The data manager sees them one by onen But often we talk as if we knew the whole thing at one timen We’re careful to do this in ways that make sensen In any case, we usually don’t need to say anything until a “commit” is issuedTransaction and Data ManagersTransactionsreadupdatereadupdatetransactions are stateful: transaction “knows” about database contents and updatesData (and Lock) ManagersTypical transactional programbegin transaction;x = read(“x-values”, ....);y = read(“y-values”, ....);z = x+y;write(“z-values”, z, ....);commit transaction;What about the locks?n Unlike other kinds of distributed systems, transactional systems typically lock the data they accessn They obtain these locks as they run:n Before accessing “x” get a lock on “x”n Usually we assume that the application knows enough to get the right kind of lock. It is not good to get a read lock if you’ll later need to update the objectn In clever applications, one lock will often cover many objectsLocking rulen Suppose that transaction T will access object x.n We need to know that first, T gets a lock that “covers” xn What does coverage entail?n We need to know that if any other transaction T’ tries to access x it will attempt to get the same lock3Examples of lock coveragen We could have one lock per objectn … or one lock for the whole databasen … or one lock for a category of objects n In a tree, we could have one lock for the whole tree associated with the rootn In a table we could have one lock for row, or one for each column, or one for the whole tablen All transactions must use the same rules!n And if you will update the object, the lock must be a “write” lock, not a “read” lockTransactional Execution Logn As the transaction runs, it creates a history of its actions. Suppose we were to write down the sequence of operations it performs.n Data manager does this, one by onen This yields a “schedule” n Operations and order they executedn Can infer order in which transactions rann Scheduling is called “concurrency control”Observationsn Program runs “by itself”, doesn’t talk to othersn All the work is done in one program, in straight-line fashion. If an application requires running several programs, like a C compilation, it would run as several separate transactions!n The persistent data is maintained in files or database relations external to the applicationSerializabilityn Means that effect of the interleaved execution is indistinguishable from some possible serial execution of the committed transactionsn For example: T1 and T2 are interleaved but it “looks like” T2 ran before T1n Idea is that transactions can be coded to be correct if run in isolation, and yet will run correctly when executed concurrently (and hence gain a speedup)Need for serializable executionData manager interleaves operations to improve concurrencyDB: R1(X) R2(X) W2(X)R1(Y) W1(X) W2(Y) commit1commit2T1: R1(X) R1(Y) W1(X) commit1T2: R2(X) W2(X) W2(Y) commit2Non serializable executionProblem: transactions may “interfere”. Here, T2 changes x, hence T1 should have either run first (read and write) or after (reading the changed value). Unsafe! Not serializableDB: R1(X) R2(X) W2(X)R1(Y) W1(X) W2(Y) commit2commit1T1: R1(X) R1(Y) W1(X) commit1T2: R2(X) W2(X) W2(Y) commit24Serializable executionData manager interleaves operations to improve concurrency but schedules them so that it looks as if one transaction ran at a time. This schedule “looks” like T2ran first.DB: R2(X) W2(X) R1(X) W1(X) W2(Y) R1(Y) commit2 commit1T1: R1(X) R1(Y) W1(X) commit1T2: R2(X) W2(X) W2(Y) commit2Atomicity considerationsn If application (“transaction manager”) crashes, treat as an abortn If data manager crashes, abort any non-committed transactions, but committed state is persistent n Aborted transactions leave no effect, either in database itself or in terms of indirect side-effectsn Only need to
View Full Document
Unlocking...