System And Method For Enabling High Read Rates To Data Element Lists

Abstract

A memory system for a network device is described. The memory system includes a main memory configured to store one or more data elements. Further, the memory system includes a link memory that is configured to maintain one or more pointers to interconnect the one or more data elements stored in the main memory. The memory system also includes a free-entry manager that is configured to generate an available bank set including one or more locations in the link memory. In addition, the memory system includes a context manager that is configured to maintain metadata for a list of the one or more data elements.

What is claimed is: 
     
         1 . A memory system for a network device comprising:
 a main memory configured to store one or more data elements;   link memory including a plurality of memory banks, each memory bank of said plurality of memory banks configured to maintain one or more pointers to interconnect said one or more memory locations in said main memory to form at least one list including a first skip list of one or more skip lists; and   a context manager configured to maintain first metadata for a first head node of said first skip list, said metadata for said first head node includes a link to second metadata for a second node of said first skip list.   
     
     
         2 . The memory system of  claim 1 , wherein said first metadata is snapshot list metadata. 
     
     
         3 . The memory system of  claim 1 , wherein said first metadata includes a sequence identifier. 
     
     
         4 . The memory system of  claim 2 , wherein said at least one list is a snapshot list. 
     
     
         5 . The memory system of  claim 2 , wherein each memory bank of said plurality of memory banks includes a single access port. 
     
     
         6 . The memory system of  claim 1  further comprising a free-entry manager configured to generate an available bank set including one or more locations in said link memory that are not currently used to maintain said one or more pointers. 
     
     
         7 . The memory system of  claim 6 , wherein said free-entry manager is configured to generate said available bank set including said one or more locations that are not currently used to maintain said one or more pointers such that a write operation to said link memory does not conflict with a read operation. 
     
     
         8 . The memory system of  claim 6 , wherein said free-entry manager is configured to generate said available bank set by removing one or more banks based on the number of clock cycles since a last write access. 
     
     
         9 . The memory system of  claim 1 , wherein each memory bank of said plurality of memory banks is designated to maintain said one or more pointers for a different one of said one or more skip lists. 
     
     
         10 . The memory system of  claim 2 , wherein said snapshot list metadata is used to form at least one snapshot skip list. 
     
     
         11 . A method for implementing a memory system in a network device comprising:
 storing one or more data elements;   maintaining one or more pointers to interconnect said one or more memory locations in said main memory to form at least one list including at least a first skip list;   allocating one or more locations in at least one memory bank of said plurality of memory banks; and   maintaining first metadata for a first head node of said first skip list, said metadata for said first head node includes a link to second metadata for a second node of said first skip list.   
     
     
         12 . The method of  claim 11  further comprising generating a sequence identifier to include in said first metadata for said first head node of said first skip list. 
     
     
         13 . The method of  claim 11 , wherein said at least one list is a snapshot list and said first skip list is a snapshot skip list. 
     
     
         14 . The method of  claim 13  further comprising determining a second snapshot skip list. 
     
     
         15 . The method of  claim 14 , wherein determining a second snapshot skip list is based on using one or more snapshot sequence identifiers. 
     
     
         16 . The method of  claim 15  further comprising determining a next data element in said second snapshot skip list. 
     
     
         17 . The method of  claim 11  further comprising generating an available bank set including one or more locations in said plurality of memory banks that are not currently being used to store metadata. 
     
     
         18 . A memory system for a network device comprising:
 a main memory configured to store one or more data elements;   a parent distributed-linked list configured to store linked-list metadata; and   a child distributed-linked list configured to maintain list metadata to interconnect said one or more data elements stored in said main memory to generate at least a first snapshot, said linked-list metadata references said first snapshot and said first snapshot including a data element list including one or more skip lists.   
     
     
         19 . The memory system of  claim 18  further configured to generate at least a second snapshot based on said list metadata and configured to generate a first snapshot skip list including said first snapshot and a second snapshot skip list including a second snapshot. 
     
     
         20 . The memory system of  claim 18 , wherein said parent distributed-linked list includes a plurality of head entries, each head entry of said plurality of head entries is configured to store a snapshot sequence identifier for a head node for the one or more skip lists. 
     
     
         21 . The memory system of  claim 19 , wherein said first snapshot is a first head node of said first snapshot skip list and said second snapshot is a second head node of said second snapshot skip list. 
     
     
         22 . The memory system of  claim 21 , wherein said second head entry is configured to store second snapshot list metadata for a second node in said second snapshot skip list. 
     
     
         23 . The memory system of  claim 18  further comprising a free-entry manager configured to generate an available bank set including one or more locations in said parent distributed-linked list that are not currently storing said linked-list metadata such that a write operation to said parent distributed-linked list does not conflict with a read operation. 
     
     
         24 . A memory system for a network device comprising:
 a means for storing one or more data elements;   a means for maintaining one or more pointers to interconnect said one or more memory locations in said means for storing one or more data elements to form at least one list including at least a first skip list; and   a means for maintaining first metadata for a first head node of said first skip list, said metadata for said first head node includes a link to second metadata for a second node of said first skip list.