System and method of a shared memory hash table with notifications and reduced memory utilization

• US 10,642,750 B2
• Filed: 08/03/2015
• Issued: 05/05/2020
• Est. Priority Date: 08/03/2015
• Status: Active Grant

• Current Assignee: Arista Networks, Inc.
• Original Assignee: Arista Networks, Inc.
• Inventors: Ritchie, Duncan Stuart, Sapa, Sebastian, Fordham, Peter John
• Primary Examiner(s): Mamillapalli, Pavan
• Application Number:
  US14/817,133
• Publication Number:
  US 20170039143A1
• Time in Patent Office: 1,737 Days
• Field of Search: 707747
• CPC Class Codes: G06F 12/1018 involving hashing techniques, e.g. inverted page tables
• CPC Class Codes: G06F 13/1663 Access to shared memory
• CPC Class Codes: G06F 13/372 using a time-dependent priority, e.g. individually loaded time counters or time slot
• CPC Class Codes: G06F 13/4022 using switching circuits, e.g. switching matrix, connection or expansion network G06F13/4009 takes precedence
• CPC Class Codes: G06F 16/2255 Hash tables
• CPC Class Codes: G06F 16/9014 hash tables

Abstract

A method and apparatus of a device that includes a shared memory hash table that notifies one or more readers of changes to the shared memory hash table is described. In an exemplary embodiment, a device receives a key that corresponds to the value, where the key used to retrieve the value form the shared memory hash table and the shared memory hash table is written to by a writer and read from by a plurality of readers. In addition, the device retrieves an index from a local values table, where the local values table stores a plurality of indices for one of the plurality of readers and the index is an index into an entry in the shared memory hash table. The device further retrieves the value from the shared memory hash table using the index.

Claims

1. A non-transitory machine-readable medium having executable instructions to cause one or more processing units perform a method to read a value from a shared memory data structure, the method comprising:

receiving a first key that corresponds to the value, the first key used to retrieve the value from the shared memory data structure and the shared memory data structure is written to by a writer and read from by a plurality of readers;

looking up the first key in a local values table, wherein the first key is located at an index in the local values table, the local values table stores a plurality of keys for one of the plurality of readers, and each of the plurality of keys is indexed into an entry in the shared memory data structure; and

retrieving the value from the shared memory data structure using the index, wherein the shared memory data structure is stored in a memory of a network element.

2. The machine-readable medium of claim 1, wherein each of the plurality of readers has a separate local values table.

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

retrieving a second key from the shared memory data structure using the index; and

comparing the first and second key.

4. The machine-readable medium of claim 3, further comprising:

if the first and second key match, returning the value.

5. The machine-readable medium of claim 3, further comprising:

if the first and second key do not match, performing a search for the first key in the shared memory lookup table.

6. The machine-readable medium of claim 5, wherein the performing the search for the first key in the shared memory data structure comprises:

looking up the first key in the shared memory data structure;

retrieving the value associated with the first key; and

returning the value.

7. The machine-readable medium of claim 1, further comprising:

receiving a signal that a notification is available in a notification queue, wherein the notification indicates that the value has been modified;

determining an entry in the notification queue for the index, wherein one or more previous entries in the notification queue corresponding to the index have been invalidated; and

if a third key in the shared memory data structure at the index is different than the first key, updating the local values table at the index with the third key.

8. The machine-readable medium of claim 1, further comprising:

receiving a signal that a notification is available in a notification queue, wherein the notification indicates that the value has been modified;

determining an entry in the notification queue for the index, wherein one or more previous entries in the notification queue corresponding to the index have been invalidated;

retrieving the first key from the shared memory data structure at the index; and

storing the first key in the local values table at the index.

9. The non-transitory machine-readable medium of claim 1, wherein the shared memory data structure is a shared memory table.

10. The non-transitory machine-readable medium of claim 9, wherein the shared memory table is a shared memory hash table.

11. A method to read a value from a shared memory data structure, the method comprising:

receiving a first key that corresponds to the value, the first key used to retrieve the value from the shared memory data structure and the shared memory data structure is written to by a writer and read from by a plurality of readers;

looking up the first key in a local values table, wherein the first key is located at an index in the local values table, the local values table stores a plurality of keys for one of the plurality of readers, and each of the plurality of keys is indexed into an entry in the shared memory data structure; and

retrieving the value from the shared memory data structure using the index, wherein the shared memory data structure is stored in a memory of a network element.

12. The method of claim 11, wherein each of the plurality of readers has a separate local values table.

13. The method of claim 11, further comprising:

retrieving a second key from the shared memory data structure using the index; and

comparing the first and second key.

14. The method of claim 13, further comprising:

if the first and second key match, returning the value.

15. The method of claim 13, further comprising:

if the first and second key do not match, performing a search for the first key in the shared memory lookup table.

16. The method of claim 15, wherein the performing the search for the first key in the shared memory data structure comprises:

looking up the first key in the shared memory data structure;

retrieving the value associated with the first key; and

returning the value.

17. The method of claim 11, further comprising:

receiving a signal that a notification is available in a notification queue, wherein the notification indicates that the value has been modified;

determining an entry in the notification queue for the index, wherein one or more previous entries in the notification queue corresponding to the index have been invalidated; and

if a third key in the shared memory data structure at the index if different than the first key, updating the local values table at the index with the third key.

18. The method of claim 11, further comprising:

receiving a signal that a notification is available in a notification queue, wherein the notification indicates that the value has been modified;

determining an entry in the notification queue for the index, wherein one or more previous entries in the notification queue corresponding to the index have been invalidated; and

retrieving the first key from the shared memory data structure at the index; and

storing the first key in the local values table at the index.

19. The method of claim 11, wherein the shared memory data structure is a shared memory table.

20. The method of claim 19, wherein the shared memory table is a shared memory hash table.

21. A network element that reads a value from a shared memory data structure, 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 receive a first key that corresponds to the value, the first key used to retrieve the value from the shared memory data structure and the shared memory data structure is written to by a writer and read from by a plurality of readers, look up the first key in a local values table, wherein the first key is located at an index in the local values table, the local values table stores a plurality of keys for one of the plurality of readers, and each of the plurality of keys is indexed into an entry in the shared memory data structure, and retrieve the value from the shared memory data structure using the index, wherein the shared memory data structure is stored in the memory.

22. The network element of claim 21, wherein each of the plurality of readers has a separate local values table.

23. The network element of claim 21, wherein the process further causes the processor to retrieve a second key from the shared memory data structure using the index and compare the first and second key.

24. The network element of claim 23, wherein the process further causes the processor to return the value if the first and second key match.

25. The network element of claim 21, wherein the shared memory data structure is a shared memory table.

26. The network element of claim 25, wherein the shared memory table is a shared memory hash table.