# US 2016/0253098 A1 · System and method of a shared memory hash table with notifications

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2016/0253098 A1
- Document ID: US20160253098A1
- Status: Published application
- Kind: A1
- Application number: 15/152,494
- Filed: 2016-05-11
- Published: 2016-09-01
- Earliest claimed: 2013-05-10
- Assignees: Arista Networks, Inc.
- Applicants: Arista Networks, Inc.
- Inventors: Hugh W. Holbrook; Duncan Stuart Ritchie; Sebastian Sapa; Simon Francis Capper
- Web page: https://patentgrep.com/patent/US20160253098A1

## CPC

- G06F 3/0604: {Improving or facilitating administration, e.g. storage management}
- G06F 3/0614: {Improving the reliability of storage systems}
- G06F 3/0638: {Organizing or formatting or addressing of data}
- G06F 3/0653: {Monitoring storage devices or systems}
- G06F 3/0655: {Vertical data movement, i.e. input-output transfer; data movement between one or more hosts and one or more storage devices}
- G06F 3/067: {Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]}
- G06F 3/0673: {Single storage device}
- G06F 16/2308: {Concurrency control (transaction processing G06F9/466)}
- G06F 16/2322: {using timestamps}
- G06F 16/2329: {using versioning}
- H04L 45/7453: using hashing
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## 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

### Claim 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 data structure has been modified, the method comprising:
modifying a value in the shared memorydata structure, 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;
and
signaling to the reader that a notification is ready to be processed.

### Claim 2 (depends on 1)

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.

### Claim 3 (depends on 2)

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

### Claim 4 (depends on 2)

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

### Claim 5 (depends on 1)

The non-transitory machine-readable medium of claim 1, further comprising:
invalidating one or more previous entries in the notification queue that corresponding to the key.

### Claim 6 (depends on 3)

The non-transitory machine-readable medium of claim 3, wherein invalidating the one or more previous entries in the notification queue comprises:
invalidating other notifications in the notification queue with the slot identifier.

### Claim 7 (depends on 1)

The non-transitory machine-readable medium of claim 1, wherein storing the notification comprises:
inserting the notification at a front of the notification queue.

### Claim 8 (depends on 1)

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.

### Claim 9 (depends on 1)

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 data structure the value associated with the next key it reads from the notification queue.

### Claim 10 (depends on 9)

The non-transitory machine-readable medium of claim 9, 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.

### Claim 11 (depends on 1)

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.

### Claim 12 (depends on 1)

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.

### Claim 13 (depends on 1)

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.

### Claim 14 (depends on 1)

The non-transitory machine-readable medium of claim 1, wherein a writer modifies the value and the writer operates independently of a state of the reader.

### Claim 15

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 data structure, 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;
modifying the local copy of the value based on comparing the value in the shared memory data structure and the local copy of the value.

### Claim 16 (depends on 15)

The non-transitory machine-readable medium of claim 15, wherein the determining comprises:
reading a next available slot identifier on the notification queue.

### Claim 17 (depends on 16)

The non-transitory machine-readable medium of claim 16, wherein the determining further comprises:
skipping over an invalidated entry in the notification queue.

### Claim 18 (depends on 16)

The non-transitory machine-readable medium of claim 16, 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.

### Claim 19

A method to notify a reader that a value in a shared memory data structure has been modified, the method comprising:
modifying a value in the shared memorydata structure, 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;
and
signaling to the reader that a notification is ready to be processed.

### Claim 20 (depends on 19)

The method of claim 19, 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.

### Claim 21 (depends on 19)

The method of claim 19, wherein storing the notification comprises:
inserting the notification at a front of the notification queue.

### Claim 22

A network element that notifies a reader that a value in a shared memory data structure 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 memorydata structure, 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,
and signal to the reader that a notification is ready to be processed.

### Claim 23

A method to modify a local copy of a value in a shared memory data structure, 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; and
modifying the local copy of the value based on comparing the value in the shared memory data structure and the local copy of the value.

### Claim 24

A network element that modifies a local copy of a value in 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 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, determine an entry in the notification queue for the value, and modifying the local copy of the value based on comparing the value in the shared memory data structure and the local copy of the value
