Acquisition of multiple synchronization objects within a computing device

• US 8,954,409 B1
• Filed: 09/22/2011
• Issued: 02/10/2015
• Est. Priority Date: 09/22/2011
• Status: Active Grant

• Current Assignee: Juniper Networks Incorporated
• Original Assignee: Juniper Networks Incorporated
• Inventors: Libby, Jeffrey G., Goel, Deepak, Ofelt, David J., Gupta, Anurag P., Kerem, Oren
• Primary Examiner(s): LE, HUNG D
• Application Number:
  US13/240,259
• Time in Patent Office: 1,237 Days
• Field of Search: None
• US Class Current: 707/704
• CPC Class Codes: G06F 16/2308 Concurrency control transaction processing G06F9/466
• CPC Class Codes: G06F 16/9014 hash tables

Abstract

In general, techniques of the present disclosure relate to synchronizing concurrent access to multiple portions of a data structure. In one example, a method includes, sequentially selecting a plurality of requests from a request queue, wherein at least one of the requests specifies a plurality of requested synchronization objects for corresponding candidate portions of a data structure to which to apply an operation associated with a data element. The method also includes querying one or more sets of identifiers to determine whether one or more of the requested synchronizations objects specified by the selected request are acquirable. The method also includes acquiring each of the requested synchronization objects that are acquirable. The method includes, responsive to acquiring all of the one or more requested synchronization objects, selecting a subset of the candidate portions of the data structure and applying the operation only to the selected subset of the candidate portions.

Claims

1. A method comprising:

sequentially selecting, by a computing device, a plurality of requests from a request queue, wherein at least one request of the plurality of requests specifies a plurality of requested synchronization objects, the requested synchronization objects corresponding to different non-contiguous candidate portions dispersed in a data structure to which to apply operations, wherein each of the plurality of requested synchronization objects for each of the corresponding candidate portions must be acquired to apply the operations for the at least one request on the corresponding candidate portions of the data structure;

responsive to determining that a first subset of the plurality of requested synchronization objects has been previously acquired by the at least one request, querying, by the computing device, one or more sets of identifiers to determine whether a second subset of the plurality of requested synchronizations objects not previously acquired by the at least one request are acquirable, wherein each respective identifier of one or more sets of identifiers identifies a respective synchronization object of the plurality of requested synchronization objects;

acquiring, by the computing device, any of the second subset of the plurality of requested synchronization objects that are acquirable; and

responsive to acquiring all of the requested synchronization objects in the first and second subsets, selecting, by the computing device, the candidate portions of the data structure and applying the operations only to the candidate portions.

2. The method of claim 1,

wherein the data structure comprises a hash table;

wherein the candidate portions of the data structure comprise buckets of the hash table; and

wherein the requested synchronization objects comprise locks that correspond to the buckets of the hash table.

3. The method of claim 1, wherein at least one of the operations of the at least one request comprises at least an insert operation to insert the data element into the selected candidate portions of the data structure or a delete operation to delete the data element from the selected candidate portions of the data structure.

4. The method of claim 1, further comprising:

receiving, by the computing device, the at least one request; and

storing, by the computing device, the at least one request at a tail of the request queue.

5. The method of claim 1, wherein sequentially selecting the at least one request from the request queue that includes a plurality of requests further comprises traversing the request queue from a head of the request queue to a tail of the request queue.

6. The method of claim 1, wherein querying one or more sets of identifiers to determine whether the second subset of the requested synchronizations objects not previously acquired by the at least one request are acquirable further comprises:

selecting, by the computing device, an index value from the at least one request, wherein the index value identifies a candidate portion of the multiple candidate portions of the data structure;

comparing, by the computing device, the index value to each identifier of the one or more sets of identifiers to identify a match between the index value and at least one identifier of the one or more sets of identifiers; and

determining, by the computing device, a requested synchronization object of the one or more specified synchronization objects identified by the index value is acquirable if the index value matches at least one identifier of the one or more sets of identifiers.

7. The method of claim 6, wherein comparing the index value to each identifier of the one or more sets of identifiers to identify the match between the index value and at least one identifier of the one or more sets of identifiers further comprises;

comparing, by the computing device, the index value to each identifier of the one or more sets of identifiers in parallel to identify the match between the index value and at least one identifier of the one or more sets of identifiers.

8. The method of claim 1, wherein the identifiers that identify the synchronization objects are stored as data in rows of a table, and wherein each row of the table is associated with a unique request of the request queue.

9. The method of claim 8, further comprising:

receiving, by the computing device, an event that indicates the operations of the at least one request executing concurrently on the multiple portions of the data structure have completed;

responsive to receiving the event, clearing, by the computing device, data of the row of the table associated with the at least one request; and

dissociating, by the computing device, the at least one request and the row of the table associated with the at least one request.

10. The method of claim 9, further comprising:

clearing data of the row of the table associated with the at least one request and dissociating the row of the table associated with the at least one request and the at least one request after traversing a tail request of the request queue and before traversing a head request of the request queue.

11. The method of claim 10, wherein the event includes data identifying the multiple candidate portions of the data structure.

12. The method of claim 1, wherein acquiring any of the second subset of the requested synchronization objects that are acquirable further comprises:

setting, by the computing device, indicators associated with each of the requested synchronizations objects that indicate that each of the requested synchronization objects are acquired.

13. The method of claim 1, wherein the computing device comprises a network device.

14. The method of claim 1, wherein the at least one request is a first request of the plurality of requests, the candidate portions are first candidate portions, and the plurality of requested synchronization objects is a first plurality of requested synchronization objects, the method further comprising:

responsive to querying the one or more sets of identifiers to determine whether one or more of the first plurality of requested synchronizations objects specified by the first request are acquirable, determining that all of the first plurality of requested synchronizations objects specified by the first request are not acquirable;

after determining that all of the first plurality of requested synchronizations objects specified by the first request are not acquirable, querying the one or more sets of identifiers to determine whether one or more of a second plurality of requested synchronizations objects specified by a second request that is queued after the first request are acquirable, each of the second plurality of requested synchronizations objects being different than each of the first plurality of requested synchronizations objects;

before acquiring all of the first plurality of requested synchronization objects and responsive to determining that all of the second plurality of requested synchronizations objects specified by the second request are acquirable, acquiring, by the computing device, all of the second plurality of requested synchronization objects; and

responsive to acquiring all of the second plurality of requested synchronization objects, applying, by the computing device, an operation of the second request only to second candidate portions that correspond to the second plurality of requested synchronization objects.

15. A computing device comprising:

a control unit having one or more hardware-based microprocessors; and

a manager module executable by the microprocessors,

wherein the manager module sequentially selects a plurality of requests from a request queue, wherein at least one request of the plurality of requests specifies a plurality of requested synchronization objects, the requested synchronization objects corresponding to different non-contiguous candidate portions dispersed in a data structure to which to apply operations, wherein each of the plurality of requested synchronization objects for each of the corresponding candidate portions must be acquired to apply the operations for the at least one request on the corresponding candidate portions of the data structure;

wherein the manager module, responsive to determining that a first subset of the plurality of requested synchronization objects has been previously acquired by the at least one request, queries one or more sets of identifiers to determine whether a second subset of the plurality of requested synchronizations objects not previously acquired by the at least one request are acquirable, wherein each respective identifier of one or more sets of identifiers identifies a respective synchronization object of the plurality of requested synchronization objects;

wherein the manager module acquires any of the second subset of the plurality of requested synchronization objects that are acquirable; and

wherein responsive to acquiring all of the requested synchronization objects in the first and second subsets, selecting, by the computing device, the candidate portions of the data structure and applying the operations only to the candidate portions.

16. The computing device of claim 15,

wherein the data structure comprises a hash table;

wherein the candidate portions of the data structure comprise buckets of the hash table; and

wherein the requested synchronization objects comprise locks that correspond to the buckets of the hash table.

17. The computing device of claim 15, wherein at least one of the operations of the at least one request comprises at least an insert operation to insert the data element into the selected candidate portions of the data structure or a delete operation to delete the data element from the selected candidate portions of the data structure.

18. The computing device of claim 15,

wherein the manager module receives the at least one request and stores the at least one request at a tail of the request queue.

19. The computing device of claim 15, wherein the manager module sequentially selects the at least one request from the request queue that includes a plurality of requests further comprises traversing the request queue from a head of the request queue to a tail of the request queue.

20. The computing device of claim 15,

wherein the manager module selects an index value from the at least one request, wherein the index value identifies a candidate portion of the multiple candidate portions of the data structure;

wherein the manager module compares the index value to each identifier of the one or more sets of identifiers to identify a match between the index value and at least one identifier of the one or more sets of identifiers; and

wherein the manager module determines a requested synchronization object of the one or more specified synchronization objects identified by the index value is acquirable if the index value matches at least one identifier of the one or more sets of identifiers.

21. The computing device of claim 20,

wherein the manager module compares the index value to each identifier of the one or more sets of identifiers in parallel to identify the match between the index value and at least one identifier of the one or more sets of identifiers.

22. The computing device of claim 15,

wherein the identifiers that identify the synchronization objects are stored as data in rows of a table, and wherein each row of the table is associated with a unique request of the request queue.

23. The computing device of claim 22,

wherein the manager module receives an event that indicates the operations of the at least one request executing concurrently on the multiple portions of the data structure have completed;

wherein the manager module, responsive to receiving the event, clears data of the row of the table associated with the at least one request; and

wherein the manager module dissociates the at least one request and the row of the table associated with the at least one request.

24. The computing device of claim 23,

wherein the manager module clears data of the row of the table associated with the at least one request and dissociates the row of the table associated with the at least one request and the at least one request after traversing a tail request of the request queue and before traversing a head request of the request queue.

25. The computing device of claim 15,

wherein the manager module sets indicators associated with each of the requested synchronizations objects that indicate that each of the requested synchronization objects are acquired.

26. The computing device of claim 15 wherein the event includes data identifying the multiple candidate portions of the data structure.

27. The computing device of claim 15, wherein the computing device comprises a network device.

28. A non-transitory computer-readable memory comprising instruction that, when executed, cause one or more processors to:

sequentially select a plurality of requests from a request queue, wherein at least one request of the plurality of requests specifies a plurality of requested synchronization objects, the requested synchronization objects corresponding to different non-contiguous candidate portions dispersed in a data structure to which to apply operations, wherein each of the plurality of requested synchronization objects for each of the corresponding candidate portions must be acquired to apply the operations for the at least one request on the corresponding candidate portions of the data structure;

responsive to determining that a first subset of the plurality of requested synchronization objects has been previously acquired by the at least one request, query one or more sets of identifiers to determine whether a second subset of the plurality of requested synchronizations objects not previously acquired by the at least one request are acquirable, wherein each respective identifier of one or more sets of identifiers identifies a respective synchronization object of the plurality of requested synchronization objects;

acquire any of the second subset of the plurality of requested synchronization objects that are acquirable; and

responsive to acquiring all of the requested synchronization objects in the first and second subsets, selecting the candidate portions of the data structure and applying the operations only to the candidate portions.

29. A computing device comprising:

a control unit having one or more hardware-based microprocessors;

a manager module executable by the microprocessors;

a hash engine configured to apply a plurality of hashing functions to a data element to generate a plurality of identifiers that identify different non-contiguous candidate portions dispersed in a hash table to which to write the data element;

wherein the manager module sequentially selects a plurality of requests from a request queue, wherein at least one request of the plurality of requests specifies a plurality of locks, each of the requested locks corresponding to a different candidate portion of the hash table to which to apply an operation, wherein each of the plurality of requested locks for each of the corresponding candidate portions must be acquired to apply the operation for the at least one request on the subset of the corresponding candidate portions of the data structure;

wherein the manager module, responsive to determining that a first subset of the plurality of requested locks has been previously acquired by the at least one request, queries one or more sets of identifiers to determine whether a second subset of the plurality of requested locks not previously acquired by the at least one request are acquirable, wherein each respective identifier of the one or more sets of identifies a respective lock of the plurality of requested locks;

wherein the manager module acquires any of the second subset of the plurality of requested locks that are acquirable;

and

a filter component that, responsive to acquiring all of the requested locks in the first and second subsets, selects, by the microprocessors, the candidate portions of the hash table and writes the data element only to the candidate portions.