System and method for implementing hierarchical distributed-linked lists for network devices

A network device comprising:

• a main memory configured to store data elements;
• write circuitry configured to:
• write a first portion of a first data packet as first data elements to the main memory;
• write a first child distributed-linked list to maintain list metadata that includes first data-element pointers to the main memory to interconnect the first data elements stored in the main memory;
• after writing the first portion of the first data packet and before writing a second portion of the first data packet to the main memory:
• write a first portion of a second data packet as second data elements to the main memory;
• write a parent distributed linked list that includes a first snapshot that represents (i) a first child pointer to the first child distributed-linked list and (ii) a first sequence identifier associated with the first snapshot;
• and
• write a second child distributed-linked list that includes second data-element pointers to the main memory to interconnect the second data elements stored in the main memory;
• after writing the first portion of the second data packet to the main memory, write the second portion of the first data packet as third data elements to the main memory;
• update the parent distributed linked list to include a second snapshot that represents (i) a second child pointer to the second child distributed-linked list and (ii) a second sequence identifier associated with the second snapshot;
• write a third child distributed-linked list that includes third data-element pointers to the main memory to interconnect the third data elements stored in the main memory;
• and
• after writing the second portion of the first data packet to the main memory, update the parent distributed linked list to include a third snapshot that represents (i) a third child pointer to the third child distributed-linked list and (ii) a third sequence identifier associated with the third snapshot, wherein a value of the third sequence identifier is between values of the first sequence identifier and the second sequence identifier;
• and
• read circuitry configured to read the main memory to reconstruct the first data packet and the second data packet in sequence using (i) snapshots included in the parent distributed linked list and (ii) data-element pointers included in the child distributed-linked lists, wherein the reconstruction of the first data packet and the second data packet are read in an order according to the values of the sequence identifiers associated with the snapshots.

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

• storing, in a main memory, data elements;
• writing a first portion of a first data packet as first data elements to the main memory;
• writing a first child distributed-linked list to maintain list metadata that includes first data-element pointers to the main memory to interconnect the first data elements stored in the main memory;
• after writing the first portion of the first data packet and before writing a second portion of the first data packet to the main memory:
• writing a first portion of a second data packet as second data elements to the main memory;
• writing a parent distributed linked list that includes a first snapshot that represents (i) a first child pointer to the first child distributed-linked list and (ii) a first sequence identifier associated with the first snapshot;
• and
• writing a second child distributed-linked list that includes second data-element pointers to the main memory to interconnect the second data elements stored in the main memory;
• after writing the first portion of the second data packet to the main memory, writing the second portion of the first data packet as third data elements to the main memory;
• updating the parent distributed linked list to include a second snapshot that represents (i) a second child pointer to the second child distributed-linked list and (ii) a second sequence identifier associated with the second snapshot;
• writing a third child distributed-linked list that includes third data-element pointers to the main memory to interconnect the third data elements stored in the main memory;
• and
• after writing the second portion of the first data packet to the main memory, updating the parent distributed linked list to include a third snapshot that represents (i) a third child pointer to the third child distributed-linked list and (ii) a third sequence identifier associated with the third snapshot, wherein a value of the third sequence identifier is between values of the first sequence identifier and the second sequence identifier;
• and
• reading the main memory to reconstruct the first data packet and the second data packet in sequence using (i) snapshots included in the parent distributed linked list and (ii) data-element pointers included in the child distributed-linked lists, wherein the reconstruction of the first data packet and the second data packet are read in an order according to the values of the sequence identifiers associated with the snapshots.