System for self-correcting updates to distributed tables

• US 20050246363A1
• Filed: 12/22/2004
• Published: 11/03/2005
• Est. Priority Date: 05/03/2004
• Status: Abandoned Application

• Current Assignee: Avago Technologies General IP PTE Limited (Broadcom, Inc.)
• Original Assignee: Avago Technologies General IP PTE Limited (Broadcom, Inc.)
• Inventors: Paussa, Gregory F.
• Application Number:
  US11/020,426
• Publication Number:
  US 20050246363A1
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 11/1402 Saving, restoring, recovering or retrying
• CPC Class Codes: G06F 16/27 Replication, distribution or synchronisation of data between databases or within a distributed database system; Distributed database system architectures therefor

Abstract

An efficient self-correcting system for updating a data table used in a distributed networking environment is described. The system attempts to change an entry in the distributed data table in response to processing the update request. A first indicator is set to reflect whether the entry was successfully changed. The system periodically compares a maximum table capacity level with a current table capacity level. Periodically, a second indicator is set to reflect the current table capacity level. The system periodically attempts to change the entry so long as the first indicator reflects a previously unsuccessful change and the second indicator reflects less than the maximum table capacity level. The unique system may be implemented in a computing device that has a main and distributed data table, a processor, and an apparatus with algorithms that is coupled to the processor. The algorithms self correct updating errors for the distributed data table.

Claims

1. A method for self-correcting updating errors to a distributed data table, comprising:

adding an entry to the distributed data table;

setting a first indicator to reflect whether the step of adding the entry was successful;

periodically comparing a current table capacity level with a maximum table capacity level; and

periodically attempting to add the entry so long as the first indicator reflects a previously unsuccessful add and the current table capacity level is less than the maximum table capacity level.

2. The method of claim 1, further comprising setting a counter to reflect the number of unsuccessful attempts to add the entry.

3. The method of claim 2, further comprising ending the periodic attempts to add when the counter reaches a predefined limit.

4. The method of claim 1, further comprising:

receiving an update request corresponding to a modify request for a second entry;

determining whether a previous add to the second entry was successful; and

after periodically adding the first entry, periodically attempting to add the second entry if the previous add was unsuccessful and the current table capacity level is less than the maximum table capacity level.

5. The method of claim 1 further comprising:

adding second and third entries to the distributed data table;

setting second and third indicators to reflect whether adding the second and third entries was successful;

identifying all entries with indicators that reflect a previously unsuccessful add; and

periodically attempting to add the identified entries so long as the current table capacity level is less than the maximum table capacity level.

6. A method for self-correcting updating errors to a distributed table, comprising:

processing a first update request;

attempting to change at least one entry in the distributed data table in response to processing the update request;

setting a first indicator to reflect whether the entry was successfully changed;

periodically comparing a maximum table capacity level with a current table capacity level;

periodically setting a second indicator to reflect the current table capacity level; and

periodically attempting to change the entry so long as the first indicator reflects a previously unsuccessful change and the second indicator reflects less than the maximum table capacity level.

7. The method of claim 6 further comprising setting a first counter to reflect a number of unsuccessful attempts to change the entry and ending the periodic attempts to change when the first counter reaches a predefined limit.

8. The method of claim 6 wherein the step of comparing a maximum table capacity level comprises:

determining the current table capacity level each time an entry in the table is successfully added to the table; and

comparing the current table capacity level to the maximum table capacity level.

9. The method of claim 6 wherein processing the first update request comprises determining whether the update request was an add request, modify request or delete request.

10. The method of claim 9 further comprising when the update request was the modify request:

determining if a previous attempt to add the entry was successful; and

modifying the entry when the previous attempt to change the entry was successful.

11. The method of claim 9 further comprising when the update request was the modify request determining if the previous attempt to add the entry was successful before periodically attempting to change the entry when the previous attempt to change the entry was not successful.

12. The method of claim 8 further comprising when the update request was the delete request:

determining if the previous attempt to add the entry was successful; and

deleting the entry when the previous attempt to change the entry was successful.

13. A computing device for self-correcting updating errors comprising:

a main data table having a plurality of entries;

a distributed data table having a plurality of entries, wherein the entries in the distributed data table are representatives of entries in the main data table;

a processor coupled to the distributed data table and the main data table, wherein the processor periodically produces update requests so the entries in the distributed data table reflect changes in the main data table; and

an apparatus for storing algorithms that is coupled to the processor, wherein the algorithms self correct updating errors for the distributed data table.

14. The computing device of claim 13 further comprising a gauge coupled to the distributed data table, wherein the gauge periodically determines a current capacity level for the distributed data table.

15. The computing device of claim 13 wherein the algorithms are for:

processing a first update request;

attempting to change at least one entry in the table in response to processing the update request;

setting a first indicator to reflect whether the entry was successfully changed;

periodically comparing a maximum table capacity level with a current table capacity level;

periodically setting a second indicator to reflect the current table capacity level; and

periodically attempting to change the entry so long as the first indicator reflects a previously unsuccessful change and the second indicator reflects less than the maximum table capacity level.

16. The computing device of claim 15 wherein the algorithms comprise a synchronization algorithm for adding new entries and recording unsuccessful attempts to the distributed data table during the update process and a recurring task algorithm for correcting updating errors.

17. The computing device of claim 13 wherein the data table is a main data table.

18. The computing device of claim 13 wherein the first indicator displays a value of TRUE when the entry was successfully added and a value of FALSE when the entry was not successfully added.

19. The computing device of claim 13 wherein the apparatus is a memory storage device.

20. A means for self-correcting updating errors to a distributed table, comprising:

a means for processing a first update request;

a means for attempting to change at least one entry in the distributed data table in response to processing the update request;

a means for setting a first indicator to reflect whether the entry was successfully added;

a means for periodically comparing a maximum table capacity level with a current table capacity level;

a means for periodically setting a second indicator to reflect the current table capacity level; and

a means for periodically attempting to change the entry so long as the first indicator reflects a previously unsuccessful change and the second indicator reflects less than the maximum table capacity level.