Speculative caching of individual fields in a distributed object system

• US 6,618,737 B2
• Filed: 12/29/2000
• Issued: 09/09/2003
• Est. Priority Date: 03/09/2000
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: International Business Machines Corporation
• Inventors: Eilam, Tamar, Factor, Michael, Aridor, Yariv, Schuster, Assaf, Teperman, Avi
• Primary Examiner(s): Metjahic, Safet
• Assistant Examiner(s): Chen, Te Y
• Application Number:
  US09/751,694
• Publication Number:
  US 20020038301A1
• Time in Patent Office: 984 Days
• Field of Search: 707/200-205, 707/101-103, 711/122-128, 711/141, 711/144, 709/100-106, 709/108, 717/106, 717/116, 717/154, 712/31, 712/36
• US Class Current: 1/1
• CPC Class Codes: G06F 9/465 Distributed object oriented systems remote method invocation [RMI] G06F9/548
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation
• CPC Class Codes: Y10S 707/99956 File allocation

Abstract

This disclosure presents a technique of field-level caching in distributed object-oriented systems, in which a speculative approach is taken to identify opportunities for caching. The speculative approach is particularly suitable for exploitation of opportunities for caching. Invalidation protocols, which are fully compliant with the Java memory model, are provided to recover from incorrect speculation, while incurring only a low overhead. The technique has been implemented on a cluster of machines, and has been found to be readily scalable with multi-threaded applications. Field caching, optionally combined with other optimizations, produces a practically important performance step up in distributed environments, such as the cluster virtual machine for Java, which transparently distributes an application'"'"'s threads and objects among the nodes of a cluster.

Claims

1. A method of distributed computing, comprising the steps of:

executing Threads of an application in a plurality of interconnected nodes in a network

allocating memory of said nodes to Java compatible data objects;

responsive to said step of allocating memory for one of said Java compatible data objects, applying a predefined set of criteria to individual fields of said one Java compatible data object;

selecting read-locally fields from said individual fields according to said predefined set of criteria;

caching said read-locally fields in a cache of at least one of said nodes to define cached instances of said read-locally fields, performance fo said step of caching being transparent to said application; and

fetching at least one of said cached instances of said read-locally fields from said cache during execution of one of said threads by a proxy that is associated with said cache.

2. The method according claim 1, wherein said step of selecting is performed by:

initializing said individual fields; and

speculatively applying said predefined set of criteria prior to said steps of caching and fetching.

3. The method according claim 1, wherein said predefined set of criteria comprises field encapsulation in a code of said application.

4. The method according claim 1, wherein said predefined set of criteria comprises field encapsulation in a library code used by said application.

5. The method according claim 1, wherein said predefined set of criteria comprises a programmer-provided indication.

6. The method according claim 1, wherein a candidate is selected from said individual fields according to a subset of said predefined set of criteria.

7. The method according to claim 1, further comprising the steps of:

mutating one of said cached instances in one of said nodes; and

responsive to said step of mutating, invalidating all of said cached instances of said one cached field to define an invalidated cache field.

8. The method according to claim 7, further comprising the steps of:

following said step of invalidating, modifying one of said individual fields, said one individual field corresponding to said one cached field in a master node of said nodes, to define a modified individual field;

notifying said nodes of said of modifying;

referencing said invalidated cache field in a referencing node of said nodes; and

thereafter transmitting said modified individual field from said master node to said referencing node.

9. The method according to claim 1, further comprising the steps of:

identifying a method of said application that accesses fields of said Java compatible data objects that are limited to said read locally fields define a locally executable method;

executing said locally executable method on one of said nodes, wherein said read-locally fields that are accessed by said locally executable method are fetched from said cache of said one node.

10. The method according to claim 9, further comprising the steps of:

mutating one of said read-locally fields that is accessed by said locally executable method; and

responsive to said step of mutating, invalidating all said cached instances of said one read-locally field;

invalidating said locally executable method to define an invalidated method, wherein said invalidated method subsequently executes on another of said nodes.

11. The method according to claim 1, wherein said Java compatible data object comprise a class having objects allocated in one of said nodes, further comprising the steps of:

mutating one of said read-locally fields in one of said objects of said class;

responsive to said step of mutating, invalidating all of said read-locally fields of all of said objects of said class in said one node.

12. The method according to claim 1, wherein said Java compatible data objects comprise a class having objects allocated in one of said nodes, and further comprising the steps of:

mutating one of said read-locally fields in one of said objects of said class;

responsive to said step of mutating, invalidating said one read-locally field in all of said objects of said class in said one node.

13. The method according to claim 1, wherein said Java compatible data objects comprise a class having objects allocated in one of said nodes, and further comprising the steps of:

mutating one of said read-locally fields in one of said objects of said class;

responsive to said step of mutating, invalidating said one read-locally field in all said objects of said class in said nodes.

14. The method according to claim 1, wherein execution of said threads of said application is performed using a Java virtual machine.

15. The method according to claim 14, wherein said Java virtual machine is a cluster virtual machine for Java.

16. A computer software product, comprising a computer-readable medium in which computer program instructions are stored, which instructions, when read by a computer, cause the computer to perform the steps of:

executing threads of an application on a plurality of interconnected nodes in a network;

allocating memory of said nodes to Java compatible data objects;

responsive to said step of limiting memory for one of said Java compatible data objects, applying a predefined set of criteria to individual fields of said one Java compatible data object;

selecting read-locally fields from said individual fields according to said predefined set of criteria;

caching said read-locally fields in a cache of at least one of said nodes to define cached instances of said read-locally fields, performance of said step of caching being transparent to said application; and

fetching at least one of said cached instances of said read-locally fields from said cache during execution of one of said threads by a proxy that is associated with said cache.

17. The computer software product according to claim 16, wherein said step of selecting is performed by:

initializing said individual fields; and

speculatively applying said predefined set of criteria prior to said steps of caching and fetching.

18. The computer software product according to claim 16, wherein said predefined set of criteria comprises field encapsulation in a code of said application.

19. The computer software product according to claim 16, wherein said predefined set of criteria comprises field encapsulation in a library code used by said application.

20. The computer software product according to claim 16, wherein said predefined set of criteria comprises a programmer-provided indication.

21. The computer software according to claim 16, wherein a candidate is selected from said individual fields according to a subset of said predefined set of criteria.

22. The computer software product according to claim 16, further comprising the steps of:

mutating one of said cached instances in one of said nodes; and

responsive to said step of mutating, invalidating all said cached instances of said one cached field to define an invalidated cache field.

23. The computer software product according to claim 22, further comprising the steps of:

following said step of invalidating, modifying one of said individual fields, said one individual field corresponding to said one cached field a master node of said nodes, to define a modified individual field;

notifying said nodes of said step of modifying,

referencing said invalidated cache field in a referencing node of said nodes; and

thereafter transmitting said modified individual field from said master node to said referencing node.

24. The computer software product according to claim 16, further comprising the steps of:

identifying a method of said application that accesses said individual fields that are limited to said read locally fields to define a locally executable method;

executing said locally executable method on one of said nodes, wherein said read-locally fields that are accessed by said locally executable method are fetched from said cache of said one node.

25. The computer software product according to claim 24, further comprising the steps of:

mutating one of said read-locally fields that is accessed by said locally executable method; and

responsive to said step of mutating, invalidating all said cached instances of said one read-locally field;

invalidating said locally executable method to define an invalidated method, wherein said invalidated method subsequently executes on another of said nodes.

26. The computer software product according to claim 16, wherein said Java compatible data objects comprise a class having objects allocated in one of said nodes, further comprising the steps of:

mutating one of said read-locally fields in one of said objects of said class;

responsive to said step of mutating, invalidating all of said read-locally fields of all of said objects of said class in said one node.

27. The computer software product according to claim 16, wherein said Java compatible data objects comprise a class having objects allocated in one of said nodes, and further comprising the steps of:

mutating one of said read-locally fields in one of said objects of said class;

responsive to said step of mutating, invalidating said one read-locally field in all of said objects of said class in said one node.

28. The compute software product according to claim 16, wherein said Java compatible data objects comprise a class having objects allocated in one of said nodes, and further comprising the steps of:

mutating one of said read-locally fields in one of said objects of said class;

responsive to said step of mutating, invalidating said one read-locally field in all said objects of said class in said nodes.

29. The computer software not according to claim 16, wherein execution of said threads of said application is performed using a Java virtual machine.

30. The computer software product according to claim 29, wherein said Java virtual machine is a cluster virtual machine for Java.

31. A distributed computing system, comprising:

a plurality of processing units interconnected in a network;

a runtime support program installed in at least one of said processing units and directing said processing units, wherein said processing units execute threads of an application, and responsive to program instructions of said application, said time support program transparently causes said processing units to execute the steps of;

allocating a portion of a memory to a Java compatible data object;

responsive to said step of allocating, applying a predefined set of criteria to individual fields of said Java compatible data object;

selecting read-locally fields from said individual fields according to said predefined set of criteria;

caching said read-locally fields in a cache of at least one of said processing units to define cached instances of said read-locally fields; and

fetching at least one of said cached instances of said read-locally fields from said cache during execution of one of said threads by said one processing unit.

32. The system according to claim 31, wherein said step of selecting is performed by:

initializing said individual field; and

speculatively applying said predefined set of criteria prior to said steps of caching and fetching.

33. The system according to claim 31, wherein said predefined set of criteria comprises field encapsulation in a code of said application.

34. The system according to claim 31, wherein said predefined set of criteria comprises field encapsulation in a library code used by said application.

35. The system according to claim 31, wherein said predefined set of criteria comprises a programmer-provided indication.

36. The system according to claim 31, wherein a candidate is selected from said individual fields according to a subset of said predefined set of criteria.

37. The system according to claim 31, wherein said runtime support program transparently causes said processing units to execute the further steps of:

mutating one of said cached instances in one of said processing units; and

responsive to said step of mutating, invalidating all of said cached instances of said one cached field to define an invalidated cache field.

38. The system according to claim 37, wherein said runtime support program transparently causes said processing units to execute the further steps of:

following said step of invalidating, modifying one of said individual fields, said one individual field corresponding to said one cached field in a master processing unit of said network, to define a modified individual field;

notifying said processing units of said step of modifying;

referencing said invalidated cache field in a referencing processing unit of said network; and

thereafter transmitting said modified individual field from said master processing unit to said referencing processing unit.

39. The system according to claim 31, wherein said runtime support program transparently causes said processing units to execute the further steps of:

identifying a method of said application that accesses fields of said Java compatible data object that are limited to said read locally fields define a locally executable method;

executing said locally executable method on one of said processing units, wherein said read-locally fields that are accessed by said locally executable method are fetched from said cache of said one processing unit.

40. The system according to claim 39, wherein said runtime support program transparently causes said processing its to execute the further steps of:

mutating one of said read-locally by fields that is accessed by said locally executable method; and

responsive to said step of mutating, invalidating all said cached instances of said one read-locally field;

invalidating said locally executable method to define an invalidated method, wherein said invalidated method subsequently executes on another of said processing units.

41. The system according to claim 31, wherein said Java compatible data object comprises a class having objects allocated in one of said processing units, wherein said runtime support program transparently causes said processing units to execute the further steps of:

mutating one of said read-locally fields in one of said objects of said class;

responsive to said step of mutating, invalidating all of said read-locally fields of all of said objects of said class in said one processing unit.

42. The system according to claim 31, wherein said Java compatible data object comprises a class having objects allocated in one of said processing units, wherein said runtime support program transparently causes said processing units to execute the further steps of:

mutating one of said read-locally fields in one of said objects of said class;

responsive to said step of mutating, invalidating said one read-locally field in all of said objects of said class in said one processing unit.

43. The system according to claim 31, wherein said Java compatible data object comprises a class having objects all in one of said processing units, wherein said runtime support program transparently causes said processing units to execute the further steps of:

mutating one of said read-locally fields in one of said objects of said class;

responsive to said step of mutating, invalidating said one read-locally field in all said objects of said class in said processing units.

44. The system according to claim 31 wherein said runtime support program comprises a Java virtual machine.

45. The system according to claim 44, wherein said Java virtual machine is a cluster virtual machine for Java.