US Patent No. 9,823,867

SYSTEM AND METHOD FOR ENABLING HIGH READ RATES TO DATA ELEMENT LISTS


Patent No. 9,823,867
Issue Date November 21, 2017
Title System And Method For Enabling High Read Rates To Data Element Lists
Inventorship William Brad Matthews, San Jose, CA (US)
Bruce H. Kwan, Sunnyvale, CA (US)
Mohammad K. Issa, Los Altos, CA (US)
Neil Barrett, Palo Alto, CA (US)
Avinash Gyanendra Mani, San Jose, CA (US)
Assignee Innovium, Inc., San Jose, CA (US)

Claim of US Patent No. 9,823,867

1. A network device comprising:
a main memory storing data elements from groups of data elements, wherein a group of data elements includes an ordered sequence
of data elements;

a child link memory including a plurality of memory banks, wherein each memory bank stores one or more entries, each entry
including: (i) a main memory location address that stores a data element identified by the entry, and (ii) a child link memory
location address storing a next data element in a group of data elements corresponding to the data element identified by the
entry;

a child manager including, for each memory bank of the plurality of memory banks in the child link memory, one or more head
nodes and one or more tail nodes, wherein each head node maintains (i) a data-element pointer to a main memory location for
accessing a particular head data element that is a first data element in the respective memory bank for a group of data elements
corresponding to the particular head data element, (ii) a child memory pointer for accessing a child link memory entry in
the same memory bank, and (iii) a data-element sequence number that represents a position of the particular head data element
in an ordered sequence of data elements in the group of data elements corresponding to the particular head data element, and
wherein each tail node maintains a data-element pointer to a main memory location for accessing a particular tail data element
that is a most recent data element in the respective memory bank for a group of data elements corresponding to the particular
tail data element;

a parent manager that includes one or more head entries for each memory bank in the plurality of memory banks in the child
link memory,

wherein each head entry of the one or more head entries stores (i) a snapshot pointer for accessing a particular snapshot
in a snapshot memory; and (ii) a snapshot sequence number to determine which snapshot from one or more snapshots stored in
the snapshot memory is to be accessed next,

wherein each snapshot stores snapshot list metadata for a particular group of data elements, wherein the snapshot list metadata
includes (i) one or more pointers to one or more nodes in the plurality of memory banks that include information for one or
more data elements in the particular group of data elements, and (ii) a data-element sequence number that represents a position
in an ordered sequence of data elements in the particular group of data elements; and

circuitry configured to use the one or more head entries to:
determine, based on the respective snapshot sequence number stored in each head entry, a snapshot order for accessing the
one or more snapshots;

access a snapshot in the snapshot memory based on the determined snapshot order; and
for each accessed snapshot, use the respective snapshot list metadata to determine a sequential order for accessing the one
or more nodes in the plurality of memory banks that include information for data elements in a group of data elements corresponding
to the snapshot.