CONTROLLING ATOMIC UPDATES OF INDEXES USING HARDWARE TRANSACTIONAL MEMORY

• US 20160357791A1
• Filed: 06/04/2015
• Published: 12/08/2016
• Est. Priority Date: 06/04/2015
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Makreshanski, Darko, Levandoski, Justin, Stutsman, Ryan
• Granted Patent: US 10,067,960 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 12/1009 using page tables, e.g. page table structures
• CPC Class Codes: G06F 16/217 Database tuning G06F16/2282 takes precedence; database performance monitoring G06F11/3409
• CPC Class Codes: G06F 16/22 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/2379 Updates performed during online database operations; commit processing
• CPC Class Codes: G06F 9/46 Multiprogramming arrangements

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.

Claims

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.