Metadata format for hierarchical data storage on a raw storage device

• US 7,136,867 B1
• Filed: 12/02/2002
• Issued: 11/14/2006
• Est. Priority Date: 04/08/2002
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Srivastava, Alok K., Chatterjee, Surojit
• Primary Examiner(s): MIZRAHI, DIANE D
• Application Number:
  US10/308,809
• Time in Patent Office: 1,443 Days
• Field of Search: 707200-205, 707 1- 10, 707100-1041, 707/103.R, 707/102, 717/108, 715/760, 709/224, 380/30
• US Class Current: 713/171
• CPC Class Codes: G06F 16/9027 Trees
• CPC Class Codes: Y10S 707/956 Hierarchical
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

A system and techniques are described for formatting a persistent storage device to store hierarchical data. According to one aspect of the invention, data structures are established, at a base level of the persistent storage device, for storing a hierarchy of key-value pairs. A first structure, which corresponds to a root node of the hierarchy, is established. A second structure, which corresponds to a key-value pair, is established. The second structure stores the value of the key-value pair. Links, which lead from the first structure to the second structure through one or more intermediate structures, are established based on a position, within the hierarchy, of the key.

Claims

1. A computer-implemented method for formatting a persistent storage device to store hierarchical data, the method comprising:

establishing structures, at a base level of the persistent storage device, for storing a hierarchy of key-value pairs;

wherein the step of establishing structures includes;

establishing a first structure that corresponds to a root node of the hierarchy;

establishing a second structure that corresponds to a first key-value pair;

wherein said first key-value pair has a particular key and a particular value;

wherein said second structure stores said particular value; and

establishing links that lead from said first structure, through one or more intermediate structures, to said second structure based on a position, within said hierarchy, of said particular key.

2. The method of claim 1, wherein:

said second structure includes at least a part of a key of a second key-value pair that is subordinately related, within said hierarchy, to said first key-value pair.

3. A computer-implemented method for storing hierarchical data on a persistent storage device, the method comprising:

storing, in a data structure that corresponds to a particular key in a hierarchy of keys, both (a) data that is associated with the key and (b) metadata that is associated with the data;

receiving a request to perform an operation relative to the particular key; and

in response to the request, performing steps comprising;

determining, based on security attributes that are contained in said metadata, whether a user has sufficient privileges to perform the operation relative to the particular key;

if the user has sufficient privileges to perform the operation relative to the particular key, then performing the operation relative to the particular key; and

if the user does not have sufficient privileges to perform the operation relative to the particular key, then preventing performance of the operation relative to the particular key;

wherein the data structure is stored on the persistent storage device.

4. The method of claim 3, further comprising:

prior to storing said data and said metadata on said persistent storage device, updating said data and said metadata in volatile memory.

5. The method of claim 3, wherein said storing of said data is performed in a same block access to said persistent storage device as said storing of said metadata.

6. The method of claim 3, wherein:

said request is a request to create a child key of said particular key;

the step of determining whether the user has sufficient privileges comprises

determining, based on security attributes that are contained in said metadata, whether the user has sufficient privileges to create said child key of said particular key; and

the step of performing the operation comprises;

creating a new data structure, which corresponds to said child key, on said persistent storage device; and

creating a key component entry for said child key in said data structure that corresponds to said particular key.

7. The method of claim 3, wherein:

said request is a request to delete said particular key;

the step of determining whether the user has sufficient privileges comprises

determining, based on security attributes that are contained in said metadata, whether the user has sufficient privileges to delete said particular key; and

the step of performing the operation comprises deleting a key component entry, which corresponds to said particular key, from a data structure that corresponds to a parent key of said particular key.

8. The method of claim 3, wherein:

said request is a request to read a value of said particular key;

the step of determining whether the user has sufficient privileges comprises

determining, based on security attributes that are contained in said metadata, whether the user has sufficient privileges to access said particular key; and

the step of performing the operation comprises providing said data to said user.

9. The method of claim 3, wherein:

said request is a request to set a value of said particular key;

the step of determining whether the user has sufficient privileges comprises

determining, based on security attributes that are contained in said metadata, whether the user has sufficient privileges to access said particular key; and

the step of performing the operation comprises updating said data.

10. The method of claim 3, wherein:

said request is a request to create a link from a source key to said particular key;

the step of determining whether the user has sufficient privileges comprises

determining, based on security attributes that are contained in said metadata, whether the user has sufficient privileges to create said link; and

the step of performing the operation comprises creating, in a data structure that corresponds to a parent key of said source key, a key component entry for said particular key.

11. The method of claim 3, further comprising storing, in said metadata, privileges for one or more users to perform selected operations in a set of specified operations, privileges for one or more groups of users to perform selected operations in said set of operations, and privileges for entities other than said users and groups to perform selected operations in said set of operations.

12. The method of claim 3, further comprising:

determining whether a data log is valid; and

if said data log is valid, then;

overwriting one or more data structures, which represent keys that were involved in a failed operation, with copies of said data structures that are stored in said data log; and

causing said data log to be invalid.

13. The method of claim 3, further comprising:

in response to said request, performing, in an atomic operation;

updating a superblock shadow to reflect a change; and

updating a boot block to refer to said superblock shadow instead of a superblock;

wherein, if a system failure occurs during said atomic operation, said boot block refers to said superblock instead of said superblock shadow.

19. A tangible computer-readable medium that carries instructions which, when executed by one or more processors, cause the one or more processors to perform the method of claim 3.

20. A tangible computer-readable medium that carries instructions which, when executed by one or more processors, cause the one or more processors to perform the method of claim 4.

21. A tangible computer-readable medium that carries instructions which, when executed by one or more processors, cause the one or more processors to perform the method of claim 5.

22. A tangible computer-readable medium that carries instructions which, when executed by one or more processors, cause the one or more processors to perform the method of claim 6.

23. A tangible computer-readable medium that carries instructions which, when executed by one or more processors, cause the one or more processors to perform the method of claim 7.

24. A tangible computer-readable medium that carries instructions which, when executed by one or more processors, cause the one or more processors to perform the method of claim 8.

25. A tangible computer-readable medium that carries instructions which, when executed by one or more processors, cause the one or more processors to perform the method of claim 9.

26. A tangible computer-readable medium that carries instructions which, when executed by one or more processors, cause the one or more processors to perform the method of claim 10.

27. A tangible computer-readable medium that carries instructions which, when executed by one or more processors, cause the one or more processors to perform the method of claim 11.

28. A tangible computer-readable medium that carries instructions which, when executed by one or more processors, cause the one or more processors to perform the method of claim 12.

29. A tangible computer-readable medium that carries instructions which, when executed by one or more processors, cause the one or more processors to perform the method of claim 13.

14. A computer-implemented method for storing hierarchical data on a persistent storage device, the method comprising:

receiving a request to store information relative to a particular key in a hierarchy of keys;

in response to the request, storing, in a first data structure that corresponds to the particular key, as much of the information as one or more specified fields of the data structure are capable of containing;

storing, in a second data structure, a part of said information that was not stored in said first data structure; and

storing, in said first data structure, location information for locating said second data structure

wherein said first data structure and said second data structure are stored on the persistent storage device.

15. The method of claim 14, wherein said information is a value of said key.

16. The method of claim 14, wherein said information is a plurality of key component entries for child keys of said key.

17. The method of claim 14, further comprising:

storing, in a third data structure, a part of said information that was not stored in said first data structure; and

storing, in said second data structure, location information for locating said third data structure.

30. A tangible computer-readable medium that carries instructions which, when executed by one or more processors, cause the one or more processors to perform the method of claim 14.

31. A tangible computer-readable medium that carries instructions which, when executed by one or more processors, cause the one or more processors to perform the method of claim 15.

32. A tangible computer-readable medium that carries instructions which, when executed by one or more processors, cause the one or more processors to perform the method of claim 16.

33. A tangible computer-readable medium that carries instructions which, when executed by one or more processors, cause the one or more processors to perform the method of claim 17.

18. A tangible computer-readable medium having stored thereon:

a data structure that corresponds to a first node in a key-value hierarchy, wherein said first node is associated with a particular key of a first key-value pair, wherein said first node includes;

a value of said first key-value pair; and

at least a part of a key of a second key-value pair that is associated with a child node of said first node in said key-value hierarchy.