NSP manager

• US 10,229,144 B2
• Filed: 03/13/2014
• Issued: 03/12/2019
• Est. Priority Date: 03/15/2013
• Status: Active Grant

• Current Assignee: Marvell Asia Pte Limited (Marvell Technology Group Limited)
• Original Assignee: Cavium, LLC (Marvell Technology Group Limited)
• Inventors: Billa, Satyanarayana Lakshmipathi, Goyal, Rajan
• Primary Examiner(s): Saeed, Usmaan
• Assistant Examiner(s): Perez-Arroyo, Raquel
• Application Number:
  US14/207,933
• Publication Number:
  US 20140280357A1
• Time in Patent Office: 1,825 Days
• Field of Search: 707797
• CPC Class Codes: G06F 11/1666 where the redundant component is memory or memory area
• CPC Class Codes: G06F 11/167 Error detection by comparing the memory output
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/0646 Horizontal data movement in storage systems, i.e. moving data in between storage devices or systems
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]

Abstract

In an embodiment, a method of updating a memory with a plurality of memory lines, the memory storing a tree, a plurality of buckets, and a plurality of rules, can include maintaining a copy of the memory with a plurality of memory lines. The method can further include writing a plurality of changes to at least one of the tree, the plurality of buckets, and the plurality of rules to the copy. The method can additionally include determining whether each of the plurality of changes is an independent write or a dependent write. The method can further include merging independent writes to the same line of the copy. The method further includes transferring updates from the plurality of lines of the copy to the plurality of lines of the memory.

Claims

1. A method of managing a database including a tree, a plurality of buckets, and a plurality of rules, the method comprising:

managing a memory with a plurality of cluster memories, the managing including storing the database across the plurality of cluster memories of the memory and designating a given cluster memory of the plurality of cluster memories as a sink memory cluster; and

improving performance, of a search processor configured to walk the tree, by packing nodes of the tree in each of the plurality of cluster memories, such that walking the tree by the search processor accesses a minimal amount of cluster memories in the memory and walking the tree by the search processor accesses each particular cluster memory no more than once by configuring the memory in such a way that prevents a migration loop from forming, the configuring including embedding one or more migration instructions in the memory that cause a migrated processing thread of the search processor to migrate to the sink memory cluster, the sink memory cluster configured to end migration of the migrated processing thread.

2. The method of claim 1, further comprising packing a first particular number of bucket chunks per bucket and a second particular number of rule pointers per bucket chunk based on addresses of the rules.

3. The method of claim 1, further comprising allocating the rules in the memory in a same order as an order of the rules in bucket chunks of the buckets.

4. The method of claim 1, further comprising:

replicating a rule or a chunk of rules across a first and second bank in a particular cluster memory such that the rule or chunk of rules can be accessed on the second bank when the first bank has a memory access conflict during a particular clock cycle.

5. The method of claim 1, further comprising:

distributing rules and buckets across a first cluster memory and a second cluster memory within the memory; and

enabling processing of the rules by a rule match engine within the first cluster memory and a rule match engine within the second cluster memory.

6. The method of claim 1, further comprising:

storing a first rule of a particular bucket of the plurality of buckets in a particular cluster memory of the plurality of cluster memories; and

storing any other rules of the particular bucket in the particular cluster memory.

7. The method of claim 1, further comprising:

allocating a node of the tree in a particular cluster memory of the memory; and

allocating a bucket in the memory that the node of the tree points to in the particular cluster memory.

8. The method of claim 1, further comprising:

allocating a bucket in a particular cluster memory of the memory; and

allocating a rule associated with the bucket in the particular cluster memory storing the bucket.

9. The method of claim 1, further comprising:

allocating the rules in chunks according to an order of the buckets;

determining a need to replicate the rules across the plurality of cluster memories; and

replicating the rules across the plurality of cluster memories, if necessary.

10. The method of claim 1, further comprising:

determining at least one division of the database, the database including the tree, the plurality of buckets, and the plurality of rules, the division based on either a horizontal division, the horizontal division separating the tree based on a depth of data of the tree or a vertical division, the vertical division separating the tree based on sub-trees of the tree; and

generating at least one memory request to store each division of the database in a respective cluster memory.

11. A system for managing a database including a tree, a plurality of buckets, and a plurality of rules, the system comprising:

a search processor configured to walk the tree;

a memory with a plurality of cluster memories, the memory configured to store the database across the plurality of cluster memories, a given cluster memory of the plurality of memories designated as a sink memory; and

a tree packing module configured to improve performance of the search processor by packing nodes of the tree in each of the plurality of cluster memories such that walking the tree by the search processor accesses a minimal amount of cluster memories in the memory and walking the tree by the search processor accesses each particular cluster memory no more than once by configuring the memory in such a way that prevents a migration loop from forming, wherein configuring the memory includes embedding one or more migration instructions in the memory that cause a migrated processing thread of the search processor to migrate to the sink memory cluster, the sink memory cluster configured to end migration of the migrated processing thread.

12. The system of claim 11, further comprising a bucket packing module configured to pack a first particular number of bucket chunks per bucket and a second particular number of rule pointers per bucket chunk based on addresses of the rules.

13. The system of claim 11, wherein a bucket packing module is configured to allocate the rules in the memory in a same order as an order of the rules in bucket chunks of the buckets.

14. The system of claim 11, further comprising:

a bucket packing module configured to replicate a rule or a chunk of rules across a first and second bank in a particular cluster memory such that the rule or chunk of rules can be accessed on the second bank when the first bank has a memory access conflict during a particular clock cycle.

15. The system of claim 11, further comprising a bucket packing module configured to distribute rules and buckets across a first cluster memory and a second cluster memory within the memory and enable processing of the rules by a rule match engine within the first cluster memory and a rule match engine within the second cluster memory.

16. The system of claim 11, further comprising a bucket packing module configured to store a first rule of a particular bucket of the plurality of buckets in a particular cluster memory of the plurality of cluster memories and store any other rules of the particular bucket in the particular cluster memory.

17. The system of claim 11, further comprising a bucket packing module configured to allocate a node of the tree in a particular cluster memory of the memory and allocate a bucket in the memory that the node of the tree points to in the particular cluster memory.

18. The system of claim 11, further comprising a bucket packing module configured to allocate a bucket in a particular cluster memory of the memory, and allocate a rule associated with the bucket in the particular cluster memory storing the bucket.

19. The system of claim 11, further comprising a bucket packing module configured to allocate the rules in chunks according to an order of the buckets, determine a need to replicate the rules across the plurality of cluster memories, replicate the rules across the plurality of cluster memories, if necessary.

20. The system of claim 11, wherein the tree packing module is further configured to determine at least one division of the database, the database including the tree, the plurality of buckets, and the plurality of rules, the division based on either a horizontal division, the horizontal division separating the tree based on a depth of data of the tree or a vertical division, the vertical division separating the tree based on sub-trees of the tree, and generate at least one memory request to store each division of the database in a respective cluster memory.

21. A non-transitory computer-readable medium configured to store instructions for managing a database including a tree, a plurality of buckets, and a plurality of rules, the instructions, when loaded and executed by a control plane processor, causes the control plane processor to:

manage a memory with a plurality of cluster memories used by a search processor to walk the tree the manage operation including storing the database across the plurality of cluster memories of the memory and designating a given cluster memory of the plurality of cluster memories as a sink cluster memory; and

improve performance of the search processor by packing nodes of the tree in each of the plurality of cluster memories such that walking the tree by the search processor accesses a minimal amount of cluster memories in the memory and walking the tree by the search processor accesses each particular cluster memory no more than once by configuring the memory in such a way that prevents a migration loop from forming, wherein configuring the memory includes embedding one or more migration instructions in the memory that cause a migrated processing thread of the search processor to migrate to the sink memory cluster, the sink memory cluster configured to end migration of the migrated processing thread.