Performing transactions in distributed transactional memory systems

Patent metadata

Field	Value
Publication number	US-10929376-B2
Application number	US-201815933230-A
Country	US
Kind code	B2
Filing date	Mar 22, 2018
Priority date	Mar 22, 2018
Publication date	Feb 23, 2021
Grant date	Feb 23, 2021

Abstract

In various examples, there is provided methods performed by nodes in a cluster of nodes for performing transactions comprising one or more read operations and/or one or more write operations. The node comprises a local clock which is synchronized with a master clock and maintains a measure of uncertainty indicating current minimum and maximum values of the master clock. The method to perform transactions involving read operations generates a read timestamp representing a point in time which is earlier than a current minimum value of the master clock. The method then reads the objects and determines, for each of them, whether a timestamp associated with that object is later than the read timestamp. If so, an error handling procedure is performed for that object.

First claim

The invention claimed is:

1. A method for performing a transaction at a node in a cluster of nodes comprising one or more read operations which read respective objects in a distributed transactional memory system, wherein the node comprises a local clock which is synchronized with a master clock of the cluster of nodes and maintains a measure of uncertainty indicating a current minimum value and a current maximum value of the master clock, the method comprising:
determining, prior to generating a read timestamp, the maximum value of the master clock at a point in time based on the measure of uncertainty;
waiting, prior to generating the read timestamp, until the current minimum value of the master clock indicated by the measure of uncertainty is after the determined maximum value of the master clock;
generating the read timestamp representing a point in time which is earlier than the current minimum value of the master clock, the read timestamp representing a point in time at which the read operations of the transaction are considered to occur, wherein the point in time represented by the generated read timestamp is after or equal to the determined maximum value of the master clock;
performing the one or more read operations to read the respective objects;
determining, for each of the respective objects, whether a timestamp associated with that object representing a point in time at which that object was written indicates a time that is after the time represented by the read timestamp; and
in response to determining that the timestamp associated with one of the respective objects indicates a time that is after the time represented by the read time stamp, performing an error handling procedure for that object.

2. The method of claim 1 , wherein the measure of uncertainty is based on a predetermined maximum rate of clock drift and an amount of time elapsed since a last synchronization with the master clock.

3. The method of claim 1 , wherein the error handling procedure comprises aborting the transaction.

4. The method of claim 1 , wherein the memory system is a multi-version memory system and the error handling procedure, in response to determining that the object is associated with a pointer indicating the location of a previous version of the object stored by the distributed transactional memory system:
reading the previous version of the object from the location indicated by the pointer;
in response to determining that a timestamp associated with the previous version of the object indicates a time that is either before or equal to the time represented by the read time stamp, completing the transaction using the previous version of the object; and
in response to determining that the timestamp associated with the previous version of the object indicates a time that is after the time represented by the read time stamp, re-performing the error handling procedure with respect to the previous version of the object.

5. The method of claim 1 , wherein one or more of the respective objects read by the read operations are stored locally on the node.

6. The method of claim 1 , wherein one or more of the respective objects read by the read operations are stored remotely on another node in the cluster of nodes.

7. The method of claim 1 , wherein the memory system is a multi-version memory system and the read operations are arranged to read a particular version of an object stored in a multi-version memory system, the particular version representing the object as it existed at a particular point in time, the method further comprising:
determining, based on a timestamp associated with a retrieved version of the object indicating a point in time that is after the particular point in time, that a previous version of the object is required;
determining whether version history for the retrieved version of the object has been truncated;
in response to determining that the version history for the retrieved version of the object has been truncated, providing an error;
in response to determining that the version history for the retrieved version of the object has not been truncated, retrieving the previous version of the object and repeating the previous steps in relation to the previous version of the object until either a version of the object is retrieved which has an associated timestamp which indicates a point in time that is before or equal to the particular point in time or an error is provided.

8. The method of claim 7 , wherein:
each version of the object is associated with a respective pointer indicating the location of the previous version of the object; and
determining whether version history for the retrieved version of the object has been truncated comprises determining whether a value of the respective pointer for the retrieved version of the object is null.

9. The method of claim 1 , wherein the memory system is a multi-version memory system and the method further comprises:
maintaining a first local timestamp indicating a read time of the oldest transaction that is currently being processed by the node;
providing the first local timestamp to a master node of the cluster of nodes;
receiving, from the master node, a first global timestamp corresponding to an earliest first local timestamp received by the master node from the nodes in the cluster;
storing the first global timestamp, the stored first global timestamp being the most recently received first global timestamp;
rejecting any transactions that comprise a read timestamp that indicates a time that is older than the stored first global timestamp;
providing the stored first global timestamp to the master node;
receiving, from the master node, a second global timestamp corresponding to an earliest stored first global timestamp received by the master node from the nodes in the cluster;
storing the second global timestamp, the stored second global timestamp being the most recently received second global timestamp; and
performing garbage collection on each of a plurality of previous versions of objects stored on the node when a respective write timestamp associated with the previous version is less than the stored second global timestamp.

10. A method for performing a transaction at a node in a cluster of nodes comprising one or more write operations which write to respective objects in a distributed transactional memory system, wherein the node comprises a local clock which is synchronized with a master clock of the cluster of nodes and maintains a measure of uncertainty indicating a current minimum value and a current maximum value of the master clock, the method comprising:
reading the respective objects to be written;
locking the respective objects to be written to by the one or more write operations;
determining, for each of the respective objects for which locks are obtained, that the timestamp associated with that object representing a point in time has not changed since it was read;
generating a write timestamp representing a point in time at which the write operations of the transaction are considered to occur based on the measure of uncertainty, the point in time represented by the write timestamp being after a maximum value of the master clock at the point in time that all of the respective objects to be written have been locked;
waiting until the current minimum value of the master clock indicated by the measure of uncertainty is after the time represented by the write timestamp;
performing the one or more write operations on the respective objects to be written to and committing the transaction by unlocking the respective objects, wherein performing the one or more write operations comprises associating the respective object to b

Assignees

• Microsoft Technology Licensing Llc

Inventors

• Castro Miguel
• Narayanan Dushyanth
• Dragojevic Aleksandar
• Renzelmann Matthew
• Shamis Alexander
• Khanna Richendra
• Novakovic Stanko
• Gjerdrum Anders
• Chatzopoulos Georgios

Classifications

• G06F16/2315

  Optimistic concurrency control · CPC title

• G06F9/467 Primary

  Transactional memory (G06F9/528 takes precedence) · CPC title

• G06F11/1446

  Point-in-time backing up or restoration of persistent data · CPC title

• G06F11/0745

  in an input/output transactions management context (input/output processing in general G06F13/00) · CPC title

• G06F11/1474

  in transactions (updating of structured data in databases G06F16/23) · CPC title