Managing associations between keys and values

• US 8,627,111 B2
• Filed: 10/01/2008
• Issued: 01/07/2014
• Est. Priority Date: 04/23/2008
• Status: Active Grant

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Kirshenbaum, Evan R
• Primary Examiner(s): Zele, Krista
• Assistant Examiner(s): Benoit, Esther
• Application Number:
  US12/243,903
• Publication Number:
  US 20100083004A1
• Time in Patent Office: 1,924 Days
• Field of Search: 713/193
• US Class Current: 713/193
• CPC Class Codes: G06F 21/6218 to a system of files or objects, e.g. local or distributed file system or database
• CPC Class Codes: G06F 2221/2145 Inheriting rights or properties, e.g., propagation of permissions or restrictions within a hierarchy
• CPC Class Codes: H04L 2209/60 Digital content management, e.g. content distribution
• CPC Class Codes: H04L 9/083 involving central third party, e.g. key distribution center [KDC] or trusted third party [TTP]

Abstract

Provided are, among other things, systems, methods and techniques for managing associations between keys and values within a computer processing system. In one exemplary implementation, requests to store associations between keys and data values corresponding to the keys are input, and the associations are stored in entry nodes within a data structure represented as a hash-based directed acyclic graph (HDAG). Upon receipt of a data value request and accompanying request key, together with satisfaction of any additional access criterion, a return data value corresponding to the request key automatically is provided, the return data value having been generated based on at least one of the associations that involve the request key.

Claims

1. A method of managing associations between keys and values within a computer processing system, comprising:

inputting requests to store associations between keys and data values corresponding to the keys;

storing the associations in entry nodes within a data structure represented as a hash-based directed acyclic graph (HDAG); and

upon receipt of a data value request that includes a specified function of a request key, together with satisfaction of any additional access criterion, automatically providing a return data value corresponding to the request key,

wherein the return data value has been generated based on at least one of the associations that involve the request key,

wherein the data values are managed in value list nodes and references to the value list nodes are generated using a hashing algorithm that is different than one or more hashing algorithms used to generate the HDAG.

2. A method according to claim 1, wherein the value list nodes correspond to individual ones of the keys, and the data values corresponding to a given key are managed in a single value list node.

3. A method according to claim 2, further comprising a step of:

storing references between (1) the entry nodes storing associations involving a particular key and (2) the value list node corresponding to said particular key.

4. A method according to claim 3, further comprising a step of:

determining whether an entry node storing an association involving the particular key has been deleted and, if so, at least one of (1) deleting a corresponding association in the value list node corresponding to said particular key and (2) restoring an association previously overridden by the association involving the particular key in the deleted entry node.

5. A method according to claim 3, wherein the references between the entry nodes and the value list nodes are stored within the entry nodes, and wherein said method further comprises a step, executed upon receipt of a request to retrieve a chunk corresponding to a reference to a specified entry node, of excluding the references between the specified entry node and the value list nodes in a returned result.

6. A method according to claim 2, wherein the data value request comprises a request to retrieve a reference to the value list node corresponding to the request key.

7. A method according to claim 1, wherein at least one hashing algorithm used is identified by a digest abstraction having a first field indicating a type of hash and a separate second field indicating a length of bytes comprising resulting hash code.

8. A method according to claim 1, wherein a plurality of the associations include override information, and the return data value provided in response to the data value request excludes overridden data values.

9. A method according to claim 1, wherein a specified request to store a set of at least one association comprises a request to store a chunk containing contents of a corresponding entry node.

10. A method according to claim 1, wherein at least one of the associations comprises a reference to a HDAG node, and wherein the HDAG node is protected from deletion at least until the entry node storing said at least one of the associations is deleted.

11. A method according to claim 1, wherein at least one of the entry nodes is associated with a retention group which is associated with an expiration criterion, and wherein said at least one of the entry nodes is protected from deletion at least until the expiration criterion is satisfied.

12. A method of managing associations between keys and values within a computer processing system, comprising:

inputting requests to store associations between keys and data values corresponding to the keys;

storing the associations in entry nodes of a hash-based directed acyclic graphic (HDAG); and

upon receipt of a data value request that includes a specified function of a request key, together with satisfaction of any additional access criterion, automatically providing a return data value corresponding to the request key,

wherein the return data value is generated based on a plurality of the associations involving the request key that were previously stored,

wherein the data values are managed in value list nodes and references to the value list nodes are generated using a hashing algorithm that is different than one or more hashing algorithms used to generate the HDAG.

13. A method according to claim 12, wherein the requests to store associations are made by different entities and the associations used to generate the return data value resulted from requests made by a plurality of said different entities.

14. A method according to claim 12, wherein a plurality of the associations include override information, and the return data value provided in response to the data value request excludes overridden data values.

15. A method according to claim 14, wherein the override information for a first association includes an override lock for which a matching key must be provided in order to override said first association, and the override information for a second association includes an override key that provides the matching key, whereby the second association overrides the first association, resulting in an overridden data value.

16. A method according to claim 12, wherein the request key is associated, through a plurality of previously stored associations, with a plurality of data values having different access criteria, and wherein any data values for which the corresponding access criteria have not been satisfied are excluded from the return data value.

17. A method according to claim 16, wherein at least one of the access criteria comprises a required demonstration of at least one of an identity, a role and a capability of an entity submitting the data value request.

18. A method according to claim 16, wherein the return data value includes a plurality of component values, and wherein an order in which the component values are returned is different in response to different submissions of the data value request.

19. A non-transitory computer readable medium storing computer-executable process steps for managing associations between keys and values within a computer processing system, said process steps comprising:

inputting requests to store associations between keys and data values corresponding to the keys;

storing the associations in entry nodes within a data structure represented as a hash-based directed acyclic graph (HDAG); and

upon receipt of a data value request that includes a specified function of a request key, together with satisfaction of any additional access criterion, automatically providing a return data value corresponding to the request key,

wherein the return data value has been generated based on at least one of the associations that involve the request key,

wherein the data values are managed in value list nodes and references to the value list nodes are generated using a hashing algorithm that is different than one or more hashing algorithms used to generate the HDAG.