Title of Invention


Abstract The present invention relates to a method for updating cached copies of a data item. Servers (110, 112, 113) in a network cluster (104) can each store a copy (116, 118, 120) of a data item (122) in local cache, providing read access to these copies through read−only entity bean. The original data item (122) in the database (108) can be updated through a read/write entity bean on one of the cluster servers. The cluster server has access to an invalidation target, which contains identification information relating to copies (116, 118, 120) of the data item stored on servers in the cluster. Once the read/write bean updates the data item in the database, an invalidate request can be sent or multicast to all cluster members, or to any read−only bean or server contained in the invalidation target. Each server or read−only bean receiving the request knows to drop any copy of the data item in local cache, and can request a current copy of the data item from the database.
[0001 ] This application claims priority to the following applications which
are incorporated herein:
10002| U.S. Provisional Patent Application No. 60/335,633, filed October
by Dean Bernard Jacobs and Rob Woollen.
[0003] U.S. Patent Application No. 10/212,382, filed August 5, 2002,
Dean Bernard Jacobs, Rob Woollen and Seth White.
[0004] A portion of the disclosure of this patent document" contains
material which is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent document of the patent disclosure, as it appears in the Patent and Trademark Office patent file or records, but otherwise reserves all copyright rights whatsoever.
[0005] The following applications are cross-referenced and incorporated
herein by reference:

[0006] U.S. Provisional Application No. 60/305,986 entitled "DATA
REPLICATION PROTOCOL," by Dean Bernard Jacobs, Reto Kramer, and Ananthan Bala Srinvasan, filed July 16, 2001.
[00071 U.S. Provisional Application No. 60/316,187 entitled "CLUSTER
CACHING WITH CONCURRENCY CHECKING," by Dean Bernard Jacobs and Rob Woollen, filed August 30, 2001.
[0008] The invention relates generally to a system and method for storing
data on a network.
(0009] When a data item is stored in a single database or data store that is
accessible over a network, it is often the case that multiple servers or clients will require access to that data item. Traditionally, this requires a hit to the database each time the data item is accessed. Each hit to a database is relatively resource intensive and relatively inefficient.
[00] 0J One way of overcoming some of the efficiency and scalability
problems is to store a local copy of the data item in cache memory. A server or
client can then use that local copy if future access to the data item is needed. This
process may be appropriate and efficient for data items that never change, but
problems can arise when a data item is updated in the database.
[0011 ] If a data item in the database is updated, a copy of that data item
stored in a local cache on the network will be different than the item in the database, as the cache will not automatically receive the update. The problem intensifies when there are local copies on multiple servers and/or .clients on the

network. Since each of these local copies is created at a different time, there can
be multiple versions of the data item on the network. If a user tries to update or
view the data item, the copy accessed by the user may not be current and correct.
[0012] Such a problem with data latency can cause serious problems for
applications that require near real-time accuracy, such as web sites that offer "real time" stock prices. Such an application might utilize a database table having at least two columns, one column containing stock symbols, which can be used as primary keys for the table, and one column containing the current price of each stock. In such an application, most of the activity involves users accessing the site and reading the current stock values. There is typically also activity involving back-end applications or systems that come in periodically, such as once every minute, with updated stock prices. These back-end systems need read/write access to the database in order to update the data.
I0013J Most access to the system will be read only. For these read-only
users, the system can cache data to provide faster access. The system can update the cached information periodically, such as every fifteen minutes. In such a "read-mostly" situation, however, it may be preferable to give a user the most recent data. A fifteen minute delay in providing accurate information may be undesirable for many applications. It is typically desirable to give users information that is as accurate as possible.
[00H| One way to ensure that users get accurate information, or at least
information that is current with data stored in the database, is to pull the
information from the database for each request instead of reading a cached copy.
This can be very expensive for many applications, as a hit to a database is much
more time and resource intensive than reading a value from memory.
[0015] For people updating the data in the database, it may be desirable to
wrap as many updates as possible into a batch transaction in order to improve performance. Wrapping updates into a single transaction also ensures that either

all the updates occur or none of the updates occur. Problems arise, however, in how to update cached copies for each item updated in a transaction.
[0016] A system and method are included for updating a copy of a data
item stored in local cache on at least one server in a network cluster. Identification information is provided to a read/write bean stored on a server in the cluster. The identification information relates to any server in the cluster that contains a read¬only bean and a copy of the data item in local cache. A read-only bean provides read access to the local copy of the data item. The original data item is stored in a network database, and is updated using the read/write bean. When the data item is updated by the read/write bean, an invalidate request can be sent or multicast from the server containing the read/write bean to- the entire cluster, or can be sent to any server or read-only bean identified by the identification information having a local copy of the data item. Any local copy of the data item can then be dropped in response to the request. A current copy of the data item can be read from the database and stored in local cache.
(0017] Figure 1 is a diagram of a system in accordance with one
embodiment in accordance with the present invention.
[00] 8] Figure 2 is a diagram of a system in accordance with the
embodiment of Figure 1.
10019] Figure 3 is a diagram of an alternative embodiment of the system
of Figure 1.

[0020] Figure 4 is a flowchart for a method in accordance with one
embodiment of the present invention.
[0021] Figure S is a flowchart for a method in accordance with another
embodiment of the present invention.
[0022] Figure 6 is a diagram of a system in accordance with another
embodiment in accordance with the present invention.
[0023] In order to maintain consistency among items distributed on a
network, a system in accordance with the present invention can take advantage of beans, or JavaBeans. A bean is basically a framework for components that can be added to a server to extend functionality. One embodiment utilizes two types of beans, "read-only" entity beans and "read/write" entity beans. An entity bean is a bean that is persistent, allows shared access, has primary keys, and can participate in relationships with other entity beans. Each entity bean can have an underlying table in arelational database, with each instance of the bean corresponding to arow in that table.
[0024] A read-only bean is a bean that can be cached on a server, such as
an enterprise JavaBean that resides in a network cluster. The read-only bean can provide read access to any server in the cluster, as well as to any client inside or outside of the cluster. The read/write bean is transactional, residing on a server in the cluster and providing cluster servers with read/write access to a network database. The read-only bean deals with data in local cache on a cluster server. The read/write bean deals with information in a database.
[0025] One way to address the concurrency of information in the cache and
in the database is to associate a timeout value with each read-only entity bean. For example, a read-only bean can be deployed with a default cycle of ten minutes.

After each period of ten minutes passes, the read-only bean goes back to the database and reads the current value. This approach can work well for certain applications, such as those applications with values that change at a regular interval.
(0026] There may be applications, however, which have data that changes
very infrequently. When this data changes, users may want to know about the
change as soon as possible. Since the data does not change very often, it is
tempting to set a long read cycle time in order to conserve resources. This can
have the undesirable effect, however, of creating latency issues with the data, as the
resultant delay in updating the data can be almost as long as the cycle time,
depending on the point in the cycle at which the update occurs. For such
applications, it is desirable that the data accessible by a read-only user is updated
as soon as possible after the data is the database is updated.
(0027] One system in accordance with the present invention provides an
interface, exposed by a read-only bean. The interface allows a user or application to tell the system to drop a cache, or "invalidate" a cache, when the user updates a data item or is aware of an update. This interface shall be referred to as a "CachingHome," as an entity bean typically has a "home" or factory that creates it. CachingHome can have three methods on it, and be coded as follows:
package weblogic.ejb;
public interface CachingHome {
public void invalidate(Object pk) throws RemoteException;
public void invalidate(Collection pks) throws RemoteException;
public void invalidateAllO throws RemoteException;

[0028] The method invalidate{Object pk) lets a user invalidate data
associated with a particular primary key in a database or data table. The method invalidate(Collection pks)lets a user invalidate data for a collection or group of keys. The method invalidateA110 allows a user to invalidate data for all keys in the database table. These invalidate methods allow a user to ensure that values are stored in local cache until a programmer, application, user, or system says otherwise.
[0029] One such method 300 is shown in the flowchart of Figure 5. A
copy of a data item is stored on at least one server in a network cluster 302. The
data item can be updated in the database using a read/write bean on one of the
cluster servers 304. An invalidate request can then be initiated using an interface
of a read-only bean located on one of the servers, the request being sent to any
server containing a local copy of the data item 306. Any copy of the data item can
then be dropped from a server receiving the request 308.
[0030] In a system 100 with a network cluster 104, such as is shown in
Figure 1, it is possible that a copy of a value 122 stored in a database 108 is cached on each server 110,112,114 in the cluster 104. If a client 102 contacts server 110 through the network 106 and requests that server 110 invalidate a given key, such as by making the request "invalidate (Key)," it is easy for server 110 to drop its cached copy 116 of the value 122 or values associated with that key. A problem exists, however, in how to get servers 112 and 114 to drop their cached copies 118, 120 as well.
10031] One embodiment allows server 110 to drop a copy 116 in local
cache when it receives an invalidate request 124 from the client 102, as shown in Figure 2. After dropping the copy 116 from local memory, server 110 can send a message 126 on multicast to the other servers 118,120 or read-only beans in the cluster 104 to drop the copy of the value in local cache. Multicast is a technique

for sending a packet of information or a message from one server, or source, to other servers without having any unnecessary packet duplication, as one packet is sent from the source and replicated across the network as needed. This approach allows each server to drop the cached value when the value in the database is updated.
[0032] Figure 6 shows another system which includes multiple clients 402
and multiple databases 416 in communication with the network 404. A data item 418 is stored in one of the databases 416. A copy 420 of the data item is stored in a cluster server 406 of cluster 408. There are two copies 422 stored in cluster servers 422 of cluster 412, as well as a copy 424 on server 414, which is not contained in any server cluster. This system would work similar to the system of Figures 1 and 2, in that one of the servers 406, 410, 414 containing a copy of the data item 418 can drop a copy in local cache when it receives an invalidate request from a client, and can send a message on multicast to the other servers on the network to drop any copy of the value in local cache.
[0033J Another problem exists due to the fact (hat a multicast message is
only sent once by the source and does not wait for confirmation of receipt by the other servers. A server in the cluster might not get ari invalidate request, such as if it is temporarily offline. A system in accordance with the present invention can provide a more reliable multicast by tagging each such message or request with a version number or sequential number. In this way, a server receiving a request will know the version of the request, as well as the version of the last request it received, such that the server will know if it missed a message. Once a server determines that it has missed a message, it can request that the message be sent again so that it can update accordingly.
[0034] One problem with this approach, however, is that a server will not
know it has missed an update until another update is sent. In certain applications

such as an on-line store posting weekly specials for weeks 1, 2, and 3, it may be unacceptable to wait until the next update to get correct information. The store would not realize that it had missed the specials for week 2 until the update for week 3. The week I specials would have remained up during week 2, displaying the wrong information to any user accessing the system during that time. When the system realizes that it missed the week 1 update, it will already be week 3. The server will end up simply discarding the week 2 information without the information ever having been displayed to a user.
|0035J A system in accordance with the present invention can get around
this problem by periodically "heartbeating" information to the servers in the cluster. A server heartbeats a packet of information or a message by sending the message periodically over the network orcluster. A heartbeat message can contain information such as the latest version number, previous version numbers, or the actual update information itself if the update information is small enough to be practical. If a server receives a heartbeat message containing the latest version number, and the server is not on that version of the data or did not receive the latest invalidate request, the server can request or pull the invalidate message" from the server.
[0036J The initiating server that initially sent the invalidate request, which
may also be the server sending the multicast and/or heartbeats, can store recent requests for a certain amount of time or can store a certain number of recent requests. If a cluster server requests an invalidate message that the initiating server is still storing, the initiating server can simply send the message to the cluster server, by a method such as a multicast or a point-to-point connection. If the initiating server no longer has the message, the initiating server can tell the cluster server to simply drop its entire cache, since it is not possible to tell the cluster server which keys have changed. The cluster server can read new and/or current information from the database. This can temporarily lessen performance, but the

newly-cached information will at least be current with the information in the database.
[0037) In operation, a client or application can update a data item through
a read/write entity bean. The update, or a transaction containing multiple updates, will commit to the database. An invalidate message can be sent to the servers in the cluster, with the message being triggered for example by the client or server updating the data item. The cluster servers can each drop any copy in local cache and can read in the new value from the database, either right away, later, or when necessary to serve a request. Normally it is not possible to read uncommitted data, so it may be preferable to use a two-step process where the data is committed first and then a message is multicast to the cluster.
[0038] One problem with the above approach is that it forces a client to
initiate an invalidate request, which cart involve a little more complexity for the client. There is also the possibility that the client could use the invalidate method incorrectly or make a mistake. It may therefore be preferable that the system can do it automatically.
[0039] A system in accordance with the present invention can address this
problem by using an "invalidation target." An invalidation target is based on the idea that the read-only and read/write beans point to the same data in the database, with the people reading the data using the read-only bean and the people updating the data using the read/write bean. The idea is to invalidate the read-only bean when the read/write bean is updated or modified. |
[0040] When deploying an entity bean or enterprise JavaBean, there is
typically a deployment descriptor used to store meta data about the actual entity bean. A deployment descriptor can be, for example, an XML document used to provide information about the services provided by the bean that should be made available to clients. The information can provide a wide variety of information to the clients, such as request routing information, as well as method and class details"

for a supporting Java class. A tag can be added to the deployment descriptor, referred to previously as an "invalidation target." The invalidation large! for a read/write bean can contain the identity of any associated read-only bean. The invalidation target canbe used to automatically invalidate any associated read-only bean(s) when the read-only bean is updated.
[0041J In one embodiment, the invalidation target can be updated when a
server requests information from a read/write bean or generates a read-only bean does the request. When the read/write bean forwards information from a database or data store to the requesting server, the read/write bean can also update the invalidation target. An XML file stored on the server containing the read/write bean can be updated to include the identity of the server requesting the information or creating the bean.
[0042] Figure 3 again shows the system 100 of Figure 1, except in this
embodiment the system is shown taking advantage of an invalidation target. Whenever a read/write bean 128 is used to update a data item 122, the system can look to the invalidation target associated with that read/write bean 128 and send an invalidate request to each read-only bean 130 associated with that read/write bean. The invalidate request can be acted on directly by server 110, which contains both the read/write bean 128 and a read-only bean 130. The invalidate request can also be sent by any appropriate protocol to other servers containing a read-only bean 130, which would be in the invalidation target. In one approach, server 110 contacts server 112 directly by a point-to-point connection 134, telling the read¬only bean 130 on server 112 to drop the cached copy 118 on server 112. In another approach, server 110 can send a multicast message 132 over the network 106 to any server which contains a read-only bean 130 within the scope of the invalidation target, such as server 112.

[0043) A subsequent call to an invalidated read-only bean can cause a
method such as ejbLoad to be called, which can read current information from the
database into cache. For example, a container-managed persistence (CMP) bean,
an entity bean whose state is automatically synchronized with a database, can use
an invalidation-target element in an XML file such as ejb-jar.xml to specify a read-
only entity bean that should be invalidated when the read/write bean has been
modified. The container in this example can automatically invalidate the
invalidation-target, such as after the transaction is completed.
[0044] Such a method 200 is shown in the flowchart of Figure 4, A copy
of a data item is stored on at least one server in a network cluster 202. Identification information, or an invalidation target, is provided to a read/write bean on a server in the cluster, the information relating to any server in the cluster containing a read-only bean and a local copy of the data item 204. The data item can be updated in the database using a read/write bean 206. An invalidation request can be sent from the server containing the read/write bean to any server identified by the identification information 208. The copy of the data item can then be dropped by each server receiving the request 210.
[0045] In this way, customers or clients do not"have to write any additional
code to invalidate an item. In accordance with an embodiment of the present invention, only an invalidation target must be specified in order to keep the read/write and read-only beans coherent. The beans can coexist on the same server, with the read-only bean reading items from local cache and the read/write bean reading from, and writing to, the database.
[0046] In order to improve performance, a system in accordance with the
present invention can instead wait unti] an entire transaction or series of updates is committed to the database or data table, instead of sending an individual message for each update. A server, such as the server initiating the update, can keep track

of which keys were updated during the transaction and multicast a single message that includes information for all updated primary keys. Such batching of messages can improve the overall performance of such a system and can reduce the opportunity for error or inconsistencies.
[0047] One example of a system that can be used in accordance with the
present invention contains a table of stock symbols, as well as information associated with each symbol, such as price and volume. A Java server page can be used io allow a user to request the current price of a stock. The Java server page can read the information from a read-only entity enterprise Java bean. A Java Message Service (JMS) queue can receive messages with updates to stock prices. An message-driven bean can de-queue these messages and update the associated CMP entity bean. When this modification occurs, the container can invalidate the associated read-only bean.
[0048] The foregoing description of preferred embodiments of the present
invention has been provided for the purposes of illustration and description. It is
not intended to be exhaustive or to limit the invention to the precise forms
disclosed. Many modifications and variations will be apparent to one of ordinary
skill in the relevant arts. The embodiments were chosen and described in order to
best explain the principles of the invention and its practical application, thereby
enabling others skilled in the art to understand the invention for various
embodiments and with various modifications that are suited to the particular use
contemplated. It is intended that the scope of the invention be defined by the
following claims and their equivalence. ■

1. The method for updating a cached copy of a data item in a database,
comprising the steps of:
-storing a copy of a data item on a server, the data item being stored in a database;
-generating a read-only bean to provide read access to the copy and storing identification information relating to the read-only bean;
generating a read/write bean to provide read and write access, to the data item in the database and updating the data item using the read/write bean;
and sending an invalidate request to the read-only bean using the identification information so the copy of the data item can be deleted.
2. The method as claimed in claim 1, wherein:
storing a copy of a data item stores the copy in cache on a first server.
3. The method as claimed in claim 2, wherein:
generating a read-only bean generates the read-only bean on the first server;
generating a read/write bean generates the read/write bean on a second server.
4. The method as claimed in claim 3, wherein:
sending an invalidate request sends the request from the second server containing the read/write bean to the first server containing the read-only bean.
5. The method as claimed in claim 1, wherein:
sending an invalidate request to the read-only bean involves multicasting the request

to any read-only bean storing a copy of the data item as identified by the identification information.
6. The method as claimed in claim I, wherein:
sending an invalidate request to the read-only bean involves multicasting the request to any member of a cluster, the server being a member of the cluster.
7. The method as claimed in claim 6, comprising the step of: periodically multicasting the invalidate request across the cluster.
8. The method as claimed in claim 1, wherein:
sending an invalidate request to the read-only bean occurs by a point-to-point connection.
9. The method as claimed in claim 1, wherein:
sending an invalidate request involves multicasting a request containing a version number.
10. The method as claimed in claim 1, comprising the step of: comprising a version identifier in the invalidate request.
11. The method as claimed in claim 10, comprising the step of: determining whether an invalidate request for the read-only bean was missed
by checking the version identifier; and requesting that an invalidate message be resent to the read- only bean if the read-only bean missed an invalidate request.
12. The method as claimed in claim 1, comprising the step of:
storing recent invalidate requests.

13. The method as claimed in claim 1, comprising the step of:
collecting information for multiple updates and batching the update information into one invalidate request.


1136-chenp-2004 abstract.jpg

1136-chenp-2004 abstract.pdf

1136-chenp-2004 assignment.pdf

1136-chenp-2004 claims duplicate.pdf

1136-chenp-2004 claims.pdf

1136-chenp-2004 correspondence-others.pdf

1136-chenp-2004 correspondence-po.pdf

1136-chenp-2004 description (complete) duplicate.pdf

1136-chenp-2004 description (complete).pdf

1136-chenp-2004 drawings.pdf

1136-chenp-2004 form-1.pdf

1136-chenp-2004 form-19.pdf

1136-chenp-2004 form-26.pdf

1136-chenp-2004 form-3.pdf

1136-chenp-2004 form-5.pdf

1136-chenp-2004 others.pdf

1136-chenp-2004 petition.pdf

Patent Number 202064
Indian Patent Application Number 1136/CHENP/2004
PG Journal Number 05/2007
Publication Date 02-Feb-2007
Grant Date 18-Sep-2006
Date of Filing 25-May-2004
Name of Patentee M/S. BEA SYSTEMS, INC
Applicant Address 2315 North First Street, San Jose, CA 95131
# Inventor's Name Inventor's Address
1 JACOBS, Dean, Bernard; 1747 Madera Street, Berkeley, CA 94707
2 WOOLLEN, Rob; 2531 14th Avenue, San Francisco, CA 94127
3 WHITE, Seth; 1045 Rivera Street, Apartment B, San Francisco, CA 94116
PCT International Classification Number G06F 17/30
PCT International Application Number PCT/US2002/033659
PCT International Filing date 2002-10-21
PCT Conventions:
# PCT Application Number Date of Convention Priority Country
1 60/335,633 2001-10-25 U.S.A.
2 10/212,382 2002-08-05 U.S.A.