System and Method for Enabling High Read Rates to Data Element Lists

A method for operating a network device, the method comprising:

• storing, in a main memory, data elements from groups of data elements, wherein a group of data elements includes an ordered sequence of data elements;
• storing one or more entries in each memory bank of a child link memory that includes a plurality of memory banks, wherein each entry includes (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;
• storing, in each head node in a child manager that includes one or more head nodes and one or more tail nodes for each memory bank of the plurality of memory banks in the child link memory, (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;
• storing, in each tail node in the child manager, 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;
• storing, in each head entry of one or more head entries for each memory bank stored in a parent manager, (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;
• determining, based on the respective snapshot sequence number stored in each head entry, a snapshot order for accessing the one or more snapshots;
• accessing a snapshot in the snapshot memory based on the determined snapshot order;
• and
• for each accessed snapshot, using 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.

A system 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;
• and
• a processor configured to perform operations comprising:
• storing, in each head node of one or more head nodes for each memory bank of the plurality of memory banks in the child link memory, (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;
• storing, in each tail node of one or more tail nodes for each memory bank of the plurality of memory banks in the child link memory, 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;
• storing, in each head entry of one or more head entries for each memory bank in the plurality of memory banks in the child link memory, (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;
• determining, based on the respective snapshot sequence number stored in each head entry, a snapshot order for accessing the one or more snapshots;
• accessing a snapshot in the snapshot memory based on the determined snapshot order;
• and
• for each accessed snapshot, using 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.