Transaction processing system, method and program

A system and method of implementing distributed transactions on a KVS having a simple configuration without unnecessarily causing rollbacks. The method includes providing a management map including a global transaction ID as a key and {a state of global transaction, a waiting global transaction ID list} as a value, starting a management local transaction on one of the plurality of servers, inserting a key-value pair including an ID of the global transaction to be processed as a key and {a state “working”, null} as a value into the management map in the management local transaction, and updating a value having the ID of the global transaction to be processed as a key to {a state “waiting”, a waiting global transaction ID list for the global transaction to be processed} on the management map in the management local transaction and committing the management local transaction.

CROSS-REFERENCE TO RELATED APPLICATION

This application claims priority under 35 U.S.C. §119 from Japanese Patent Application No. 2011-168461 filed Aug. 1, 2011, the entire contents of which are incorporated herein by reference.

BACKGROUND OF THE INVENTION

1. Field of the Invention

The present invention relates to processing of transactions on a distributed processing system, in particular, on a distributed database system and, more specifically, to processing of transactions in a Key Value Store (hereinafter abbreviated as KVS).

2. Description of Related Art

Distributed database systems are well known and employ conventional techniques. JP2007-188518A relates to distributed database systems that use ownership groups and discloses a step of changing data that indicates ownership of a data item that is an atomic operation.

Distributed database systems generally implement relational databases and use syntaxes such as SQL syntaxes in querying.

More recently, database management software called key value store (KVS) has come into use. This architecture manages maps to store pairs of key and value and allows its application to read a value of a map by specifying the key and write a value of a map with the key. This simple architecture enables low latency for search/update operations and high scalability to increase the performance according to the number of severs. To provide database service with low latency and high throughput, therefore, distributed KVS that can distribute data across multiple servers has been also implemented.

In a simple implementation of KVS, the atomicity and isolation of processes are limited to small processing units. For example, in KVS systems such as memcached and Redis, the atomicity and isolation are guaranteed only for single query/update operation. In WebSphere eXtreme Scale and Google App Engine, the atomicity and isolation are guaranteed only for query/update operations on data managed by only one server. However, when an application performs update operations on data on multiple servers, guaranteeing atomicity and isolation for the operations can be mandatory.

On the other hand, with distributed lock systems, atomicity and isolation for the operations on data managed by multiple servers can be guaranteed, as in conventional distributed databases. However, additional distributed lock systems cause additional complexity for the entire system and lose characteristics of simple implementations of KVS. Specifically, implementing a distributed lock mechanism that covers multiple servers in key value stores with the capabilities of the key value stores is absolutely necessary.

Distributed transactions can be implemented on the KVS by handling each operation of transactions (global transactions) on an application as multiple transactions (local transactions) on the KVS. The transaction is as follows:First, a state of a lock (ID of a global transaction that holds a lock and the type of the lock), a committed value, and a value being updated are provided as a value of KVS.A management map is provided on the KVS to manage global transactions. When a global transaction is started, the state of the global transaction is added to the management map as a local transaction.A query/update process is processed as a local transaction. For each query/update operation in a global transaction, the state of a lock, a committed value, and a value being updated are queried/updated as a local transaction.A commit/rollback operation in a global transaction is processed as multiple local transactions. The transaction state of the global transaction in the management map is updated as a local transaction, and each queried/updated value of KVS (the state of a lock, a committed value and a value being updated) is also updated as a local transaction.

An example of such an approach is one described in “How to fully use Open-Source: Slim3 on Google App Engine for Java” by Yasuo Higa and Shin-ichi Ogawa, Shuwa System, pp. 241-251. The literature describes how to implement global transactions with Google App Engine.

Also, Google Percolator is described in http://research.google.com/pubs/pub36726.html.

The existing methods provide a management map on KVS to manage states (Working, Committed and Aborted) of transactions by taking into account an abortion of an application. If the state of a global transaction that is likely to hold a lock for a value is Committed or Aborted, a committed value or a value not updated, respectively, is made available for the other global transactions. However, whenever contention for a lock occurs in such a system, a rollback needs to be performed in order to guarantee isolation.

Google Chubby, described in http://labs.google.com/papers/chubby.html, uses a distributed lock mechanism to enable implementation of distributed transactions. However, building additionally a distributed lock mechanism requires extra software development and management costs.

The present invention eliminates the need for taking into consideration the partitioning of key-value pairs in a simple KVS and therefore increases the versatility of the KVS. In the past, credit transfer applications cannot use a simple KVS in the case where data is divided among multiple servers on a user-ID by user-ID basis. The present invention enables implementation of distributed transactions on KVS without needing to implement an extra distributed lock mechanism.

Moreover, transaction processing for a management map and transaction processing for an application map according to the present invention can increase throughput with an increased number of servers. When lock contention occurs, a transaction is caused to wait for the lock and therefore overhead is low. The present invention has the effect of reducing unintended rollbacks by maintaining an exclusive lock of a management map during a transaction.

SUMMARY OF THE INVENTION

In one aspect of the invention, in a distributed key value store system which includes a plurality of servers, each having an exclusive control mechanism, and in which transaction atomicity and isolation on each of the servers are guaranteed, a distributed key-value-store system control method for implementing global transaction processing that preserves transaction atomicity and isolation on all of the servers by combining local transaction processes on the servers is provided. The method includes the steps of providing beforehand a management map including a global transaction ID as a key and {a state of global transaction, a waiting global transaction ID list} as a value before any global transaction is started, starting a management local transaction on one of the plurality of servers by processing by the computer when a global transaction to be processed is started, inserting a key-value pair including an ID of the global transaction to be processed as a key and {a state “working”, null} as a value into the management map in the management local transaction, and updating a value having the ID of the global transaction to be processed as a key to {a state “waiting”, a waiting global transaction ID list for the global transaction to be processed} on the management map in the management local transaction and committing the management local transaction.

In another aspect of the invention, in a distributed key value store system which includes a plurality of servers having an exclusive control mechanism and in which transaction atomicity on each of the servers is guaranteed, a non-transitory computer readable storage medium tangibly embodying a computer readable program code having computer readable instructions which, when implemented, cause a computer to carry out the steps of a method of global transaction processing that preserves transaction atomicity and isolation on all of the servers by combining local transaction processes on the servers is provided. The method includes the steps of providing beforehand a management map including a global transaction ID as a key and {a state of global transaction, a waiting global transaction ID list} as a value before any global transaction is started, starting a management local transaction on one of the plurality of servers by processing by the computer when a global transaction to be processed is started, inserting a key-value pair including an ID of the global transaction to be processed as a key and {a state “working”, null} as a value into the management map in the management local transaction, and updating a value having the ID of the global transaction to be processed as a key to {a state “waiting”, a waiting global transaction ID list for the global transaction to be processed} on the management map in the management local transaction and committing the management local transaction.

In yet another aspect of the invention, in a distributed key value store system which includes a plurality of servers having an exclusive control mechanism and in which transaction atomicity on each of the servers is guaranteed, a system which implements global transaction processing that preserves transaction atomicity and isolation on all of the servers by combining local transaction processes on the servers is provided. The system includes a memory unit, means for providing in the memory beforehand a management map including a global transaction ID as a key and {a state of global transaction, a waiting global transaction ID list} as a value before any global transaction is started, means for starting a management local transaction on one of the plurality of servers by processing by a computer when a global transaction to be processed is started, means for inserting a key-value pair including an ID of the global transaction to be processed as a key and {a state “working”, null} as a value into the management map in the management local transaction, and means for updating a value having the ID of the global transaction to be processed as a key to {a state “waiting”, a waiting global transaction ID list for the global transaction to be processed} on the management map in the management local transaction and committing the management local transaction.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS

An object of the present invention is to implement distributed transactions on a KVS having a simple configuration without unnecessarily causing rollbacks. The present invention solves the problem by using an exclusive control mechanism of each server to maintain lock dependency between global transactions on a distributed KVS which guarantees atomicity and isolation for local transactions on each server while using an exclusive control mechanism of the KVS to recognize a lock release wait status.

More specifically, a system of the present invention provides a management map including a global transaction ID as a key and a value, {state of global transaction, waiting global transaction ID list}.

In an operation for starting a global transaction identified with a global transaction ID, [TxID], the system of the present invention starts a local transaction for management (management local transaction) on a server that manages the key [TxID] on the management map on the KVS. Then, the system inserts a key-value pair including [TxID] as the key and {working, null} as the value in the management local transaction. The management local transaction does not end until the end (commit or rollback) of the global transaction or until the global transaction enters a state in which it waits for another global transaction to release a lock.

In an operation for the global transaction identified with the global transaction ID, [TxID] to wait for the end of a transaction with [waiting TxID], the system of the present invention updates the value associated with the key [TxID] to {waiting, [waiting TxID]} in the management local transaction and commits the management local transaction. Then, the system starts a local transaction to wait for the end of the global transaction identified with [waiting TxID] (wait-for-lock-release local transaction) on a server that manages the key [waiting TxID] on the management map and queries the value associated with the key [waiting TxID].

Here, if the queried value is not found or the state of the global transaction in the value is “committed” or “aborted”, the system of the present invention commits a wait-for-lock-release local transaction, restarts the management local transaction, updates the value associated the key [TxID] to {working, null}, and notifies that the lock contention has ended (there is a possibility that contention has occurred again).

On the other hand, when the state of [waiting TxID] in the queried value is “waiting” and there is an additional waiting TxID list as a value, the system of the present invention commits the wait-for-lock-release local transaction and adds the waiting TxID list to the waiting TxID list for [TxID] to generate a new waiting TxID list for [TxID]. Then the system restarts the management local transaction on the server that manages [TxID] as a key, updates the state of the global transaction with [TxID] to “waiting”, updates the waiting TxID list for [TxID] to the newly generated list, and commits. After the commit, the system performs waiting processing for the global transaction associated with TxID at the end of the newly generated waiting TxID list for [TxID]. If [TxID] is contained in the newly generated waiting TxID list for [TxID], the system performs a rollback process and notifies the application of the rollback. There is a possibility of deadlock.

When committing or rolling back a transaction, the system of the present invention updates a value having [TxID] as a key to {committed, null} or {aborted, null} in the management local transaction and commits the management local transaction.

An embodiment of the present invention will be described with reference to the drawings. Like reference numerals denote like elements through the drawings unless otherwise stated. It should be noted that the following is a description of an embodiment of the present invention and is not intended to limit the present invention to specifics described with the embodiment.

FIG. 1is a schematic diagram generally showing an entire system for carrying out the present invention. A plurality of client computers102a,102b, . . . ,102zinFIG. 1access a distributed processing system106through the Internet according to a protocol such as HTTP.

The distributed processing system106includes a plurality of servers106a,106b, . . . ,106zwhich are interconnected through a structure such as a LAN or WAN. The distributed server system106is a system that uses a key-value store (KVS) system to build a distributed database. IDs are assigned to the servers106a,106b, . . . ,106zand preferably, but not limited to, the mod of a hash value of a key is calculated to uniquely determine the server that holds the key.

Accordingly, a server106a,106b, . . . ,106zto access by any of the client computers102a,102b, . . . ,102zis determined by a key queried. One of the servers106a,106b, . . . ,106zis a server called catalogue server, where keys and other information that are stored in other servers are stored. The client computers102a,102b, . . . ,102zfirst access the catalogue server to obtain information indicating which of the servers106a,106b, . . . ,106zis to be accessed and then establish a connection to the server indicated. Alternatively, any of the servers that have been accessed by a client computer can broadcast to a plurality of other servers to obtain information. For convenience, the following description starts where a client computer has found an intended server and established a connection to the server.

Each of the client computers102a,102b, . . . ,102zgenerate a unique global transaction ID in order to access the distributed processing system106and uses the global transaction ID for a subsequent transaction with the distributed processing system106.

A hardware configuration of a client computer out of the client computers denoted by reference numerals102a,102b, . . . ,102zinFIG. 1will be described with reference toFIG. 2. The client computer inFIG. 2includes a main memory206, a CPU204, and an IDE controller208, which are connected to a bus202. A display controller214, a communication interface218, a USB interface220, an audio interface222, and a keyboard/mouse controller228are also connected to the bus202. A hard disk drive (HDD)210and a DVD drive212are connected to the IDE controller208. The DVD drive212is used for installing a program from a CD-ROM or a DVD as necessary. Preferably, a display device216having an LCD screen is connected to the display controller214. A screen of an application is displayed on the display device216through a Web browser.

Devices such as an extended hard disk can be connected to the USB interface220as necessary. A keyboard230and a mouse232are connected to the keyboard/mouse controller228. The keyboard230is used for typing in key data for a search, a password and other information. The CPU204can be any CPU that is based on a 32-bit architecture or a 64-bit architecture.

At least an operating system and a client application program402(FIG. 4) for accessing the distributed processing system106are stored in the hard disk drive210. On startup of the system, the operating system is loaded into the main memory206. The client application program402awill be described later in detail with reference to a block diagram ofFIG. 4and flowcharts ofFIGS. 9 to 14.

The communication interface218uses TCP/IP communication facilities provided by the operating system to communicate with the distributed processing system106through the Internet104according to conventional protocols.

FIG. 3is a schematic block diagram of a hardware configuration of a server such as the server106ain the distributed processing system106. As illustrated, servers106a,106b, . . . ,106zare connected through the Internet104. The servers106a,106b, . . . ,106zhave basically the same configuration and therefore the server106awill be illustrated here as a representative example. As illustrated inFIG. 3, client computers102a,102b, . . . ,102zare connected to a communication interface302of the server106athrough the Internet104. The communication interface302is connected to a bus304, to which a CPU306, a main memory (a RAM)308, and a hard disk drive (HDD)310are connected.

Although not depicted, a keyboard, a mouse and a display are also connected to the server106aand can be used by maintenance personnel to manage and maintain the entire server106a. An operating system is stored in the hard disk drive310of the server106a.

Software programs, such as Apache, for causing the server106ato function as a Web server, Java EE, which provides a Java virtual environment, and an application program402aaccording to the present invention, which runs in the Java virtual environment, are also stored in the hard disk drive310. These programs are loaded into and run on the main memory308on startup of the server106a. This enables the client computer102a,102b, . . . ,102zto access the server106aaccording to TCP/IP protocols.

Software for implementing a KVS, is also stored in the hard disk drive310of the server106a. A KVS transaction processing program406a(FIG. 4) according to the present invention is also stored in the hard disk drive310. A function of the transaction processing program406awill be described later in detail with reference to the block diagram ofFIG. 4and the flowcharts ofFIGS. 9 to 14.

FIG. 4is a schematic block diagram of a processing program on the client computers102a,102b, . . . ,102zand a processing program on the servers106a,106b, . . . ,106z. Here, the client computer102aand the server106aare illustrated as representative examples.

The client computer application program402ais stored in the hard disk drive210, and loaded into and executed on the main memory206in response to a predetermined operation by a user of the client computer. The client computer application program402ahas the function of directing a KVS system provided on a server from the client computer to start a transaction, query data, update data, commit, and perform other processing.

The application program402ahas the function404aof generating a global transaction ID (TxID) that is unique across the entire system. An example of a method for generating a global transaction ID is to assign a unique ID to each of the client computers102a,102b, . . . ,102zand each of the servers106a,106b, . . . ,106zand, every time a client computer starts a transaction, add a serial number that is in the client computer and is incremented to the ID of the client computer to generate a global transaction ID. However, any method can be used to generate a global transaction ID that is unique across the entire system.

The application program402acan generate a global transaction ID and access the server106aand generate other global transaction IDs to access a plurality of servers at a time.

A transaction processing program406a, a KVS program408a, and a pair of key (KEY) and value (VALUE) that are referred to by the KVS program408aare stored in the hard disk drive310of the server106a. The transaction processing program406aand the KVS program408aare loaded into and run on the main memory308upon startup of the server106a.

In response to a request with a global transaction ID from the client computer102a, the transaction processing program406acontrols the KVS program408aso as to perform an operation such as locking of a record or rollback, generates a management map412awhich has an entry including the global transaction ID, a state, and a waiting global transaction ID preferably in the main memory308, and maintains the management map412afor each server.

Before describing a configuration and operation of a KVS system according to the present invention, configurations and operations of a number of typical conventional KVS systems will be described. Features of the system according to the present invention will be more apparent by referring to these configurations and operations.

FIG. 5is a diagram illustrating a configuration of a typical conventional KVS. Data is divided into pieces, data502a,502b,502cand502d, as illustrated and are distributed across a plurality of servers102a,102b,102cand102d. A client computer102arequests one server to perform transaction processing. The data is distributed in such a manner that the pieces of data are disjoint. The servers on which the data is placed are preferably determined by calculating the mod of a hash value of a key.

The client computer102asends a command such as begin (to start a transaction), put (to associate a value), get (to acquire a corresponding value), and commit (to commit, that is, confirm an update) to a server that is determined by the value of a key to request the server to perform processing.

The KVS having the conventional configuration described above does not support distributed transactions and therefore cannot be used in a case where an update range in each transaction is complicated. Examples in which an update range in a transaction is complicated are a bank account transfer, especially in the case where the balances on accounts are distributed, and an online shopping site where histories of accounts and goods stock quantities are distributed.

Therefore, a configuration of KVS as illustrated inFIG. 6has been implemented. In this configuration, a field storing data is extended to add a NEXT field which stores a dirty update, and a VER field which stores a lock version as indicated by reference numerals602a,602b,602cand602d.

According to this configuration, a client102aacquires a lock before accessing data. When updating, the client102awrites a dirty update and the version of the lock. On the other hand, a distributed lock mechanism604is separately provided and manages the versions of committed locks. When there is a NEXT value even though the lock has been successfully acquired, the NEXT value is changed to a NOW value, the version of the lock is updated and the processing is continued. This mechanism enables implementation of distributed transactions. However, separately building the distributed lock mechanism604increases software development and management costs.

To avoid this, a KVS configuration that does not use a separate distributed lock mechanism, like the one illustrated inFIG. 7, has been proposed. In this configuration, management tables704a,704b,704cand704d, each of which includes transaction IDs (TxID) and the states of the transactions, for recording the states of transactions, are separately provided on servers106a,106b,106cand106din addition to data tables702a,702b,702cand702d. In this configuration, a client102arecords a version it has queried and can commit only if the queried version has not been updated. After the commit, the state of the transaction is updated with another transaction and the value is updated.

When contention occurs, that is, when a plurality of clients attempts to update the same data in this configuration, the state of an existing transaction is changed to a rollback state. This enables implementation of distributed transactions but only optimistic transactions. Furthermore, while this configuration can be implemented by using existing products alone, frequent rollbacks take place when contention occurs, which can prevent improvement of performance.

FIG. 8illustrates a configuration of the present invention which is an improvement on a KVS configuration like the one illustrated inFIG. 7. Reference numerals used here correspond to those in the functional block diagram ofFIG. 4. Specifically, management maps412a,412b,412cand412dincluding a global transaction ID (TxID), the state of the transaction, and the global transaction ID of a waiting global transaction are separately provided on servers106a,106b,106cand106d. The state of a transaction is stored in a STATE field and the global transaction ID of a waiting global transaction is stored in a WAITING field.

Tables (data maps)410a,410b,410cand410dthat store data of KVS are also provided on the servers106a,106b,106cand106d. Each of the data maps410a,410b,410cand410dincludes a KEY field which contains a key, a NOW field which contains a committed value, a NEXT field which contains a value that is currently being updated, a WRITING field which contains a global transaction ID, TxID in a lock state, that is, an update state, and a READING field which contains a global transaction ID, TxIDs, in a query state.

In this configuration, a client102aupdates information about a lock at every query and update. When contention for a lock occurs, the state of a transaction is updated and the state of a waiting transaction is monitored. After committing, the client102aupdates the state of the transaction and updates a value with another transaction.

When a plurality of clients attempts to update the same data, that is, when contention occurs, an existing lock mechanism is used to wait for the contending transaction(s) to end.

A data structure and an interface for processing of the present invention will be described below.

The following KVS map interface is assumed:get (key): acquires a shared lock for a key and obtains the value associated with the key.put (key, value): acquires an exclusive lock for a key and associates a value with the exclusive lock.cas (key, prev, value): acquires an exclusive lock for a key and, if the value is prev, associates the value with the key.remove (key): acquires an exclusive lock for a key and removes the value.commit ( ): confirms an update to a key and releases all locks acquired.Map configuration (The assumption is that an application uses a single distribution map.)Map (TxStateMap) for managing the state of a transaction: Table such as tables412a,412band412cshown inFIG. 8.key: TxID (global transaction ID)value: State (Working|Committed|Rollbacked|Waiting) (STATE), waiting TxID (WAITING)Map (DataMap) for data management and management of the state of a lock. This is a data map such as data maps410a,410band410cillustrated inFIG. 8.key: Key specified by an applicationvalue: A commit confirmed value (NOW), a value currently being updated (NEXT), a global transaction ID in a lock state, that is, the ID of a global transaction that is currently updating (WRITING), a list of a global transaction ID that is currently querying (READING)

A client that is currently executing a transaction has the following states:TxID

Global transaction ID

This is generated at the start of a transaction.DirtyList

Value of DataMap being updatedReadingKeyList

Key of DataMap being queriedIn addition, FinishTxIDs are provided as finished TxID list

Processes according to the present invention will be described below with reference to the flowcharts ofFIGS. 9 to 14. Throughout the operations in the flowcharts ofFIGS. 9 to 14, basically a client computer issues instructions, processes are performed on a server in response to the instructions, and the server returns responses to the client as necessary.

FIG. 9shows a flowchart of a process at the start of a transaction. The process is executed basically by any of application programs402a,402b, . . . ,402zon any of the client computers102a,102b, . . . ,102z.

At step902, the client computer generates a global transaction ID TxID by adding a serial number that is incremented on the client computer to a unique ID of the client computer.

At step904, the client computer102asets an initial state INIT.STATE=Working and INIT.WAITING={ } and executes put (TxID, INIT) on a map TxStateMap for transaction state management on the corresponding server106ausing the global transaction ID (TxID). At this point in time, the client computer102adoes not commit. The transaction for the management map is called management local transaction.

It should be noted that while the description is provided by taking the combination of the client computer102aand the server106aas an example, there can be any combination of any of client computers102a,102b. . . ,102zand servers106a,106b, . . . ,106zin practice. While actually the application program402aon the client computer102aexecutes a transaction with the server, such execution will be described as “the client computer102aexecutes a transaction” in the following description for convenience.

FIG. 10shows a flowchart of a process of querying, specifically, a process of querying a map for the value of a key. At step1002ofFIG. 10, the client computer102asends a query, DataMap.put (key), to the transaction processing program406aon the corresponding server106aand stores an entry of the result of the query in V. The client computer102athen commits by executing DataMap.commit ( ).

In response to an instruction from the client computer102a, the server106afirst uses NEW=V to copy V in NEW and then executes NEW.READING.add (TxID) to store TxID in the READING field of the data map (DataMap)410aat step1004.

At step1006, the server106adetermines whether or not V.WRITING==NULL. If not, the server106awaits for the V.WRITING transaction to end at step1008. At step1010, the server106athen determines whether or not V.WRITING has been committed. If committed, the server106astores NEW.NOW=NEW.NEXT and sets NEW.NEXT=NULL at step1012; otherwise, the server106asimply sets NEW.NEXT=NULL at step1014. Then the process proceeds to step1016.

If the server106adetermines at step1006that V.WRITING==NULL, the process directly proceeds to step1016. At step1016, the client computer102ainstructs the transaction processing program406ato execute DataMap.cas (key, V, NEW) and then the transaction processing program406aexecutes DataMap.commit ( ) to commit.

The server106adetermines at step1018whether or not CAS has succeeded. If succeeded, the server106aexecutes ReadingKeyList.add (key) to add a key to ReadingKeyList and ends the process at step1020. If the server106adetermines at step1018that CAS has failed, the process returns to step1002.

FIG. 11shows a flowchart of an update process, that is, a process of updating the value of a key to v′ on the map. At step1102ofFIG. 11, the client computer102aissues a query, DataMap.put (key), to the transaction processing program406aand then the server106astores an entry of the result of the query in V. The server106athen executes DataMap.commit ( ) to commit.

At step1104, the server106afirst uses DIRTY=V to copy V in DIRTY, sets DIRTY.NEXT=v′, and sets DIRTY.WRITING=TxID.

At step1106, the server106adetermines whether or not V.WRITING==TxID. If not, the server106adetermines at step1108whether or not V.WRITING==NULL. If not, the server106awaits for termination processing of Tx of V.WRITING at step1110. Then, at step1112, the server106adetermines whether or not V.WRITING has been committed. If committed, the server106asets DIRTY. NOW=V.NEXT and the process proceeds to step1116. If V.WRITING has not been committed, the process directly proceeds to step1116. On the other hand, if it is determined at step1108that V.WRITING==NULL, the process directly proceeds to step1116.

At step1116, the server106aexecutes DIRTY.READING.remove (TxID) to remove TxID from DIRTY.READING.

At step1118, the server106aexecutes V.READING.isEmpty ( ) to determine whether or not V.READING is empty. If it is empty, the server106aproceeds to step1122; otherwise, the server106aperforms wait-for end processing for all transaction in DIRTY.READING.

In this way, if the determination is YES at step1106, or the determination is YES at step1118, or following step1120, the server106aexecutes DIRTY.READING={ }, DataMap.cas (key, V, DIRTY), and DataMap.commit ( ) at step1122.

At step1124, the server106adetermines whether or not CAS has succeeded. If succeeded, the server106aexecutes ReadingKeyList.remove (key) to remove the key from ReadingKeyList and executes DirtyList.add (DIRTY) to add DIRTY to DirtyList. On the other hand, if the server106adetermines that CAS has failed, the process returns to step1102.

FIG. 12shows a flowchart of a commit process. When a commit is to be made, Working is set in PrevState.STATE, which represents the previous state, Committed is set in NewState.STATE, which represents a new state, and TxStateMap.cas (TxID, PrevState, NewState) is executed, then TxStateMap.commit( ) is executed.

At the next step,1204, the server106adetermines whether or not CAS has succeeded. If not, the server106aproceeds to the rollback process at step1206. The failure of CAS here means that CAS has been forced to abort by another transaction.

On the other hand, if CAS has succeeded, the server106adetermines at step1208whether all values in DirtyList have been selected. If selected, the server106adetermines at step1210whether all values in ReadingKeyList have been selected. If not, the server106aselects a key for which CAS has not succeeded from ReadingKeyList at step1212and executesV=DataMap.get (key)NEW=VV.READING.remove (TxID)DataMap.cas (key, V, NEW)DataMap.commit ( )
at step1214. The server106areturns to step1212unless CAS is successful. When CAS has succeeded, the process proceeds to step1210and, when it is determined at step1210that all values in ReadingKeyList have been selected, the process ends.

Returning to step1208, if the server106adetermines that not all values in DirtyList have been selected, the server106aselects a value that has not been selected in DirtyList at step1218, then executesNEW=DIRTYNEW.NEXT=NULLNEW.NOW=DIRTY.NEXTNEW.WRITING=NULL
at step1220, executes DataMap.cas (key, DIRTY, NEW) and DataMap.commit ( ) at step1222, then returns to step1208.

FIG. 13shows a flowchart of a process of a global transaction having a global transaction ID, TxID, to wait for the end of a transaction having a global transaction ID, TgtTxID. At step1302, the client computer102acauses the transaction processing program406aon the server106ato executeWorkingState.STATE=WorkingWaitState.STATE=WaitingWaitState.WAITING={TgtTxID}TxStateMap.cas (TxID, WorkingState, WaitState)TxStateMap.commit ( ).

Then, at step1304, the server106adetermines whether or not CAS has succeeded. If CAS has failed, it means that CAS has been forced to abort by another transaction and therefore a rollback process is performed at step1306.

If the server106adetermines that CAS has succeeded, the server106aexecutes TgtState=TxStateMap.get (TgtTxID) and then TxStateMap.commit ( ) at step1308. Here, get is executed only when the transaction having TgtTxID is Waiting, Committed, or Rollbacked.

At step1310, the server106adetermines whether or not TgtState.WAITING.contained (TxID), that is, whether or not WAITING of TgtState contains TxID. If not, the server106aassumes that there is a possibility of a deadlock and performs a rollback process at step1306.

If the server106adetermines at step1310that WAITING of TgtState contains TxID, the server106adetermines at step1312whether TgtState.STATE is any of Committed and Rollbacked. If so, the server106aproceeds to step1322, where the server106aexecutes TxStateMap.cas (TxID, WaitState, WorkingState) and FinishTxID.add (WaitingTxID), and determines at step1324whether or not CAS has succeeded as a result of the execution. If succeeded, the process ends; otherwise a rollback process is performed at step1326.

Returning to step1312, if TgtState.STATE is not Committed nor Rollbacked, the server106adetermines at step1314whether TgtTxID is zombie, that is, long Waiting. If so, the server106aproceeds to step1318, where the server106aexecutes the following process:NewTgtStage.STATE=RollbackedTxStateMap.cas (TgtTxID, TgtState, NewTgtState)TxStateMap.commit( )

At step1320, the server106adetermines whether or not CAS has succeeded. If succeeded, the server106aproceeds to step1322; otherwise the server106areturns to step1308.

Returning to step1314, if the server106adetermines that TgtTxID is not zombie, the server106aproceeds to step1316, where the server106aexecutes the following process:PrevWaitState=WaitState//This copies WaitState to PrevWaitState.WaitState.WAITING.addAll (TgtState.WAITING)//This adds all global transaction IDs in WaitState.WAITING to WaitState.WAITING.TxStateMap.cas (key, prevWaitState, WaitState)TxStateMap.commit ( )TgtTxID=TgtState.tail ( )//This assigns the global transaction ID listed at the tail of TgtState.WAITING to TgtTxID.
Then the process returns to step1304.

FIG. 14shows a flowchart of a rollback process. At step1402inFIG. 14, Working is set in PrevState.STATE, which represents the previous state, Committed is set in NewState.STATE, which represents a new state, and TxStateMap.cas (TxID, PrevState, NewState) is executed, then TxStateMap.commit ( ) is executed.

Then, at step1404, the server106adetermines whether all values in DirtyList have been selected. If so, at step1406, the server106adetermines whether all values in ReadingKeyList have been selected. Otherwise, the server106aselects a key for which CAS has not succeeded from ReadingKeyList and executesV=DataMap.get (key)NEW=VV.READING.remove (TxID)DataMap.cas (key, V, NEW)DataMap.commit ( )
at step1410. The server106areturns to step1408unless CAS is successful. When it is determines at step1210that all values in ReadingKeyList have been selected, the process ends.

Returning to step1208, if the server106adetermines that not all values in DirtyList have been selected, the server106aselects at step1414a value (DIRTY) that has not been selected in DirtyList, and executesNEW=DIRTYNEW.NEXT=NULLNEW.NOW=DIRTY.NEXTNEW.WRITING=NULL
at step1416, executes DataMap.cas (key, DIRTY, NEW) and DataMap.commit ( ) at step1418, then returns to step1404.

A number of typical exemplary processes of the present invention will be described below with reference to examples inFIGS. 15 to 18. For convenience of explanation, values of NOW and NEXT on a data map (DataMap) will be omitted in the following description. InFIGS. 15 to 18, “s” denotes a shared lock (Shared) and “x” denotes an exclusive lock (eXclusive).

First,FIG. 15illustrates an example in which Tx1queries K1and then commits. In1inFIG. 15, a client computer initiates a transaction Tx1. As a result, Tx1is stored in KEY on a management map412aand STATE becomes Working. In2inFIG. 15, Tx1acquires a shared lock, K1, which is then stored in KEY on a data map410aand {Tx1} is stored in READING on the data map410a.

In3inFIG. 15, a commit process of Tx1is performed and STATE on the management map412becomes Committed. In4inFIG. 15, another commit process of Tx1is performed and READING on the data map410abecomes { }.

FIG. 16illustrates an example in which Tx2attempts to update K1while Tx1is querying K1and, after Tx1has committed, the update is processed. InFIG. 16, 1represents that Tx1is querying K1. In2inFIG. 16, Tx2attempts to acquire the shared lock K1. However, the query by Tx2is blocked because Tx1is querying K1. {Tx1} is placed in Waiting of the entry of KEY=Tx2on the management map412a.

After the commit process of Tx1has ended, Tx2is allowed to query in3inFIG. 16. At4inFIG. 16, Tx2reattempts to acquire the shared lock K1. In response to this, STATE in the entry of KEY=Tx2on the management map412abecomes Working and WAITING becomes { }. In5inFIG. 16, an update process of Tx2is started and Tx2is stored in WRITING corresponding to Key=K1on the data map410a.

FIG. 17illustrates an example in which Tx2waits for Tx1to end, Tx3waits Tx2to end and, upon the end of Tx1, Tx2starts working whereas Tx3is still waiting Tx2to end. In1inFIG. 17, Tx2is waiting for Tx1to commit, as indicated by an entry of the management map412a. In2inFIG. 17, Tx3starts updating K2which is being queried by Tx2. Here, Tx3recognizes that Tx2is waiting for Tx1to end.

In3inFIG. 17, Tx3enters the Tx1wait state. This is indicated by the entry, {Tx2, Tx1}, of WAITING corresponding to KEY=Tx3of the management map412a. In4inFIG. 17, it is shown that after Tx1has been committed and ended, Tx3enters the Tx2wait state.

FIG. 18illustrates an example of a process in which when Tx1, Tx2and Tx3encounter a deadlock, Tx1rolls back. In1inFIG. 18, Tx1and Tx3enter the Tx1wait state. In2inFIG. 18, Tx1attempts to update a value that is being queried by Tx3.

However, as illustrated in3inFIG. 18, Tx1rolls back because WAITING of the entry corresponding to Tx3contains Tx1as can be seen from entries of the management map412a.

Then, as illustrated in4inFIG. 18, after the rollback of Tx1, Tx1is removed from the WAITING field of the entries of Tx2and Tx3of the management map412a, and Tx3enters the Tx2wait state. Here, if Tx2and Tx3query STATE of Tx1before STATE of Tx1is set to Rollbacked, all of the transactions roll back but the atomicity of the transactions is guaranteed.

While an embodiment of the present invention on a particular hardware and software platform has been described, it will be apparent to those skilled in the art that the present invention can be embodied on any computer hardware and platform.