Disclosed are systems and methods for using a priority cache to store frequently used data items by an application. The priority cache may include multiple cache regions. Each of the cache regions may be associated with a different priority level. When a data item is to be stored in the priority cache, the application may review the context of the data item to determine if the data item may be used again in the near future. Based on that determination, the application may be configured to assign a priority level to the data item. The data item may then be stored in the appropriate cache region according to its assigned priority level.

BACKGROUND

The present invention relates to the field of information technology, including, more particularly, to systems and techniques for cache memory management.

Large organizations, such as businesses, often use one or more computer programs, such as enterprise applications, during the course of their activities. An enterprise application may be enterprise software that is used to offer services from a cloud-based environment. The enterprise application may perform various operations that may cause accessing, updating or adding new data items. The data items may be stored in a database. The database may be associated with a database cache. When a database query operation results in a large number of data items, the data items in the database cache may be replaced by new data items. This may not be desirable if some of the replaced data items are frequently used by the application.

DETAILED DESCRIPTION

For some embodiments, an application is configured to assign priority levels to data items that are to be stored in a priority cache. The priority cache may be associated with a database cache. The priority cache is logically divided into different cache regions. Each of the cache regions is associated with a unique priority level. When a data item is to be stored in the priority cache, the priority level of the data item is used to determine the appropriate cache region to store the data item. A data item is stored in a cache region using a linked list. The linked list may be implemented as a least recently used (LRU) linked list (referred to as LRU linked list) where the most recently used (MRU) item is added to the tail of the linked list, and the LRU data item is positioned at the head of the linked list. The priority level of a data item may be updated by the application. If the updated priority level is higher than a current priority level, the data item may be promoted from its current LRU linked list to a LRU linked list associated with a cache region having a higher priority level. A data item may be removed from the head of its LRU linked list to make room for another data item if the LRU linked list is full.

Prior to describing the subject matter in detail, an exemplary computer network in which the subject matter may be implemented shall first be described. Those of ordinary skill in the art will appreciate that the elements illustrated inFIG. 1may vary depending on the system implementation. With reference toFIG. 1,FIG. 1is a simplified block diagram of a distributed computer network100. Computer network100includes a number of client systems113,116, and119, and a server system122coupled to a communication network124via a plurality of communication links128. There may be any number of clients and servers in a system. Communication network124provides a mechanism for allowing the various components of distributed network100to communicate and exchange information with each other.

Communication network124may itself be comprised of many interconnected computer systems and communication links. Communication links128may be hardwire links, optical links, satellite or other wireless communications links, wave propagation links, or any other mechanisms for communication of information. Various communication protocols may be used to facilitate communication between the various systems shown inFIG. 1. These communication protocols may include TCP/IP, HTTP protocols, wireless application protocol (WAP), vendor-specific protocols, customized protocols, and others. While in one embodiment, communication network124is the Internet, in other embodiments, communication network124may be any suitable communication network including a local area network (LAN), a wide area network (WAN), a wireless network, a intranet, a private network, a public network, a switched network, and combinations of these, and the like.

Distributed computer network100inFIG. 1is merely illustrative of an embodiment and is not intended to limit the scope of the invention as recited in the claims. One of ordinary skill in the art would recognize other variations, modifications, and alternatives. For example, more than one server system122may be connected to communication network124. As another example, a number of client systems113,116, and119may be coupled to communication network124via an access provider (not shown) or via some other server system.

Client systems113,116, and119typically request information from a server system which provides the information. For this reason, server systems typically have more computing and storage capacity than client systems. However, a particular computer system may act as a client or a server depending on whether the computer system is requesting or providing information. Additionally, although aspects of the invention have been described using a client-server environment, it should be apparent that the invention may also be embodied in a stand-alone computer system. Aspects of the invention may be embodied using a client-server environment or a cloud-computing environment.

Server122is responsible for receiving information requests from client systems113,116, and119, performing processing required to satisfy the requests, and for forwarding the results corresponding to the requests back to the requesting client system. The processing required to satisfy the request may be performed by server system122or may alternatively be delegated to other servers connected to communication network124.

Client systems113,116, and119enable users to access and query information stored by server system122. In a specific embodiment, a “Web browser” application executing on a client system enables users to select, access, retrieve, or query information stored by server system122. Examples of web browsers include the Internet Explorer® browser program provided by Microsoft® Corporation, and the Firefox® browser provided by Mozilla® Foundation, and others.

FIG. 2shows an exemplary client or server system. In an embodiment, a user interfaces with the system through a computer workstation system, such as shown inFIG. 2. WhileFIG. 2illustrates a computer workstation, the user can interface with the system through a mobile device such as a mobile phone, laptop computer or computer tablet.FIG. 2shows a computer system201that includes a monitor203, screen205, cabinet207, keyboard209, and mouse211. Mouse211may have one or more buttons such as mouse buttons213. Cabinet207houses familiar computer components, some of which are not shown, such as a processor, memory, mass storage devices217, and the like.

For example, a binary, machine-executable version, of software may be stored or reside in RAM or cache memory, or on mass storage device217. The source code of the software may also be stored or reside on mass storage device217(e.g., hard disk, magnetic disk, tape, or CD-ROM). As a further example, code may be transmitted via wires, radio waves, or through a network such as the Internet.

FIG. 3shows a system block diagram of computer system201. As inFIG. 2, computer system201includes monitor203, keyboard209, and mass storage devices217. Computer system201further includes subsystems such as central processor302, system memory304, input/output (I/O) controller306, display adapter308, serial or universal serial bus (USB) port312, network interface318, and speaker320. In an embodiment, a computer system includes additional or fewer subsystems. For example, a computer system could include more than one processor302(i.e., a multiprocessor system) or a system may include a cache memory.

Arrows such as322represent the system bus architecture of computer system201. However, these arrows are illustrative of any interconnection scheme serving to link the subsystems. For example, speaker320could be connected to the other subsystems through a port or have an internal direct connection to central processor302. The processor may include multiple processors or a multicore processor, which may permit parallel processing of information. Computer system201shown inFIG. 2is but an example of a suitable computer system. Other configurations of subsystems suitable for use will be readily apparent to one of ordinary skill in the art.

Computer software products may be written in any of various suitable programming languages, such as C, C++, C #, Pascal, Fortran, Perl, Matlab® (from MathWorks), SAS, SPSS, JavaScript®, AJAX, Java®, SQL, and XQuery (a query language that is designed to process data from XML files or any data source that can be viewed as XML, HTML, or both). The computer software product may be an independent application with data input and data display modules. Alternatively, the computer software products may be classes that may be instantiated as distributed objects. The computer software products may also be component software such as Java Beans® (from Oracle Corporation) or Enterprise Java Beans® (EJB from Oracle Corporation). In a specific embodiment, the present invention provides a computer program product which stores instructions such as computer code to program a computer to perform any of the processes or techniques described.

An operating system for the system may be one of the Microsoft Windows® family of operating systems (e.g., Windows 95®, 98, Me, Windows NT®, Windows 2000®, Windows XP®, Windows XP® x64 Edition, Windows Vista®, Windows 7®, Windows CE®, Windows Mobile®), Linux, HP-UX, UNIX, Sun OS®, Solaris®, Mac OS X®, Alpha OS®, AIX, IRIX32, or IRIX64. Other operating systems may be used. Microsoft Windows® is a trademark of Microsoft® Corporation.

Furthermore, the computer may be connected to a network and may interface to other computers using this network. The network may be an intranet, internet, or the Internet, among others. The network may be a wired network (e.g., using copper), telephone network, packet network, an optical network (e.g., using optical fiber), or a wireless network, or any combination of these. For example, data and other information may be passed between the computer and components (or steps) of the system using a wireless network using a protocol such as Wi-Fi (IEEE standards 802.11, 802.11a, 802.11b, 802.11e, 802.11g, 802.11i, and 802.11n, just to name a few examples). For example, signals from a computer may be transferred, at least in part, wirelessly to components or other computers.

FIG. 4shows a data source or data service in the form of a database system. A database may be part of a database management system. One suitable database management system architecture is a three-tiered architecture as shown.

In a first tier is the core of a database management system, a central storage401that holds or stores a database or repository403. The database typically resides on one or more hard drives, and is generally part of a larger computer system. The information may be stored in the database in a variety of formats. An example is an Extensible Markup Language (XML) database. An XML database is a data persistence software system that allows data to be stored in XML format. Another example is a relational database management system (RDMS) which uses tables to store the information.

In a second tier are database servers405. The database servers are instances of a program that interacts with the database. Each instance of a database server may, among other features, independently query the database and store information in the database. Depending on the implementation, the database servers405may or may not include user-friendly interfaces, such as graphical user interfaces.

In a third tier is an application server407. There may be multiple application servers. In an implementation, the application server provides the user interfaces to the database servers. By way of example, the application server may be a web application server on the Internet or any other network. The application server may also be a virtual database server or a virtual directory server. The application server may provide user-friendly mechanisms and interfaces for accessing the database through the database servers. In an implementation, a web browser409is utilized to access the application server.

FIG. 5shows a block diagram of an example of a system500for selecting a dialog layout, implemented in accordance with some implementations. In various implementations, system500may handle a request to optimize a dialog layout of a software application, such as an enterprise application. In some implementations, system500may include server502, applications module504, enterprise application506, web server508, network510, user interface optimizer512, rendering engine514, dialog library516, storage volume517A, storage volume517B, analytics engine518, storage device522, storage volume523A, and storage volume523B. Moreover, system500may include any number of clients such as first, second, and third clients501A,501B, and501C which access server502via network510.

The clients are general purpose computers with hardware and software, such as shown inFIGS. 1 and 3described above. For example, the first client includes a first display525A, a first application program (e.g., first browser program)527A, an input device, a processor, memory, and storage. Similarly, the second client includes a second display525B, a second application program (e.g., second browser program)527B, an input device, a processor, memory, and storage. The third client includes a third display525C, a third application program (e.g., third browser program)527C, an input device, a processor, memory, and storage.

FIG. 5shows three clients. It should be appreciated that an enterprise can have any number of clients such as tens, hundreds, or thousands of clients. The clients execute executable code (or computer-readable code) that embodies a technique or algorithm as described in this application. The browser is an application program that can request, receive, and process data from a user, the server, or both. The data can be shown via a display. WhileFIG. 5illustrates the data being displayed on a client machine, the data can also be displayed on a mobile device such as a mobile phone, laptop computer or computer tablet.

In various implementations, system500may include server502. The server includes components similar to the components described inFIGS. 1 and 4. In some implementations, server502may include hardware and software used to run one or more services to serve the needs of other computers and users on network510. Thus, server502may include one or more processors and memory capable of executing software operations and serving webpages. It will be appreciated that in some implementations, server502may comprise several servers in a distributed or cloud computing network.

In various implementations, server502may include an applications module, such as applications module504. In some implementations, applications module504includes software and hardware that may be used to execute one or more software applications. Thus, applications module may include software and/or firmware instructions that configure the functionality of server502.

According to various implementations, applications module504includes enterprise application506. In particular implementations, enterprise application506may include software instructions that, when executed by one or more processors, execute one or more processes associated with an enterprise application. Thus, enterprise application506may include software instructions that configure one or more tasks performed by a user when the user is performing a process of the enterprise application.

In various implementations, applications module504may include an application used to serve webpages, such as web server508. In some implementations, web server508serves web pages to a client machine operated by a user of the enterprise application. Thus, according to various implementations, an application such as a web server508may deliver webpages and other content from a storage volume of server502to the browsers of the client machines. Thus, according to various implementations, an enterprise application may be accessible to a client machine over the network using the browser. For example, first, second, and third users at clients501A-501C, respectively, login by using a browser to access the application. The application may require that the user input a username and a password so that the user can be authenticated. The users may be employees, colleagues, partners, or members of the same company, organization, entity, partnership, joint venture, or have a business relationship (e.g., supplier-manufacturer relationship, or client-vendor relationship), and so forth.

In various implementations, system500may include user interface (UI) optimizer512. In some implementations, UI optimizer512may be configured to handle requests to optimize a dialog layout for one or more dialogs in a process of an enterprise application. Thus, UI optimizer512may communicate with other entities, such as a client machine or server502, via network510and receive a request to optimize a dialog layout. UI optimizer512may handle the request by communicating with other components of system500that may be coupled to a network, such as analytics engine518and dialog layout library516. UI optimizer may return a result or response to the request via network510.

In various implementations, UI optimizer512may include a rendering engine, such as rendering engine514. In various implementations, rendering engine514may be configured to render a data object into a rendered data object capable of being displayed in a display device of a client machine. For example, rendering engine514may render an intermediate data structure into hypertext markup language (HTML) capable of being displayed by an web browser. Thus, according to various implementations, rendering engine514may be configured to render a dialog layout into a dialog that may be displayed in a web browser of a client machine, mobile phone, laptop computer or computer tablet.

In various implementations, system500may include dialog layout library516. In some implementations, dialog layout library516may include one or more storage volumes, such as storage volume517A and517B. In particular implementations, dialog layout library516may be configured to store information associated with various dialog layouts, such as content that may be displayed in the dialog layouts. For example, dialog layout library516may store one or more data values identifying the content of a text box or the appearance and function of a control. Thus, dialog layout library516may provide a repository for information and content associated with various different dialog layouts that may be used at various different stages of the methods described herein.

In various implementations, system500may include analytics engine518. In some implementations, analytics engine518may be configured to dynamically analyze responses from users of the enterprise application and select one or more dialog layouts to be provided to the users. Thus, analytics engine518may be configured to track input received from users and other components of system500, and may be further configured to make one or more decisions based on that tracked information.

In various implementations, analytics engine518may be configured to store data and metadata related to decisions that have been made, and data that was used to make them. Thus, according to some implementations, system500may include storage system522, where storage system522may be coupled to analytics engine518. In various implementations, storage system522may include one or more storage volumes, such as storage volume523A and storage volume523B. In particular implementations, storage system522may store information generated by analytics engine518and used by analytics engine518. Thus, one or more data values identifying decisions made by and metrics measured by analytics engine518may be stored in storage system522.

FIG. 6Ashows an example of cache implementations in a system, performed in accordance with some implementations. The priority cache606may be associated with application605which may be part of the application server407(shown inFIG. 4). The application may interact with database system610. The database system610may include one or more database servers and one or more databases (shown inFIG. 4). The one or more databases may be stored in a storage device which is part of a file system. The database system610may be associated with an operating system615which may include logic to interact with the file system. To improve performance, the operating system615may use a file system cache616. Similarly, the database system610may use the database system cache611(also referred to as a database cache). Many general-purpose cache designs use a replacement policy that removes existing data items from the cache and replace them with new data items. One such replacement policy is the least recently used (LRU). The LRU policy may add a new data item to the cache or promote an existing data item within the cache any time that data item is accessed. The LRU policy may not consider the context of the data items in the database system cache611, and it is susceptible to data scan operations. With data scan operations, one-time iteration over a large number of data items may cause overrun or replacement of many or all data items in the database system cache611if the amount of data items is more than the capacity of the database system cache611. This normally would be sufficient for most generalized applications. However, in certain situations, many of the replaced data items may include data items that may be accessed frequently.

For some embodiments, the application605may include operations that frequently access the same data items. For example, the application605may include media database operations that repeatedly access the same data items in a media database. The media database may include data items for volumes, save sets, and client ID maps. For some embodiments, the application605may be associated with a priority cache606. For the media database, a separate cache instance of the priority cache606may be used for each data item type (e.g., volumes, save sets, client ID) allowing for separate sizing and priority management.

FIG. 6Bshows an example of a priority cache, performed in accordance with an exemplary embodiment. The priority cache606may be configured to store copies of the data items that may be repeatedly accessed by the application605. The priority cache606may be logically divided into cache regions. Each of the cache regions may be associated with a priority level and may be configured to store data items assigned with the same priority level. For example, the priority cache606may include cache region650associated with a first priority level, cache region660associated with a second priority level, and cache region670associated with an nthpriority level. For example, the first priority level may be considered the highest priority level, and the data items stored in the cache region650may need to be replaced less frequently than the data items in the other cache regions. Each cache region may store zero or more data items. Each cache region may have a minimum size (also referred to as a reservation). The reservation for each cache region may enable storing a minimum number of data items for each priority level. The reservation prevents higher priority data items from consuming the entire cache at the expense of lower priority data items. The capacity of each cache region may vary depending on the type of data items it is configured to store. For example, the size of the cache region650may be larger than the size of the cache region660because it is configured to store a higher amount of data items configured with a higher priority level.

For some embodiments, the sum of all the reservations for all the cache regions may not need to be equal to the total capacity of the priority cache606. A shared pool of cache capacity may be used to allocate additional space to one or more cache regions when necessary. For some embodiments, the unused portion of the reservation of a cache region may be borrowed or reallocated to one or more of the other cache regions. For example if a cache region has a reservation of ten (10) data entries but its associated LRU linked list contains only seven (7) data entries, then the remaining unused space (for three (3) data entries) may be available for use with the other cache regions. For some embodiments, when a cache region associated with a higher priority level has exceeded its reservation, additional cache space may be claimed from a cache region associated with a lower priority level. If the cache region associated with the lower priority level has exceeded its own reservation, a data item from the cache region associated with the lower priority level may be dropped for the cache space to be claimed.

FIG. 7shows an example of an update to a priority cache, performed in accordance with an exemplary embodiment. The application605may use an application programming interface (API)705to update the priority cache606with the data item715. For some embodiments, the application605is configured with logic to give it the ability to evaluate the data item715based on its context and determine if the data item715will be used in the short term. An appropriate priority level710is then assigned by the application605. For example, a high priority is assigned if the data item715is going to be used very shortly, and a low priority is assigned if the data item715is less likely to be used in the short time. For some embodiments, the application605may be configured to decide not to add a low value data item to the priority cache606when further reference to the data item may not be likely. The use of different priority levels may prevent lower priority data items from displacing higher priority data items from the priority cache606. For example, when a low priority level cache region is full, and a new low priority level data item is to be added to that cache region, a LRU data item from the low priority level cache region is removed to enable adding the new data item, instead of adding the new data item to a higher priority level cache region.

FIG. 8shows an example of a priority cache with data items in the different cache regions, performed in accordance with an exemplary embodiment. In this example, the cache region650includes three data items811,812and813. The cache region660includes two data items821and822. The number of distinct cache regions and associated priority levels may vary depending on the implementation and depending on whether the application605is configured with sufficient logic or intelligence to make more granular determinations. For example, there may be two cache regions, one associated with a high priority level and one associated with a low priority level, where the high priority level may be considered more important than the low priority level.

The cache606may be configured to maintain an array of LRU linked lists separated by priority level. The priority values may be used as the basis for the array index. An LRU linked list (e.g., LRU linked list850) may be used to manage all data items (e.g., data items811,812,813) at a given priority level (e.g., first priority level). Each LRU linked list may be implemented using a linked list data structure to link a distinct set of data items in the cache606. Each LRU linked list is ordered by when a data item is last used. A head of the LRU linked list may be used to identify the least recently used data item, and the tail of the LRU linked list may be used to identify the most recently used (MRU) data item. In the current example, the data item811may be the head and the data item813may be the tail of the LRU linked list850. Similarly, the data item821may be the head and the data item822may be the tail of the LRU linked list851. For some embodiments, the cache replacement model is least recently used (LRU) by priority. That is, a data item at the head of the LRU linked list is removed based on it being the LRU data item. This allows LRU methodology but prevents frequent access of low-priority items from displacing high-priority items.

FIG. 9shows an example of a hash table that may be used to look up data items in the priority cache, performed in accordance with an exemplary embodiment. For some embodiments, the caching strategy using the priority cache606is to optimize simple, critical workflows but not duplicate database query functionality. Thus an approach is used where the priority cache606can satisfy a query which is based on a unique identifier of the data item. For example, when using the priority cache606with the media database, the unique identifier for the volumes and save sets is the volume ID or the save set ID. For client lookups, the client ID may be used; however, the client name may be used instead of the client ID since it is also unique and a more frequently used query criterion.

For some embodiments, the organization of the priority cache606may be based on a single-key hash table900. This may be used to map a data item to a slot in a hash table900for lookup purposes. For example, the hash table900may help determining where to store a data item, and how to look up or access a data item. Each of the slots or buckets (e.g.,905,910,915,950, etc.) of the hash table900may be associated with a key generated by a hash function using a unique identifier associated with the data item (e.g., the unique identifier for a volume is the volume ID, as described above). For example, the data item906is associated with the bucket905of the hash table900. It may be possible that the hash function may generate the same key for a different data item thus causing more than one data item to be associated with a bucket (referred to as a collision). Collisions are handled by using a linked list in each hash bucket. In the current example, the bucket905is associated with a collision linked list960that shows three data items906,907and908. Similarly, the data items911and912are associated with the bucket910. There may be no collision with the bucket915since there is only one data item916.

FIG. 10shows an example LRU linked lists superimposed onto the hash table structure, performed in accordance with an exemplary embodiment. In the current example, there are two LRU linked lists1050and1060. The LRU linked list1050includes the data items1015,1011and1013. Each of the data items1015,1011and1013is associated with a respective key915,905or910of the hash table900. The data items1015,1011and1013may be associated with the same priority level. The data item1015may be at the head of the LRU linked list1050, and the data item1013may be at the tail of the LRU linked list1050. Similarly, the LRU linked list1060includes the data items1012and1014with the data item1012at the head and the data item1014at the tail. The data items1012and1014may be associated with the same priority level. It may be noted that the data items1014and1015may be associated with the same key915of the hash table900because of collision, even though each may be associated with a different priority level. The data items1011and1012may also be in the same situation.

For some embodiments, the data items described with the priority cache606(shown inFIG. 8) and with the hash table900(shown inFIG. 9) are not duplicated data items of one another for priority and order management. The priority cache606stores one copy of a data item for both purposes of lookup and priority management. For some embodiments, the hash table900may be implemented as a cache of the data items, and the priority management method described withFIG. 8may be superimposed upon the look up method (shown inFIG. 9) by adding another set of links describing the priority division and ordering. For some embodiments, the priority cache606may be independent of other caches (e.g., database system cache611or the file system cache616shown inFIG. 6) and the structure and content of those caches may not directly relate to the priority cache606.

FIG. 11shows an example of two instances of the same priority cache to reflect changes due to a cache access or update, performed in accordance with an exemplary embodiment. The priority cache1105A and the priority cache1105B are the same priority cache having three cache regions1106,1107and1108. Each of these cache regions1106,1107,1108may be associated with a different respective priority level1,2or3and a different LRU linked list. In the current example, the cache region1106may include the data items1110,1011and1012. At time t1, the cache region1107may include the data items1103and1104, and the cache region1108may include the data items1115and1116. The data item1115may be at the head and the data item1116may be at the tail of the corresponding LRU linked list. When the data item1115is accessed by the application605(shown inFIG. 6), the data item1115becomes the MRU data item. As a result, it is moved to the tail of the LRU linked list. This is shown in the priority cache1105B at time t2. The arrow1140shows the change in position of the data item1115at time t1and at time t2.

For some embodiments, a data item may be added to the priority cache606at any priority level if the priority cache606is below capacity. When the priority cache606becomes full (e.g., based on a threshold number), all of the LRU linked lists may be examined. A new data item may displace an existing item if the LRU linked list associated with the existing data item exceeds its reservation. A new data item may displace the LRU data item of the same LRU linked list (same priority level). In general, if a data item is to be replaced, it is the LRU data item.

It may be possible for a data item to be a high value data item for different purposes. For some embodiments, to support access of the data item in multiple unrelated purposes, the priority level of the data item may only be promoted and not demoted during an update operation. For some embodiments, an age value may be stored with each data item in order to keep track of the age of one data item relative to the ages of all other data items in the priority cache606. The age value may be used as a tiebreaker if multiple LRU linked lists are over the reservation count, in order to determine which data item in the LRU linked lists among all of the data item candidates to remove. The application605may update the age of the data item in an update operation or when the data item is accessed from the priority cache606. For some embodiments, a time-to-live aging method may be used to determine which data item to remove. For some embodiments, when the capacity of the priority cache606is divided all to the cache regions (i.e., sum of capacity of all cache regions is equal to capacity of priority cache606), the priority cache606may eventually settle into an assigned distribution. In situations when not all of the capacity of the priority cache is allocated, the remaining capacity may shift among the different cache regions over time.

FIG. 12shows another example of two instances of the same priority cache to reflect changes due to a promotion of a data item to a different priority level, performed in accordance with an exemplary embodiment. The priority cache1105A and the priority cache1205B are the same priority cache having three cache regions1106,1107and1108. At time t3, the cache region1108may include the data items1115and1116. The data item1115may be at the head and the data item1116may be at the tail of the corresponding LRU linked list. When the data item1116is updated by the application605(shown inFIG. 6), the data item1116may be promoted from its current priority level (associated with the cache region1108) to a higher priority level (associated with the cache region1107) and also becomes the MRU data item (at the head of the corresponding LRU linked list) at the higher priority level. This is shown in the priority cache1205B at time t4. The arrow1240shows the change in position of the data item1115from the cache region1108to the cache region1107at time t4.

For some embodiments, when a data item is added or updated in a cache region, it is moved from its current position of its associated LRU linked list to the tail of the LRU linked list. When necessary, the data item in the head position of the same LRU linked list is removed to make room for the new or updated data item at the tail of the LRU linked list. It may be possible that the data item to be added to a cache region is a first data item and it may be both the head and the tail of the LRU linked list.

When the application605needs to access a data item, it may first query the priority cache606before querying the database. When it is necessary for the application605to query the database for a specific data item because the data item is not in the priority cache606, the application605may need to determine whether to cache the data item in the priority cache606, and if so, the application605may also need to determine a priority level to assign to the data item, based on the context.

For some embodiments, when the application605adds a new data item to the database or updates an existing data item in the database, the application605may update the database and then update the priority cache606if it determines that the new or updated data item is to be added to the priority cache606. When the application605needs to remove a data item from the database and that data item is currently stored in the priority cache606, the application605may first remove the data item from the priority cache606, then remove the data item from the database. For some embodiments, the application605may release the priority cache606before it closes the database.

FIG. 13shows a flowchart of an example of a method for enabling an application to assign a priority level to a data item, performed in accordance with an exemplary embodiment. At block1305, an application may be associated with a priority cache such as, for example, the priority cache606. The priority cache may include several logical cache regions. Each of the cache regions may be associated with a priority level, as shown in block1310. Each of the cache regions may be associated with an LRU linked list and may be configured to store data items used by the application. At block1315, the application is configured to assign a priority level to a data item. This may be based on the context of the data. For example, the application may be configured to determine whether the data item is a high value data item that may be likely to be used again.

Depending on that determination, the application may assign one of the available priority levels to the data item, as shown in block1320. A high priority level may result to the data item being stored in a cache region associated with the high priority level. A low priority level may result in the data item being stored in a cache region associated with a low priority level. At block1325, the cache regions of the priority cache may be updated based on the operation of the application. This may include promoting a data item from one cache region to another cache region. This may include moving a data item within a LRU linked list based on being the most recently used (MRU). This may include removing a data item from a cache region based on the associated LRU linked list being full.

Although the block1310describes assigning a priority level to a data item, it may be possible that the application accesses a data item from the priority cache, and a priority level has already been assigned to the data item. In this situation, the status of the data item may be changed in the cache region that it is associated with. For example, this status change may reflect the data item being the most recently used (MRU). It's possible that the status change may reflect the data item being promoted from one cache region to another cache region if the application determines that the data item should be assigned a higher priority level. It's possible that the status change may reflect the data item being demoted from one cache region to another cache region if the application determines that the data item should be assigned a lower priority level. It's also possible that the data item may be dropped completely from the priority cache if the application determines that the data item will not be used again in the near future.

In the description above and throughout, numerous specific details are set forth in order to provide a thorough understanding of an embodiment of this disclosure. It will be evident, however, to one of ordinary skill in the art, that an embodiment may be practiced without these specific details. In other instances, well-known structures and devices are shown in block diagram form to facilitate explanation. The description of the preferred embodiments is not intended to limit the scope of the claims appended hereto. Further, in the methods disclosed herein, various steps are disclosed illustrating some of the functions of an embodiment. These steps are merely examples, and are not meant to be limiting in any way. Other steps and functions may be contemplated without departing from this disclosure or the scope of an embodiment.