Controlling atomic updates of indexes using hardware transactional memory

Patent metadata

Field	Value
Publication number	US-2016357791-A1
Application number	US-201514731379-A
Country	US
Kind code	A1
Filing date	Jun 4, 2015
Priority date	Jun 4, 2015
Publication date	Dec 8, 2016
Grant date	—

Abstract

A current state of one or more entries in a mapping table that are associated with latch-free updates of a data structure that uses indirection mapping tables is accessed. A transformation of the current state of the one or more entries in the mapping table to a transformed state of the entries in the mapping table, is controlled. The controlling includes initiating an atomic multi-word compare-and-swap (MWCAS) operation on a plurality of words using a hardware transactional memory (HTM) resident in a device processor, and the MWCAS operation is performed using hardware primitive operations of the HTM, via the device processor. A transformation of a current state of the data structure to an updated state of the data structure, is controlled, via the transformation of the current state of the one or more entries in the mapping table to the transformed state of the entries in the mapping table.

First claim

what is claimed is:

1 . A system comprising:
at least one hardware device processor; and a computer-readable storage medium storing executable instructions that, when executed, cause one or more of the at least one hardware device processor to:
control a transformation of a current state of one or more entries in a mapping table to an updated state of the entries in the mapping table in a latch-free manner by initiating an atomic multi-word compare-and-swap (MWCAS) operation on a plurality of words using a hardware transactional memory (HTM) resident in the device processor, the MWCAS operation using hardware primitive operations of the HTM, the one or more mapping table entries associated with a lock-free index of a database.

2 . The system of claim 1 , wherein the executable instructions, when executed, cause the one or more of the at least one hardware device processor to:
control the transformation by bracketing accesses to the mapping table in a hardware transaction.

3 . The system of claim 1 , wherein:
controlling the transformation includes bracketing an entire index traversal in a hardware transaction.

4 . The system of claim 1 , wherein:
controlling the transformation includes bracketing only singleton read operations in a hardware transaction.

5 . The system of claim 1 , wherein:
controlling the transformation includes performing read operations non-transactionally.

6 . The system of claim 1 , wherein the executable instructions, when executed, cause the one or more of the at least one hardware device processor to:
control the transformation by bracketing only multi-slot updates to the mapping table in hardware transactions.

7 . The system of claim 1 , wherein the executable instructions, when executed, cause the one or more of the at least one hardware device processor to:
control the transformation by bracketing accesses to the mapping table in hardware transactions; and avoid memory page faults by executing a fallback code path.

8 . The system of claim 7 , wherein the executable instructions, when executed, cause the one or more of the at least one hardware device processor to:
avoid the memory page faults by executing a fallback code path that pre-faults addresses to be executed by one or more of the hardware transactions.

9 . The system of claim 8 , wherein:
pre-faulting the addresses to be executed by the one or more of the hardware transactions includes executing an atomic MWCAS to read the values of respective target words and to perform a compare and swap (CAS) operation on each respective read word that assigns to each respective target word location, the read value of the respective each read word.

10 . The system of claim 8 , wherein the executable instructions, when executed, cause the one or more of the at least one hardware device processor to:
retry executing the fallback code path that pre-faults addresses to be executed by one or more of the hardware transactions.

11 . The system of claim 10 , wherein:
the retry of executing the fallback code path is performed for a configurable number of retries.

12 . The system of claim 1 , wherein the executable instructions, when executed, cause the one or more of the at least one hardware device processor to:
control the transformation by bracketing accesses to the mapping table in hardware transactions; and provide an atomic MWCAS with exclusive access to target words via lockaside operations.

13 . The system of claim 12 , wherein the executable instructions, when executed, cause the one or more of the at least one hardware device processor to:
maintain a respective thread-local read/write lock for each thread of a plurality of concurrently executing threads; and before starting an operation by one of the threads, acquire exclusive access for the one of the threads, to the respective thread-local read/write lock for the one of the threads, wherein the lockaside operations include obtaining exclusive access to the mapping table by acquiring all respective thread-local read/write locks from other threads of the plurality of concurrently executing threads.

14 . The system of claim 13 , wherein:
obtaining the exclusive access to the mapping table includes acquiring all respective thread-local read/write locks from other threads of the plurality of concurrently executing threads, in a deterministic order.

15 . The system of claim 14 , wherein the executable instructions, when executed, cause the one or more of the at least one hardware device processor to:
modify target mapping table entries, by the one of the threads, and release all the respective thread-local read/write locks from the other threads, after the modifying of the target mapping table entries.

16 . A method comprising:
controlling a transformation of a first state of one or more entries in a mapping table to a second state of the entries in the mapping table that are associated with latch-free updates that are associated with a data structure that uses an indirection mapping table that includes the mapping table, the controlling including initiating an atomic multi-word compare-and-swap (MWCAS) operation on a plurality of words using a hardware transactional memory (HTM) resident in a device processor, the MWCAS operation performed using hardware primitive operations of the HTM, via the device processor.

17 . The method of claim 16 , wherein:
controlling the transformation includes controlling progress of hardware transactions that are not guaranteed to succeed, by bracketing accesses to the mapping table in hardware transactions, and by providing an atomic MWCAS with exclusive access to target words via lockaside operations.

18 . A computer program product comprising a computer-readable storage medium storing executable instructions that when executed by at least one processor cause at least one computing device to:
access a current state of one or more entries in a mapping table that are associated with latch-free updates of a data structure that uses an indirection mapping table for lock freedom; control a transformation of the current state of the one or more entries in the mapping table to a transformed state of the entries in the mapping table, the controlling including initiating an atomic multi-word compare-and-swap (MWCAS) operation on a plurality of words using a hardware transactional memory (HTM) resident in a device processor, the MWCAS operation performed using hardware primitive operations of the HTM, via the device processor; and control a transformation of a current state of the data structure to an updated state of the data structure, via the transformation of the current state of the one or more entries in the mapping table to the transformed state of the entries in the mapping table.

19 . The computer program product of claim 18 , wherein:
controlling the transformation of the current state of the one or more entries in the mapping table includes bracketing accesses to the mapping table in a hardware transaction.

20 . The computer program product of claim 19 , wherein:
bracketing accesses to the mapping table in the hardware transaction includes bracketing accesses for an entire index traversal in the hardware transaction.

Assignees

• Microsoft Technology Licensing Llc

Inventors

• Levandoski Justin
• Stutsman Ryan
• Makreshanski Darko

Classifications

• G06F16/217

  Database tuning (G06F16/2282 takes precedence; database performance monitoring G06F11/3409) · CPC title

• G06F16/22 Primary

  Indexing; Data structures therefor; Storage structures · CPC title

• G06F9/46

  Multiprogramming arrangements · CPC title

• G06F16/2379 Primary

  Updates performed during online database operations; commit processing · CPC title

• G06F12/1009 Primary

  using page tables, e.g. page table structures · CPC title