Methods and apparatus for clustering and prefetching data objects

• US 6,954,752 B2
• Filed: 07/19/2001
• Issued: 10/11/2005
• Est. Priority Date: 07/19/2001
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Iyengar, Arun Kwangil
• Primary Examiner(s): Alam, Shahid Al
• Application Number:
  US09/909,287
• Publication Number:
  US 20030018639A1
• Time in Patent Office: 1,545 Days
• Field of Search: 707/3, 707/8, 707/10, 707/100, 707/202, 707/200, 714/31, 709/202, 709/224
• US Class Current: 1/1
• CPC Class Codes: G06F 16/9574 of access to content, e.g. by caching
• CPC Class Codes: H04L 67/5681 Pre-fetching or pre-delivering data based on network characteristics
• CPC Class Codes: H04L 67/5682 Policies or rules for updating, deleting or replacing the stored data
• CPC Class Codes: Y10S 707/99938 Concurrency, e.g. lock management in shared database
• CPC Class Codes: Y10S 707/99953 Recoverability

Abstract

Techniques for managing data objects in conjunction with a computer system are provided. In a technique for clustering data objects on a disk storage device, the invention comprises maintaining a log of at least a portion of accesses (e.g., read and for write operations) to the data objects; determining from the maintained log a cluster comprised of data objects accessed at substantially similar times; and storing the data objects comprising the cluster in close proximity to one another on the disk storage device. In a technique for prefetching data objects on a disk storage device, the invention comprises receiving a request for a data object in a cluster, determining from the log a probability that at least one other data object in the cluster may be subsequently requested; and, in response to the probability being not less than a predetermined value, retrieving both the requested data object and the at least one other data object. Such clustering and prefetching techniques substantially reduce the number of storage device seeks.

Claims

1. A method of managing data objects in a computer system, the method comprising the steps of:

maintaining a log of at least a portion of accesses to the data objects;

determining from the maintained log at least one cluster comprised of data objects accessed at substantially similar times;

storing the data objects comprising the at least one cluster in close proximity to one another in a memory;

receiving a request for a data object in a cluster;

determining from the log a probability that at least one other data object in the cluster may be subsequently requested; and

in response to the probability being not less than a predetermined value, retrieving both the requested data object and the at least one other data object.

2. The method of claim 1, wherein an access comprises a request to one of read and write a data object.

3. The method of claim 1, wherein the data objects comprise Web data and the log comprises at least one Web log.

4. The method of claim 1, wherein the cluster determining step further comprises the steps of:

determining a number of time periods, c(a), a cluster is accessed;

determining a number of time periods, c(o), an object is accessed along with the cluster; and

using c(a) and c(o) to determine whether to add the object to the cluster.

5. The method of claim 4, wherein the using step further comprises the step of computing a quotient, c(o)/c(a), and adding the object to the cluster when c(o)/c(a) is not less than a predetermined value.

6. The method of claim 1, wherein the cluster determining step further comprises the steps of:

determining a number of time periods, c(o), an object is accessed along with the cluster; and

adding the object to the cluster when c(o) is not less than a predetermined value.

7. The method of claim 1, wherein the step of determining from the log a probability further comprises the steps of:

determining a number of time periods, c(o), the object is accessed along with the cluster;

determining a number of time periods, t(o), the object is accessed; and

determining the probability using c(o) and t(o).

8. The method of claim 7, wherein the probability determining step further comprises computing a quotient, c(o)/t(o).

9. The method of claim 1, wherein the memory comprises a disk storage device.

10. Apparatus for managing data objects in a computer system, the apparatus comprising:

at least one processor operative to;

(i) maintain a log of at least a portion of accesses to the data objects;

(ii) determine from the maintained log at least one cluster comprised of data objects accessed at substantially similar times;

(iii) store the data objects comprising the at least one cluster in close proximity to one another in a data storage device;

(iv) receive a request for a data object in a cluster;

(v) determine from the log a probability that at least one other data object in the cluster may be subsequently requested; and

(vi) in response to the probability being not less than a predetermined value, retrieve both the requested data object and the at least one other data object; and

memory, operatively coupled to the at least one processor, for storing at least one of the log and a cluster membership identifying the at least one cluster.

11. The apparatus of claim 10, wherein an access comprises a request to one of read and write a data object.

12. The apparatus of claim 10, wherein the data objects comprise Web data and the log comprises at least one Web log.

13. The apparatus of claim 10, wherein the cluster determining operation further comprises:

(i) determining a number of time periods, c(a), a cluster is accessed;

(ii) determining a number of time periods, c(o), an object is accessed along with the cluster; and

(iii) using c(a) and c(o) to determine whether to add the object to the cluster.

14. The apparatus of claim 13, wherein the using operation further comprises computing a quotient, c(o)/c(a), and adding the object to the cluster when c(o)/c(a) is not less than a predetermined value.

15. The apparatus of claim 10, wherein the cluster determining operation further comprises:

(i) determining a number of time periods, c(o), an object is accessed along with the cluster; and

(ii) adding the object to the cluster when c(o) is not less than a predetermined value.

16. The apparatus of claim 10, wherein the operation of determining from the log a probability further comprises:

(i) determining a number of time periods, c(o), the object is accessed along with the cluster, (ii) determining a number of time periods, t(o), the object is accessed; and

(iii) determining the probability using c(o) and t(o).

17. The apparatus of claim 16, wherein the probability determining operation further comprises computing a quotient, c(o)/t(o).

18. The apparatus of claim 10, wherein the data storage device comprises a disk storage device.

19. In a system comprising at least one server and at least one disk storage device operatively coupled to the at least one server, apparatus for managing data objects in accordance with the at least one server and the at least one disk storage device, the apparatus comprising:

memory for storing at least one log, the log comprising information relating to at least a portion of accesses to the data objects; and

a module, operatively coupled to the log memory, and operative to;

(i) cause the storing of the data objects in at least one cluster on the at least one disk storage device via the at least one server based on the at least one log;

(ii) learn of a request for a data object in a cluster;

(iii) determine from the log a probability that at least one other data object in the cluster may be subsequently requested; and

(iv) in response to the probability being not less than a predetermined value, cause the retrieval of both the requested data object and the at least one other data object from the at least one disk storage device.

20. The apparatus of claim 19, wherein the at least one server is one of a Web server and a proxy server.

21. An article of manufacture for managing data objects in a computer system, comprising a machine readable medium containing one or more programs which when executed implement the steps of:

maintaining a log of at least a portion of accesses to the data objects;

determining from the maintained log at least one cluster comprised of data objects accessed at substantially similar times;

storing the data objects comprising the at least one cluster in close proximity to one another in a memory;

receiving a request for a data object in a cluster;

determining from the log a probability that at least one other data object in the cluster may be subsequently requested; and

in response to the probability being not less than a predetermined value, retrieving both the requested data object and the at least one other data object.