 










              Designing an Optimized Transaction Commit Protocol


              By Peter M. Spiro, Ashok M. Joshi, and T. K. Rengarajan



          Abstract                               kernel called KODA. In
              Digital's database                 addition to other database
             products, VAX Rdb/VMS               services, KODA provides the
             and VAX DBMS, share the             transaction capabilities
             same database kernel                and commit processing for
             called KODA. KODA uses              these two products.

             a grouping mechanism to              In this paper, we address
             commit many concurrent              some of the issues relevant
             transactions together.              to efficient commit
             This feature enables high           processing. We begin by
             transaction rates in a              explaining the importance
             transaction processing (TP)         of commit processing in
             environment. Since group            achieving high transaction
             commit processing affects           throughput. Next, we
             the maximum throughput              describe in detail the
             of the transaction                  current algorithm for group
             processing system, the              commit used in KODA. We
             KODA group designed                 then describe and contrast
             and implemented several             several new designs
             grouping algorithms and             for performing a group
             studied their performance           commit. Following these
             characteristics.                    discussions, we present
             Preliminary results                 our experimental results.
             indicate that it is                 And, finally, we discuss
             possible to achieve up              the possible direction
             to a 66 percent improvement         of future work and some
             in transaction throughput           conclusions. No attempt
             by using more efficient             is made to present formal
             grouping designs.                   analysis or exhaustive
             Introduction                        empirical results for
                                                 commit processing;
              Digital has two general-           rather, the focus is on
             purpose database products,          an intuitive understanding
             Rdb/VMS software, which             of the concepts and trade-
             supports the relational             offs, along with some
             data model, and VAX DBMS            empirical results that
             software, which supports            support our conclusions.
             the CODASYL (Conference
             on Data Systems Languages)
             data model. Both products
             layer on top of a database


                          Digital Technical Journal Vol. 3 No. 1 Winter 1991  1

 


           Designing an Optimized Transaction Commit Protocol



          Commit Processing                       For the purpose of
              To follow a discussion             analysis, it is useful
             of commit processing, two           to divide a transaction
             basic terms must first              processed by KODA into four
             be understood. We begin             phases: the transaction
             this section by defining a          start phase, the data
             transaction and the "moment         manipulation phase, the
             of commit."                         logging phase, and the
                                                 commit processing phase.
              A transaction is the               Figure 1 illustrates the
             execution of one or                 phases of a transaction
             more statements that                in time sequence. The
             access data managed by a            first three phases are
             database system. Generally,         collectively referred to as
             database management systems         "the average transaction's
             guarantee that the effects          CPU cost (excluding the
             of a transaction are                cost of commit)" and the
             atomic, that is, either             last phase (commit) as "the
             all updates performed               cost of writing a group
             within the context of the           commit buffer." [1]
             transaction are recorded
             in the database, or no
             updates are reflected in
             the database.

              The point at which a
             transaction's effects
             become durable is known
             as the "moment of commit."
             This concept is important
             because it allows database
             recovery to proceed in a
             predictable manner after
             a transaction failure. If
             a transaction terminates
             abnormally before it
             reaches the moment of
             commit, then it aborts.
             As a result, the database
             system performs transaction
             recovery, which removes all
             effects of the transaction.
             However, if the transaction
             has passed the moment of
             commit, recovery processing
             ensures that all changes
             made by the transaction are
             permanent.

             Transaction Profile





          2  Digital Technical Journal Vol. 3 No. 1 Winter 1991

 


                             Designing an Optimized Transaction Commit Protocol



              The transaction start              have to fetch and modify
             phase involves acquiring            every employee/salary
             a transaction identifier            record in the company
             and setting up control              database. The commit
             data structures. This phase         processing phase, in this
             usually incurs a fixed              example, represents 0.2
             overhead.                           percent of the transaction
                                                 duration. Thus, for this
              The data manipulation              class of transaction,
             phase involves executing            commit processing is a
             the actions dictated by             small fraction of the
             an application program.             overall cost. Figure 2
             Obviously, the time spent           illustrates the profile of
             in this phase and the               a transaction modifying 500
             amount of processing                records.
             required depend on the               In contrast, for
             nature of the application.          transaction processing

              At some point a request            applications such as
             is made to complete the             hotel reservation systems,
             transaction. Accordingly            banking applications, stock
             in KODA, the transaction            market transactions, or
             enters the logging phase            the telephone system,
             which involves updating the         the data manipulation
             database with the changes           phase is usually short
             and writing the undo/redo           (requiring few I/Os).
             information to disk.                Instead, the logging and
             The amount of work done             commit phases comprise the
             in the logging phase is             bulk of the work and must
             usually small and constant          be optimized to allow high
             (less than one I/O) for             transaction throughput.
             transaction processing.             The transaction profile
              Finally, the transaction           for a transaction modifying
             enters the commit                   one record is shown in
             processing phase. In KODA,          Figure 3. Note that the
             this phase involves writing         commit processing phase
             commit information to disk,         represents 36 percent of
             thereby ensuring that the           the transaction duration,
             transaction's effects are           in this example.

             recorded in the database            Group Commit
             and now visible to other             Generally, database
             users.                              systems must force

              For some transactions, the         write information to
             data manipulation phase is          disk in order to commit
             very expensive, possibly            transactions. In the
             requiring a large number            event of a failure, this
             of I/Os and a great deal of         operation permits recovery
             CPU time. For example,              processing to determine
             if 500 employees in a               which failed transactions
             company were to get a 10            were active at the time
             percent salary increase,            of their termination and
             a transaction would                 which ones had reached

                          Digital Technical Journal Vol. 3 No. 1 Winter 1991  3

 


           Designing an Optimized Transaction Commit Protocol



             their moment of commit.              There are several
             This information is often           variations of the basic
             in the form of lists of             algorithms for grouping
             transaction identifiers,            multiple commit lists into
             called commit lists.                a single I/O. The specific
              Many database systems              group commit algorithm
             perform an optimized                chosen can significantly
             version of commit                   influence the throughput
             processing where commit             and response times of
             information for a group of          transaction processing. One
             transactions is written to          study reports throughput
             disk in one I/O operation,          gains of as much as 25
             thereby, amortizing the             percent by selecting
             cost of the I/O across              an optimal group commit
             multiple transactions.              algorithm. [1]

             So, rather than having               At high transaction
             each transaction write              throughput (hundreds of
             its own commit list to              transactions per second),
             disk, one transaction               efficient commit processing
             writes to disk a commit             provides a significant
             list containing the commit          performance advantage.
             information for a number            There is little information
             of other transactions. This         in the database literature
             technique is referred to            about the efficiency
             in the literature as "group         of different methods
             commit." [2]                        of performing a group
              Group commit processing            commit. Therefore, we
             is essential for achieving          analyzed several grouping
             high throughput. If every           designs and evaluated their
             transaction that reached            performance benefits.

             the commit stage had to             Factors Affecting Group
             actually perform an I/O to          Commit
             the same disk to flush its           Before proceeding to
             own commit information,             a description of the
             the throughput of the               experiments, it is
             database system would be            useful to have a better
             limited to the I/O rate of          understanding of the
             the disk. A magnetic disk           factors affecting the
             is capable of performing            behavior of the group
             30 I/O operations per               commit mechanism. This
             second. Consequently,               section discusses the group
             in the absence of group             size, the use of timers to
             commit, the throughput of           stall transactions, and the
             the system is limited to            relationship between these
             30 transactions per second          two factors.
             (TPS). Group commit is
             essential to breaking this           Group Size. An important
             performance barrier.                factor affecting group
                                                 commit is the number
                                                 of transactions that
                                                 participate in the group
                                                 commit. There must be

          4  Digital Technical Journal Vol. 3 No. 1 Winter 1991

 


                             Designing an Optimized Transaction Commit Protocol



             several transactions in the         transaction throughput of
             group in order to benefit           the transaction processing
             from I/O amortization. At           system.
             the same time, transactions          Use of Timers to Stall
             should not be required              Transactions. One of the
             to wait too long for the            mechanisms to increase
             group to build up to a              the size of the commit
             large size, as this factor          group is the use of timers.
             would adversely affect              [1, 2] Timers are used
             throughput.                         to stall the transactions

              It is interesting to               for a short period of time
             note that the incremental           (on the order of tens of
             advantage of adding one             milliseconds) during commit
             more transaction to a               processing. During the
             group decreases as the              stall, more transactions
             group size increases. The           enter the commit processing
             incremental savings is              phase and so the group size
             equal to 1/(G x (G + 1),            becomes larger. The stalls
             where G is the initial              provided by the timers have
             group size. For example,            the advantage of increasing
             if the group consists of 2          the group size, and the
             transactions, each of them          disadvantage of increasing
             does one-half a write. If           the response time.
             the group size increases             Trade-offs. This section
             to 3, the incremental               discusses the trade-offs
             savings in writes will              between the size of the
             be (1/2 - 1/3), or 1/6              group and the use of timers
             per transaction. If we do           to stall transactions.
             the same calculation for a          Consider a system where
             group size incremented from         there are 50 active
             10 to 11, the savings will          database programs, each
             be (1/10 - 1/11), or 1/110          repeatedly processing
             of a write per transaction.         transactions against a

              In general, if G represents        database. Assume that on
             the group size, and I               average each transaction
             represents the number               takes between 0.4 and
             of I/Os per second for              0.5 seconds. Thus, at
             the disk, the maximum               peak performance, the
             transaction commit rate             database system can
             is I x G TPS. For example,          commit approximately 100
             if the group size is 45             transactions every second,
             and the rate is 30 I/Os             each program actually
             per second to disk, the             completing two transactions
             maximum transaction commit          in the one-second time
             rate is 30 x 45, or 1350            interval. Also, assume that
             TPS. Note that a grouping           the transactions arrive
             of only 10 will restrict            at the commit point in a
             the maximum TPS to 300 TPS,         steady stream at different
             regardless of how powerful          times.
             the computer is. Therefore,
             the group size directly
             affects the maximum

                          Digital Technical Journal Vol. 3 No. 1 Winter 1991  5

 


           Designing an Optimized Transaction Commit Protocol



              If transaction commit is            The concept of using commit
             stalled for 0.2 seconds             timers is discussed in
             to allow the commit group           great detail by Reuter.
             to build up, the group              [1] However, there are
             then consists of about 20           significant differences
             transactions (0.2 seconds x         between his group commit
             100 TPS). In this case,             scheme and our scheme.
             each transaction only               These differences prompted
             incurs a small delay at             the work we present in this
             commit time, averaging              paper.
             0.10 seconds, and the                In Reuter's scheme, the
             database system should              timer expiration triggers
             be able to approach its             the group commit for
             peak throughput of 100 TPS.         everyone. In our scheme, no
             However, if the mechanism           single process is in charge
             delays commit processing            of commit processing based
             for one second, an                  on a timer. Our commit
             entirely different behavior         processing is performed
             sequence occurs. Since the          by one of the processes
             transactions complete in            desiring to write a commit
             approximately 0.5 seconds,          record. Our designs involve
             they accumulate at the              coordination between the
             commit stall and are forced         processes in order to elect
             to wait until the one-              the group committer (a
             second stall completes. The         process).
             group size then consists
             of 50 transactions,                  Reuter's analysis to
             thereby maximizing the              determine the optimum
             I/O amortization. However,          value of the timer based
             throughput is also limited          on system load assumes
             to 50 TPS, since a group            that the total transaction
             commit is occurring only            duration, the time taken
             once per second.                    for commit processing,
              Thus, it is necessary to           and the time taken for
             balance response time and           performing the other
             the size of the commit              phases are the same for
             group. The longer the               all transactions. In
             stall, the larger the               contrast, we do not make
             group size; the larger              that assumption. Our
             the group size, the better          designs strive to adapt
             the I/O amortization that           to the execution of many
             is achieved. However, if            different transaction types
             the stall time is too long,         under different system
             it is possible to limit             loads. Because of the
             transaction throughput              complexity introduced by
             because of wasted CPU               allowing variations in
             cycles.                             transaction classes, we do
                                                 not attempt to calculate
             Motivation for Our Work             the optimal timer values as
                                                 does Reuter.





          6  Digital Technical Journal Vol. 3 No. 1 Winter 1991

 


                             Designing an Optimized Transaction Commit Protocol



          Cooperative Commit Processing           The Commit-Lock Design uses
              In this section, we present        a VMS lock to generate
             the stages in performing            groups of committing
             the group commit with               transactions; the lock
             cooperating processes, and          is also used to choose the
             we describe, in detail, the         group committer.

             grouping design currently            Once a process completes
             used in KODA, the Commit-           all its updates and
             Lock Design.                        wants to commit its
             Group Committer                     transaction, the procedure
                                                 is as follows. Each
              Assume that a number of            transaction must first
             transactions have completed         declare its intent to
             all data manipulation and           join a group commit. In
             logging activity and are            KODA, each process uses
             ready to execute the commit         the interlocked queue
             processing phase. To group          instructions of the VAX
             the commit requests, the            system running VMS software
             following steps must be             to enqueue a block of
             performed in KODA:                  commit information, known
             1. Each transaction                 as a commit packet, onto a
                must make its commit             globally accessible commit
                information available to         queue. The commit queue
                the group committer.             and the commit packets
                                                 are located in a shared,
             2. One of the processes             writeable global section.
                must be selected as the           Each process then issues a
                "group committer."               lock request for the commit

             3. The other members                lock. At this point, a
                of the group need                number of other processes
                to be informed that              are assumed to be going
                their commit work                through the same sequence;
                will be completed by             that is, they are posting
                the group committer.             their commit packets and
                These processes must             making lock requests for
                wait until the commit            the commit lock. One of
                information is written           these processes is granted
                to disk by the group             the commit lock. For the
                committer.                       time being, assume the
             4. Once the group committer         process that currently
                has written the commit           acquires the lock acts as
                information to stable            the group committer.

                storage, it must inform           The group committer,
                the other members that           first, counts the number
                commit processing is             of entries on the commit
                completed.                       queue, providing the
             Commit-Lock Design                  number of transactions
                                                 that will be part of the
                                                 group commit. Because of
                                                 the VAX interlocked queue
                                                 instructions, scanning

                          Digital Technical Journal Vol. 3 No. 1 Winter 1991  7

 


           Designing an Optimized Transaction Commit Protocol



             to obtain a count and                Once the commit block
             concurrent queue operations         is modified, the group
             by other processes can              committer writes it to
             proceed simultaneously.             disk in one atomic I/O.
             The group committer uses            This is the moment of
             the information in each             commit for all transactions
             commit packet to format             in the group. Thus, all
             the commit block which              transactions that were
             will be written to disk. In         active and took part in
             KODA, the commit block              this group commit are now
             is used as a commit                 stably marked as committed.
             list, recording which               In addition, as explained
             transactions have committed         above, these transactions
             and which ones are active.          now have new transaction
             In order to commit for a            identifiers. Next, the
             transaction, the group              group committer sets a
             committer must mark each            commit flag in each commit
             current transaction as              packet for all recently
             completed. In addition,             committed transactions,
             as an optimization, the             removes all commit packets
             group committer assigns a           from the commit queue,
             new transaction identifier          and, finally, releases
             for each process's next             the commit lock. Figure
             transaction. Figure 4               5 illustrates a committed
             illustrates a commit block          group with new transaction

             ready to be flushed to              identifiers and with commit
             disk.                               flags set.



























          8  Digital Technical Journal Vol. 3 No. 1 Winter 1991

 


                             Designing an Optimized Transaction Commit Protocol



              At this point, the                 lock request is mastered
             remaining processes that            on a different node in a
             were part of the group              VAXcluster system, the lock
             commit are, in turn,                enqueue/dequeues are very
             granted the commit lock.            expensive.
             Because their commit flags           Also, there is no explicit
             are already set, these              stall time built into the
             processes realize they              algorithm. The latency
             do not need to perform a            associated with the lock
             commit and, thus, release           enqueue/dequeue requests
             the commit lock and proceed         allows the commit queue
             to the next transaction.            to build up. This stall is
             After all these committed           entirely dependent on the
             processes release the               contention for the lock,
             commit lock, a process              which in turn depends on
             that did not take part in           the throughput.
             the group commit acquires
             the lock, notices it has
             not been committed, and,         Group Commit Mechanisms- Our
             therefore, initiates the         New Designs
             next group commit.                   To improve on the

              There are several                  transaction throughput
             interesting points about            provided by the Commit-
             using the VMS lock as the           Lock Design, we developed
             grouping mechanism. Even            three different grouping
             though all the transactions         designs, and we compared
             are effectively committed           their performances at
             after the commit block              high throughput. Note
             I/O has completed, the              that the basic paradigm of
             transactions are still              group commit for all these
             forced to proceed serially;         designs is described in the
             that is, each process is            Group Committer section.
             granted the lock, notices           Our designs are as follows:
             that it is committed, and           Commit-Stall Design
             then releases the lock.
             So there is a serial                 In the Commit-Stall Design,
             procession of lock enqueues         the use of the commit lock
             /dequeues before the next           as the grouping mechanism
             group can start.                    is eliminated. Instead, a
              This serial procession can         process inserts its commit
             be made more concurrent             packet onto the commit
             by, first, requesting the           queue and, then, checks
             lock in a shared mode,              to see if it is the first
             hoping that all processes           process on the queue. If
             committed are granted the           so, the process acts as
             lock in unison. However, in         the group committer. If
             practice, some processes            not, the process schedules
             that are granted the                its own wake-up call, then
             lock are not committed.             sleeps. Upon waking, the
             These processes must then           process checks to see if it
             request the lock in an              has been committed. If so,
             exclusive mode. If this             the process proceeds to its


                          Digital Technical Journal Vol. 3 No. 1 Winter 1991  9

 


           Designing an Optimized Transaction Commit Protocol



             next transaction. If not,           automatically, because the
             the process again checks to         database management system
             see if it is first on the           cannot judge which is more
             commit queue. The algorithm         important to the user in a
             then repeats, as described          general customer situation-
             above.                              the transaction response
              This method attempts to            time or the throughput.

             eliminate the serial wake-           The Willing-to-Wait
             up behavior displayed               Design provides a user
             by using the commit                 parameter called WTW time.
             lock. Also, the duration            This parameter represents
             for which each process              the amount of time the
             stalls can be varied                user is willing to wait
             per transaction to allow            for the transaction to
             explicit control of the             complete, given this wait
             group size. Note that               will benefit the complete
             if the stall time is too            system by increasing
             small, a process may wake           throughput. WTW time may
             up and stall many times             be specified by the user
             before it is committed.             for each transaction. Given
             Willing-to-Wait Design              such a user specification,
                                                 it is easy to calculate the
              As we have seen before,            commit stall to increase
             a delay in the commit               the group size. This stall
             sequence is a convenient            equals the WTW time minus
             means of converting a               the time taken by the
             response time advantage             transaction thus far, but
             into a throughput gain.             only if the transaction
             If we increase the stall            has not already exceeded
             time, the transaction               the WTW time. For example,
             duration increases, which           if a transaction comes to
             is undesirable. At the              commit processing in 0.5
             same time, the grouping             second and the WTW time
             size for group commit               is 2.0 seconds, the stall
             increases, which is                 time is then 1.5 seconds.
             desirable. The challenge            In addition, we can make
             is to determine the                 a further improvement by
             optimal stall time. Reuter          reducing the stall time
             presented an analytical way         by the amount of time
             of determining the optimal          needed for group commit
             stall time for a system             processing. This delta time
             with transactions of the            is constant, on the order
             same type. [1]                      of 50 milliseconds (one I/O
              Ideally, we would like to          plus some computation).

             devise a flexible scheme             The WTW parameter gives
             that makes the trade-off            the user control over
             we have just described in           how much of the response
             real time and determines            time advantage (if any)
             the optimum commit stall            may be used by the system
             time dynamically. However,          to improve transaction
             we cannot determine                 throughput. The choice of
             the optimum stall time              an abnormally high value

          10  Digital Technical Journal Vol. 3 No. 1 Winter 1991

 


                             Designing an Optimized Transaction Commit Protocol



             of WTW by one process only          actually schedule the wake-
             affects its own transaction         up call after a delay.
             response time; it does not          Such a delay allows the
             have any adverse effect on          next group size to become
             the total throughput of the         larger.
             system. A low value of WTW
             would cause small commit         Experiments
             groups, which in turn would
             limit the throughput.                We implemented and tested
             However, this can be                the Commit-Lock, the
             avoided by administrative           Commit-Stall, and the
             controls on the database            Willing-to-Wait designs
             that specify a minimum WTW          in KODA. The objectives of
             time.                               our experiments were

             Hiber Design                        o  To find out which
              The Hiber Design is similar           design would yield
             to the Commit-Stall Design,            the maximum throughput
             but, instead of each                   under response time
             process scheduling its                 constraints

             own wake-up call, the group         o  To understand
             committer wakes up all                 the performance
             processes in the committed             characteristics of the
             group. In addition, the                designs

             group committer must wake            In the following sections,
             up the process that will be         we present the details
             the next group committer.           of our experiments, the

              Note, this design exhibits         results we obtained, and
             a serial wake-up behavior           some observations.

             like the Commit-Lock                Details of the Experiments
             Design, however, the
             mechanism is less costly             The hardware used for
             than the VMS lock used by           all of the following
             the Commit-Lock Design.             tests was a VAX 6340
             In the Hiber Design, if a           with four processors,
             process is not the group            each rated at 3.6 VAX
             committer, it simply                units of performance
             sleeps; it does not                 (VUP). The total possible
             schedule its own wake-              CPU utilization was 400
             up call. Therefore, each            percent and the total
             process is guaranteed               processing power of the
             to sleep and wake up at             computer was 14.4 VUPs.
             most once per commit, in            As the commit processing
             contrast to the Commit-             becomes more significant
             Stall Design. Another               in a transaction (in
             interesting characteristic          relation to the other
             of the Hiber Design is that         phases), the impact of
             the group committer can             the grouping mechanism on
             choose to either wake up            the transaction throughput
             the next group committer            increases. Therefore, in
             immediately, or it can              order to accentuate the
                                                 performance differences

                         Digital Technical Journal Vol. 3 No. 1 Winter 1991  11

 


           Designing an Optimized Transaction Commit Protocol



             between the various                 by the formula: number
             designs, we performed               of servers x 1000/WTW =
             our experiments using a             maximum TPS. For example,
             transaction that involved           our maximum TPS for the
             no database activity except         WTW design was obtained
             to follow the commit                with 50 servers and 90
             sequence. So, for all               milliseconds WTW time.
             practical purposes, the             Using the formula, 50 x
             TPS data presented in this          1000/90 = 555. The actual
             paper can be interpreted            TPS achieved was 500,
             as "commit sequences per            which is 90 percent of
             second." Also, note that            the maximum TPS. This
             our system imposed an upper         ratio is also a measure
             limit of 50 on the grouping         of the effectiveness of the
             size.                               experiment.

             Results                              During our experiments, the
              Using the Commit-Lock              maximum group size observed
             Design, transaction                 was 45 (with the Willing-
             processing bottlenecked             to-Wait Design). This is
             at 300 TPS. Performance             close to the system-imposed
             greatly improved with               limit of 50 and, so, we
             the Commit-Stall Design;            may be able to get better
             the maximum throughput              grouping with higher limits
             was 464 TPS. The Willing-           on the size of the group.

             to-Wait Design provided             Observations
             the highest throughput,              In the Commit-Stall
             500 TPS. Using this last            and the Willing-to-Wait
             design, it was possible to          designs, given a constant
             achieve up to a 66 percent          stall, if the number of
             improvement over the less-          servers is increased, the
             efficient Commit-Lock               TPS increases and then
             Design. Although both timer         decreases. The rate of
             schemes, i.e., the Commit-          decrease is slower than
             Stall and Willing-to-Wait           the rate of increase. The
             designs, needed tuning              TPS decrease is due to
             to set the parameters and           CPU overloading. The TPS
             the Commit-Lock Design did          increase is due to more
             not, we observed that the           servers trying to execute
             maximum throughput obtained         transactions and better
             using timers is much better         CPU utilization. Figure 6
             than that obtained with the         illustrates how TPS varies
             lock. These results were            with the number of servers,
             similar to those of Reuter.         given a constant stall WTW

              For our Willing-to-                time.
             Wait Design, the minimum             Again, in the stalling
             transaction duration is             designs, for a constant
             the WTW time. Therefore,            number of servers, if the
             the maximum TPS, the number         stall is increased, the
             of servers, and the WTW             TPS increases and then
             stall time, measured in             decreases. The TPS increase
             milliseconds, are related           is due to better grouping

          12  Digital Technical Journal Vol. 3 No. 1 Winter 1991

 


                             Designing an Optimized Transaction Commit Protocol



             and the decrease is due
             to CPU underutilization.
             Figures 7 and 8 show the
             effects on TPS when you
             vary the commit-stall time
             or the WTW time, while
             keeping the number of
             servers constant.

              To maximize TPS with
             the Commit-Stall Design,
             the following "mountain-
             climbing" algorithm was
             useful. This algorithm is
             based on the previous two
             observations. Start with
             a reasonable value of the
             stall and the number of
             servers, such that the
             CPU is underutilized. Then
             increase the number of
             servers. CPU utilization
             and the TPS increase.
             Continue until the CPU
             is overloaded; then,
             increase the stall time.
             CPU utilization decreases,
             but the TPS increases due
             to the larger group size.

              This algorithm demonstrates
             that increasing the number
             of servers and the stall
             by small amounts at a
             time increases the TPS,
             but only up to a limit.
             After this point, the TPS
             drops. When close to the
             limit, the two factors
             may be varied alternately
             in order to find the true
             maximum. Table 1 shows the
             performance measurements
             of the Commit-Stall Design.
             Comments are included in
             the table to highlight the
             performance behavior the
             data supports.







                         Digital Technical Journal Vol. 3 No. 1 Winter 1991  13

 


           Designing an Optimized Transaction Commit Protocol




                                        Table 1

                          Commit-Stall Design Performance Data

          ___________________________________________________________________
                  Commit
                  Stall     CPU Uti-
          Number  (Mil-     lization
          of      lisec-    (Per-
          Servers_onds)_____cent)*____TPS__Comments__________________________

          50      20        360       425  Starting point

          55      20        375       454  Increased number of servers,
                                           therefore, higher TPS

          60      20        378       457  Increased number of servers,
                                           therefore, CPU saturated

          60      30        340       461  Increased stall, therefore, CPU
                                           less utilized

          65      30        350       464  Increased number of servers,
                                           maximum TPS

          70      30        360       456  "Over-the-hill" situation, same
                                           strategy of further increasing
                                           the number of servers does not
                                           increase TPS

          70      40        330       451  No benefit from increasing number
                                           of servers and stall

          65      40        329       448  No benefit from just increasing
                                           stall
          *_Four_processors_were_used_in_the_experiments._Thus,_the_total____

          possible CPU utilization is 400 percent.
          ___________________________________________________________________

             The same mountain-                 TPS with this design is
            climbing algorithm is               inversely proportional to
            modified slightly to                the WTW time, while CPU
            obtain the maximum TPS              is not fully utilized.
            with the Willing-to-Wait            The first four rows of
            Design. The performance
            measuremenmts of this               Table 2 illustrate this
            design are presented                behavior. The rest of the
            in Table 2. As we have              table follows the same
            seen before, the maximum            pattern as Table 1.

                                        Table 2

                            Willing-to-Wait Performance Data

          14  Digital Technical Journal Vol. 3 No. 1 Winter 1991

 


                             Designing an Optimized Transaction Commit Protocol




                                     Table 2 (Cont.)

                             Willing-to-Wait Performance Data

           ___________________________________________________________________
                   Willing-
                   to-Wait
                   Stall     CPU Uti-
           Number  (Mil-     lization
           of      lisec-    (Per-
           Servers_onds)_____cent)*____TPS__Comments__________________________

           45      100       285       426  Starting point, CPU not saturated

           45      90        295       466  Decreased stall to load CPU, CPU
                                            still not saturated

           45      80        344       498  Decreased stall again

           45      70        363       471  Further decreased stall, CPU
                                            almost saturated

           50      80        372       485  Increased number of servers, CPU
                                            more saturated

           50      90        340       500  Increased stall to lower CPU
                                            usage, maximum TPS

           55      90        349       465  "Over-the-hill"situation, same
                                            strategy of further increasing
                                            number of servers does not
                                            increase TPS

           50      100       324       468  No benefit from just increasing
                                            stall
           *_Four_processors_were_used_in_the_experiments._Thus,_the_total____

           possible CPU utilization is 400 percent.
           ___________________________________________________________________

              The Willing-to-Wait Design         we expect the Willing-to-
             performs slightly better            Wait Design to perform much
             than the Commit-Stall               better than the Commit-
             Design by adjusting to the          Stall Design.
             variations in the speed at
             which different servers          Future Work
             arrive at the commit
             point. Such variations               There is scope for more
             are compensated for by              interesting work to further
             the variable stalls in the          optimize commit processing
             Willing-to-Wait Design.             in the KODA database
             Therefore, if the variation         kernel. First, we would
             is high and the commit              like to perform experiments
             sequence is a significant           on the Hiber Design and
             portion of the transaction,         compare it to the other

                         Digital Technical Journal Vol. 3 No. 1 Winter 1991  15

 


           Designing an Optimized Transaction Commit Protocol



             designs. Next, we would
             like to explore ways of
             combining the Hiber Design          considerable gains in
             with either of the two              transaction processing
             timer designs, Commit-Stall         performance.

             or Willing-to-Wait. This         Acknowledgments
             may be the best design               We wish to acknowledge
             of all the above, with a            the help provided by Rabah
             good mixture of automatic           Mediouni in performing the
             stall, low overhead, and            experiments discussed in
             explicit control over               this paper. We would like
             the total stall time. In            to thank Phil Bernstein
             addition, we would like             and Dave Lomet for their
             to investigate the use              careful reviews of this
             of timers to ease system            paper. Also, we want
             management. For example,            to thank the other KODA
             a system administrator may          group members for their
             increase the stalls for             contributions during
             all transactions on the             informal discussions.
             system in order to ease             Finally, we would like
             CPU contention, thereby             to acknowledge the efforts
             increasing the overall              of Steve Klein who designed
             effectiveness of the                the original KODA group
             system.                             commit mechanism.

          Conclusions                         References

              We have presented the
             concept of group commit             1. P. Helland, H. Sammer,
             processing as well as a                J. Lyon, R. Carr, P.
             general analysis of various            Garrett, and A. Reuter,
             options available, some                "Group Commit Timers and
             trade-offs involved, and               High Volume Transaction
             some performance results               Processing Systems,"
             indicating areas for                   High Performance
             possible improvement. It               Transaction Systems,
             is clear that the choice               Proceedings of the 2nd
             of the algorithm can                   International Workshop
             significantly influence                (September 1987).
             performance at high                 2. Gawlick and D.
             transaction throughput.                Kinkade, "Varieties
             We are optimistic that with            of Concurrency Control
             some further investigation             in IMS/VS Fast Path,"
             an optimal commit sequence             Database Engineering
             can be incorporated into               (June 1985).
             Rdb/VMS and VAX DBMS with








          16  Digital Technical Journal Vol. 3 No. 1 Winter 1991
=============================================================================
Copyright 1991 Digital Equipment Corporation.  Forwarding and copying of this 
article is permitted for personal and educational purposes without fee 
provided that Digital Equipment Corporation's copyright is retained with the 
article and that the content is not modified. This article is not to be 
distributed for commercial advantage. Abstracting with credit of Digital 
Equipment Corporation's authorship is permitted.  All rights reserved.
=============================================================================
