text:
|Publication number
|Publication type
|Application number
|Publication date
|Nov 2, 2006
|Filing date
|Apr 29, 2005
|Priority date
|Apr 29, 2005
|Publication number
|Petio Petev
|Original Assignee
|Petev Petio G
|Export Citation
|BiBTeX, EndNote, RefMan
|Patent Citations (4), Referenced by (31), Classifications (5), Legal Events (1)
|External Links: USPTO, USPTO Assignment, Espacenet
Embodiments of the present invention relate to memory management, and in one embodiment, a method of maintaining cache coherency using a shared lock construct.
The prior art computing system 100 runs are extensive amount of concurrent application threads per virtual machine. Specifically, there are X concurrent application threads (112 1 through 112 X) running on virtual machine 113; there are Y concurrent application threads (212 1 through 212 Y) running on virtual machine 213; . . . and, there are Z concurrent application threads (N12 1 through N12 Z) running on virtual machine N13; where, each of X, Y and Z are a large number.
A virtual machine, as is well understood in the art, is an abstract machine that converts (or "interprets") abstract code into code that is understandable to a particular type of a hardware platform. For example, if the processing core of computing system 100 included PowerPC microprocessors, each of virtual machines 113, 213 through N13 would respectively convert the abstract code of threads 112 1 through 112 X, 212 1 through 212 Y, and N12 1 through N12 Z into instructions sequences that a PowerPC microprocessor can execute.
Because virtual machines operate at the instruction level they tend to have processor-like characteristics, and, therefore, can be viewed as having their own associated memory. The memory used by a functioning virtual machine is typically modeled as being local (or "private") to the virtual machine. Hence,
A portion of a virtual machine's local memory may be implemented as the virtual machine's cache. As such,
For example, in an object-oriented environment, an object that is subjected to frequent use by a virtual machine (for whatever reason) may be stored in the virtual machine's cache. The combination of the cache's low latency and the frequent use of the particular object by the virtual machine corresponds to a disproportionate share of the virtual machine's fetches being that of the lower latency cache; which, in turn, effectively improves the overall productivity of the virtual machine.
A problem with the prior art implementation of
Given that the application threads running on an application server 100 typically have "mission critical" importance, the wholesale crash of scores of such threads is a significant problem for the enterprise.
The Java programming language provides for object synchronization which stops two threads from accessing the same object at the same time. This objected is "locked." Any object can be locked and only one thread may hold this lock at one time. In other words, an exclusive lock is put on the object.
Locks in Java are not explicitly set but instead are generated by executing a synchronized method. For example the generic code below synchronizes an object:
This method is based on the concepts of monitors and locks. A monitor is basically a protective wrapper around a critical code section and a lock is a software entity that a monitor uses to prevent multiple threads from entering the monitor. When a thread wishes to enter a monitor-guarded critical code section that thread must acquire the lock associated with an object that associates with the monitor (each object has its own lock). If some other thread holds that lock, the virtual machine (VM) forces the requesting thread to wait in a waiting area associated with the monitor/lock. When the thread in the monitor releases the lock, the VM removes one of the waiting threads from the monitor's waiting area and allows that thread to acquire the lock and proceed to the monitor's critical code section. However, shared locks and intentional locks are not supported.
Systems and methods for a treatment of objects are described. In one embodiment, cache coherence is maintained using shared locks and messaging between worker nodes and/or virtual machines. These messages utilize a message protocol. The protocol includes a hashable object key, a region identifier, and message type.
The present invention is illustrated by way of example, and not limitation, in the figures of the accompanying drawings in which:
In the following description, for the purposes of explanation, numerous specific details are set forth in order to provide a thorough understanding of the present invention. It will be apparent, however, to one skilled in the art that the present invention may be practiced without some of these specific details. In other instances, well-known structures and devices are shown in block diagram form.
Note that in this detailed description, references to "one embodiment" or "an embodiment" mean that the feature being referred to is included in at least one embodiment of the invention. Moreover, separate references to "one embodiment" in this description do not necessarily refer to the same embodiment; however, neither are such embodiments mutually exclusive, unless so stated, and except as will be readily apparent to those skilled in the art. Thus, the invention can include any variety of combinations and/or integrations of the embodiments described herein.
The present invention includes various steps, which will be described below. The steps of the present invention may be performed by hardware components or may be embodied in machine-executable instructions, which may be used to cause a general-purpose or special-purpose processor programmed with the instructions to perform the steps. Alternatively, the steps may be performed by a combination of hardware and software.
The present invention may be provided as a computer program product that may include a machine-readable medium having stored thereon instructions, which may be used to program a computer (or other electronic devices) to perform a process according to the present invention. The machine-readable medium may include, but is not limited to, floppy diskettes, optical disks, CD-ROMs, and magneto-optical disks, ROMs, RAMs, EPROMs, EEPOMs, magnetic or optical cards, flash memory, or other type of media/machine-readable medium suitable for storing electronic instructions.
According to the depiction of
In order to concurrently execute a comparable number of application threads as the prior art system 100 of
Thus, for example, if the prior art system 100 of
Here, the prior art system 100 instantiates one virtual machine per CPU while the improved system 200 of
Recall from the discussion of
Thus, whereas the prior art computing system 100 of
According to an object oriented approach where each of virtual machines 123, 223, . . . M23 does not have visibility into the local memories of the other virtual machines, specific rules are applied that mandate whether or not information is permitted to be stored in shared memory 230. Specifically, to first order, according to an embodiment, an object residing in shared memory 230 should not contain a reference to an object located in a virtual machine's local memory because an object with a reference to an unreachable object is generally deemed "non useable".
That is, if an object in shared memory 230 were to have a reference into the local memory of a particular virtual machine, the object is essentially non useable to all other virtual machines; and, if shared memory 230 were to contain an object that was useable to only a single virtual machine, the purpose of the shared memory 230 would essentially be defeated.
In order to uphold the above rule, and in light of the fact that objects frequently contain references to other objects (e.g., to effect a large process by stringing together the processes of individual objects; and/or, to effect relational data structures), "shareable closures" are employed. A "closure" is a group of one or more objects where every reference stemming from an object in the group that references another object does not reference an object outside the group. That is, all the object-to-object references of the group can be viewed as closing upon and/or staying within the confines of the group itself. Note that a single object without any references stemming from can be viewed as meeting the definition of a closure.
If a closure with a non shareable object were to be stored in shared memory 230, the closure itself would not be shareable with other virtual machines, which, again, defeats the purpose of the shared memory 230. Thus, in an implementation, in order to keep only shareable objects in shared memory 230 and to prevent a reference from an object in shared memory 230 to an object in a local memory, only "shareable" (or "shared") closures are stored in shared memory 230. A "shared closure" is a closure in which each of the closure's objects are "shareable."
A shareable object is an object that can be used by other virtual machines that store and retrieve objects from the shared memory 230. As discussed above, in an embodiment, one aspect of a shareable object is that it does not possess a reference to another object that is located in a virtual machine's local memory. Other conditions that an object must meet in order to be deemed shareable may also be effected. For example, according to a particular Java embodiment, a shareable object must also posses the following characteristics: 1) it is an instance of a class that is serializable; 2) it is an instance of a class that does not execute any custom serializing or deserializing code; 3) it is an instance of a class whose base classes are all serializable; 4) it is an instance of a class whose member fields are all serializable; 5) it is an instance of a class that does not interfere with proper operation of a garbage collection algorithm; 6) it has no transient fields; and, 7) its finalize ( ) method is not overwritten.
Exceptions to the above criteria are possible if a copy operation used to copy a closure into shared memory 230 (or from shared memory 230 into a local memory) can be shown to be semantically equivalent to serialization and deserialization of the objects in the closure. Examples include instances of the Java 2 Platform, Standard Edition 1.3 java.lang.String class and java.util.Hashtable class.
Note that the introduction of the shared memory 230 introduces the prospect of a shared cache 240. Thus, the architecture of
Different types of containers may exist. For example, a first type of container may contain instances of pages and servlets for executing a web based "presentation" for one or more applications. A second type of container may contain granules of functionality (generically referred to as "components" and, in the context of Java, referred to as "beans") that reference one another in sequence so that, when executed according to the sequence, a more comprehensive overall "business logic" application is realized (e.g., stringing revenue calculation, expense calculation and tax calculation components together to implement a profit calculation application).
The cache management service 302 is configured to have visibility into the local memory cache 325 of the virtual machine 323, the shared memory cache 340 and one or more other storage resources 350 such as a database or file system used for storing persisted objects. Here, as will be described in more detail below, different applications whose abstract code (e.g., Java byte code in the case of Java) is executed by virtual machine 323 can specially configure the cache management service 302 to treat its cached objects in accordance with specific guidelines.
According to various schemes, the cache manager 302 effectively configures regions of cache for the storage of objects in local cache memory 326 and/or in shared memory cache 340 according to different treatment policies. Multiple cache regions defining different cache treatments may be established for a single application. Cached objects placed in local memory cache 326 may be conveniently utilized by the virtual machine 323 associated with the local memory where local cache 326 resides for quick processing by the application. By contrast, cached objects placed in shared memory cache 340 may be utilized by the local virtual machine 323 as well as other virtual machines that have visibility into the shared memory in which the shared memory cache 340 is implemented.
A cache region effectively determines the treatment that an object that is stored in the cache region will receive. For example, cache region_1 410 determines the treatment of object 460, while cache region_2 412 determines the treatment of cached object 461. By comparison, object 460 will receive different treatment than object 461 because of the different treatment imposed by the different cache regions 410, 412.
For each cache region, in an embodiment, cache manager 402 implements a storage plug-in and an eviction policy plug-in. The storage plug-in may be, in one embodiment, the actual piece of software or code that executes the "get" and "put" operations for the objects stored according to the treatment determined by the associated cache region. That is, for example, whether the object is placed in the local memory cache, the shared memory cache, or some other type of storage resource such as a database or file system for storing persisted objects. The eviction policy plug-in may be, in one embodiment, the actual piece of software or code that dictates the removal of an object from cache (e.g., when some form of cache capacity threshold is exceeded).
In continuing from the example provided above, cache region_1 410 defines the treatment of object 460 with storage plug-in_1 420 and eviction policy plug-in_1 421. Cache region_2 412 defines the treatment of object 461 with storage plug-in_2 422 and eviction policy plug-in_2 423. Cache region_N 414 is generally represented as having storage plug-in_N 424 and eviction policy plug-in_N 425. For simplicity of description, each cache region is described as having only a single object that is treating according to the treatment determined by the cache region, but, it should be appreciated that any number of objects may be referenced by a particular cache region. Moreover, any object stored in, copied from, written to, or removed from the shared memory cache 432 may be a single object; or, an object that is part of a shared closure where the shared closure itself is respectively stored in, copied from, written to, or removed from the shared memory cache 432.
As illustrated in
Until now, a cache region (e.g., cache region_1 410) has been generally described as defining the treatment for a particular object, that is, for putting and/or getting an object to/from either the local memory cache and/or the shared memory cache. The following provides greater detail as to the different types of cache regions that may be implemented by cache manager 402 for the treatment of objects as defined by its storage and eviction policy plug-ins. The different types of cache management treatments are referred to as "flavors" or "cache flavors".
As shown in
Active removal of an object by the eviction policy plug-in (e.g., eviction) ignores the referenced states of the object as described above. As such, hard referenced objects may be just as easily removed as weak referenced objects according to the policies set forth by the eviction policy plug-in 521. Here, note that storage plug-in 520 may also institute "spooling" and "write through" policies to deeper storage. In an embodiment, a separate plug-in in cache region 511 (not shown) is used to interface with the deeper storage and is called upon as needed by storage plug-in 520 to institute spooling and write through policies.
When the active eviction process is invoked, soft reference 573 is changed to a weak reference 574. Under this condition, object 561 may be removed by a garbage collector if the application's hard reference no longer exists (e.g., because the application is no longer actively using the object 561). That is, object 561 remains protected from removal by the garbage collector as long as the application's hard reference 572 to the object 561 is present, otherwise the object will be removed. Here, note that storage plug-in 522 may also institute "spooling" and "write through" policies to deeper storage. In an embodiment, a separate plug-in in cache region 512 (not shown) is used to interface with the deeper storage and is called upon as needed by storage plug-in 522 to institute spooling and write through policies. In one embodiment, by invoking the removal of object 560 from local memory cache_1 530 (either by active eviction or garbage collection), cache region_2 512 may also provide for object 560 to be copied to deeper storage.
Before moving forward it is important to re-emphasize that objects stored according to either of the local flavors discussed above may be of the non shareable type so as to be incapable of membership in a shared closure and storage into shared memory. Moreover, the application is apt to configure its different local cache regions such that objects receiving local flavor treatment are apt to be more heavily used (e.g., some combination of the number of "get" and "put" accesses over time) than objects treated according to the Soft Local flavor.
The application 501 is then free to use the local copy 562 a as a "work horse" object. For each "put" operation made to the local copy 562 a, (e.g., to effectively modify the object's earlier content) the storage plug-in 524 updates/writes to the shared copy 562 b to reflect the "put" into the local memory cache 530. Note that because of the presence of shared copy 562 b, a virtual machine other than the virtual machine that is associated with the local memory within which local memory cache_1 530 is implemented may copy the shared copy 562 b into its local memory cache (e.g., local memory cache 531) so as to create a third copy 562 c of the object. The third copy 562 c of the object can be used as a "work horse" object for another application (not shown) that runs off of the other local memory cache 531. This other application will make a hard reference to this object 562 c as well (not shown). In one embodiment, storage plug-in 524 does not place any kind of reference to shared copy 562 b because any shared closure is reachable in shared memory through a key name that uniquely identifies that shared closure; and moreover, shared closures are kept in shared memory until an application explicitly calls a "delete" operation (e.g., no garbage collection process is at work in shared memory at least for cached objects). As such, there is no need for any type of reference to a shared closure residing in shared memory.
If the other application associated with local memory cache_2 531 effectively modifies its local object 562 c (e.g., with a "put" operation), the storage plug-in for local memory cache_2 531 will create a "second version" 563 of shared object 562 b in shared memory cache 532 that incorporates the modification made to local object 562 c. According to an implementation, the storage plug-in 524 does not receive any affirmative indication of the existence of the new version but is instead configured to look for new versions in shared memory (e.g., upon a "put" or "get" operation) given the possibility of their existence under the shared flavor scheme. For instance, a "get" operation by application 501 will result in the reading of object 562 a and object 563 by plug-in 524. Likewise, a "put" operation by application 501 can result in the fetching of object 563 by plug-in 524 so that it is possible to modify a local copy of the object 563 version. Here, note that storage plug-in 524 may also institute "spooling" and "write through" policies to deeper storage. In an embodiment, a separate plug-in in cache region 513 (not shown) is used to interface with the deeper storage and is called upon as needed by storage plug-in 524 to institute spooling and write through policies.
In an extended embodiment, if a requirement to modify the object 564 arises, the storage plug-in 526 associated with the application 501 that desires to make the modification creates an entirely new object and places it into the shared memory 532 as a second version 565. Subsequently, when object 564 is requested from shared memory 532 by another application, the updated, second version 565 may also be retrieved. Here, note that storage plug-in 526 may also institute "spooling" and "write through" policies to deeper storage. In an embodiment, a separate plug-in in cache region 514 (not shown) is used to interface with the deeper storage and is called upon as needed by storage plug-in 526 to institute spooling and write through policies.
For either of the shared flavors discussed above, the storage plug-in may be configured to control the size of the shared closures that are being entered into shared memory cache 532. Specifically, smaller shared closures may be "bundled" with other shared closures to form effectively a data structure that contains multiple shared closures and that is effectively treated as a single shared closure for copying operations from shared memory cache 532 into local memory cache 530 (or vice versa). Here, a bundle may be created simply by ensuring that each shared closure in the bundle is associated through a reference to another shared closure in the bundle.
By increasing bundle size, overhead associated with copying objects back and forth between shared memory and local memory is reduced in certain circumstances, particularly, environments where many smaller shared closures are to be sent between shared memory and local memory at about the same time. Here, by bundling them, all shared closures can effectively be transported between shared memory and local memory by a single transfer process.
Until now, the storage plug-in for a particular cache region has been generally described as defining the cache storage treatment of one or more objects associated with the cache region. The storage plug-in may be, in one embodiment, the actual piece of software or code that executes various operations (e.g., "get" or "put") for objects stored according to the treatment determined by the associated cache region.
Storage plug-in 603, in one embodiment, is logically represented as being capable of performing several functions, including Key Object Manipulation 604, Key Attribute Manipulation 605, Group Manipulation 606, Key Set Operations 607, Key System Attribute Manipulation 608, and Object Size Information 609. Several functionalities are also associated with eviction policy plug-in 610. These functionalities include Sorting 611, Eviction Timing 612, and Object Key Attribution 613. The various functionalities of eviction policy plug-in 610, which also define a treatment of objects in local memory cache 630 and shared memory cache 632, are described in greater detail further below with respect to
Key Object Manipulation 604 is a storage plug-in function that relates to the "get" and "put" operations for an object. For example, a "get" operation retrieves a particular object from local cache memory 630 and/or shared memory cache 632 depending on the "flavor" of the plug-in (consistent with the different caching flavors described in the preceding section). A "put" operation places a copy of an object into local memory cache 630 and/or shared memory cache 632 (again, consistent with the specific "flavor" of the plug-in). For each object associated with a cache region, an object name may be assigned to each object. In turn, each object name may correspond to a unique key value. One embodiment of this organizational structure is illustrated in
Referring to
Each object of cache group_1 620 is associated with a unique key. That is, for example, Key_1 640 is associated with object 670, key_2 641 is associated with object 671, and key_N is associated with object 672. Each key is a value (e.g., alphanumeric) that, for instance, in one embodiment, is the name of the object. In an embodiment, the key for an object undergoes a hashing function in order to identify the numerical address in cache memory where the object is located.
As such, the Key Object Manipulation functionality 604 of storage plug-in 603 utilizes the key associated with an object to carry out "put" and "get" operations on that object. For simplicity, only a local memory cache 635 is considered (e.g., the storage plug-in may be a "local" or "soft local" flavor).
As an example, object 670 may have the key "Adam" in simple text form. An application (e.g., application_1 601 of
A feature of the Key Object Manipulation 604 functionality is that an application does not need to know the exact location of a desired object. The application merely needs to reference an object by its key only and the Key Object Manipulation 604 functionality of the storage plug-in is able to actually put the object with that key into the local memory cache 630.
A "get" operation may be performed by the Key Object Manipulation 604 functionality in a similar manner. For example, object 671 may have the name "Bob." An application (e.g., application_1 601 of
Key Attribute Manipulation 605 is a functionality that relates to defining or changing particular attributes associated with an object. Here, each object has its own associated set of "attributes" that, in one embodiment, are stored in cache address locations other than that of the object itself. Attributes are characteristics of the object's character and are often used for imposing appropriate treatment upon the object. Examples of attributes include shareable/non-shareable and time-to-live (an amount of time an object is allowed to stay in a cache region before being evicted). As each cached object is associated with a key, an object's attributes may also be associated with the key.
Thus, as depicted in
The Key System Attribute Manipulation 608 allows for system attributes (e.g., system level parameters) to be keyed and manipulated, and, operates similarly to the key attribute manipulation 605.
Group Manipulation 606 is a storage plug-in functionality that allows for "put" or "get" manipulation of all the objects within a particular group. By specifying the group name for a group of objects, the application may retrieve ("get") all the objects within that group. In an embodiment, the keys for a particular group are registered with the storage plug-in 603. As such, a group name that is supplied by the application is "effectively" converted into all the keys of the objects in the group by the storage plug-in 603. For example, application_1 601 may run a "get" operation for cache group_1 620. By using the name of cache group_1 620 as the input, each of keys key_1 640, key_2 641, . . . key_N 642 are used by the storage plug in cache of keys to perform a "get" operation.
The Object Size Information function 609 causes the storage plug-in 603 to calculate the size of an object (e.g., in bytes). Here, the application supplies the key of the object whose size is to be calculated and specifies the object size information function 609. Combined with a Group Manipulation function, the Object Size Information function 609 enables storage plug-in 603 to calculate the size of an entire group. The Key Set Operations function 607 is used to perform specific operations with the keys themselves (e.g., return to the application all key values in a group specified by the application).
As discussed above, each object may have a collection of attributes (e.g., shareable/non-shareable, time-to-live, etc.). In one embodiment, these attributes may be organized in local memory cache to be accessed by an application in a manner similar to the retrieving of an object with a "get" operation described above with respect to the Key Object Manipulation 604 function. In one embodiment, a series of hashing operations may be performed to retrieve one or attributes of a particular object.
A "get" operation for a particular attribute of an object may be carried out in the following manner. Application_1 601 specifies: 1) the operation 658 (e.g., "get"); 2) the key for the object 668 (e.g., "ADAM"); and, 3) the applicable attribute 678 (e.g., "SHAREABLE/NON-SHAREABLE"). As discussed above with respect to
A second hashing function (e.g., hash_2 651) is performed using the desired attribute 678 (e.g., SHAREABLE/NON-SHAREABLE) as the key. The hash_2 651 hashing function identifies the particular numerical address of the particular attribute of attributes table 655 that is to be accessed. For example, if the Shareable/Non-shareable attribute value corresponds to value_2 663, the alphanumeric "name" of the attribute (e.g., "Shareable/Non-shareable") would map to address_2 662 of attributes table 655.
Caches, either local or shared, have limited storage capacities. As such, a cache may require a procedure to remove lesser used objects in order, for example, to add new objects to the cache. Similar to a storage plug-in being designed to impose certain storage treatment(s) on an object, the eviction policy plug-in provides various functionalities for the active removal of an object from cache. As briefly discussed above with respect to
Referring to
To the extent the sorting component 611 can be viewed as a component that chooses "what" object should be removed from cache, the eviction timing component 612 is a component that determines "when" an object should be removed from cache. Different flavors for eviction timing components may also exist and be chosen from for implementation. Typically, a single eviction timing component is instantiated per cache region; but, conceivably, multiple eviction policy components may be instantiated as well (e.g., one per cache group). The object key attribution 613 component enables the involvement of certain object attributes (e.g., object size) in eviction processes.
For simplicity, the remainder of this detailed description will be written as if an eviction policy plug-in applies to an entire cache region.
According to the design of the LRU queue 617, objects cached in a cache region that are accessed least recently (e.g., through either a "get" or "put" operation) are discarded first. LRU queue 617 is represented with a vertical ordering structure for multiple keys (e.g., key_1 655, key_2 656, . . . key_N 657). Essentially, the top of the queue represents keys for objects that have been used most recently, and, the bottom of the queue represents keys for objects that have been used least recently. According to one implementation of LRU queue 617, the object corresponding to the key at the very bottom would be next evicted. Removal of a key from the bottom of the queue triggers the eviction of that key's corresponding object from cache.
Here, any time an object is accessed (e.g., by way of a "get" or "put" operation), the key corresponding to that object is positioned at the very top of LRU queue 617. As illustrated by the position of key_1 655, the object associated with key_1 655 is the most recently accessed object. If, however, in a following operation an application (e.g., application_1 601) accesses the object associated with key_2 656, then, key_2 656 would be repositioned above key_1 655 in the LRU queue 617.
At any given instant of time, the key whose object has spent the longest amount of time in the cache region without being accessed will reside at the bottom of the queue. As such, when the moment arises to remove an object from the cache region, the object whose key resides at the bottom of the queue will be selected for removal from the cache region.
LFU queue 618 is an eviction policy in which cached objects accessed least frequently (e.g., through either a "get" or "put" operation), based on a counter, are discarded first. Each key for an object may have an associated counter that measures or keeps track of the number of times the object is accessed (e.g., the counter for the object's key is incremented each time the object is accessed). In one embodiment, the counter value may be an "attribute" for the object as described previously.
As with LRU queue 617, LFU queue 618 is represented with a vertical ordering structure for multiple keys (e.g., key_1 665, key_2 666, . . . key_N 667). The top of the queue represents keys for objects that have the highest counter value, and the bottom of the queue represents keys for objects with the lowest counter value. Here, over the course of time, those keys whose corresponding objects are accessed more frequently than other cached objects will be "buoyant" and reside near the top of the queue; while, those keys whose corresponding objects are accessed less frequently than the other objects in the cache region will "sink" toward the bottom of the queue.
At any instant of time, the key whose corresponding object has been used less than any other object in the cache region will be at the bottom of the queue. Thus, according to one implementation of LFU queue 618, the object corresponding to the key at the very bottom would be next evicted, because that object has the lowest counter value (e.g., lowest frequency of use). Removal of the key from the bottom of the queue triggers the eviction of that key's corresponding object from the cache region. Note that the counters for all the keys may be reset periodically or with each entry of a newly cached object in order to ensure that all the counter values can be used as a comparative measurement of use.
Size-based queue 619 is an eviction policy in which cached objects are prioritized according to size (e.g., the number of total bytes for the object). As such, object size may be another object attribute. The keys for objects in size-based queue 619 are shown arranged vertically with the smallest objects positioned near the top of the queue and keys for the largest objects positioned near the bottom of the queue. According to one implementation of size-based queue 619, the object corresponding to the key at the very bottom would be evicted first, because that object consumes the most amount of cache region space, and its subsequent removal would result in the most amount of free cache region space recovered (amongst all the objects that are cached in the cache region).
FIFO queue 621 is an eviction policy in which cached objects are removed according to the order that they are placed in the cache relative to one another. In one embodiment, when an eviction moment arises, the first cached object eligible for eviction corresponds to the object that has spend the most time in the cache, followed by the next oldest object, and so on. FIFO queue 621, illustrated in
Referring back to
In one embodiment, three threshold levels may be established for the cache region. A first threshold level, threshold_1 645, corresponds to a level at which the eviction of a key from the sorting queue occurs on a timely basis. For example, when the count exceeds threshold_1 645 (but not threshold_2 646), a key is evicted from the sorting queue every millisecond until the total count falls below threshold_1 645. In one embodiment, no active eviction occurs for count levels below threshold_1 645.
A second threshold level, threshold_2 646, corresponds to a level above which eviction of a key occurs on each entry into the cache of a newly cached object. That is, with each new addition of an object into cache, the key at the bottom of the applicable sorting queue is removed from the queue resulting in its corresponding object's eviction from cache. With this approach, the population of the cache region should remain constant in the absence of objects being removed from the cache region by processes other than eviction (such as deletion and/or garbage collection and/or attribute based as described below with respect to Object Key Attribution). With processes other than eviction, the cache region population may fall below threshold_2 646 after the threshold has been crossed.
A third threshold level, threshold_3 647, corresponds to a level equal to the targeted maximum allocation 648 for the cache region. When this level is exceeded, keys are evicted from the sorting queue until, in one embodiment, the total count of keys decreases to threshold_3 647 (or just beneath threshold_3 647). Note that this approach contemplates the population of the cache region exceeding its "targeted" maximum allocation for some reason.
Either of the eviction timing techniques may be used with the LRU 617 LFU 618 or FIFO 619 sorting technique.
In one embodiment, threshold_1 685, threshold_2 686, and threshold_3 687 have similar properties with threshold_1 645, threshold_2 646, and threshold_3 647, respectively. The only difference is that the memory consumption of the cache region (through the caching of its cached objects) triggers the crossing of the various thresholds.
Referring again back to
Also, in the case of size based eviction policies, each objects size may be found in its attribute table.
The preceding discussions revealed that, referring to
Here, definition of a specific cache region is effected by selecting 1604 a storage plug-in from the storage plug-in part 1602 of the cache management library 1601 and by selecting 1605 a sorting component plug-in from the sorting component plug-in part 1603 of the cache management library 1601. For each new cache region to be implemented, another iteration of the selection processes 1604, 1605 is performed. Thus, if a single application were to establish multiple cache regions, the configuration for the application would entail running through selection processes 1604, 1605 for each cache region to be implemented.
As discussed above with respect to
In another example, a first computing system having a first virtual machine may crash during the course of running operations with a number of objects. If the objects are stored in a persisted database, a second virtual machine from a second computing system may be able to restore the operations that were running on the first computing system, using the same objects retrieved from the persisted database.
In one embodiment, a Structured Query Language (SQL), or SQL-like command statement may be used to write a serialized version of object 850 b into database 820. (In
Upon receiving the success notification and the de-serialized key for object 850 b, cache manager_1 804 serializes 833 the key for object 850 b and sends the serialized key 834 across a network 806 to computing system_2 802. Cache manager_2 808 receives the serialized key for object 850 b and then de-serializes the key, 835. The de-serialized key may then be registered with a storage plug-in associated with cache manager_2 808.
When application_2 807 running on computing system_2 802 requests 837 object 850 b, the de-serialized object key that is registered with cache manager_2 808 is used to retrieve 838 the serialized object 850 b from database 820 at computing system_2 802. The serialized object 850 b may then be de-serialized 839 by cache manager_2 808. The de-serialized object 850 a may then be saved in local memory cache_2 809 and/or shared memory cache_2 810.
An object may be shared between threads of a single VM, threads of different VMs on the same machine or of the same instance, or threads of different VMs on separate machines. A shared object is any object that may be accessed by more than one thread. For example, a shared object may be located in a shared memory (including shared closures) and/or have a local copy in local memory.
A thread of an application operates on objects accessible to that application. There may be times when one thread of an application is accessing an object when another thread also requires access to the same object. In some cases there are no problems with this occurring. For example, if both threads are simply reading the contents of the object. However, it may be desirable to assure that access to this object is restricted to one thread at a time so that the values of the object are not altered by different threads at the same time thereby rendering unwanted results to at least one of the threads accessing the object. In other words, to prevent so-called "dirty writes" to the object.
As the virtual machine 1905 processes the threads of the application 1901 it may be necessary to effectively lock out the other threads from accessing an object in memory 1907 that is shared by more than one thread. As discussed in the background, the Java programming language provides for a lock associated with each object that is used during synchronization. This lock restricts access to the object to only one thread until the lock is released.
However, a shared object may be locked without relying on Java synchronization that has been discussed in the background. In fact, the synchronization techniques (synchronized, wait, and notify statements) inherent within the Java language do not address the problem locking an object when more than one VM is used especially in a shared closure environment. The Java techniques only impact on a local VM. Therefore, another locking mechanism is necessary that enables Java application and infrastructure developers to define a block of operations which is executed in an atomic manner similar to the synchronized statement provided by the Java language, but apply to all Java virtual machines (VMs) on one instance (for example, a application server instance).
In one embodiment, a shared lock class provides a static factory method named getSharedLock(java.lang.String name) that returns an instance of the SharedLock class. This method expects a string parameter as its input, which represents the name to be locked. The factory method does not do any locking. The shared lock instance may be shared between VMs on the same physical machine. That means if more than one VM or more than one VM thread wants to get a shared lock of the same name, they all will get the same shared lock instance. This is because a shared lock instance is a shareable object and that makes it possible to use it in Shared Closures.
As the factory does not lock anything each thread that will access the shared object contains a snippet or block of code that prevents access to that object while another thread has control over the object. This snippet of code will now be referred to as either a shared lock or the shared locking construct.
The shared lock pseudo code of one embodiment is as follows:
sharedLock.executeLocked("key", new runnable( )){ run( ){ . . . cache.put("key", object); }; }; }
In the above pseudo code, the lock is implemented by the call "sharedLock.executeLocked." In one embodiment, this snippet of code is an object that only one thread may obtain and execute on as the "sharedLock" is object acquired from the shared domain (for example, cache). This object is acquired by a specific name and thus concurrent threads trying to acquire the sharedLock with the same name will reference the same shared resource. Therefore, the executeLocked(java.lang.Runnable) instance method enables the developer to define a block of operations which is executed in an atomic manner. The java.lang.Runnable interface contains a run( ) method, which has to be implemented by a respective class. This method represents the critical section, which is executed atomically. If several concurrent threads in one or several VMs are executing the executeLocked method, all but one thread will get the lock based on the specified name and the corresponding executeLocked method is performed. The other threads will be blocked until the execution finishes. Then the waiting threads are competing for the lock and the analogous procedure takes place.
In the above code, the run method executes a put operation which uses the key ("key") to determine the location in cache to place the shared object ("object") and places (puts) the shared object in that location. The concept of a key has already been discussed. Each key is a value that, for instance, is the name of the object. The key for an object undergoes a hashing function in order to identify the numerical address in memory where the object is located. Of course, other operations involving the manipulation of the shared object occur before the put function. The lock is released once the run method finishes, allowing other threads to access the shared object. Of course it should be understood that equivalent code snippets may be used with the underlying principles.
The cache manager 1903 provides the ability to store in various cache regions as described earlier. Of course it should be understood that the principles described above are applicable to configurations that use a shared memory implementation including those with shared closures, for example as in the system as described in
The shared locking construct is applicable to systems that include more than one virtual machine including systems that have virtual machines on different physical machines that are interconnected by a network. In order to ensure that information is shared properly between virtual machines or physical machines a message server may be implemented. Each physical machine has a message server and/or there is a central message server. This message server receives messages from one system and routes them to another system. For example, a message may be sent from a first physical machine that it is altering a shared object that other physical machines also access.
The messaging service 2103 allows each worker node to communicate with one another via a message passing protocol (to be discussed later). For example, messages from one server may be broadcast to all other worker nodes via the messaging service 2103. Alternatively, messages may be addressed directly to specific worker nodes (e.g., rather than being broadcast to all servers).
In one embodiment, the messaging service 2103 is implemented on dedicated server or machine other than the server or machine that is implementing the worker nodes. However, the messaging service 2103 may be implemented on the same server while still complying with the underlying principles of the invention.
The shared memory 2101 may contains several regions including cache 2105. Shared memory may be a part of local memory or a deeper storage such as a database. This shared memory 2101 and its contents, including cache 2105, are accessible by both worker nodes 2109, 2111. For example, the cache 2105 includes an object 2107 a (e.g., OBJ_A) that both worker nodes access. A worker node generically includes at least an application, a cache manager, a virtual machine, and local memory. Of course it should be understood that multiple applications, virtual machines, etc. may be utilized while still complying with the underlying principles of the invention.
Each cache manager (or cache management service) 2113, 2143 includes a registration table 2125, 2147 and a listener node 2135, 2145. Listener nodes of other worker nodes' cache managers may be registered in the in the registration table of a particular worker node. The registration table may be created at deployment but is updateable during operation. These listener nodes are also referred to as "internal" listener nodes in this description.
An internal listener node receives notifications that a shared object has been or may be modified or removed from cache. These objects may include local copies 2107(b), 2107(c) stored in a cache region 2105 of local memory 2117, 2161 of objects 2107(a) in shared cache 2105 that may be operated on by a worker node's applications. One example of a region of local memory is a cache region.
As illustrated, the virtual machine 2115, 2159 of a worker node 2109, 2111 may support several applications 2119, 2121, 2123 (e.g., APP_A, APP_B, and APP_C) or a single application 2153 (e.g., APP_D). Each application 2119, 2121, 2123, 2153 may contain a single or multiple threads as discussed earlier. Each application 2119, 2121, 2123, 2153 also includes an application listener node 2137, 2139, 2141, 2157 that communicates with its respective cache manager. The application listener nodes are also known as "external" listener nodes.
Each external listener node 2137, 2139, 2141, 2157 is registered in its respective cache manager's registration table 2125, 2147. Effectively this registration provides for an address of the applications and/or listener nodes that are accessible to a particular cache manager. There may be separate registration tables for external and internal listeners.
Registration Table_1 2125 of worker node 2109 has an entry 2127 for Listener_2 2145 of worker node 2111 and entries 2129, 2131, 2133 for the applications 2119, 2121, 2123 of the worker node 2109. This means that Cache Manger_1 2113 may send messages to its applications 2119, 2121, 2123 and to Cache Manager_2 2143. Likewise, Registration Table_2 2153 of worker node 2111 an entry 2149 for Listener_2 2135 of worker node 2109 and an entry 2151 for the application 2153 of worker node 2111.
In one embodiment, the messaging service 2103 contains a registration table of all listeners of the system and routes messages accordingly. Each listener and/or its respective cache manager communicates directly with the messaging service without knowledge of the other worker nodes that share the object.
When an application of a first worker node desires to remove an object that is shared between two worker nodes, notice is sent to the second worker node of the intent to invalidate at 2201. As discussed earlier, a listener node receives a notification that a shared object has been or may be modified or removed from cache. Notification helps to ensure that each application that may access that object (or its copy) will be operating on the same object values. If one thread changes the object values the rest should be alerted to make sure that they have those new values.
The listener of the second worker node that needs to be notified of may be found using the first worker node's registration table. The message of notice of intent to invalidate is passed through the messaging service to the listener of the second worker node. For example, Listener_1 2135 is registered with Cache Manager_2 2143 and should therefore be notified when Cache Manager_2 2143 is going to make a change with respect to Cache Manager_2's 2143 local copy of the shared object 2107 c. The address for Listener_1 2149 may be found in Registration Table_2 2147 and Cache Manager_2 2143 will send the notice of intent to invalidate through the messaging service 2103 to the listener 2135 of Cache Manager_1 2113.
When the notice of intent to invalidate has been received by the second worker node, the second worker node invalidates it local copy of the object at 2203. Specifically, the cache manager of the second worker node will invalidate the local copy of the object. At this time, the copy in shared memory may also be invalidated. For example, Listener_1 2135 will receive the notice to invalidate from Cache Manager_2 2143 and Cache Manager_1 2113 will invalidate its local copy of the object 2107 b.
With the local copy of the second worker node invalidated or concurrently with the invalidation, the second worker node sends an acknowledgement of its invalidation to the first worker node at 2205. The first worker node, upon receipt of the acknowledgement, will know that its notice was received and that it is safe to invalidate its copy. In an alternative embodiment, the acknowledgement is sent before the invalidation is performed.
Sending a message and waiting for an acknowledgment is called synchronous messaging. In synchronous messaging the worker node that sent the message loses control of the object (e.g., cannot perform operations on the object) until an acknowledgment comes back to it. While this form of messaging requires more overhead and causes a delay, it helps to ensure that the object data is uniform. For example, if the sending worker node does not "hear" from all of the other worker nodes that they have invalidated their respective copy, the sender node may make a change that at least one worker has not made resulting in different copies of the object.
Conversely, in asynchronous messaging control is returned immediately after the message is sent without waiting for an acknowledgement. In one embodiment, asynchronous messaging is used and the first worker node does not wait for acknowledgement and invalidates its local copy after it sends its notice of invalidation. Internal notice may be synchronous or asynchronous.
In one embodiment, if the first worker node does not receive an acknowledgment it will resend its intent to invalidate message to the worker node(s) that has not responded at 2206 and again wait for an acknowledgment to come back. For example, the first worker node will wait for a set period of time before sending out this extra message. Furthermore, in one embodiment, if the first worker node does receive an acknowledgment after a set number of retries it will assume that the worker node not responding has died (e.g., its virtual machine has crashed) and continue as if an acknowledgement was received. The cache manager of the first worker node may remove the entry to the failed worker node's listener from the registration table so that the "dead" worker node is not notified if a later change is made and thereby causing another delay. In another embodiment, the sending of acknowledgment of invalidation at 2205 is unconditional and block 2206 does not exist.
A problem may arise where invalidation notices regarding the same object are sent at the same time. In other words, the first and second worker nodes both want to make a change to the same object at the same time. Essentially both worker nodes are now deadlocked and each waiting an acknowledgement from the other that will never occur. As described above each worker node has a set period of time to wait for acknowledgements to come back. After that time period has passed, one of the senders will fail, thus breaking the deadlock. The sender that failed will then get the acknowledgement from the successful sender.
The notice of intent to invalidation and/or acknowledgement scenario described above is called the internal phase of invalidation as all of the listener nodes notified are internal to the cache managers.
The listener of each application that may access the object to be invalidated is also sent notice of the invalidation at 2207. The registration table of each cache manager has entries for those application listeners that need to be notified. For example, Registration Table_1 2125 has entries 2129, 2131, 2133 for Listener_A 2137, Listener_B 2139, Listener_C 2141. In this example, App_A 2119, App_B 2121, and App_C 2123 may access the copy of the local object.
Application listener notice at 2207 typically occurs after the internal phase has completed or concurrent with the internal phase and is initiated by the sender of the internal notice. This external messaging may be either synchronous or asynchronous. Using synchronous messaging, each application listener node sends through the cache manager an acknowledgement message to the first worker node at 2209. Upon receiving an acknowledgement from each application listener, the first worker node invalidates its local copy of the object 2211. For example, the listener nodes for App_A 2137, App_B 2139, and App_C 2141 send an acknowledgement to worker node 2111 through Cache Manager_1 2113 and the messaging service 2103. Upon receiving those acknowledgments the local copy 2107(c) is invalidated.
Using asynchronous messaging, the each application listener node does not send an acknowledgement message and the first worker node invalidates its copy 2211 after the completion of the internal phase.
With the local copies of the object invalidated (or assumed to be) the object may need to be re-created or modified at 2213. Re-creation or modification uses a similar locking construct to that described earlier. This allows for only one worker node or virtual machine of a worker node to re-create or modify the object and thus keeping the object consistent. The earliest worker node to need access to the object will lock the other worker nodes out and re-create or modify the object. This locking of the object has the added benefit in that if the virtual machine working on the object crashes, the lock will be released and another worker node will re-create or modify the object.
For example, in one embodiment of re-create by a worker node the following code is used:
locker.execute("key", new runnable( )){ run( ){ if(cache.get("key" = = NULL){ object new = recreateObject( ); . . . cache.put("key", new); }; }; }
With this code, the virtual machine of the worker node re-creating first sees if the object exists using the object's key. If the object does not exist a null value should be returned. This means that the object needs to be re-created and that the object has been successfully removed. The object is then recreated. Finally, the object is put back into memory using the same key as before. Each application has this snippet of code and only one worker node may execute it at a time. Of course it should be understood that equivalent code snippets may be used with the underlying principles.
In one embodiment, after the object has been re-created or modified, notice of this is sent to all of the worker nodes registered and the basic principles described above apply (i.e, the worker node ensures that everyone knows of the change) as described earlier in the Distributed Cache Architecture section. In one embodiment, this notice of re-creation or modification further includes a copy of the object.
Additionally, if the object to be invalidated is a shared closure in shared memory, the worker node that desires to remove or modify object may use the shared locking mechanism as described earlier. This may eliminate the need for using the messaging service unless the system still requires notification of the change to be made.
The above description described a scenario where only two worker nodes were present and the object to be removed was in one worker node's local memory. However, the same principals are applicable when more than two worker nodes are used. For example, the notice of intent to invalidate 2201 would be sent to all cache manager listeners that were found in the respective registration table. Additionally, the principals are applicable across machines (e.g., in a clustered environment).
As mentioned earlier, the message server of
In one embodiment, the message protocol includes components for object key, region identification (ID), type of message, transportable object, and queue of messages. However, it should be understood that each message may not need to use all of the components.
The object key is the same key that has been described before. For details regarding object keys please see the discussion regarding
In one embodiment, the message is one of three types: internal, remove, or modify. An internal message is a message sent only to "internal" listeners as described above. For example, a notice of intent to invalidate or an acknowledgement of invalidation are internal messages. A remove type message is sent to the invalidation listeners as a part of alerting listeners that an object that had been previously removed has now been recreated. A modified type message is sent to the invalidation listeners to alert listeners that an object has now been modified.
In one embodiment, a serialized version of the object is desired for transmittal. This object is called a transportable object. For example, a storage plug-in may provide this serialized object. The use of serialization will generally make the overall message smaller in size as the entire object is not sent but instead only information need to reconstruct the object is sent. A cache manager that receives a serialized object may reconstruct the object from the serialized object and store it in memory. In alternative embodiment, an object is not serialized but is simply transmitted in its current state.
If the object removed/recreated or modified is in a shared closure, shared memory environment a message may still be sent but may not require that a "copy" of the object be sent as a part of the message. If a message is not sent, each worker node must access the shared closure to get a copy of the object.
In yet another embodiment, an object may be serialized into a database or shared storage as discussed earlier in the Distributed Cache Architecture section. In this case, the message does not contain a transportable object. Each listener receiving the object will instead have its cache manager get the object from the database or shared storage.
At any given time, there may be a need to send several messages through a message server. For example, when a worker node desires to remove a local copy of a shared object it must send notice to each "internal" listener registered with that worker node. This could require several messages without optimization. In one embodiment, several messages may be tied together in a single queue of messages thus reducing the count of messages sent. This allows for one or more larger message to be transmitted instead of several smaller messages. In one embodiment, this larger message is null, or in other words, simply one complete message or this larger message is a linked list of messages. Of course it should be understood that which optimization is chosen may depend on the type of message, size of the transportable object, available bandwidth, etc. From a performance standpoint it is generally better, although not always, to have a larger message as that may eliminate to send several messages tying up the message server. From a consistency standpoint it is generally better to have several smaller messages.
Another possible optimization, available in one embodiment, is the use of wildcards. A wildcard allows for a single message to be sent to the message server that may address a group of related items. For example, A*, where * is the wildcard would address all items that begin with A including A1, A2, and Ab. In one embodiment, upon receiving a message with a wildcard the message server will create several smaller messages to distribute appropriately. For example, if a particular worker node only requires learning about A1 then only the information about A1 is sent to that worker node from the message server. In another embodiment, the message server simply routes the message as sent to it by a worker node without further processing on the message. In this embodiment, each worker node receiving the message processes the message according to what it needs to know and discards the rest. For example, if a worker node only needs to know about A1 and Ab it discards the information about A2. In one embodiment, wildcards are only used with remove type messages.
Yet another possible optimization, available in one embodiment, is the use of patterns or properties that may be associated with objects. For example, an object may have the property of language type=English. A message may utilize that property to only address objects that have that particular language type.
An exemplary of message that may be sent using the protocol will now be described. This message uses the key "BUTTERS", has a region ID of local cache, is an internal type message, and is a null message. A cache manager that receives this message will hash the key "BUTTERS" to determine the address in local cache that the object associated with the key "BUTTERS" is stored. Since this is an internal message it may then invalidate the object. In this particular example, the message is null because only one message needed to be sent (not trying to address more than this one object).
Of course it should be understood that the protocol and embodiments described above may be utilized in systems that do not have a message server.
In enterprising applications, it is desirable to have both consistency and flexibility with respect to creating and configuring a cache. More specifically, each region of cache may need to be configured independent of the others. For example, the JNDI service may not need to utilize as many resources or even different resources as an application that is running.
Typically each service and application requires different amounts of cache storage. For example, an application may need to access and store only one (1) object in cache thereby needing less space than an application needing to access and store four (4) objects in cache. Therefore, the cache space allotted to each application or service is usually different.
With respect to the worker node 2301 and memory 2309 of
In one embodiment, a configuration structure is created and maintained for each application of the worker node and for the services supported. This configuration structure stores the parameters by which the service or application is defined. Typically, a configuration structure is built using property sheets for each region that is configured.
The following is an exemplary document type definition ("DTD") that describes how to create a configuration structure for the J2EE services/regions (e.g., JNDI, RMI, etc.) and is the generic template for each application/service. It should be noted, however, that many of the specific formats employed within the DTD are not required for complying with the underlying principles of the invention.
cache-configuration.dtd <!ELEMENT cache-configuration (global-configuration, regions)> <!ELEMENT global-configuration EMPTY> <!ATTLIST global-configuration TOTAL_SIZE CDATA #REQUIRED > <!-- Global size of the cache. For example, the number of megabytes of memory available to use as cache. --> <!ELEMENT regions (region-configuration*)> <!-- Each region of cache is definable. In other words, each service and application may get its own region of cache. --> <!ELEMENT region-configuration (count-thresholds, size-thresholds, scopes, plug-ins, principal, direct-invalidation, logging-mode, synchronous, weight)> <!-- Parameters that dictate the configuration of each region. Count-thresholds - this is an input for the eviction plug-in (as discussed earlier). Size-thresholds - this is an input for the eviction plug-in (as discussed earlier). Scopes - may either be local (single worker node), instance (shared memory), or cluster-wide (across machines). Plug-ins - eviction and storage plug-ins (as discussed earlier). Principal - class name of a region. Direct-invalidation - Boolean flag. If set as true, then the shared object that is to be invalidated is notified of its own invalidation (see earlier discussion of modifying a shared object). Logging mode - Boolean flag. If set true, transactions are logged. Synchronous - Boolean flag. If set true, then the second wave of messages is sent synchronously (see earlier discussion of modifying a shared object). Weight - relative weight given to a region (to be discussed in detail later). --> <!ATTLIST region-configuration name CDATA #REQUIRED enabled CDATA #REQUIRED > <!-- Name of the region defined and if it is enabled. --> <!ELEMENT count-thresholds EMPTY> <!ATTLIST count-thresholds start CDATA #REQUIRED upper CDATA #REQUIRED critical CDATA #REQUIRED > <!-- Three numbers used by the eviction policy plug-in - a start value, upper value, and critical value. --> <!ELEMENT size-thresholds EMPTY> <!ATTLIST size-thresholds start CDATA #REQUIRED upper CDATA #REQUIRED critical CDATA #REQUIRED > <!-- Three numbers used by the eviction policy plug-in - a start value, upper value, and critical value. --> <!ELEMENT scope EMPTY> <!ATTLIST scopes region CDATA #REQUIRED > <!-- Three numbers used by the eviction policy plug-in - a start value, upper value, and critical value. --> <!ELEMENT PLUGINS (storage-configuration, eviction-configuration)> <!ATTLIST plug-ins storage CDATA #REQUIRED eviction CDATA #REQUIRED > <!ELEMENT storage-configuration (property*) <!ELEMENT eviction-configuration (property*)> <!-- Type of storage or eviction policy respectively. --> <!ELEMENT principal (#PCDATA)> <!ELEMENT direct-invalidation (#PCDATA)> <!ELEMENT logging-mode (#PCDATA)> <!ELEMENT synchronous (#PCDATA)> <!ELEMENT weight (#PCDATA)> <!ELEMENT property EMPTY> <!—See above discussion regarding these elements. This is the definition of those elements. --> <!ATTLIST property key CDATA #REQURIED value CDATA #REQURIED >
An eXtensible Markup Language (XML) document may be created from the DTD as is known in the art. Both file types are easily understood and maintainable by a user. The DTD defines the building blocks of an XML document and the document structure with a list of elements. A DTD is declarable inline in a XML document or as an external reference.
An exemplary XML document created from the above DTD for the JNDI service is illustrated in
The scopes region 2411 determines which type of system is being configured. Exemplary regions are local (e.g., single worker node), instance (e.g., more than one worker node of a physical machine that shares memory), and cluster-wide (e.g., across physical machines).
Line 2415 begins the definition of the storage plug-in used in the region. The value "DBStorage" and "BackendStoragePlugin" indicate a write-through process in which an object is persisted into deeper storage (e.g., a database) in addition to the normal "CombinatorsStorage" (e.g., local memory). The eviction plug-in configuration 2417 shown is the "recentlyUsedPeriod" or the LRU 617 as described earlier. The period is set at 5000 ms. Other eviction plug-in configurations (e.g., LFU and FIFO) have already been described.
The principal of line 2419 is used with respect to the isolation of the cache region. It serves as an identifier mapping between the cache region and cache user. Typically, the principal is unique. The principal is a class name that is used to identify the user that has the right to use a particular cache region. The class name is chosen so that it exists in the stack of traces of the calls in the application or service that invokes the "getCacheRegion" in the cache region factory. The stack trace is inspected for the principal, if the principal is missing (null) then the application or service trying to access this region of cache is not authorized and will not be granted access.
Direct-invalidation is decided at 2421. As discussed before this is a Boolean flag value. If set as true, then the shared object that is to be invalidated is notified of its own invalidation (see earlier discussion of modifying a shared object). The logging setting (Boolean flag) is set at 2423. If set true, transactions are logged. In this illustration the second wave of messages for object invalidation is synchronous as indicated by the "TRUE" Boolean flag of 2425.
Of course more than one region may be defined. At line 2429 the RMI service definition begins.
Line 2427 gives the relative normalized weight of the cache region JNDI. Weight is a number that represents the relative amount of memory that will determine the size-thresholds for the region. This amount of memory is calculated using the total cache memory for all caches and all cache region weight property. Generically, each region is defined relative to the others and each region does not know how much space the other regions use. It is important to note that relative weight is not the equivalent of using percentages.
For example, consider the local flavor embodiment of
"R" is the total number of cache regions (number of applications and services running). "Total size" is the total cache space. "RW" is the relative normalized weight of the service or application. The sum of all cache region weights will be 100 (meaning 100% of "total size").
For example, consider a scenario where the total size is 60 MB, the weight is 100, and the threshold values for two services and an application are 102,400; 768,000; and 102,400 respectively. The space allotted to the application with a RW of 102,400 is 6.3 MB as calculated below.
Equation (1) is applicable in a shared read only embodiment, with only shared memory, as all of the services and applications use the same total size of memory and can be weighted against each other. In a shared flavor embodiment, with local and shared memory, each local flavor determines its local regions.
In another embodiment, weight is not used and instead each region declares a set amount cache to occupy. The total amount from all of the regions cannot exceed the size of the memory.
The second utility is a deploy container for the deploy service 2511 in the J2EE engine. It is registered in the deploy service 2511 and listens for a cache configuration file that will be included in an application archive 2509. The application archive contains information regarding each application that may be run on the system. In an alternative embodiment, each application interfaces with the deploy service 2511 individually. The deploy service passes the XML to the cache management service 2513. The cache management service serves as a proxy to the Cache Manager 2515. Only the trusted code of the cache management service is allowed to invoke these methods of the Cache Manager 2515. The Cache Manager 2515 uses the same implementation as the offline deploy tool 2503 to transform the information from the applications into property sheets 2517 for the applications. The configuration structures 2507, 2517 may be stored in a persistent database (not shown).
If a property (plug-in configuration, thresholds, weight, etc.) is not specified in the property sheets 2517 of the applications, they may inherit properties from the global configuration structure 2507 through the use of a parent concept. A parent is the name of an inheritable region configuration. For example, an application with the parent JNDI will use the values from the JNDI region as defined in the global configuration structure 2507 to fill the missing parts of its property sheet.
In one embodiment, the Cache Manager 2515 is also capable of exporting an XML file out of created property sheets 2517. This is really helpful in the development phase of services, because it provides an easy way to configure (using GUI and property sheets) and have a deployable XML that is readable and structured.
The Cache Manager 2515 dynamically reconfigures the cache regions upon the start or stop of an application or service. The threshold values change upon starting or stopping of an application or service and therefore change the allotment of space in the cache region using the earlier describing relative normal weighting scheme.
The GUI 2721 uses the offline configuration manager to get the needed sub-configurations and reads/writes through it to them. Import 2703 and export 2705 functionality is provided which uses the same utility classes as offline deploy and cache manager to parse XML's. The DTD is the same that is used during deploy.
Through importing and exporting the GUI 1021 may extend the property sheets of the configuration structures 2507, 2517 with new properties and build up an XML from them.
In one embodiment, the GUI 2721 interfaces with the cache manager 2515 instead of the configuration structures.
Typically, systems with good performance and reliability rely on a combination of coherence and isolation. Coherence provides consistency. For example, the earlier discussion and embodiments of messaging help to provide consistency to shared objects of a system.
Isolation provides exclusivity of operation. There are two types of isolation: 1) isolation between different applications and 2) isolation between different threads or virtual machines of the same application.
Isolation between different applications is intrinsic if each application receives different memory regions (including cache) with different names. With this approach no collisions can occur between applications because the applications simply do not require all of the same resources.
Isolation between threads or virtual machines of the same application may be provided by using the previously described locker construct and/or synchronization. If both the application and cache manager support the locker construct it should ensure that each operation is executed exclusively of all others. Effectively operations are serialized. One way to do that is through atomic operations where either every step within a transaction completes or none of them do.
Processes taught by the discussion above may be performed with program code such as machine-executable instructions which cause a machine (such as a "virtual machine", a general-purpose processor disposed on a semiconductor chip or special-purpose processor disposed on a semiconductor chip) to perform certain functions. Alternatively, these functions may be performed by specific hardware components that contain hardwired logic for performing the functions, or by any combination of programmed computer components and custom hardware components.
An article of manufacture may be used to store program code. An article of manufacture that stores program code may be embodied as, but is not limited to, one or more memories (e.g., one or more flash memories, random access memories (static, dynamic or other)), optical disks, CD-ROMs, DVD ROMs, EPROMs, EEPROMs, magnetic or optical cards or other type of machine-readable media suitable for storing electronic instructions. Program code may also be downloaded from a remote computer (e.g., a server) to a requesting computer (e.g., a client) by way of data signals embodied in a propagation medium (e.g., via a communication link (e.g., a network connection)).
A high-level language virtual machine (e.g., a Java Virtual Machine, a Parrot virtual machine, etc.) or interpreter (e.g., Common Language Runtime ("CLR")) runs as an application program on top of a computer operating system and converts source code from a high-level language (e.g., Java, C#, VB.NET, Python, C, C++, J#, APL, etc.) into an intermediate form (e.g., Java byte code, Microsoft Intermediate Language, etc.). This intermediate form is then converted to machine level code by compiling the intermediate code at run-time (e.g. JIT compiler), interpreting the intermediate code, or a combination of both. The end result is machine level code that is understandable to a specific processor(s) of a processing core of a computer(s). The use of a virtual machine or an interpreter allows a developer to write computer programs that run independently of platforms, languages, and hardware. For example, any program developed under the J2EE standard can run on any computer where a corresponding Java Virtual Machine is installed and any .NET program may run on any computer with .NET installed.
There are many different implementations of the Java Virtual Machine (e.g., those offered by Sun, Oracle, BEA, IBM, SAP, and etc.) and interpreters (e.g., those offered through .NET, Mono, dotGNU, etc.), however these different implementations work in the same general fashion as discussed above. It is believed that processes taught by the discussion above can be practiced within these various software environments.
Throughout the foregoing description, for the purposes of explanation, numerous specific details were set forth in order to provide a thorough understanding of the invention. It will be apparent, however, to one skilled in the art that the invention may be practiced without some of these specific details. For example, while the embodiments of the invention described above focus on the Java environment, the underlying principles of the invention may be employed in virtually any environment in which objects are managed. These environments include, but are not limited to J2EE, the Microsoft .NET framework, and the Advanced Business Application Programming ("ABAP") standard developed by SAP AG.
In the foregoing specification, the invention has been described with reference to specific exemplary embodiments thereof. It will, however, be evident that various modifications and changes may be made thereto without departing from the broader spirit and scope of the invention as set forth in the appended claims. The specification and drawings are, accordingly, to be regarded in an illustrative rather than a restrictive sense.
|Cited Patent
|Filing date
|Publication date
|Feb 26, 1993
|Jul 19, 1994
|Schlumberger Technology Corporation
|Communications protocol for digital telemetry system
|Feb 5, 1998
|May 16, 2000
|Oak Technology, Inc.
|DVD system for seamless transfer between titles on a DVD disc which minimizes memory consumption
|May 28, 1999
|Nov 29, 2005
|William H. Gates, III
|Method and system for property notification
|Apr 23, 2004
|Oct 28, 2004
|Oracle International Corporation
|Partitioned shared cache
|Citing Patent
|Filing date
|Publication date
|Sep 14, 2006
|May 19, 2009
|International Business Machines Corporation
|Method and apparatus for space efficient identification of candidate objects for eviction from a large cache
|Jun 12, 2006
|Nov 24, 2009
|Sap Ag
|Complex data assembly identifier thesaurus
|Nov 17, 2006
|Feb 2, 2010
|Sun Microsystems, Inc.
|Cache coherence protocol with write-only permission
|Mar 12, 2007
|May 18, 2010
|Citrix Systems, Inc.
|Systems and methods of freshening and prefreshening a DNS cache
|Mar 12, 2007
|Aug 24, 2010
|Citrix Systems, Inc.
|Systems and methods of revalidating cached objects in parallel with request for object
|Mar 12, 2007
|Oct 5, 2010
|Citrix Systems, Inc.
|Systems and method of using HTTP head command for prefetching
|Mar 12, 2007
|Oct 11, 2011
|Citrix Systems, Inc.
|Systems and methods of dynamically checking freshness of cached objects based on link status
|Mar 12, 2007
|Dec 6, 2011
|Citrix Systems, Inc.
|Systems and methods of providing a multi-tier cache
|Mar 12, 2007
|Jan 24, 2012
|Citrix Systems, Inc.
|Systems and methods of providing security and reliability to proxy caches
|Jul 21, 2009
|Sep 25, 2012
|Citrix Systems, Inc.
|Systems and methods of prefetching objects for caching using QoS
|Dec 9, 2009
|Jan 29, 2013
|Citrix Systems, Inc.
|Systems and methods for domain name resolution interception caching
|Oct 26, 2007
|Jun 18, 2013
|Netapp, Inc.
|System and method for utilizing a virtualized compute cluster as an execution engine for a virtual machine of a storage system cluster
|Mar 12, 2007
|Aug 6, 2013
|Citrix Systems, Inc
|Systems and methods of prefreshening cached objects based on user's current web page
|May 13, 2005
|Oct 8, 2013
|Microsoft Corporation
|Transparent code
|May 3, 2010
|Nov 5, 2013
|Citrix Systems, Inc.
|Systems and methods for establishing a cloud bridge between virtual storage resources
|Jul 13, 2010
|Dec 24, 2013
|Citrix Systems, Inc.
|Systems and methods of revalidating cached objects in parallel with request for object
|May 19, 2005
|Dec 24, 2013
|Oracle International Corporation
|Liquid computing
|Sep 18, 2007
|Feb 4, 2014
|Oracle International Corporation
|Mobile applications
|Mar 12, 2007
|Apr 15, 2014
|Citrix Systems, Inc.
|Systems and methods of using the refresh button to determine freshness policy
|Jan 27, 2012
|Jul 14, 2015
|Oracle International Corporation
|Push replication for use with a distributed data grid
|Feb 28, 2012
|Aug 4, 2015
|Hewlett-Packard Development Company, L.P.
|Persistent volume at an offset of a virtual block device of a storage server
|May 19, 2005
|Feb 16, 2006
|Patrick Paul B
|Liquid computing
|May 13, 2005
|Nov 16, 2006
|Microsoft Corporation
|Transparent code
|Oct 26, 2007
|Apr 30, 2009
|Brian Pawlowski
|System and method for utilizing a virtualized compute cluster as an execution engine for a virtual machine of a storage system cluster
|Sep 18, 2007
|Dec 3, 2009
|Bea Systems, Inc.
|Mobile applications
|Jan 26, 2012
|Nov 1, 2012
|Oracle International Corporation
|Event distribution pattern for use with a distributed data grid
|Jun 15, 2011
|Dec 20, 2012
|Microsoft Corporation
|Two-phase eviction process for file handle caches
|Sep 3, 2010
|Jun 27, 2013
|Adobe Systems Incorporated
|Reconstructable digital image cache
|Feb 28, 2012
|Aug 29, 2013
|Timothy Reddin
|Persistent volume at an offset of a virtual block device of a storage server
|Aug 7, 2012
|Feb 13, 2014
|Dell Products L.P.
|System and Method for Utilizing a Cache with a Virtual Machine
|Mar 12, 2008
|Sep 18, 2008
|Citrix Systems Inc
|Systems and methods for cache operations
|U.S. Classification
|International Classification
|Cooperative Classification
|European Classification
|Aug 29, 2005
Owner name: SAP AG, GERMANY
Free format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNOR:PETEV, PETIO G.;REEL/FRAME:016673/0229
Effective date: 20050801


text:
Hello and welcome to Mind-N-Body Fitness. We are a Nationwide service provider of Private, Community and Corporate Fitness.
Mind-N-Body Fitness will partner with you, teach you, train you, and keep you accountable.. Our Fitness Professionals can help you to change your life, regardless of what your fitness goals are and where you are located..
Your browser does not support IFRAME's.
New Fitness Book Coming Out - 4th Quarter 2011!"Real Deal Fitness - FAQs, Quick Tips and Philosophies" Written by ZeZor DeForce aka Trainer Z.
Click for more details..
"Healthy & Fit - You Can Be It" Newsletter!Download the current issue of my 4 page, full color, complimentary fitness newsletter.Click To Download Your Copy..
"Real Deal Fitness" Article and Content Writing By Trainer Z!
Does your business or organization publish a newsletter, magazine, newspaper or other periodical?
Would you like to provide your readership with motivating fitness content that they can use to help enrich their lives?
Please read on to learn more..
Client Testimonials!
Words of appreciation from a few of the many clients that I have personally been blessed to work with..
Testimonial from Irene G:
"I have had a personal trainer for over 27 years; the last two and a half years I have been fortunate to meet Zor and work with him from my home. It was a new and refreshing experience to work with this friendly, fit and knowledgeable trainer. I thought I was fit when I began but he has helped me reach a higher fitness level that I didn't think possible. I am going to be 67 years old and because of my training with Zor, I was able to be featured in the Westchester Magazine article titled Beautiful Bodies.
I loved working with Zor, always encouraging, always watching my form to avoid injury. His countdown approach to doing sets was major because I was able to workout according to how I felt each day. I love him as a person and trainer. How fortunate I am to know him."
Testimonial from Bettina S:
"Over the years I have tried all kinds of exercise classes, from aerobics to yoga to pilates but I always managed to injure myself. When I met Zor, I was thrilled that he offered personal training sessions which I took with my 86 year old mother, together we worked on precisely what each of our needs were, we both needed to build up strength in our legs and arms but at different levels. Zor found a way to teach us at the same time, making sure we both got enough attention and challenge. Zor made exercising fun."
Testimonial from Debbie G:
"I have sporadically exercised through the years, though at age 50 I was introduced to ZeZor DeForce. I trained with Zor in a group class for over 2 years and maintained a daily workout schedule of 5 days a week. Even though I was working out within a group, it felt as though I was being trained personally, one-on-one. Zor knows the whole-person approach to fitness, which is engaging the mind, body and spirit."
Testimonial from Sara B:
"About three years ago, I became a client of Mind N Body Fitness, a new fitness program which was started in Dobbs Ferry, NY by Trainer Z. It was a totally new experience for me and a very positive one. Most of my classes were with Trainer Z who worked us hard but made it fun at the same time. The best thing about the classes besides achieving positive body results, was Trainer Z's countdown method which allowed each person to perform at his/her own pace. Each routine was timed so that it was easy to assess how much energy to expend at one time. All of Trainer Z's classes were truly total body workouts but varied; i.e., strength and motion, awesome abs and kickboxing, which was my favorite."
Testimonial from Jacquelyn J:
"For me, the group workout classes created by Trainer Z, the owner of Mind N Body Fitness offers the perfect workout selection. There's a class to fill every need - weight training, cardio, core strengthening, stretching and more. Each person is encouraged to work at his own pace, with motivation to improve provided by the attentive instructors."
Testimonial from Joy M:
"I have been a member of Mind N Body Fitness in Dobbs Ferry, NY since September, 2006. Trainer Z has created a unique exercise regimen which focuses on the mind and body connection.
The classes are small and intimate, allowing the instructors to focus on helping clients achieve the best results possible and making sure that we understand the correct form. The workouts are fun and target the entire body. Because the classes are small, it is like having a personal instructor who can concentrate on each client giving us individual attention. Each person can go at his or her own pace and not feel that they have to keep up with everyone else in the class.
Each day offers a different workout and I have noticed a change in my body shape and have become more agile and much stronger than what I was when I first started. I also enjoy the camaraderie of the other clients who have become my friends and we all encourage each other to do our best. I look forward to going to class every time."

subset: commoncrawl


text:
Affluent Lifestyle Guide
You might like Best Runway Models >
Hi 2 All members,
Look for premier Concierge ?
Warm regrads, Gilles BERTHET, CEO of World ART Associates > http://gb.worldartassociates.comhttp://www.worldartassociates.com // email@example.com // Skype.com: lliges4uFrance: +33 (0...Go to Story
Read stories, check out member reviews, explore photo galleries and answer community questions.
Upload your own stories and post personal reviews. Upload your own photos and ask your peers their opinion.
Enhance your standing in the luxury world by making your voice heard.


text:
September 29, 30 and October 1
The San Francisco Symphony will honor the San Francisco Waldorf School music department at upcoming performances, Thursday, September 29th through Saturday, October 1st by naming us in the concert program notes. This was made possible through a generous donation by high school parents Rick and Kim Beleson.
The tribute performances include the following pieces:
MOZART: Symphony No. 35 in D major, K.385, Haffner
ADÈS: Polaris: Voyage for Orchestra
STRAVINSKY: Petrushka (1947 Version)
To learn more about the program or to purchase tickets, please visit the SF Symphony website:


text:
"We have taken a sharp focus to launch the products and brands that consumers are moving toward at the most affordable prices," said Kevin O'Connor, vice president and general merchandise manager, Wal-Mart Electronics. "The Skype hardware and pre-paid cards are a great fit with Wal-Mart because they offer long-term money-saving solutions at the right time for many customers -- parents, grandparents, college students and military families."
Wal-Mart will sell a $8.85 calling card that will provide customers with unlimited calling in the United States and Canada for three months, becoming the first and only retailer to offer such cards.
The addition of Skype Internet communications products to Wal-Mart stores comes at a time when Voice over Internet Protocol (VoIP) adoption among U.S. households is growing rapidly. According to the Telecommunications Industry Association, 9.9% of all landlines in the U.S. were VoIP lines in 2006, and this will rise to 34.1% by 2010. In addition, Skype is the number one software-based VoIP application in the U.S. by market share, according to a March 2007 report by In-Stat.
This is a huge win for Skype, with an already large user base of 196 million registered users around the world, the deal will bring many Wal-Mart shoppers not familiar with Skype to give it a try and help drive usage among the mainstream public.


text:
Comment guidelines: Please be respectful to other people when making comments on this page. Bullying and abuse will not be tolerated and may result in your account being banned. Due to feedback from our user community, comments are now only available to registered users.
Jis Desh Mein Ganga Rehta Hai (English: The Country Where Ganga Lives") is 2000 Hindi film directed by Mahesh Manjrekar and starring Govinda and Sonali Bendre as leads. It is a remake of Dada Kondke's blockbuster Marathi film Eakta Jeev Sadashiv released in 1972.
Register to update information, save favorites, post photos, news stories and comments.


text:
The College has developed the following protocol for the collection of information from human populations through the use of online forms or surveys by members of the campus community. The purpose of these guidelines is threefold:
- Provide guidance to developers of online forms and surveys, and to the technical staff that support them, concerning compliance with ethical and legal rules governing research and data collection from human subjects.
- Coordinate technical support for the development, distribution, and analysis of online forms and surveys.
- Consolidate and coordinate online forms and surveys so as to avoid over-surveying.
Supported tools for administering online forms and surveys
The college currently supports two software tools for conducting online forms and surveys. Both tools are themselves web-based.
Accounts with one of these tools generally do not limit the number of surveys or forms users can develop and conduct. However, users should review the following guidelines in light of each survey or form-based data collection project.
Legal / ethical policies governing data collection
The College's Institutional Review Board (IRB) is charged with protecting the welfare, rights, and privacy of all persons participating in research – of which the web-based surveys and forms covered in this protocol are an example. The IRB reviews research activities with human subjects – including web-based forms and surveys – in light of this charge. Data collection that is conducted solely for the purposes of educational or program improvement is usually considered exempt from IRB review but if, after reviewing the College IRB's website you have any questions about whether a review is required for your project, please contact David Consiglio (x6534, email@example.com).
Examples for deciding whether your project requires full IRB review. This list is for guidance only, and does not replace IRB review itself. It applies to surveys for research or opinion polling as well as forms used by administrative offices. Click here for a link to Bryn Mawr College's Institutional Review Board.
Require IRB review:
Examples that do not require IRB review:
- attitudes or behavior which, if known outside the research, might harm the respondent's reputation
- information about mental or physical health
- participation in illegal activities (including alcohol or drug use)
- personal or private information (e.g., annual income, sexual behavior, student grades, financial aid status)
- information that is normally confidential (e.g., social security number, criminal background information, information about health history, religious or political background)
- form asking respondents to RSVP or register for an event
- form asking students to register for classes or apply to study abroad
- form asking respondents to select a T-shirt style or make a meal selection for an event.
Technical / expert support for your online form or survey
Once you have a user account for one of these tools, you will find they are easy to use, and that the related help menus and guides will address many technical questions for simple forms and surveys. However, we encourage you to think through the entire data collection process before launching your form or survey, as this will ensure that the data you collect are valid and usable. Contact David Consiglio (x6534 email@example.com) or Richard Barry (x6532 email@example.com) for expert advice on implementing good surveys and forms.
If the information you will collect will need to be integrated with existing databases such as People Soft or Financial Edge, either now or in the future, please contact the help desk for assistance with your project.


text:
Please welcome the newest members of the Baseball Bloggers Alliance:
- Kevin Lochner of Hattaway's Moustache joins the Minnesota Twins Chapter.
- Jeff Louderback of BoSox Banter joins the Boston Red Sox Chapter.
- Jonathan Hacohen of MLB reports joins the General Baseball Chapter.
The BBA now has 309 member blogs as of June 28th, 2011. Be sure to visit the Membership Directory to check out all of the great sites in the Alliance.


text:
Since the 1980s, hot water condensing boilers (CB) have…Continue
Posted on May 29, 2013 at 9:31am — 15 Comments
"Americans can always be counted on to do the right thing...after they have exhausted all other possibilities." Winston Churchill
How much does it cost to perform a deep-energy retrofit at a 100-year-old single-family home? Thanks to a recent study in Utica, New York, we now know the answer: about $100,000.…Continue
Posted on January 3, 2013 at 1:44pm — 32 Comments
Hi Igor,
Welcome to Home Energy Pros! Feel free to join the conversation in the Forum and Groups. And share your energy efficiency photos, videos and upcoming events. If you're blogging about home performance, this is the place for you!
Don't forget to upload your profile photo. And add your location on our Member Map!
Diane, HEP Moderator
© 2015 Created by Lawrence Berkeley National Laboratory.