System and method of a shared memory hash table with notifications

• US 9,367,251 B2
• Filed: 05/05/2014
• Issued: 06/14/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, Capper, Simon Francis
• Primary Examiner(s): Dudek, Jr., Edward
• Application Number:
  US14/270,226
• Publication Number:
  US 20140359232A1
• Time in Patent Office: 771 Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2308 Concurrency control transaction processing G06F9/466
• CPC Class Codes: G06F 3/0604 Improving or facilitating administration, e.g. storage management
• 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/0653 Monitoring storage devices or systems
• CPC Class Codes: G06F 3/0655 Vertical data movement, i.e. input-output transfer; data movement between one or more hosts and one or more storage devices
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]
• 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 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 modifies a value in the shared memory hash table, where the value has a corresponding key. The device further stores a notification in a notification queue that indicates the value has changed. In addition, the device invalidates a previous entry in the notification queue that indicates the value has been modified. The device signals to the reader that a notification is ready to be processed.

Claims

1. A non-transitory machine-readable medium having executable instructions to cause one or more processing units perform a method to notify a reader that a value in a shared memory hash table has been modified, the method comprising:

modifying a value in the shared memory hash table, where in the value has a corresponding key;

storing a notification in a notification queue that indicates the value associated with the corresponding key has changed;

invalidating one or more previous entries in the notification queue that corresponding to the key; and

signaling to the reader that a notification is ready to be processed.

2. The non-transitory machine-readable medium of claim 1, wherein the modifying comprises:

identifying a slot identifier for the key corresponding to the value, wherein the slot identifier references a slot entry in a slot table.

3. The non-transitory machine-readable medium of claim 2, wherein the slot includes a reference to the modified value.

4. The non-transitory machine-readable medium of claim 2, wherein the notification includes the slot identifier.

5. The non-transitory machine-readable medium of claim 2, wherein invalidating the one or more previous entries in the notification queue comprises:

invalidating other notifications in the notification queue with the slot identifier.

6. The non-transitory machine-readable medium of claim 1, wherein storing the notification comprises:

inserting the notification at a front of the notification queue.

7. The non-transitory machine-readable medium of claim 1, wherein the modifying is selected from the group of adding a value, deleting a value, and changing a value.

8. The non-transitory machine-readable medium of claim 1, wherein the reader updates a local copy of the value using the notification by reading from the shared memory hash table the value associated with the next key it reads from the notification queue.

9. The non-transitory machine-readable medium of claim 8, wherein the reader updates the local copy by reading a version associated with the key, reading a value corresponding with the key, and validating the version.

10. The non-transitory machine-readable medium of claim 1, wherein the signaling uses a kick mechanism that notifies the reader in response to the reader sending a notification that the reader is blocked and ready for new notifications.

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

compacting the notification queue if the notification queue is full without disrupting read access for the reader, wherein the compacting occurs by,

creating a new notification queue;

copying active slot identifier entries to the new notification queue; and

notifying the reader to use the new notification queue.

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

auditing the notification queue to ensure valid entries, wherein the auditing occurs in response to a writer restarting.

13. A non-transitory machine-readable medium having executable instructions to cause one or more processing units perform a method to modify a local copy of a value in a shared memory hash table, the method comprising:

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

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

modifying the local copy of the value based on comparing the value in the shared memory hash table and the local copy of the value.

14. The non-transitory machine-readable medium of claim 13, wherein the determining comprises:

reading a next available slot identifier on the notification queue.

15. The non-transitory machine-readable medium of claim 14, wherein the determining further comprises:

skipping over an invalidated entry in the notification queue.

16. The non-transitory machine-readable medium of claim 14, wherein the determining further comprises:

reading the key associated with the slot identifier; and

comparing the key with another key identified by the slot identifier in a shadow slot table.

17. A method to notify a reader that a value in a shared memory hash table has been modified, the method comprising:

modifying a value in the shared memory hash table, where in the value has a corresponding key;

storing a notification in a notification queue that indicates the value associated with the corresponding key has changed;

invalidating one or more previous entries in the notification queue that corresponding to the key; and

signaling to the reader that a notification is ready to be processed.

18. The method of claim 17, wherein the modifying comprises:

identifying a slot identifier for the key corresponding to the value, wherein the slot identifier references a slot entry in a slot table.

19. The method of claim 17, wherein storing the notification comprises:

inserting the notification at a front of the notification queue.

20. A network element that notifies a reader that a value in a shared memory hash table has been modified, 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 modify a value in the shared memory hash table, where in the value has a corresponding key, store a notification in a notification queue that indicates the value associated with the corresponding key has changed, invalidate one or more previous entries in the notification queue that corresponding to the key; and

signal to the reader that a notification is ready to be processed.