Version-controlled cached data store

• US 7,716,182 B2
• Filed: 05/25/2005
• Issued: 05/11/2010
• Est. Priority Date: 05/25/2005
• Status: Active Grant

• Current Assignee: Dassault Systemes Enovia Corporation (Dassault Systemes SA)
• Original Assignee: Dassault Systemes Enovia Corporation (Dassault Systemes SA)
• Inventors: Tewksbary, David E.
• Primary Examiner(s): Cottingham; John R
• Assistant Examiner(s): Uddin; Mohammed R
• Application Number:
  US11/137,460
• Publication Number:
  US 20060271606A1
• Time in Patent Office: 1,812 Days
• Field of Search: 707/200, 707/201, 707/202, 707/203, 707/204, 707/205
• US Class Current: 707/638
• CPC Class Codes: G06F 16/172 Caching, prefetching or hoarding of files
• CPC Class Codes: G06F 16/1774 Locking methods, e.g. locking methods for file systems allowing shared and concurrent access to files

Abstract

Described are methods, systems, and apparatus, including computer program products for a version-controlled cached data store. A first node is associated with a first identifier and a first version. A control file is received, where the control file includes information associating a second node with a second identifier and a second version. The first version is compared with the second version when the first identifier and the second identifier are identical.

Claims

1. A method for a version-controlled database representation comprising:

receiving a first node from a file system associated with a data store module, the first node comprising a first identifier, a first version, and a first set of one or more data elements for indexing or searching data stored on the data store module;

storing the first node in a memory device;

receiving a first control file from the file system, the first control file comprising information associating a plurality of identifiers with a plurality of versions, including associating a second identifier with a second version; and

removing the first node from the memory device if the first identifier is identical to the second identifier and if the first version is different from the second version

determining whether a second node is stored in the memory device;

if it is determined that the second node is not stored in the memory device, then determining whether a path associated with the second node in the file system is valid;

if it is determined that the path is valid, then

(1) receiving the second node from the file system, the second node comprising the second identifier, the second version, and a second set of one or more data elements for indexing or searching data stored on the data store module;

(2) storing the second node in the memory device; and

if it is determined that the path is not valid, then receiving a second control file from the file system, the second control file comprising information associating the second identifier with a third version.

2. The method of claim 1 further comprising:

determining whether a third node is stored in the memory device, the third node comprising a third set of one or more data elements for indexing or searching data stored on the data store module;

if it is determined that the third node is stored in the memory device, then modifying the third set of one or more data elements and modifying a third version of the third node;

if it is determined that the third node is not stored in the memory device, then inserting the third node into the memory device and associating the third node with the third version;

updating the first control file to associate a third identifier of the third node with the third version; and

writing, to the file system, the updated first control file and the third node.

3. The method of claim 2 further comprising rebalancing a tree if the third node is inserted into the memory device.

4. The method of claim 2 wherein writing the updated first control file to the file system comprises replacing a file system control file.

5. The method of claim 2 further comprising creating, by a first processing module, a lock file on the file system, the lock file preventing one or more processing modules other than the first processing module from changing, modifying, or writing to the file system.

6. The method of claim 5 further comprising deleting the lock file after the updated first control file and the third node have been written to the file system.

7. The method of claim 5 further comprising:

creating a list of changed nodes file comprising a list representing at least the third node; and

storing the list of changed nodes on the memory device.

8. The method of claim 1 wherein receiving the first node and the first control file from the file system is without regard to a lock on the file system.

9. The method of claim 1 wherein the memory device is a cache.

10. The method of claim 1 wherein the memory device is remote from the file system and communicates with the file system using a communications network.

11. The method of claim 1 wherein each of the plurality of identifiers comprise a filename or a property.

12. The method of claim 1 wherein the first or second sets of one or more data elements are data elements in a B−

tree, a B+tree, a binary tree, a pi-tree, a hash table, a hash map, or any combination thereof.

13. The method of claim 12 wherein the first or second nodes are nodes in a B−

tree, a B+tree, or a binary tree.

14. The method of claim 1 wherein the data stored on the data store module comprises business objects.

15. The method of claim 1 wherein the information in the first control file comprises a table.

16. The method of claim 1 further comprising receiving an updated first node from the file system if the first identifier is identical to the second identifier and if the first version is different from the second version, the updated first node comprising the first identifier, an updated first version, and an updated first set of one or more data elements for indexing or searching data stored on the data store module.

17. The method of claim 1 wherein determining whether the second node is stored in the memory device comprises traversing a tree.

18. The method of claim 1 wherein determining whether the path associated with the second node is valid comprises examining the file system location that corresponds to the second identifier.

19. A system for a version-controlled database representation comprising:

a memory device comprising a first node and a first control file, the first node comprising a first identifier, a first version, and a first set of one or more data elements for indexing or searching data stored on a data store module, the first control file comprising information associating a plurality of identifiers with a plurality of versions, including associating a second identifier with a second version; and

a processing module configured to

remove the first node from the memory device if the first identifier is identical to the second identifier and if the first version is different from the second version;

determine whether a second node is stored in the memory device;

if it is determined that the second node is not stored in the memory device, then determine whether a path associated with the second node in a file system associated with the data store module is valid;

if it is determined that the path is valid, then

(1) receive the second node from the file system, the second node comprising the second identifier, the second version, and a second set of one or more data elements for indexing or searching data stored on the data store module;

(2) store the second node in the memory device; and

if it is determined that the path is not valid, then receive a second control file from the file system, the second control file comprising information associating the second identifier with a third version.

20. The system of claim 19 wherein the processing module is further configured to:

determine whether a third node is stored in the memory device, the third node comprising a third set of one or more data elements for indexing or searching data stored on the data store module;

if it is determined that the third node is stored in the memory device, then modify the third set of one or more data elements and modifying a third version of the third node;

if it is determined that the third node is not stored in the memory device, then insert the third node into the memory device and associating the third node with the third version;

update the first control file to associate a third identifier of the third node with the third version; and

write, to the file system, the updated first control file and the third node.

21. A computer program product, tangibly embodied in a machine-readable storage device, for use in a version-controlled database representation, the computer program product including instructions being operable to cause a data processing apparatus to:

read, from a memory device, a first node, the first node comprising a first identifier, a first version, and a first set of one or more data elements for indexing or searching data stored on a data store module;

read, from the memory device, a first control file, the first control file comprising information associating a plurality of identifiers with a plurality of versions, including associating a second identifier with a second version; and

remove the first node from the memory device if the first identifier is identical to the second identifier and if the first version is different from the second version

determine whether a second node is stored in the memory device;

if it is determined that the second node is not stored in the memory device, then determine whether a path associated with the second node in a file system associated with the data store module is valid;

if it is determined that the path is valid, then

(1) receive the second node from the file system, the second node comprising the second identifier, the second version, and a second set of one or more data elements, the second set of one or more data elements for indexing or searching data stored on the data store module;

(2) store the second node in the memory device; and

if it is determined that the path is not valid, then receive a second control file from the file system, the second control file comprising information associating the second identifier with a third version.

22. The computer program product of claim 21 further including instructions being operable to cause a data processing apparatus to:

determine whether a third node is stored in the memory device, the third node comprising a third set of one or more data elements for indexing or searching data stored on the data store module;

if it is determined that the third node is stored in the memory device, then modify the third set of one or more data elements and modifying a third version of the third node;

if it is determined that the third node is not stored in the memory device, then insert the third node into the memory device and associating the third node with the third version;

update the first control file to associate a third identifier of the third node with the third version; and

write, to the file system, the updated first control file and the third node.

23. A system for a version-controlled database representation comprising:

means for receiving a first node from a file system associated with a data store module, the first node comprising a first identifier, a first version, and a first set of one or more data elements for indexing or searching data stored on the data store module;

means for storing the first node in a memory device;

means for receiving a first control file from the file system, the first control file comprising information associating a plurality of identifiers with a plurality of versions, including associating a second identifier with a second version;

means for removing the first node from the memory device if the first identifier is identical to the second identifier and if the first version is different from the second version; and

means for causing a data processing apparatus to;

determine whether a second node is stored in the memory device;

if it is determined that the second node is not stored in the memory device, then determine whether a path associated with the second node in the file system is valid;

if it is determined that the path is valid, then

(1) receive the second node from the file system, the second node comprising the second identifier, the second version, and a second set of one or more data elements for indexing or searching data stored on the data store module;

(2) store the second node in the memory device; and

if it is determined that the path is not valid, then receive a second control file from the file system, the second control file comprising information associating the second identifier with a third version.

24. The system for a version-controlled database representation of claim 23 further comprising:

means for determining whether a third node is stored in the memory device, the third node comprising a third set of one or more data elements for indexing or searching data stored on the data store module;

means for, if it is determined that the third node is stored in the memory device, modifying the third set of one or more data elements and modifying a third version of the third node;

means for, if it is determined that the third node is not stored in the memory device, inserting the third node into the memory device and associating the third node with the third version;

means for updating the first control file to associate a third identifier of the third node with the third version; and

means for writing, to the file system, the updated first control file and the third node.