Method and apparatus for caching and reusing object identifiers6662191Abstract A method and system is provided for distributing and reusing object identifiers in a distributed database system. A first table of object identifiers created by the database is maintained for supplying unallocated object identifiers for each type. A second table of object identifiers is also maintained containing reusable and distributable object identifiers to one or more application server in the database system. The application server obtains a predetermined number of object identifiers from the first and second tables to be stored in each of the application servers for servicing client applications related to the application server. Claims What is claimed is: Description TECHNICAL FIELD
TABLE 1
Objid Type Objid Number
0 10
1 40
2 30
3 50
4 11
5 10
As shown in Table 1, there are five different types of objids, and the "Objid Number" column contains the most recently generated objid for each type. Since this New Object Table generates new objids (i.e., previously unallocated objids) in a sequential manner, the objid number therein is the "high watermark" of all the objids generated in the past. For instance, for type 0, the objid 10 has been previously provided. If a new objid is needed, it would be objid 11. Every time the database 12 generates new objids upon the request of the application server or the second tier clients, this New Objid Table will be updated to reflect the status of the objids of each type. The second table in the database 12 contains discrete blocks of available objids ready to be distributed to the application servers (Reusable Objid Table). Table 2 below is a simple example of such a table.
TABLE 2
Objid Type Min Objid Num of Objid
1 5 3
1 9 4
3 25 10
4 10 2
4 23 4
. . .
4 50 5
In the present example, the Reusable Objid Table is the primary source for providing the objids to the application servers. The objids of each type in this table may be in discrete blocks because they are unused objids returned from the application servers. The Reusable Objid Table is appended or updated whenever the application servers check back in objids. For instance, in Table 2, the objids of type 1 have two rows or two discrete blocks, the first one starting from an objid of 5, and containing three objids. According to the present example, in the first block of objids of type 1, the available objids are 6, 7, and 8. Similarly, the second block of objids of type 1 contains the objids of 10, 11, 12, and 13. Having extraneous rows of a single type (if for instance there were 5000 separate rows for type 1 objids instead of 2 rows as shown in Table 2) is considered a "problem," because it can slow down queries to the table and therefore defeat the purpose of reusing objids in a timely fashion. The number of extraneous rows considered to be a problem will depend on the size and specific parameters of a particular database. Similarly, the threshold number of the objids considered to be a mark of a problem can be determined by database programmers depending on the configuration of the database system. In this case, as it will be explained below, it is preferred to distribute these problem objids out from the Reusable Objid Table before the database generates any new ones. It is noted that there are only three types of objids currently available in the Reusable Objid Table. These discrete blocks of objids are "leftovers" from the application server after has been shut down legally. Before the application server is terminated in its normal operation, through the connection it has with the database, it returns these unused or unassigned objids to the database. Once returned, they can then be used by any application server in the system that is still in operation. It is also possible that, upon starting up the next time, the application server that has returned certain objids may attempt to retrieve those returned objids first. These two tables are basically an indication of what objids have been generated or readily available in the database. For illustration purposes, it is assumed that when an application server "accesses" these two tables, it can get needed or requested objids. In some embodiments, the application server may "cache" or temporarily store a predetermined number of objids for servicing its own clients without going to the database (or more precisely, the two tables) every time a request of objids from its client is initiated. The application servers may cache or store a relatively small number of objids to prevent the database from exhausting its available objids. The storage medium for the objids may be any suitable temporary storage medium, such as the server cache memory, RAM memory, or in some cases, disk memory. In one example of the present invention, when a client 22 requests a set of objids from its related application server 14, the application server 14 uses existing objids saved in its cache memory to fulfill the request. If the cache memory is empty, the application server 14 may access the database to obtain more objids. Whenever the application server 14 goes to the database 12 for obtaining objids, it is preferred that a set of objids larger than the size requested by the client 22 are delivered to the application server 14. Therefore, the application server 14 can continue servicing the clients without making round way trips to the database for each request made by any client (i.e., clients 22, 24 or 26). An adjusting mechanism can be provided so that the application server obtains additional number of objids while requesting the same from the database. For example, for each type of objids within a server the next request made to the database can be about 50 percent more than the sum of what has been used up. If the application server is terminated in its normal operation, i.e., there is no abnormality such as power disruption or network crash in terminating the application server, then the application server returns to the database the unused or unassigned objids. FIG. 2 graphically illustrates the relation among client requests 30, an exemplary application server, reusable objid table 27, and new objid table 28. For illustration purposes, the application server 14 of FIG. 1 will be used as the exemplary application server. For this example, the reusable objid table 27 may be populated as illustrated in table 2. Similarly, the new objid table 28 may be populated as illustrated in Table 1. Referring now to FIG. 3, a flow diagram 30 illustrates a detailed algorithm for caching and reusing an objid. For the sake of example, it is assumed the objids are stored in the cache memory of each application server 14 (FIG. 2). First, in step 32, the cache memory in the application server 14 is checked to see whether it is initialized for distributing objids. If the cache is not initialized, a query may be made to the database 12 so that the cache can be initialized (step 34). When the application server 14 queries the database 12, the Reusable Objid Table 27 is searched, and information about each available type of objids is provided. For example, referring back to the reusable Objid Table 27, after the query, the application server 14 could store information regarding which types of objids are available, which types of objids are not available, and which types of objids are designated as "problems" in the Reusable Objid Table 27. When the Reusable Objid Table 27 is populated as in the example as illustrated by Table 2, there are altogether four types of objids, and types 1 and 3 are available, while type 4 is a problem, and type 2 is unavailable. With this information, the cache is initialized. If the cache has been initialized, when a client application sends a request 30 for a set of objids of different types, the application server 14 would fill as many of the objids as possible from its cache in step 36 before it requests for more from the database 12. A determination is made in step 38 to see whether the available objids in the cache have fully met the request from the client. For instance, if a request from the client asks for two objids of type 1, two objids of type 2, and five objids of type 4, assuming the application server has only one objid for each requested type, it will fill the request partially and further request one objid of type 1, one objid of type 2, and 4 objids of type 4 from the database. When the application server 14 goes to the database 12 seeking more objids, there is a preference for using the Reusable Objid Table 27 to obtain the needed objids first before the New Objid Table 28 is accessed. In this way, existing and available objids are used, so that more objid numbers can be preserved for future use. In step 40, it is determined whether the needed objids are a problem type in the Reusable Objid Table 27 (e.g., there is an excessively abundant supply of the objids). If so, it is further determined in step 42 whether other types of objids needed are available in the Reusable Objid Table 27. Following the example immediately above, if one objid of type 1, one objid of type 2, and four objids of type 4 are needed, and it is then determined that type 4 is a problem type, and type 2 is not available in the Reusable Objid Table 27, type 4 objids are fetched from the Reusable Objid Table 27 while type 1 and type 2 objids are retrieved from the New Objid Table 28. If only one type 1 objid and 1 type 4 objids are needed, all the requested objids are fetched from the Reusable Objid Table 27. The general rule is that if there is a problem type, the objids of such a type, and any other types still available in the Reusable Objid Table 27 will be obtained from the Reusable Objid Table 27 instead of the New Objid Table 28 in step 44. If in step 42, there is a type such as type 2 in the example indicated as not available in the Reusable Objid Table 27, the application server 14 goes directly to the New Objid Table 28 for obtaining new numbers in step 48. If step 44 results in no block of objids being returned for a certain type, the application server deems the type "exhausted" in its memory and does not go back to the Reusable Objid Table 27 for as long as its operation lasts. If the Reusable Objid Table 27 only provides some of the needed objids of a particular type, it does not imply that the Reusable Objid Table has "exhausted" this type of objid. The application server 14 will go back to the Reusable table again for such a type. If all the needed types are available in the Reusable Objid Table 27, it will be the sole source for providing the application server the needed objids. If the Reusable Objid Table 27 only provides a partial fill of the request, additional objids must be obtained from the New Objid Table 28 (step 48). It is noted that the Reusable Objid Table 27 is the source for providing any problem type objids regardless of the availability of the other types. Therefore, it is possible that the application server 14 will receive sufficient objids from both Tables (such as the example immediately above wherein type 4 objids are obtained from the Reusable Objid Table 27 and the rest from the New Objid Table 28). It is further noted that it would be preferred that only one table is accessed if possible to save time and resources, and thus, the Reusable Objid Table 27 is accessed first to see if the objids are available because one primary goal of the present invention is to reuse the objids as much as possible. In other words, the Reusable Objid Table 27 is the preferred source for the objids. While obtaining the needed objids from the New Objid Table 28, an additional number of objids of each type may be obtained for each request growing at a certain rate or factor. For instance, if the predetermined rate is 50% and the current number for the additional objids requested from the New Objid Table 28 is 4, the next rounds of extra objids of the same type will be set at a number of 6, 9, 13, 19, etc. respectively, until a predetermined maximum is reached. In some examples of the present invention, the maximum is preferred to be 128 objids for application servers, and 16 objids for the second tier clients. After obtaining these additional objids, the application server 14 builds up a cache for the objids so that minimum requests will be made to the database for obtaining objids requested by its clients. The above disclosure provides many different embodiments, or examples, for implementing different features of the invention. Also, specific examples of components and processes are described to help clarify the invention. These are, of course, merely examples and are not intended to limit the invention from that described in the claims. While the invention has been particularly shown and described with reference to the preferred embodiment thereof, it will be understood by those skilled in the art that various changes in form and detail may be made therein without departing from the spirit and scope of the invention, as set forth in the following claims.
|
Same subclass Same class Consider this |
||||||||||