Atomic operations on data structures

Abstract

Performing atomic operations on data entities having an arbitrary size is disclosed. Version data is associated with a data entity. The version data is saved to a first attribute. The data entity is then accessed. The saved version data is compared to the current version data. If the two are equal, the data entity is valid.

1. A computerized method for performing one or more atomic operations on a data entity of arbitrary size and characterized by version data, the method comprising the following steps:
 in a first thread of execution: 
 acquiring exclusive access to the version data;  
 setting the version data to a first value indicating that the data entity is invalid and not accessible by other operations;  
 modifying the data entity;  
 updating the version data to a second value indicating that the data entity is valid and accessible; and  
 terminating exclusive access to the version data;  
 
 
       in a second thread of execution, the second thread executing concurrently with the first thread of execution:
 (a) reading the first value of  the version data;  
 (b) if the first value is determined to be an invalid value  the version data has a value indicating that the data entry is invalid, repeating steps (a) and (b); and  
 (c) upon completion of step (b), reading the data entity.  
 
     
     
       2. The computerized method of  claim 1 , wherein acquiring exclusive access to the version data comprises acquiring a lock on the version data and wherein terminating exclusive access to the version data releases the lock. 
     
     
       3. The computerized method of  claim 2 , wherein the lock is identified by the version data. 
     
     
       4. The computerized method of  claim 1 , further comprising setting the version data to a predetermined invalid value after acquiring the lock on the version data. 
     
     
       5. The computerized method of  claim 4 , further comprising flushing writes after setting the version data to a predetermined invalid value. 
     
     
       6. The computerized method of  claim 1 , further comprising flushing writes after updating the data entity. 
     
     
       7. The computerized method of  claim 1 , further comprising:
 (d) upon completion of step (c), reading the second value of the  version data a second time;  
 (e) if the first  value of the version data read in step ( a ) does not match the second  value of the version data read the second time, repeating steps (a), (b), (c), (d) and (e).  
 
     
     
       8. The method of  claim 1 , wherein the first thread of execution is executed by one or more read  write units. 
     
     
       9. The method of  claim 1 , wherein the second thread of execution is executed by one or more write  read units. 
     
     
       10. The method of claim  9    8 , wherein at least one of the write units is a web server. 
     
     
       11. The method of  claim 1 , wherein the data entity is stored in a memory that is accessible by both the first and second threads of execution. 
     
     
       12. The method of  claim 1 , wherein the updating step comprises incrementing the version data. 
     
     
       13. The method of  claim 1 , wherein the version data comprises a timestamp, and the updating step comprises updating a timestamp. 
     
     
       14. The method of  claim 1 , wherein the data entity comprises a timestamp. 
     
     
       15. The method of  claim 1 , wherein the data entity comprises a date. 
     
     
       16. The method of  claim 15 , wherein the data entity further comprises a timestamp. 
     
     
       17. The method of  claim 1 , wherein the setting step comprises setting the version data to a value that has been predetermined to represent an invalid version. 
     
     
       18. The method of  claim 1 , further comprising choosing a predetermined value to represent an invalid version. 
     
     
       19. The method of  claim 1 , further comprising:
 in the second thread of execution, 
 saving the first  value of the version data read in step ( a );  
 reading a second value of  the version data a second time; and  
 comparing the first  value and  of the version data read in step ( a )  with  the second  value of the version data read the second time, wherein step (b) is performed based on the comparing step.  
 
 
     
     
       20. The method of  claim 1 , wherein the step of reading the first value of the version data  step ( a ) is performed during the modifying step. 
     
     
       21. The method of  claim 1 , wherein the step of reading the first value of the version data  step ( a ) is performed prior to the updating step. 
     
     
       22. The method of  claim 1 , wherein the first version of execution is executed by one or more read units.  
     
     
       23. A computer-readable medium: having computer-executable instructions to cause a computer to perform a method for performing one or more atomic operations on a data entity of arbitrary size and characterized by version data, the method comprising the following steps:
 in a first thread of execution; 
 acquiring exclusion access to the version data;  
 setting the version data to a first value indicating that the data entity is invalid and not accessible by other operations;  
 modifying the data entity;  
 updating the version data to a second value indicating that the data entry is valid and accessible; and  
 terminating exclusive access to the version data;  
 
 
       in a second thread of execution, the second thread executing concurrently with the first thread of execution:
 (a) reading the first value of  the version data;  
 (b) if the first value is determined to be an invalid value  the version data has a value indicating that the data entity is invalid, repeating steps (a) and (b); and  
 (c) upon completion of step (b), reading the data entity.  
 
     
     
       24. The computer-readable medium of  claim 23 , wherein acquiring exclusive access to the version data comprises acquiring a lock on the version data and wherein terminating exclusive access to the version data releases the lock. 
     
     
       25. The computer-readable medium of  claim 24 , wherein the lock is identified by the version data. 
     
     
       26. The computer-readable medium of  claim 23 , further comprising setting the version data to a predetermined invalid value after acquiring the lock on the version data. 
     
     
       27. The computer-readable medium of  claim 26 , further comprising flushing writes after setting the version data to a predetermined invalid value. 
     
     
       28. The computer-readable medium of  claim 23 , further comprising flushing writes after updating the data entity. 
     
     
       29. The computer-readable medium of  claim 23 , wherein the method further comprises:
 (d) upon completion of step (c), reading the second value of the  version data a second time;  
 (e) if the first  value of the version data read in step ( a ) does not match the second  value of the version data read the second time, repeating steps (a), (b), (c), (d) and (e).  
 
     
     
       30. A computerized method for performing one or more atomic operations on a data entity of arbitrary size and characterized by version data, the method comprising the following steps:
 in a first thread of execution: 
 acquiring exclusion access to the version data;  
 setting the version data to a first value indicating that the data entity is invalid and not accessible by other operations;  
 modifying the data entity;  
 updating the version data to a second value indicating that the data entity is valid and accessible; and  
 terminating exclusive access to the version data;  
 
 
       in a second thread of execution, the second thread executing concurrently with the first thread of execution:
 (a) reading the first value of  the version data a first time;  
 (b) upon completion of step (a), reading the data entity;  
 (c) upon completion of step (b), reading the second value of  the version data a second time;  
 (d) if the first  value of the version data read the first time is different from the second  value of the version data read the second time, or if the first  value of the version data read the first time indicates that the data entry is invalid, repeating steps (a), (b), (c) and (d).  
 
     
     
       31. The method of  claim 30 , wherein the second  first thread of execution is executed by one or more write units. 
     
     
       32. The method of  claim 31 , wherein at least one of the write units is a web server. 
     
     
       33. The method of  claim 30 , wherein the data entity is stored in a memory that is accessible by both the first and second threads of execution. 
     
     
       34. The method of  claim 30 , wherein the updating step comprises incrementing the version data. 
     
     
       35. The method of  claim 30 , wherein the version data comprises a timestamp, and the updating step comprises updating the timestamp. 
     
     
       36. The method of  claim 30 , wherein the data entity comprises a timestamp. 
     
     
       37. The method of  claim 30 , wherein the data entity comprises a date. 
     
     
       38. The method of  claim 37 , wherein the data entity further comprises a timestamp. 
     
     
       39. The method of  claim 30 , wherein the setting step comprises setting the version data to a value that has been predetermined to represent an invalid version. 
     
     
       40. The method of  claim 30 , further comprising choosing a predetermined value to represent an invalid version. 
     
     
       41. The method of  claim 30 , wherein the step of reading the first value of the  version data the first time is performed during the modifying step. 
     
     
       42. The method of  claim 30 , wherein the step of reading the first value of the  version data the first time is performed prior to the updating step. 
     
     
       43. A computer-readable medium having computer-executable instructions to cause a computer to perform a method for performing one or more atomic operations on a data entity of arbitrary size and characterized by version data, the method comprising the following steps:
 in a first thread of execution: 
 acquiring exclusive access to the version data;  
 setting the version data to a first value indicating that the data entity is invalid and not accessible by other operations;  
 modifying the data entity;  
 updating the version data to a second value indicating that the data entity is valid and accessible; and  
 terminating exclusive access to the version data;  
 
 
       in a second thread of execution, the second thread executing concurrently with the first thread of execution:
 (a) reading the first value of the  version data a first time;  
 (b) upon completion of step (a), reading the data entity;  
 (c) upon completion of step (b), reading the second value of the  version data a second time;  
 (d) if the first  value of the version data read the first time is different from the second  value of the version data read the second time, or if the first  value of the version data read the first time indicates that the data entry is invalid, repeating steps (a), (b), (c) and (d).