SYSTEM AND METHOD OF A SHARED MEMORY HASH TABLE WITH NOTIFICATIONS AND REDUCED MEMORY UTILIZATION

• US 20170039143A1
• Filed: 08/03/2015
• Published: 02/09/2017
• Est. Priority Date: 08/03/2015
• Status: Active Grant

• Current Assignee: Arista Networks, Inc.
• Original Assignee: Arista Networks, Inc.
• Inventors: Fordham, Peter John, Ritchie, Duncan Stuart, Sapa, Sebastian
• Granted Patent: US 10,642,750 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• 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 hash table, the method comprising:

receiving a first key that corresponds to the value, the first key used to retrieve the value from 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;

looking up the first key in a local values table, wherein the first 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 hash table; and

retrieving the value from the shared memory hash table using the index.

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 hash table 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 hash table comprises:

looking up the first key in the shared memory hash table;

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 hash table 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 hash table at the index; and

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

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

9. A method to read a value from a shared memory hash table, the method comprising:

receiving a first key that corresponds to the value, the first key used to retrieve the value from 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;

looking up the first key in a local values table, wherein the first 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 hash table; and

retrieving the value from the shared memory hash table using the index.

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

11. The method of claim 9, further comprising:

retrieving a second key from the shared memory hash table using the index; and

comparing the first and second key.

12. The method of claim 11, further comprising:

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

13. The method of claim 11, further comprising:

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

14. The method of claim 13, wherein the performing the search for the first key in the shared memory hash table comprises:

looking up the first key in the shared memory hash table;

retrieving the value associated with the first key; and

returning the value.

15. The method of claim 9, 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 hash table at the index if different than the first key, updating the local values table at the index with the third key.

16. The method of claim 9, 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 hash table at the index; and

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

17. A network element that reads a value from a shared memory hash table, 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 hash table and the shared memory hash table 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 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 hash table, and retrieve the value from the shared memory hash table using the index.

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

19. The network element of claim 17, wherein the process further causes the processor to retrieve a second key from the shared memory hash table using the index and compare the first and second key.