iKen BirmanCornell University. CS5410 Fall 2008. Transactionsy The most important reliability technology for client‐server systemsN tt idth iti f th tiyNow start an in‐depth examination of the topicy How transactional systems really workyImplementation considerationsImplementation considerationsy Limitations and performance challengesy Scalability of transactional systemsy Traditionally covered in multiple lectures, but with the cloud emphasis in CS5410 this year, compressed into a single onecompressed into a single oneTransactionsy There are several perspectives on how to achieve re liabilityyWe’v e talked at some length about non‐transactional replication via multicastyAnother approach focuses on reliability of yAnother approach focuses on reliability of communication channels and leaves application‐oriented issues to the client or server – “stateless”y But many systems focus on the data managed by a system. This yields transactional applicationsTransactions on a single gdatabase:y In a client/server architecture,y A transaction is an execution of a single program of the application(client) at the server.y Seen at the server as a series of reads and writes.yWe want this setup to work wheny There are multiple simultaneous client transactions running at the serverrunning at the server.y Client/Server could fail at any time.Transactions –The ACID PropertiesyAre the four desirable properties for reliable handling of concurrent transactions.yAtomicityyy The “All or Nothing” behavior.y C: stands for either yConcurrency: Transactions can be executed concurrentlyConcurrency: Transactions can be executed concurrentlyy … or Consistency: Each transaction, if executed by itself, maintains the correctness of the database.yIsolation (Serializability)yIsolation (Serializability)y Concurrent transaction execution should be equivalent (in effect) to a serialized execution.yDurabilityyDurabilityy Once a transaction is done, it stays done.Transactions in the real worldy In cs514 lectures, transactions are treated at the same level as other techniquesy But in the real world, transactions represent a huge chunk (in $ value) of the existing market for di t ib t d t!distributed systems!y 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)y But even on the web, we use transactions when we buy productsThe transactional modely Applications are coded in a stylized wa y:y begin transactionyPerform a series of read updateoperationsyPerform a series of read, updateoperationsy Terminate by commit or abort. y Terminologyy The application is the transaction managery The data manager is presented with operations from concurrently active transactionsco cu e t y act ve ta sacto sy It schedules them in an interleaved but serializableorderA side remarky Each transaction is built up incrementallyy Application runsyAnd as it runs, it issues operationsy The data manager sees them one by oneB f lk if k h hl hi yBut often we talk as if we knew the whole thing at one timeyWe’re careful to do this in wa ys that make senseyWe re careful to do this in ways that make sensey In any case, we usually don’t need to say anything until a “commit” is issuedTransaction and DataTransaction and Data ManagersgTransactionsData (and Lock) Managersreadupdatereadreadupdatetransactions are stateful: transaction “knows” about database contents and updatesTypical transactional programbegin transaction;x = read(“x‐values”, ....);y = read(“y‐values”, ....);z = x+y;write(“z‐values”, z, ....);commit transaction;What about the locks?y Unlike other kinds of distributed systems, transactional systems typically lock the data they accessaccessy They obtain these locks as they run:yBefore accessing “x” get a lock on “x”Before accessing x get a lock on xy 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 objectlock if you ll later need to update the objecty In clever applications, one lock will often cover many objectsy jLocking ruley Suppose that transaction T will access object x.y We need to know that first, T gets a lock that “covers” xyWhat does cov erage entail?y We need to know that if any other transaction T’ tries to access xit will attempt to get the same lockaccess xit will attempt to get the same lockExamples of lock cover agey We could have one lock per objecty … or one lock for the whole database lk f f bj y … or one lock for a category of objects y In a tree, we could have one lock for the whole tree associated with the rooty In a table we could have one lock for ro w, or one for each column, or one for the whole tableyAll transactions must use the same rules!All transactions must use the same rules!y And if you will update the object, the lock must be a “write” lock, not a “read” lockTransactional Execution Logy As the transaction runs, it creates a history of its actions. Suppose we were to write down the f i i fsequence of operations it performs.y Data manager does this, one by oney This yields a “schedule” y Operations and order they executedC if d i hi h i yCan infer order in which transactions rany Scheduling is called “concurrency control”Observationsy Program runs “by itself”, doesn’t talk to othersy 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 l t tti!run as several separate transactions!y The persistent data is maintained in files or database relations external to the applicationdatabase relations external to the applicationSerializabilityy Means that effect of the interleaved execution is indistinguishable from some possible serial i f h id iexecution of the committed transactionsy For example: T1 and T2 are interleaved but it “looks lik ” T bf Tlike” T2 ran before T1y Idea is that transactions can be coded to be correct if run in isolation and yet will run correctly when if run in isolation, and yet will run correctly when executed concurrently (and hence gain a speedup)Need for serializable ex ecutionT1: R1(X) R1(Y) W1(X) commit1T2:R2(X) W2(X) W2(Y) commit222()2()2()2DB: R1(X) R2(X) W2(X) R1(Y) W1(X)