System and method for storage and retrieval of arbitrary content and application data

• US 7,469,300 B2
• Filed: 01/16/2003
• Issued: 12/23/2008
• Est. Priority Date: 01/18/2002
• Status: Active Grant

• Current Assignee: TiVo Corporation (Adeia Inc.)
• Original Assignee: MobiTV Incorporated (Adeia Inc.)
• Inventors: Stiers, Todd A., de Bonet, Jeremy S., Alvelda, VII, Annison, Jeffrey R., Scanlan, Paul M.
• Primary Examiner(s): Cardone; Jason
• Assistant Examiner(s): Mirza; Adnan M
• Application Number:
  US10/345,593
• Publication Number:
  US 20030177197A1
• Time in Patent Office: 2,168 Days
• Field of Search: 709/245, 709/213, 705/15
• US Class Current: 709/245
• CPC Class Codes: G06Q 50/12 Hotels or restaurants

Abstract

Systems and methods for improving the performance of a data storage and retrieval system by enabling dynamic switching from one internal data structure to another in response to detecting conditions indicating that a switch would improve performance. In one embodiment, a network proxy implements a cache using a first internal data structure. The caches objects comprise Web pages, and the cache keys comprise URLs corresponding to the Web pages. The proxy monitors cache usage and periodically determines costs associated with usage of the first data structure and an alternative data structure. If the costs associated with the alternative data structure are less than the costs associated with the first data structure, the proxy crates the alternative data structure, migrates data from the first data structure to the alternative data structure, begins using the alternative data structure for the cache, and deletes the first data structure.

Claims

1. A system comprising:

a data processor; and

a memory coupled to the data processor;

wherein the data processor is configured to;

implement a cache system that stores a plurality of data objects and corresponding keys within a first internal data structure in the memory,

store data in the first internal data structure,

monitor usage of the cache system,

associate costs with one or more operations on the first internal data structure,

determine a first cost of operation associated with the first internal data structure based on the costs associated with the one or more or operations, and

if the first cost of operation is greater than a second cost of operation associated with a second data structure which is distinct from the first internal data structure,

create the second data structure,

migrate the data stored in the first internal data structure to the second data structure, and

switch operations from the first internal data structure to the second data structure.

2. The system of claim 1, wherein the data processor and memory reside within a network proxy.

3. The system of claim 2, wherein the data objects comprise Web pages and the corresponding keys comprise uniform resource locators (URLs).

4. The system of claim 1, wherein the system is configured to store network connection and DNS information by storing data objects comprising IP addresses and keys comprising server names corresponding to the IP addresses.

5. The system of claim 1, wherein the system is configured to store configuration parameters by storing selected configuration data as objects and parameter names as keys corresponding to the objects.

6. The system of claim 1, wherein the system is configured to store shared resources as objects and resource identifiers as keys corresponding to the objects.

7. The system of claim 1, wherein the system is configured to store open network connections as objects and systems, ports and communication protocols corresponding to the open network connections as keys corresponding to the objects.

8. The system of claim 1, wherein the internal data structures in the cache system comprise at least two types selected from the group consisting of:

lists;

hashes, trees, heaps and hybrid data structures.

9. The system of claim 1, wherein the cache system is multi-tiered, and at least one tier of caches is configured to store references to caches as data objects.

10. The system of claim 1, wherein the data processor is configured to create one or more caches in the cache system using a C++ template.

11. The system of claim 1, wherein the data processor is configured to determine second cost of operation associated with the second data structure and compare the first and second costs.

12. The system of claim 11, wherein determining the second cost of operation associated with the second data structure includes determining a cost for transitioning to the second data structure.

13. The system of claim 12, wherein determining a cost for transitioning to the second data structure comprises

determining a cost for creating the second data structure,

determining a cost for migrating data from the first internal data structure to the second data structure, and

determining a cost for switching operations from the first internal data structure to the second data structure.

14. A method comprising:

providing a first internal data structure for storing a plurality of objects;

storing objects in the first internal data structure;

using the first internal data structure;

monitoring usage of the first internal data structure;

associating costs with one or more operations on the first internal data structure;

determining a first cost of operation associated with the first internal data structure based on the costs associated with the one or more operations;

determining a second cost of operation associated with a second internal data structure which is distinct from the first internal data structure;

comparing the first cost of operation to the second cost of operation; and

if the first cost of operation is greater than the second cost of operation,

creating the second internal data structure; and

migrating the objects stored in the first internal data structure to the second internal data structure.

15. The method of claim 14, wherein determining the second cost of operation associated with the second internal data structure comprises determining a cost associated with creating the second internal data structure and migrating the objects to the second internal data structure.

16. The method of claim 15, wherein determining the second cost of operation associated with the second internal data structure further comprises determining a cost associated with storing objects in the second internal data structure and retrieving objects from the second internal data structure.

17. The method of claim 14, further comprising periodically repeating the steps of determining the first cost of operation associated with the first internal data structure, determining the second cost of operation associated with the second internal data structure and comparing the first cost of operation to the second cost of operation.

18. The method of claim 14, wherein determining the cost of operation associated with at least one of the first internal data structure and the second internal data structure comprises computing a cost based on estimated usage.

19. The method of claim 14, wherein determining the cost of operation associated with at least one of the first internal data structure and the second internal data structure comprises computing a cost based on empirical usage data.

20. The method of claim 14, further comprising, if the first cost of operation is greater than the second cost of operation, deleting the first internal data structure after migrating the plurality of objects to the second internal data structure.

21. The method of claim 14, wherein providing the first internal data structure for storing a plurality of objects comprises providing a cache system having the first internal data structure in a network proxy.

22. The method of claim 21, wherein using the first internal data structure comprises storing and retrieving entries in the first internal data structure, wherein each entry includes an object comprising a Web page and a corresponding key comprising a uniform resource locators (URL) corresponding to the Web page.

23. The method of claim 21, wherein using the first internal data structure comprises storing and retrieving entries in the first internal data structure, wherein each entry includes an object comprising an IP address and a corresponding key comprising a server name corresponding to the IP address.

24. The method of claim 21, wherein using the first internal data structure comprises storing and retrieving entries in the first internal data structure, wherein each entry includes an object comprising selected configuration data and a key comprising a parameter name.

25. The method of claim 21, wherein using the first internal data structure comprises storing and retrieving entries in the first internal data structure, wherein each entry includes an object comprising a shared resource and a key comprising a resource identifier.

26. The method of claim 21, wherein using the first internal data structure comprises storing and retrieving entries in the first internal data structure, wherein each entry includes an object comprising an open network connection and at least one key comprising one or more of:

a system and a port to which the connection has been made and a communication protocol used for the connection.

27. The method of claim 14, wherein the first and second internal data structures comprise at least two types selected from the group consisting of:

lists;

hashes, trees, heaps and hybrid data structures.

28. The method of claim 14, wherein the first internal data structure comprises a cache within a multi-tiered cache system, and wherein at least one tier of caches in the multi-tiered cache system is configured to store references to caches as data objects.

29. The method of claim 14, wherein providing each internal data structure comprises creating a corresponding cache using a C++ template.

30. A computer readable storage medium embodying a plurality of instructions readable by a data processor, wherein the instructions are configured to cause the data processor to perform the method comprising:

providing a first internal data structure for storing a plurality of objects;

storing objects in the first internal data structure;

using the first internal data structure;

monitoring usage of the first internal data structure;

associating costs with one or more operations on the first internal data structure;

determining a first cost of operation associated with the first internal data structure based on the costs associated with the one or more operations;

determining a second cost of operation associated with a second internal data structure which is distinct from the first internal data structure;

comparing the first cost of operation to the second cost of operation; and

if the first cost of operation is greater than the second cost of operation,

creating the second internal data structure and

migrating the objects stored in the first internal data structure to the second internal data structure.

31. The software product of claim 30, wherein determining the second cost of operation associated with the second internal data structure comprises determining a cost associated with creating the second internal data structure and migrating the objects to the second internal data structure.

32. The software product of claim 31, wherein determining the second cost of operation associated with the second internal data structure further comprises determining a cost associated with storing objects in the second internal data structure and retrieving objects from the second internal data structure.

33. The software product of claim 30, wherein the method further comprises periodically repeating the steps of determining the first cost of operation associated with the first internal data structure, determining the second cost of operation associated with the second internal data structure and comparing the first cost of operation to the second cost of operation.

34. The software product of claim 30, wherein determining the cost of operation associated with at least one of the first internal data structure and the second internal data structure comprises computing a cost based on estimated usage.

35. The software product of claim 30, wherein determining the cost of operation associated with at least one of the first internal data structure and the second internal data structure comprises computing a cost based on empirical usage data.

36. The software product of claim 30, wherein the method further comprises, if the first cost of operation is greater than the second cost of operation, deleting the first internal data structure after migrating the plurality of objects to the second internal data structure.

37. The software product of claim 30, wherein providing the first internal data structure for storing a plurality of objects comprises providing a cache system having the first internal data structure in a network proxy.

38. The software product of claim 37, wherein using the first internal data structure comprises storing and retrieving entries in the first internal data structure, wherein each entry includes an object comprising a Web page and a corresponding key comprising a uniform resource locators (URL) corresponding to the Web page.

39. The software product of claim 37, wherein using the first internal data structure comprises storing and retrieving entries in the first internal data structure, wherein each entry includes an object comprising an IP address and a corresponding key comprising a server name corresponding to the IP address.

40. The software product of claim 30, wherein the internal data structures are configured to store configuration parameters by storing selected configuration data as objects and parameter names as keys corresponding to the objects.

41. The software product of claim 30, wherein the internal data structures are configured to store shared resources as objects and resource identifiers as keys corresponding to the objects.

42. The software product of claim 30, wherein the internal data structures are configured to store open network connections as objects and systems, ports and communication protocols corresponding to the open network connections as keys corresponding to the objects.

43. The software product of claim 30, wherein the first and second internal data structures comprise at least two types selected from the group consisting of:

lists;

hashes, trees, heaps and hybrid data structures.

44. The software product of claim 30, wherein the first internal data structure comprises a cache within a multi-tiered cache system, and wherein at least one tier of caches in the multi-tiered cache system is configured to store references to caches as data objects.

45. The software product of claim 30, wherein providing each internal data structure comprises creating a corresponding cache using a C++ template.