# US 2016/0253375 A1 · Transaction processing system, method and program

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2016/0253375 A1
- Document ID: US20160253375A1
- Status: Published application
- Kind: A1
- Application number: 15/148,386
- Filed: 2016-05-06
- Published: 2016-09-01
- Earliest claimed: 2011-08-01
- Assignees: International Business Machines Corporation
- Applicants: International Business Machines Corporation
- Inventors: Hiroshi Horii
- Web page: https://patentgrep.com/patent/US20160253375A1

## CPC

- G06F 16/2379: {Updates performed during online database operations; commit processing}
- G06F 9/466: {Transaction processing}
- G06F 16/2308: {Concurrency control (transaction processing G06F9/466)}
- G06F 16/2329: {using versioning}
- G06F 16/2343: {Locking methods, e.g. distributed locking or locking implementation details}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

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.

## Claims

### Claim 1

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, the method comprising 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;
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; and
starting a wait-for-lock-release transaction on the server that manages a waiting global transaction ID as a key of the management map and querying a value having the waiting global transaction ID as a key; and
when the value queried on the management map is {a state “waiting”, a waiting global transaction ID list for a waiting global transaction},
committing the wait-for-lock-release local transaction,
adding a waiting global transaction ID list for a waiting global transaction to the waiting global transaction ID list of the global transaction to be processed to generate a new waiting global transaction ID list for a global transaction to be processed,
restarting the management local transaction,
updating a value having the ID of the global transaction to be processed to {a state “waiting”, the new waiting global transaction ID list for the global transaction to be processed},
committing the management local transaction, and
setting the global transaction ID at the tail of the new waiting global transaction ID list for the global transaction to be processed as a waiting global transaction ID and performing waiting processing for the global transaction.

### Claim 2 (depends on 1)

The method according to claim 1, further comprising:
starting a wait-for-lock-release transaction on the server that manages a waiting global transaction ID at the tail of the waiting global transaction ID list for the global transaction to be processed as a key of the management map and querying a value having a waiting global transaction ID as a key; and
in response to that the value queried does not exist on the management map or that the state of a waiting global transaction in the value is either committed or aborted, committing the wait-for-lock-release transaction, restarting the management local transaction, and updating a value having a global transaction ID as a key to {a state “working”, null} to notify that lock contention has ended, by processing by the computer.

### Claim 3 (depends on 1)

The method according to claim 1, further comprising the step of, when the global transaction to be processed is committed, updating the value having the ID of the global transaction to be processed to {committed, { }} in the management local transaction and committing the management local transaction.

### Claim 4 (depends on 1)

The method according to claim 1, further comprising the step of, when the global transaction to be processed is rolled back, updating the value having the ID of the global transaction to be processed as a key to {aborted, { }} in the management local transaction and committing the management local transaction.

### Claim 5

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 servers by combining local transaction processes on the servers, the method comprising 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; and
starting a wait-for-lock-release transaction on the server that manages a waiting global transaction ID as a key of the management map and querying a value having the waiting global transaction ID as a key; and
when the value queried on the management map is {a state “waiting”, a waiting global transaction ID list for a waiting global transaction},
committing the wait-for-lock-release local transaction,
adding a waiting global transaction ID list for a waiting global transaction to the waiting global transaction ID list of the global transaction to be processed to generate a new waiting global transaction ID list for a global transaction to be processed,
restarting the management local transaction,
updating a value having the ID of the global transaction to be processed to {a state “waiting”, the new waiting global transaction ID list for the global transaction to be processed},
committing the management local transaction, and
setting the global transaction ID at the tail of the new waiting global transaction ID list for the global transaction to be processed as a waiting global transaction ID, and performing waiting processing for the global transaction.

### Claim 6 (depends on 5)

The non-transitory computer readable storage medium according to claim 5, further comprising the steps of:
starting a wait-for-lock-release transaction on the server that manages a waiting global transaction ID at the tail of the waiting global transaction ID list for the global transaction to be processed as a key of the management map and querying a value having a waiting global transaction ID as a key; and
in response to that the value queried does not exist on the management map or that the state of a waiting global transaction in the value is either committed or aborted, committing the wait-for-lock-release transaction, restarting the management local transaction, and updating a value having a global transaction ID as a key to {a state “working”, null} to notify that lock contention has ended.

### Claim 7 (depends on 5)

The non-transitory computer readable storage medium according to claim 5, further comprising the step of, when the global transaction to be processed is committed, updating the value having the ID of the global transaction to be processed as a key to {committed, { }} in the management local transaction and committing the management local transaction.

### Claim 8 (depends on 5)

The non-transitory computer readable storage according to claim 5, further comprising the step of, when the global transaction to be processed is rolled back, updating the value having the ID of the global transaction to be processed as a key to {aborted, { }} in the management local transaction and committing the management local transaction.

### Claim 9

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, the system comprising:
a memory unit;
one or more processing units, a processing unit configured to:
provide 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;
start 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;
insert 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
update 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
starting a wait-for-lock-release transaction on the server that manages a waiting global transaction ID as a key of the management map and querying a value having the waiting global transaction ID as a key; and
when the value queried on the management map is {a state “waiting”, a waiting global transaction ID list for a waiting global transaction}, the processor unit is further configured to:
commit the wait-for-lock-release local transaction,
add a waiting global transaction ID list for a waiting global transaction to the waiting global transaction ID list of the global transaction to be processed to generate a new waiting global transaction ID list for a global transaction to be processed,
restart the management local transaction,
update a value having the ID of the global transaction to be processed to {a state “waiting”, the new waiting global transaction ID list for the global transaction to be processed},
commit the management local transaction, and
set the global transaction ID at the tail of the new waiting global transaction ID list for the global transaction to be processed as a waiting global transaction ID, and performing waiting processing for the global transaction.

### Claim 10 (depends on 9)

The system according to claim 9, wherein said processing unit is further configured to:
start a wait-for-lock-release transaction on the server that manages a waiting global transaction ID at the tail of the waiting global transaction ID list for the global transaction to be processed as a key of the management map and querying a value having a waiting global transaction ID as a key; and
in response to that the value queried does not exist on the management map or that the state of a waiting global transaction in the value is either committed or aborted, commit the wait-for-lock-release transaction, restarting the management local transaction, and updating a value having a global transaction ID as a key to {a state “working”, null} to notify that lock contention has ended.

### Claim 11 (depends on 9)

The system according to claim 9, wherein said processing unit is further configured to:
when the global transaction to be processed is committed, update the value having the ID of the global transaction to be processed as a key to {committed, { }} in the management local transaction and committing the management local transaction.

### Claim 12 (depends on 9)

The system according to claim 9, further comprising:
when the global transaction to be processed is rolled back, update the value having the ID of the global transaction to be processed as a key to {aborted, { }} in the management local transaction and committing the management local transaction.
