System and method for reading and writing data with a shared memory hash table

• US 9,495,114 B2
• Filed: 05/05/2014
• Issued: 11/15/2016
• Est. Priority Date: 05/10/2013
• Status: Active Grant

• Current Assignee: Arista Networks, Inc.
• Original Assignee: Arista Networks, Inc.
• Inventors: Holbrook, Hugh W., Ritchie, Duncan Stuart, Sapa, Sebastian
• Primary Examiner(s): Dudek, Jr., Edward
• Application Number:
  US14/270,122
• Publication Number:
  US 20140337593A1
• Time in Patent Office: 925 Days
• US Class Current: 1/1
• CPC Class Codes: G06F 12/1027 using associative or pseudo-associative address translation means, e.g. translation look-aside buffer [TLB]
• CPC Class Codes: G06F 16/137 Hash-based content-based indexing of textual data G06F16/31
• CPC Class Codes: G06F 2212/507 using speculative control
• CPC Class Codes: G06F 3/0614 Improving the reliability of storage systems
• CPC Class Codes: G06F 3/0638 Organizing or formatting or addressing of data
• CPC Class Codes: G06F 3/065 Replication mechanisms
• CPC Class Codes: G06F 3/0656 Data buffering arrangements
• CPC Class Codes: G06F 3/0673 Single storage device
• CPC Class Codes: H04L 45/7453 using hashing

Abstract

A method and apparatus of a device that reads and writes data using a shared memory hash table and a lookaside buffer is described. In an exemplary embodiment, a device locates a bucket for the data in a shared memory hash table, where a writer updates the shared memory hash table and a reader that is one of a plurality of readers reads from the shared memory hash table. The device further retrieves an initial value of a version of the bucket. If the initial value of the version is odd, the device copies the data from a lookaside buffer of the writer to a local buffer for the reader, wherein the lookaside buffer stores a copy of the data while the bucket is being modified.

Claims

1. A non-transitory machine-readable medium having executable instructions to cause one or more processing units to perform a method to read data for a local buffer of a reader of a network element, the method comprising:

locating a bucket for the data in a shared memory hash table, wherein a writer updates the data in-place in the bucket in the shared memory hash table and the reader is one of a plurality of readers that reads from the shared memory hash table;

retrieving an initial value of a version of the bucket;

if the initial value of the version indicates that the data is being modified,

copying the data from a lookaside buffer to the local buffer for the shared memory hash table, wherein the lookaside buffer stores a copy of the data of the bucket while the bucket is being modified and is accessible by the plurality of readers.

2. The non-transitory machine-readable medium of claim 1, wherein the bucket data is a key-value pair.

3. The non-transitory machine-readable medium of claim 1, further comprising:

if the initial value of the version is indicates that the data is not being modified,

copying the data from the bucket to the local buffer, wherein an even value of the version indicates that the writer is not modifying the data in the bucket.

4. The non-transitory machine-readable medium of claim 1, further

comprising:

reading a subsequent value of the version of the bucket.

5. The non-transitory machine-readable medium of claim 4, wherein, if the initial value and the subsequent value of the version are different,

discarding the data in the local buffer.

6. The non-transitory machine-readable medium of claim 1, wherein an odd value of the version indicates the data in the bucket is being modified by the writer.

7. A non-transitory machine-readable medium having executable instructions to cause one or more processing units to perform a method to write data by a writer of a network element, the method comprising:

locating a bucket that stores bucket data in a shared memory hash table, wherein the writer modifies the shared memory hash table and a plurality of readers that read from the shared memory hash table, and the bucket is an element of a bucket chain;

copying the bucket data to a lookaside buffer, wherein the bucket data stored in the lookaside buffer can be read by the plurality of readers while the bucket data in the bucket is being modified;

incrementing a version of the bucket in the bucket chain, wherein the incremented version indicates that the bucket is being modified;

modifying the bucket data in place; and

subsequently incrementing the incremented version of the bucket to indicate the bucket data is not being modified.

8. The non-transitory machine-readable medium of claim 7, wherein the bucket data is a key-value pair.

9. The non-transitory machine-readable medium of claim 7, wherein the incremented version is an odd value.

10. The non-transitory machine-readable medium of claim 7, wherein the subsequently incremented version is an even value.

11. The non-transitory machine-readable medium of claim 7, wherein the modifying the bucket data further comprises:

modifying the bucket data without allocating a new bucket to store the bucket data.

12. The non-transitory machine-readable medium of claim 7, wherein the modifying the bucket data further comprises:

modifying the bucket data without using a lock to lock the bucket data being modified.

13. A method to read data for a local buffer of a reader of a network element, the method comprising:

locating a bucket for the data in a shared memory hash table, wherein a writer updates the data in-place in the bucket in the shared memory hash table and the reader is one of a plurality of readers that reads from the shared memory hash table;

retrieving an initial value of a version of the bucket;

if the initial value of the version indicates that the data is not being modified,

copying the data from a lookaside buffer to the local buffer for the shared memory hash table, wherein the lookaside buffer stores a copy of the data of the bucket while the bucket is being modified and is accessible by the plurality of readers.

14. The method of claim 13, wherein the bucket data is a key-value pair.

15. The method of claim 13, further comprising:

if the initial value of the version is indicates that the data is not being modified,

copying the data from the bucket to the local buffer, wherein an even value of the version indicates that the writer is not modifying the data in the bucket.

16. The method of claim 13, further comprising:

reading a subsequent value of the version of the bucket.

17. The method of claim 16, wherein, if the initial value and the subsequent value of the version are different,

discarding the data in the local buffer.

18. The method of claim 13, wherein an odd value of the version indicates the data in the bucket is being modified by the writer.

19. A network element to read data for a local buffer of a reader of the network element, the network element comprising:

a processor;

a memory coupled to the processor through a bus; and

a process executed from the memory by the processor to cause the processor to locate a bucket for the data in a shared memory hash table, wherein a writer updates the data in-place in the bucket in the shared memory hash table and the reader is one of a plurality of readers that reads from the shared memory hash table, retrieve an initial value of a version of the bucket, and, if the initial value of the version indicates that the data is being modified, copy the data from a lookaside buffer to the local buffer for the shared memory hash table, wherein the lookaside buffer stores a copy of the data of the bucket while the bucket is being modified and is accessible by the plurality of readers.

20. The network element of claim 19, wherein the process further causes the processor to if the initial value of the version is indicates that the data is not being modified, copy the data from the bucket to the local buffer, wherein an even value of the version indicates that the writer is not modifying the data in the bucket.

21. A method to write data by a writer of a network element, the method comprising:

locating a bucket that stores bucket data in a shared memory hash table, wherein the writer modifies the shared memory hash table and a plurality of readers that read from the shared memory hash table, and the bucket is an element of a bucket chain;

copying the bucket data to a lookaside buffer, wherein the bucket data stored in the lookaside buffer can be read by the plurality of readers while the bucket data in the bucket is being modified;

incrementing a version of the bucket in the bucket chain, wherein the incremented version indicates that the bucket is being modified;

modifying the bucket data in place; and

subsequently incrementing the incremented version of the bucket to indicate the bucket data is not being modified.