DROPBOX EX. 1015
`
`DROPBOX EX. 1015
`
`
`
`

`
`JIM GRAY
`
`DIGITAL EQUIPMENT CORPORATION
`
`ANDREAS NEUTER
`
`UNIVERSITY OF STUTTGART
`
`TRANSACTION PROCESSING:
`
`CONCEPTS AND TECHNIQUES
`
`Edition
`
`MORGAN KAUFMANN PUBLISHERS
`
`An Imprint of Elsevier
`
`SAN FRANCISCO, CALIFORNIA
`
`Dropbox Ex. 1015
`
`
`
`Dropbox Ex. 1015
`
`

`
`
`
`.5-‘,t:ra!z
`Senior Editor: Brtrce M.
`Manufacturing Manager: Yonie O-aerton
`Project lvianagernent; Proi'essr'onat Book Center
`Text Designer: Gary Head
`Cover Designer: Waits Larson /\SSOCi'L':i‘fFJS
`Copyeditor: Jeanne Tmerne
`Composilor: im,oressr'oris. a division of Edwards Brothers, Inc.
`Indexer: Srepheri Kati_qbair
`Proofreader: Czrryi Rioder
`Printer: Edwards Brothers, Inc.
`
`Software; Cornpaiibte software for course use is available from Transarc Corporation.
`Information about academic site licenses for the Encina family of products and further details
`about Encina can be obtained by contacting Encina University Coordinator at 412-338-4400 or
`via the internet: er1(:inatCitti'ar1sar'c.Com
`
`Morgan Kaufmann Publishers, inc.
`An Imprint of Elsevier
`Editorial Office:
`340 Pine Street, Sixth Floor
`San Francisco, CA 94104
`
`© 1993 Morgan Kaufmann Publishers, inc.
`All rights reserved
`Printed in the United States of America
`
`No part of this publication may be reproduced, stored in a retrieval s
`ystem, or transmitted in any
`form or by any means electronic, meclwanical. photocopying.
`recording, or otherwise without the
`prior written permission ol the publisher:
`Permissions may be sought directly from E|se\rier's Science and Te
`chnology Flights Department in
`Oxtord, UK. Phone: (44) 1865 843830, Fax: (44) 1865 853333. e-m
`ail: permissiensfielseirierco.uk.
`You may also cornpiele your request on~line via the Elsevier home
`page: http:irwww.elsevier.corn by
`selecting "Customer Support" and then "Obtaining Permissions".
`
`Transferred to Digital Printing, 2011
`
`ISBN-13: 978-l—55860—l90—l
`ISBN-10: 1-55860-190-2
`
`Library of Congress Cataloging-in—Pub|ication Data
`
`Gray, Jim, 1944-
`Transaction processing : concepts and techniques / Jim Gray,
`Andreas Fleuter.
`
`
`
`p. cm. — (The Morgan Kaufmann series in data management
`systems)
`Includes bibliographical references and index.
`ISBN-13: 978-1-55860-190-1
`ISBN-10: 1-55860-190-2
`1. Transaction systems (Computer systems)
`i. Reuter, A.
`(Andreas)
`ll. Title.
`III. Series.
`QA76.545.G73 1993
`004’.33—dc2O
`
`92-25954
`Dr@p‘box Ex. 1015
`
`
`
`Dropbox Ex. 1015
`
`

`
`—
`
`Introduction
`
`1.1 Historical Perspective
`
`gix n.m1s::1ml years ago, [he SllII‘IeI‘i:II'lH invenlzed writing for transaction processing. The ear-
`|iL‘..~s'[ known writing, is found on clay tablets recording the royal inventory of taxes, land,
`.nruin. uultlc. slm-‘-.:s, mid gold: .~;crib::s cvitlemly kept records of each transaction. This early
`_:wL.m hall Ihu key aispu.-.cts; of LI transanzlion processing system (see Figure 1.1):
`
`Database. An abstract system state, represented as marks on clay tablets, was maintained.
`Today, we would call this the database.
`
`Scribes recorded state changes with new records (clay tablets) in the
`Transactions.
`database. Today, we would call these state changes transactions.
`
`The Sumerians’ approach allowed the scribes to easily ask questions about the current and
`past state, while providing a historical record of how the system got to the present state.
`The technology of clay-based transaction processing systems evolved over several
`thousand years through papyrus, parchment, and then paper. For over a thousand years, pa-
`
`Abstraction
`
`pa
`
`‘
`
`Transaction
`"
`R
`
`.
`
`I
`I
`
`'
`
`Change
`
`.
`
`___.
`
`‘I
`
`..
`D”
`
`r"
`
`‘
`
`\
`
`‘.
`
`\_
`
`| b
`3
`
`In’
`
`fa.‘
`
`fa Answer
`
`Figure 1.1: The
`basic abstraction of transaction processing systems. The real state is represented
`strtl t~
`by an ab
`.
`a
`C 10n, called the database, and the transformation of the real state is mirrored by the exe-
`cution of
`Program, called a transactzon, that transforms the database
`
`3
`
`Dropbox Ex. 1015
`
`
`
`Dropbox Ex. 1015
`
`

`
`
`
`
`
`Setting up and billing for telephone calls, electronic mail, and so on.
`
`4 Introduction
`
`
`
`per, ink, and ledgers were the technology for transaction processing. The [HOSE I‘C.t‘Cl1l inno-
`vation began late in the 18005 when Herman Hollerith built a punched-card etmiputer system
`to record and report the 1890 United States census. During the first hall" of the twentieth
`century, the need liir It‘nI1.-eaeliun ]'JI"{1L't‘.‘-}5l[]g fueled the evolution and growth of punched-card
`equipment. These early computers were used primarily for itwenlnry control and accounting.
`in el'l"et‘I, they replaeetl clay tablets with paper tablets (ea1‘tl.<.): their virtue was that the sys-
`{ems eoultl .‘it:ttl'(.:l1 and update tthout one "tablet" {curd} per .*i{:t.'0tltl.
`The second half of the twentieth century saw two main developments in transaction
`processing: batch transaction processing based on magnetic storage (tape and disc), followed
`by online transaction processing based on electronic storage and computer networks. These
`two developments were largely responsible for growth in the computer industry, and trans-
`action processing applications accounted for the majority of computer systems revenues.
`
`Today, the primary use of general-purpose computers is still transaction processing. Typical
`
`
`applications and examples include the following:
` Communications.
`
`
`
`Finance. Banking, stock trading, point of sale, and so on.
`
`
`
`Travel. Reservations and billing for airlines, hotels, cars, trains, and so on.
` Manufacturing. Order entry, job and inventory planning and scheduling, accounting, and
`so on.
` Process control. Control of factories, warehouses, steel, paper, and chemical plants, and
`so on.
` Consider the example of a telephone call. Each time you make a phone call, there is a
`call setup transaction that allocates some resources to your conversation; the call teardown is
`
`a second transaction, freeing those resources. The call setup increasingly involves complex
`algorithms to find the callee (800 numbers could be anywhere in the world) and to decide
`
`who is to be billed (800 and 900 numbers have complex billing). The system must deal with
`
`features like call forwarding, call waiting, and voice mail. After the call teardown, billing
`
`may involve many phone companies (e.g., direct dial from San Francisco to Madagascar in-
`
`volves several phone companies).
`
`As another example, computer integrated manufacturing (CIM) is a key technique for
`improving industrial productivity and efficiency. Just-in-time inventory control, automated
`
`warehouses, and robotic assembly lines each require a reliable data storage system to repre-
`
`sent the factory state. In addition, computers control and monitor the flow of goods through
`
`the factory.
`these two applications—telephony and
`As with most modern enterprises,
`
`manufacturing—require vast quantities of software. In the past, such systems were often
`implemented using specialized computers and ad hoc techniques. This meant that the
`
`applications had to be reprogrammed for each new generation of computers. However, the
`
`development effort for these applications has become so huge that the investment must be
`
`preserved for several hardware generations. As a result, standard software is now used to
`
`ensure that the application will work on the next generation of computer systems. Project
`
`risks and costs are also reduced by using high-level
`tools to improve programmer
`productivity. Consequently, system control functions are being implemented using standard
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Dropbox Ex. 1015
`
`Dropbox Ex. 1015
`
`

`
`What Is a Transaction Processing System?
`
`5
`
`1 2 what Is a Transaction Processing System?
`1' views 11 ll‘:-'lIl.:i1IL‘lil‘J['t DI'()t'..‘L.'.}i!~ill‘Il__{ systein fmm many different perspectives: a user
`.
`-1iv= ‘Ill
`‘I lI!IilIi'\'ll"ll0l‘ iers ective andaTPs stemim le-
`'|"his i_~I-iuiitf:
`;. pmgrtiiiiiiiei PM-HI ti
`K--i
`it
`-
`=
`l
`P
`-
`_
`.
`‘
`_Y
`‘P
`__
`.,,.l,-,,-,»_.
`[Milan I
`l’-i'vIlL'IJll\"L‘ Because each views the system quite differently, it IS difficult to give a
`' JL‘.
`--
`'
`.
`,
`,
`,
`,
`lmnim 1| finiiiraii tit" what ti ti':iiis;ii:ttuii pi'tii:essiiti_~, system 1S and what it does. If forced to do
`.-
`~
`,
`.
`‘
`‘
`:2
`-"”‘=]'-‘ L
`: WI. n.,,,.,t wit] gigrec l.L!
`llIL‘ lullciwing sttttciiitziitz
`Ml. 10V“
`~
`'
`"
`
`t"|"P system _} pi-in-itlcs tools to ease or automate appli-
`.\'_'y'.\'.Ili"."iTl
`A t,.ansa,.,,-,,,, l;ii‘.«J{'.~:’_\'.N'i'."i_t_’
`_
`I
`_
`,
`L‘-
`cation pm:-1-iiiiiiiiiiig, uset:iilion. and LiLllllll‘li5ll"t1ill'I|lI. '|"i':iiis;ictinii processing applications
`typically ;-;'|_||l}}t'i1'l
`:1 iieiwmk oi" tleviccs that submit quei‘1es until updates to the applica-
`tion BaS.._.L| on these inputs. llit: ilppllcililtm mtiintaiiiis :ld£lit'tll'tl1.\}t3 representing some real-
`world state. Application responses and outputs typically Li|'l.\-‘C i'eal-world actuators and
`transducers that alter or control the state. The applications, database, and network tend
`to evolve over several decades. Increasingly, the systems are geographically distributed,
`heterogeneous (they involve equipment and software from many different vendors),
`continuously available (there is no scheduled down-time), and have stringent response
`time requirements.
`
`The term transaction processing system is generally used to mean a complete system. A
`TP system includes application generators, operations tools, one or more database systems,
`utilities, and, of course, networking and operating system software. Historically, TP system
`meant Tele-Processing system and denoted a program supporting a variety of terminal types
`and networking protocols. Some current transaction processing systems evolved from
`teleprocessing systems, further complicating the terminology. As used here, the term TP sys-
`tem has the connotation of transaction processing.
`A TP system is a big thing; it includes application generators, networks, databases, and
`applications. Within the TP system, there is a core collection of services, called the TP moni-
`tor, that manage and coordinate the flow of transactions through the system.
`All these definitions use the term transaction. What exactly is a transaction’? It has the
`following various meanings:
`
`(1) The request or input message that started the operation.
`
`transaction request/reply
`
`(2) All effects of the execution of the operation.
`
`transaction
`
`(3) The pr0gram(s) that execute(s) the operation.
`
`transaction program
`
`stem front the v:ii‘ioI.is perspectives of people involved in the transaction.
`0I1l)'.l_l1e reiiiicsi and mrily :.ind, consequently, thinks in those terms. The
`,,[,‘.,|.mm_
`WWHI lujmini l1L_l.1l.Il-lllul priiiiarily s-cc the icquest execution, so they take that view. The
`«
`sii.-ilu:
`|:ti'g-ely deals With the naming, security, and the transaction programs;
`lIt'll]--.‘ .,.-
`.
`.
`,
`‘-wnl|»ll.Ll(llL Ull.t.‘.!I iliiiiks oi" the traiisiiction as the program source rather than the program
`--
`iiiii,
`
`Dropbox Ex. 1015
`
`
`
`Dropbox Ex. 1015
`
`

`
`6 Introduction
`
`This book adopts the second definition: A transaction is a collection of operations on
`the physical and abstract application state. The other two transaction concepts are called the
`transaction request/reply and the transaction program.
`Transaction processing systems pioneered many concepts in distributed computing and
`fault-tolerant computing. They introduced distributed data for reliability, availability, and
`performance; they developed fault-tolerant storage and fault—tolerant processes for availabil-
`ity; and they developed the client-server model and remote procedure call for distributed
`computation. Most important, they introduced the transaction ACID properties—atomicity,
`consistency, isolation, and durability—that have emerged as the unifying concepts for dis-
`tributed computation.
`This book contains considerably more information about the ACID properties. For now,
`however, a transaction can be considered a collection of actions with the following proper-
`UCSZ
`
`Atomicity. A transaction’s changes to the state are atomic: either all happen or none hap-
`pen. These changes include database changes, messages, and actions on transducers.
`
`Consistency. A transaction is a correct transformation of the state. The actions taken as a
`group do not violate any of the integrity constraints associated with the state. This re-
`quires that the transaction be a correct program.
`
`Isolation. Even though transactions execute concurrently, it appears to each transaction, T,
`that others executed either before T or after T, but not both.
`
`Durability. Once a transaction completes successfully (commits), its changes to the state
`survive failures.
`
`As an example, a banking debit transaction is atomic if it both dispenses money and updates
`your account. It is consistent if the money dispensed is the same as the debit to the account.
`It is isolated if the transaction program can be unaware of other programs reading and writ-
`ing your account concurrently (for example. your spouse making a concurrent deposit). And
`it is durable if, once the transaction is complete, the account balance is sure to reflect the
`withdrawal. 1
`It may be hard to believe that such a simple idea could be very important, but that is the
`point. Transactions specify simple failure semantics for a computation. It is up to the system
`implementors to provide these properties to the application programmer. The application
`programmer, in turn, provides these properties to his clients.
`The application program declares the start of a new transaction by invoking
`Begin_Work(). Thereafter, all operations performed by the program will be part of this trans-
`action. Also, all operations performed by other programs in service of the application pro-
`gram will be part of the transaction. The program declares the transaction to be a complete
`and correct transformation by invoking Commit_Work(). Once the transaction successfully
`commits, the transaction’s effects are durable. If something goes wrong during the transac-
`tion, the application can undo all the operations by invoking Ro||back_Work(). If there is a
`failure during the transaction’s execution, the system can unilaterally cause the transaction to
`
`‘ The term ACID was coined by l-latirdcr and Renter [1983]. The term serializable is a commonly
`used synonym for isolated. The terms pm-.w'.i-tent and stable are widely used synonyms for durable.
`None of these alternatives (e.g., PACE, sacs} gives a nice acronym like ACID.
`
`Dropbox Ex. 1015
`
`Dropbox Ex. 1015
`
`

`
`él
`
`What Is a Transaction Processing System? 7
`
`Med back Begin-Commit or Begin-Rollback, then, are used to bracket the ACID trans-
`
`be F0
`
`-’ pie and niodnlar way to build distributed applications. Each module is a
`.
`I or stih-Irniisziction. lf all goes well. the transaction eventually commits and all the
`h
`|Itl|1SflCllUl OW to a new durable state.
`It" anything goes wrong, all the modules of
`lllmllllclj, in-on arc iiutnniaiically reset to their state as of the start of the transaction. Since
`[re :,:1;liLilliIid reset logic are atttoiiialic, it is easy to build modules with very simple failure
`I
`IL‘
`'
`5Cnll:,l[l.:llS' of the techniques used to achieve the ACID properties have direct analogies in
`h”mm1‘5§i;t;_-ni,~;_ In i'eti'nspect'. we have just abstracted them into computer terms. The notions
`-
`'- mniieity and diiriihility are explicit in contract law, in which a notary or escrow officer
`ill it
`|'
`.1“-~c,
`u
`Imsiness trmisactinii. Even more explicit
`is the Christian wedding
`which two people agree to :1 marriage. The marriage commit protocol goes as
`hi»-lrlnxvsz The niinister asks each partner. “Do you agree to marry this person?” If both say
`..W_§"' 1I1i-_‘1‘| the niinislcr tl{:t:i£l['€S the marriage committed; if either fails to respond, or says
`"inn," then the inarriage is oil" (neither is in:.u'ried). Transaction processing systems use a pro-
`u;._-nl directly analogous to this to acliieve all-or-nothing atomic agreement among several
`intlependent programs or C()II’l.pl1l€l'H.
`'Fi'aiislatcd into computer terms, this idea is called the
`“,‘_.‘,,_p)'m3,'(_> ._-.r_mmu'r p.*':J!m.‘r)t':
`il Iias it voting phase, in which all participants prepare to com-
`mil. fnllov.-ed by it second eoinmit phase, in which they execute the commit. A distinguished
`p1'nce.*;.\: ztcts much as the niitiister, cnordiiiating the commit. This protocol allows all partici-
`paiits in 3 tlistrihuted computation to eitlier agree to change state or agree to stay in the old
`state.
`The transaction concept is the computer equivalent to contract law. Imagine a society
`without contract law. That is what a computer system would be like without transactions. If
`nothing ever goes wrong, contracts are just overhead. But if something doesn’t quite work,
`the contract specifies how to clean up the situation.
`There are many examples of systems that tried and failed to implement fault-tolerant or
`distributed computations using ad hoc techniques rather than a transaction concept.
`Subsequently, some of these systems were successfully implemented using transaction tech-
`niques. After the fact, the implementors confessed that they simply hit a complexity barrier
`and could not debug the ad hoc system without a simple unifying concept to deal with ex-
`ceptions [Borr 1986; Hagmann 1987]. Perhaps even more surprising, the subsequent transac-
`tion—oriented systems had better performance than the ad hoc incorrect systems, because
`transaction logging tends to convert many small messages and random disk inputs and out-
`puts (I/Os) into a few larger messages and sequential disk 1/05.
`This book focuses on the definition and implementation of the ACID properties. First,
`let’s look at transaction processing systems from the perspectives of various people who use
`Or operate such systems: users, system administrators, system operators, application design-
`ers, and application implementors. Each has a different view of the system. Later chapters
`Etfvthe System implementor’s perspective—the person who has to implement all these other
`s.
`M iilliiéliglle £1-iii-plicatitin systeinlis needed to make the various viewsconcrete. Funds trans-
`dmi‘; wm1~.lUllt and example application used for transaction processing systems because it
`mm Ur Ir; Milli-pile, kllJ.‘i[l'ElCl,‘£1I‘lI'J valuabie eonunodity. It is also one of the major application
`.
`tIs.in.t1on pinuesstitg systciiis. For the sake of variety, let’s consider a forms-
`‘1|‘I*nt'9
`a ..
`v,
`.
`.
`.
`.
`.
`.
`‘~
`‘fl l-lLi.lI‘t,IllIL. mrtil application from the various perspectives.
`
`Dropbox Ex. 1015
`
`
`
`Dropbox Ex. 1015