SYSTEMS AND METHODS FOR DYNAMICALLY SWITCHING SYNCHRONIZATION STRATEGIES FOR ACCESSING DATA STRUCTURES

• US 20190324823A1
• Filed: 04/20/2018
• Published: 10/24/2019
• Est. Priority Date: 04/20/2018
• Status: Active Grant

• Current Assignee: Huawei Cloud Computing Technologies Company Limited (Huawei Investment & Holding Co., Ltd.)
• Original Assignee: Huawei Technologies Co., Ltd. (Huawei Investment & Holding Co., Ltd.)
• Inventors: DEPOUTOVITCH, Alexandre, LARSON, Per-Ake, GUO, Cong
• Granted Patent: US 10,783,009 B2
• Time in Patent Office: Days
• CPC Class Codes: G06F 16/2255 Hash tables
• CPC Class Codes: G06F 16/2322 using timestamps
• CPC Class Codes: G06F 16/9014 hash tables
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues
• CPC Class Codes: G06F 9/5083 Techniques for rebalancing the load in a distributed system
• CPC Class Codes: G06F 9/52 Program synchronisation; Mutual exclusion, e.g. by means of semaphores

Abstract

Systems and methods for switching a data access synchronization strategy for a data structure are provided. Workload characteristics of one or more threads of execution access the data structure are monitored. A target data access synchronization strategy is determined. If the current strategy is different than the target strategy, the current strategy is switched to the target data access synchronization strategy for the data structure.

Claims

1. A method of switching a data access synchronization strategy for a data structure stored in a memory of a computing system, the method comprising:

monitoring workload characteristics of one or more threads of execution accessing the data structure;

determining a target data access synchronization strategy for the data structure based on the workload characteristics; and

after determining that a current data access synchronization strategy for the data structure is different than the target data access synchronization strategy, switching the current data access synchronization strategy for the data structure to the target data access synchronization strategy.

2. The method of claim 1, wherein switching comprises:

notifying all of the one or more threads of execution to access the data structure using both the target data access synchronization strategy and the current data access synchronization strategy; and

after determining that all of the one or more threads of execution are accessing the data structure using both the target data access synchronization strategy and the current data access synchronization strategy, notifying, by computing system, all of the one or more threads of execution to access the data structure using only the target data access synchronization strategy.

3. The method of claim 2, wherein determining that all of the threads of execution are accessing the data structure using both the target data access synchronization strategy and the current data access synchronization strategy comprises:

during a current epoch, determining, for a previous epoch, whether any one of the one or more threads of execution are accessing the data structure using only the current data synchronization strategy; and

after determining, for the previous epoch, that none of the one or more threads execution are accessing the data structure using only the current data access synchronization strategy, determining that all of the one or more threads of execution are accessing the data structure using both the target data access synchronization strategy and the current data access synchronization strategy.

4. The method of claim 2, wherein determining, that all of the threads of execution are accessing the data structure using both the target data access synchronization strategy and the current data access synchronization strategy comprises:

assigning to each thread of execution a local epoch counter;

recording a value of a global epoch counter;

assigning, for each thread of execution, a value of the global epoch counter to the local epoch counter at time of each access of the data structure by the execution thread;

for each thread of execution accessing the data structure, determining whether a value of the local epoch counter associated with all the one or more threads of execution equals the value of the global epoch counter;

after determining that the value of all local epoch counters associated with threads of execution accessing the data structure are equal to the current value of the global epoch counter, incrementing the value of the global epoch counter;

determining whether difference between the value of the global epoch counter and the recorded value of the global epoch counter is greater than a threshold;

after determining that difference between the value of the global epoch counter and the recorded value of the global epoch counter is greater than the threshold;

determining that all of the one or more threads of execution are accessing the data structure using both the target data access synchronization strategy and the current data access synchronization strategy.

5. The method of claim 1, wherein the data structure is a hash table, a linked list, a queue, a search tree, a B-tree, or a skip list.

6. The method of claim 1, wherein the current data access synchronization strategy is a lock-free strategy and the target data access synchronization strategy is a lock-based strategy.

7. The method of claim 1, wherein the current data access synchronization strategy is a lock-based strategy and the target data access synchronization strategy is a lock-free strategy.

8. The method of claim 1, wherein the workload characteristics include at least one of a frequency of accesses to the data structure, a ratio of read-only to write accesses to the data structure, a number of elements in a working data set, and a number of data items in the data structure.

9. The method of claim 1, wherein determining the target data access synchronization strategy is further based on an operation to be performed on the data structure.

10. The method of claim 9, wherein the data structure is a hash table, and wherein the operation to be performed on the data structure is a resizing of the hash table.

11. A computing system comprising:

a processor;

a memory storing computer-readable instructions, which when executed by the processor, cause the computing system to;

monitor workload characteristics of one or more of the threads of execution accessing a data structure;

determine a target data access synchronization strategy for the data structure based on the workload characteristics; and

after determining that a current data access synchronization strategy for the data structure is different than the target data access synchronization strategy, switch the current data access synchronization strategy to the target data access synchronization strategy.

12. The computing system of claim 11, wherein the computer-readable instructions, when executed by the processor, cause the computing system to switch the current data access synchronization strategy to the target data access synchronization strategy by:

notifying all of the one or more threads of execution to access the data structure using both the target data access synchronization strategy and the current data access synchronization strategy; and

after determining that all of the one or more threads of execution are accessing the data structure using both the target data access synchronization strategy and the current data access synchronization strategy, notifying all of the one or more threads of execution to access the data structure using only the target data access synchronization strategy.

13. The computing system of claim 12, wherein determining that all of the one or more threads are accessing the data structure using both the target data access synchronization strategy and the current data access synchronization strategy comprises:

during a current epoch, determining, for a previous epoch, whether any one of the one or more threads of execution are accessing the data structure using only the current data synchronization strategy; and

after determining, for the previous epoch, that none of the one or more threads execution are accessing the data structure using only the current data access synchronization strategy, determining that all of the one or more threads of execution are accessing the data structure using both the target data access synchronization strategy and the current data access synchronization strategy.

14. The computing system of claim 11, wherein switching comprises:

assigning to each thread of execution a local epoch counter;

recording a value of a global epoch counter;

assigning, for each thread of execution, a value of the global epoch counter to the local epoch counter at time of each access of the data structure by the execution thread;

for each thread of execution accessing the data structure, determining whether a value of the local epoch counter associated with all the one or more threads of execution equals the value of the global epoch counter;

after determining that the value of all local epoch counters associated with threads of execution accessing the data structure are equal to the current value of the global epoch counter, incrementing the value of the global epoch;

determining whether a difference between the value of the global epoch counter and the recorded value of the global epoch counter is greater than a threshold;

after determining that difference between the value of the global epoch counter and the recorded value of the global epoch counter is greater than the threshold;

determining that all of the one or more threads of execution are accessing the data structure using both the target data access synchronization strategy and the current data access synchronization strategy.

15. The computing system of claim 12, wherein the data structure is a hash table, a queue, a search tree, a linked list, a B-tree, or a skip list.

16. The computing system of claim 12, wherein the current data access synchronization strategy is a lock-free strategy and the target data access synchronization strategy is a lock-based strategy.

17. The computing system of claim 12, wherein the current data access synchronization strategy is a lock-based strategy and the target data access synchronization strategy is a lock-free strategy.

18. The computing system of claim 12, wherein the workload characteristics include at least one of a frequency of accesses to the data structure, a ratio of read-only to write accesses to the data structure, a number of elements in a working data set, a number of data items in the data structure.

19. The computing system of claim 12, wherein the computer-readable instructions, when executed by the processor, cause the computing system to determine the target data access synchronization strategy based on an operation to be performed on the data structure.

20. A non-transitory computer-readable medium storing computer-readable instructions, which when executed by a processor of a computing system, cause the computing system to:

monitor workload characteristics of one or more threads of execution accessing the data structure;

determine a target data access synchronization strategy for the data structure based on the workload characteristics; and

after determining that a current data access synchronization strategy for the data structure is different than the target data access synchronization strategy, switch the current data access synchronization strategy to the target data access synchronization strategy.