KR101690288B1 - Method and system of storing and retrieving data - Google Patents

Abstract

The present invention relates to a method and system for storing data by a software application. In a data storage system that includes one or more database systems and at least one cache node, the software application interfaces with one or more database systems on a first dedicated interface and at least one cache node on a second dedicated interface independently. The method and system of the present invention is characterized in that a software application is issued first to only a plurality of cache nodes that return query data if each read query of the data storage system is available, if available. If not, the software application receives undetected triggering a fetch of the queried data from one or more database systems. Upon retrieval of the queried data, the software application adds the queried data to at least one cache node. The method and system of the present invention is further characterized in that each record of one or more database systems by a software application is concurrently performed on at least one cache node. Thus, the population of at least one cache node is quickly performed for each non-detected read query of each of the at least one cache node and each write query of the data storage system.

Description

[0001] METHOD AND SYSTEM FOR STORING AND RETRIEVING DATA [0002]

The present invention generally relates to a data management system of the type used by a large provider of products and services to track the overall merchandise and availability level that it provides, level inquiry issued by a remote user of the data storage medium that is constantly responding to the data storage medium without delay or with a very short delay without affecting the completion of the transaction updating. and to allow for inquiry.

In an interconnected world, all large providers of products and services are now deploying large-scale database systems that hold the characteristics, specifications and costs of product and service offerings. Content operated under the control of a database management system (DBMS) is made accessible to many online customers worldwide. As a result, online customers are provided with the possibility to query the database and complete the transaction using specific online software applications that enable online customers to book and purchase multiple products and services.

In the aviation industry, an example of such a very large database is a database that holds an inventory of airline companies. These databases are used to track real-time seating capacity, current reservation status, as well as fleet configurations for flights operated by a given airline.

More precisely, the merchandise listing of an airline includes all flights with normally available seats, and generally includes a service class (e.g., a first class, business or economy Grade) and many bookkeeping classes. One of the key functions of merchandise inventory management is the control of merchandise listings. Adjustment of the merchandise list controls how many seats are available in different bookkeeping classes, for example by opening and closing individual selling classes for sale. The prices for each sold seat are determined with the fare and booking conditions stored in the Fare Quote system. In most cases the adjustment of the goods list interfaces with the airline's Revenue Management System and supports permanent optimization of the bookkeeping class provided in response to changes in demand. The user accesses the airline's merchandise list via an availability application that has a display and a graphical user interface. This commodity list includes all flights provided to a specific city-pair with seats available at different bookkeeping classes.

The airline inventory database is typically managed by an airline. The airline merchandise listing database can also be further set up by a company that provides travel services to many actors in the travel industry, including airlines, traditional travel agencies, and all kinds of other online travel service providers. These companies include AMADEUS, a European travel service provider headquartered in Madrid, Spain, for example. Some product listings are operated directly by airlines and are interfaced with a global distribution system (GDS) or a central reservation system (CRS).

In this environment, the use of this database is characterized by significantly increased interrogation or read-query levels over the years. In fact, the look-to-book ratio of transactions that the database has to handle is getting very high. Thus, the travel service provider must provide the necessary computer resources to cope with this situation. As an airline, you can update your database at the same time you complete booking and selling your seats to an airline traveler, and an increasing number of online customers can effectively query the database and still get a quick response.

A large database system from several specialized companies, such as Oracle, a company based in Redwood Shores, California, USA, specializing in database management system development, is available to implement this database And is mainly used. However, standard DBMSs alone can not meet the requirement levels raised by the need for large service providers of products and services to serve tens of thousands of potential customers at the same time. To achieve this goal, the database should be shielded from innumerable user questions that could have been received directly anyway.

Thus, many solutions have been developed for caching database content. The cache may be an application cache located at the application tier, where the application basically reuses data previously fetched from the database. This immediately leads to the problem of data quality delivered in response to other user inquiries as the database content may have been updated at mean time. This can be a real problem in some applications where the database is continuously updated and requires high quality data. This is true, for example, in the case of applications related to the listing of airlines' products, where freshness of data directly affects the likelihood of selling seats and the prices provided to customers.

Thus, if the quality of the data delivered by this type of cache is not important and can not be seen as being more informative than anything else, this type of application cache invalidates previously fetched data when updated in the database it is necessary to implement a complex mechanism between the database and the cache to invalidate and / or replace the application cache and database content in order to make the application cache and database content consistent. Often, the cache is inserted into the path between the database and the application and is always the first to be interrogated by the application. If the queried data does not exist in the cache, the queried data is fetched from the database and carried to the cache before being delivered to the application. All these solutions commonly require that caches and databases be tightly coupled and aware of each other. As a result, these solutions are not readily scalable when service providers must serve more customers while deploying more computer resources and maintaining system performance to cope with increased traffic.

However, a somewhat better scale possibility is presented in U.S. Patent 6,609,126, which describes a "system and method for routing database requests to a database and a cache", which provides some independence between cache and database. In the disclosed solution, the database and the cache are independent of each other by being run separately under the control of the application. However, this cache is only used to answer the read query, while the update is performed by the application only in the database. Thus, in order to reflect changes occurring in the database to the cache, the patent document describes updating the cache by a replication component included in the database.

All of the above cache solutions provide the database with significant additional workload, but there is no guarantee that the cache and database are always consistent, and the database must recognize multiple caches. This requires that certain operations be performed in the database when adding a new cache, so that the scalability is simply not achieved. As discussed above, U.S. Patent 6,609,126 requires that the database management system include external components. This makes it incompatible with the use of standard DBMSs.

It is therefore an object of the present invention to describe a computer data system with a database that allows for high traffic and high scalability while providing appropriate data quality to the user.

Further objects, features, and advantages of the present invention will become apparent to those skilled in the art with reference to the following detailed description when read in conjunction with the accompanying drawings. Any additional advantages are intended to be included herein.

These and other problems are overcome according to an embodiment of the present invention and other advantages are realized.

In a first aspect, the present invention provides a method for storing data in a data storage system including a software application, one or more database systems and a plurality of cache nodes and retrieving data from the data storage system, Wherein the software application is configured to receive a user request that requests one reading or one write of data and wherein the software application is configured to read a read query or a write to the data storage system to process the user request, The method further comprising: interfacing the software application with the one or more database systems and the plurality of cache nodes independently, the method comprising: receiving, by the at least one data processor, Characterized in that the software application comprises a step of transmitting only a read query to the plurality of cache nodes when receiving a user request for the next step performed by the software application, . ≪ / RTI > Advantageously, when the software application receives the queried data (i.e., retrieved data) from at least one cache node in response to the read query, the software application processes the user request using the queried data do. Advantageously, if the software application receives a miss from all cache nodes (meaning that the data is not found at the cache node) in response to the read query, Fetch; When retrieving the queried data from the one or more database systems, if the queried data is present in the database system, the software application processes the user request using the queried data, and the at least one cache node To the at least one cache node, instructions to add the interrogated data to the at least one cache node.

According to a preferred embodiment, upon receiving a user request that requires at least one record of data, the software application sends a command to write the one or more database systems and simultaneously records the plurality of cache nodes Transmit; The plurality of cache nodes are populated to each undetected read query in the data storage system, i.e., to each read query where the queried data is not found in all cache nodes and to each write query. So that each data is equally stored in at least one of the plurality of cache nodes and in the one or more database systems to ensure that the database system and the plurality of cache nodes are always fully synchronized.

Thus, the present invention provides a known solution involving replicating components incorporated into the database performing updates of the cache, such that the database and cache are not completely independent, limiting the scalability of the entire storage system and requiring a particular database , The database is completely independent of the plurality of caches including the plurality of cache nodes.

Computer data systems with completely independent and non-mutually-aware databases and caches can provide unlimited scale possibilities for data systems by simply bringing more computers and storage capacity when it is necessary to cope with traffic growth .

Furthermore, high scale possibilities can be achieved while limiting the cost of the equipment. In particular, the present invention can be implemented with a standard database and a DBMS. The present invention can also reduce maintenance costs. In particular, no action is required on the database to increase the storage resources.

The software application is responsible for updating the data in the database and is responsible for populating the cache by reflecting the records in the database or by adding the queried data that exists in the database but not yet in the cache , The final-user can be provided with high-quality data, i.e., the latest data. Furthermore, the cache can be quickly populated so that as soon as a new cache node is added to the system, the throughput can be increased.

Furthermore, the present invention can provide a user with an accurate and customer-tailored reply.

According to a non-limiting embodiment, the recording query includes at least one of adding, updating and deleting data to the database system.

Optionally, the method according to the present invention may include any of the following optional features and steps:

The data model of the cache and database may be the same, but not necessarily strictly the same. The only requirement is that they must match so that exactly the same addressing keys can be derived to access the cache and database records. This key must also be able to lock the database records for consistency of the write operation. Thus, the data records are stored in the database and in the cache (if any) in the same way, or in a way that ensures the matching of the address of the same data record to the cache and database. For example, the cache data model must be adaptable to the database model to facilitate data retrieval so that the access time of the cache can be improved while keeping the addresses fully consistent between the two entities.

According to a non-limiting embodiment, the data model of the cache node is the same as the data model of the one or more databases. Each data of each cache node is equally stored in the database system. Each piece of data in the database system is equally stored in each cache node.

An instruction to write to the one or more database systems is sent to the one or more database systems by the software application.

Instructions for simultaneously writing to the plurality of cache nodes are transmitted to the plurality of cache nodes by the software application.

A single software application accesses the database system and the cache node.

The data storage system includes a single database system.

The cache includes a cache node comprising each data storage means that is not persistent.

The software application receives a positive acknowledgment when it is complete to successively add the interrogated data to the at least one cache node.

If subsequent writing of data occurs while the same queried data is fetched from the one or more database systems simultaneously, subsequent addition of the queried data to the at least one cache node is aborted and a negative acknowledgment acknowledgment is returned to the software application; The software application can use the recorded data instead.

Instructions for writing data to the one or more database systems, and instructions for simultaneously writing to the plurality of cache nodes,

Retrieving currently stored data to which said record is applied from said one or more database systems and locking said currently stored data to said one or more database systems;

Writing new data to be processed and stored in the software application to the one or more database systems

Writing a cache buffer to the software application to temporarily hold the new data to be stored;

Transferring and setting the new data to be stored to the at least one cache node;

And committing the transaction to the one or more database systems.

In the present invention, the cache node or cache is different from the cache buffer. The cache buffer temporarily stores data during recording. Data is not retrieved from the cache buffer in response to a user request. The cache buffer is write-only.

If the commit fails, the application software sends a command to the at least one cache node to delete the previously set new data.

At least one cache node containing the new data deletes the new data from the content. When a plurality of cache nodes include the new data, all the cache nodes of the plurality of cache nodes delete the new data.

The software application determines cache nodes or cache nodes to which instructions to add data or data to update or delete data are transmitted among the plurality of cache nodes.

This decision considers load balancing.

If the queried data is not present in the one or more database systems or is not present in the plurality of cache nodes,

When fetching the one or more database systems, undetected is returned to the software application instead of the queried data;

The software application sends to the at least one cache node an absence of data added to the at least one cache node for the corresponding queried data and the absence of the data is immediately available to all subsequent queries ;

Thereby avoiding further fetching of the one or more databases when the software application attempts to retrieve the undetected queried data.

The data user requested by the end-user that is not ultimately found in the database is stored in the cache as "undetected data ", indicating that the user requested data is not present in the cache or present in the database . This prevents other queries in the database from slowing down the database system.

According to one non-limiting embodiment, each data is associated with a header to form a record, wherein the header indicates whether content has been detected in at least one database system. Thus, reading only the header of the record can tell if it is necessary to fetch the database system.

According to another embodiment, the cache node stores a particular value associated with the data, which indicates that the data does not exist in the database.

The software application interfaces with the one or more database systems on a first dedicated interface and the plurality of cache nodes on a second dedicated interface independently.

The data model is chosen in such a way that it can be mapped directly between the database and the cache.

Each dataset is grouped into functional entities and indexed by keys, which make the dataset globally accessible because it is both in the database system and in the cache node.

The data is grouped by flight-date and identified by flight-date key.

The software application is a software application of a travel provider's product listing.

The software application, the database system and the cache node are included in the travel provider's list of goods.

Generally, the travel provider is an airline.

The user request received in the software application is transmitted by at least one of a travel agent, an online travel agent, and an online customer.

The data model of the cache node and the database coincides so that exactly the same address keys can be derived to access the cache node and the database data.

Data is stored in the database and in at least one cache node, if present, in the same way or in a manner that ensures the matching of addresses of the same data to the cache and database.

In a further aspect, the invention relates to a non-transitory computer-program product comprising software program instructions, wherein said computer program instructions, when executed by at least one data processor, Program product.

An exemplary embodiment also provides a method of storing data in a data storage system including a software application, one or more database systems and a plurality of cache nodes and retrieving data from the data storage system, the software application comprising at least one Wherein the software application is further configured to send a read query or record query to the data storage system to process the user request, the method comprising: Wherein the software application interfaces with the at least one database system and the plurality of cache nodes independently, the method comprising: The next step to be performed, namely

Wherein upon receiving a user request that requests reading of at least one of the data, the software application sends only a read query to the plurality of cache nodes;

The software application processing the user request using the queried data when the software application receives queried data (i.e., retrieved data) from at least one cache node;

If the software application receives undetected from all cache nodes, the software application fetches the one or more database systems; When retrieving the queried data from the one or more database systems, if the queried data is present in the database system, the software application processes the user request using the queried data, and the at least one Adding the interrogated data to a cache node and sending the interrogated data to at least one cache node; Adding information to the cache indicating that the data does not exist if not found in the database,

Characterized in that each piece of data is stored in at least one cache node of said plurality of cache nodes and in the same storage in said one or more database systems or in a manner ensuring the matching of addresses of the same data in a cache and a database. to provide.

Alternatively or additionally, upon receiving at least a user request to request the recording of data, the software application may send a command to write to the one or more database systems and to simultaneously write to the plurality of cache nodes So; And populates the plurality of cache nodes with each undetected read query and with each write query of the data storage system.

In another aspect, the present invention provides a method of storing data in a data storage system of a merchandise listing of an airline that includes a software application, one or more database systems and a plurality of cache nodes and retrieving data from the data storage system, The application is configured to receive a user request that requires at least one of reading data to obtain availability for at least one flight and recording data to change availability for at least one flight, Wherein the software application is further configured to send a read query or write query to the data storage system to process a user request, Interfacing with independently, and the method of the following steps to be performed on the at least one data processor by said software application, that is,

When receiving a user request that requires at least one read of data to obtain availability for at least one flight, the software application sending only read queries to the plurality of cache nodes;

The software application processing the user request using the queried data when the software application receives queried data (i.e., retrieved data) from at least one cache node;

If the software application receives undetected from all cache nodes, the software application fetches the one or more database systems; When retrieving the queried data from the one or more database systems, if the queried data is present in the database system, the software application processes the user request using the queried data, and the at least one Adding the interrogated data to a cache node and transmitting the interrogated data to at least one cache node,

Each data being equally stored in at least one of the plurality of cache nodes and in the one or more database systems.

Optionally but advantageously, a user request that at least requires a record that alters the availability of at least one flight is a user request for at least one of purchasing a seat, canceling a seat, changing a seat It is a request.

In another aspect, the present invention provides a data storage system comprising at least one database system, at least one cache node, at least one data processor, and a software application, wherein when the software application is executed by the at least one data processor, Wherein the at least one database system and the at least one cache node are configured to be run independently by the software application.

Advantageously, the number of cache nodes and the processing capabilities of the computing means executing the software application are configured to meet aggregated peak traffic generated by all end-users of the software application.

Optionally, a data storage system according to the present invention may include any of the following optional features and steps:

The number of cache nodes and the storage resources are configured to hold the entire database system content.

Some data in the database system is stored in two or more cache nodes.

The hit ratio question of at least one cache node ultimately reaches 100% when the entire database system content is delivered to at least one cache node by the software application.

In yet another aspect, the present invention provides a list of goods of a travel provider comprising the data storage system of the present invention.

1 illustrates a data storage system in accordance with the present invention;
Fig. 2 illustrates a process that enables the application to ultimately obtain data requested by the end user but not yet in the cache.
3 is a view for explaining a step of simultaneously recording an application and a database in a cache;
4 illustrates a process for obtaining data from a database into a cache in a particular case where a simultaneous write operation occurs;
5 is a diagram illustrating additional details of data write timing performed simultaneously in a database and a cache by an application;
Figure 6 shows the case where the requested data does not exist in the cache nor in the database.
7 is a diagram showing a case where the recording of the database and the cache is erased;

The following detailed description of the invention refers to the accompanying drawings. While this description includes exemplary embodiments, other embodiments are possible, and variations may be made in the embodiments described without departing from the spirit and scope of the invention.

Figure 1 illustrates a data storage system 100 in accordance with the present invention in which a software application 10 interfaces on the one hand with the database system 20 on the one hand and is also referred to as a cache, ). ≪ / RTI >

The database cache system of the present invention to be described below is a front-end processing layer that greatly improves the performance of the data storage system 100 by blocking all read traffic reaching the database system 20 It is noted that the set of cache nodes in operation is mainly specified due to the fact that the entire database content may eventually be delivered. A sufficient number of cache nodes are deployed to support the entire traffic and to handle the entire database content together. Thus, when the system is up and running for a significant period of time, all the data objects contained in the back-end database are eventually delivered to or present in the cache node set and all read queries are processed by the cache node Therefore, no cache miss is detected. The database records are organized in the cache and database systematically so that the cache and database contents are always consistent. The term cache is used in the following description of the present invention, although the data storage system described hereinafter is a faster front end storage and processing system than a database used as a data store.

The data storage system 100 follows a traditional tree hierarchy architecture, which is often used by data processing systems. The middle tier 120 is a layer of software application 10 on which the dedicated software application 10 of the service provider is executed. In the previously used GDS example, this is a product listing application for any airline that is intended to track all seat bookings and bookings on the airline's flight in general.

The client layer 130 is comprised of all remotely located users 40 of the application 10. In the case of a travel application installed by a service provider such as the airline merchandise list, the end user is typically a traditional travel agent. These employees are also individuals who use any of the many available travel websites or online travel agents that can issue travel requests and possibly book air trips online.

The lower layer is the storage layer 110 including the database system 20. The present invention makes no assumptions in the database system used by the service provider. This is often based on a commercially available standard database management system (DBMS), but it may be a dedicated database system. Regardless of which database system is used by the service provider, the system is implemented with a sufficient amount of hardware and software resources to hold and process all the data of the service provider. All of the hardware resources required to implement the data storage system 100 in FIG. 1 are shown as a separate machine-like machine, generally designated by the reference numeral 101. The persistent non-volatile storage medium is assumed to be available from each individual computer and is also available as a separate data disk 102 if needed, for example, to permanently retain the database content.

The data storage system of the present invention includes a storage layer 110 and an intermediate layer 120.

In the present invention, the terms 'user request' or 'request' refer to a demand coming from the user 40 and arriving at the application 10. The user may be a person such as a traveler or a travel agent, or may be a computer system that sends a request.

In the present invention, the term "data query" or "query" refers to a request sent by the application 10 to the cache node 30 and / or the database system 20. The question may be a read or write question.

The read query includes at least instructions from the cache node or instructions to read data from the database system. Generally, the operation of acquiring data from the database system is indicated as 'read' while the operation of acquiring data from the cache node is indicated as 'get'. The queried data is at least partially the data that must be retrieved or read to satisfy a user request.

A write query includes instructions to add, update, set, or delete data. Generally, the operation of changing data from the database system is indicated as 'update' while the operation of changing data from the cache node is indicated as 'set'.

Thus, in the following description, the application 10 receives a user request and sends a data query, which may be a read or write question.

Regardless of the system actually used, the present invention assumes that the database 20 is the ultimate ultimate data store of the service provider. The database 20 preferably includes ACID (Atomicity, Consistency, Isolation and Transformation) that ensures reliable handling of database transactions in terms of atomicity, consistency, isolation, and durability. Durability character set.

The software application 10 of the present invention remains directly connected and is independent of the database 20 via the dedicated interface 12, as is known in the art and for the previously mentioned database system. Thus, the operation of the database system is not affected at all by the one or more cache nodes 30 having the software application 10 and its own dedicated interface 14. As described further in the following detailed description of the present invention, whenever a required transaction that must be processed, that is, the result of completing a new bookkeeping and generally, for example, a cancellation occurs, It is solely to the software application 10 to send a transaction that permanently updates the database to the database.

Thus, there is no connection between any of the cache nodes 30 and the database system 20. No messages, commands or data are exchanged between the database system and the cache node 30. [

All traffic handled by the software application 10 in the data storage system 100 is supported through the dedicated cache software application 10 interface 14. [ As shown in FIG. 1, the cache is functionally located in a storage layer such as a database. The interface 14 and the one or more cache nodes 30 may provide sufficient hardware and software resources to satisfy the expected throughput regardless of the target throughput in the software application 10 layer 120 and the storage layer It is assumed that it is able to process all the traffic of the data storage system 100 by providing and deploying it directly to the data storage system 100. Thus, processing more data is simply accomplished by adding more computation and storage resources to the existing one. This approach provides system scalability that is not constrained by architectural considerations, that is, its cost, power consumption, and floor occupancy, that are different from the number of computer platforms required to be deployed to achieve the target throughput.

To achieve this scalability effectively, the data storage system 100 is based on a global key / value data model that allows content to be matched in a cache and database so that both content can be retrieved using the same key. The data model is thus selected in such a way that it can be mapped directly to the database and cache. In particular, each data set is grouped by functional entities and indexed by a common unique key. This allows the data to be accessed entirely directly from the unique keys in both the database and the cache, but the content can be somewhat different. The only requirements for the data model to operate as described above are:

- Prior to updating, the ability to lock a superset of data to be updated in the cache;

- The ability to update all of the cache keys affected by a given update in the database by updating them.

Typical examples taken in the travel industry are as follows:

Where ( ^* ) O and D are the origin and destination

( ^** ) A leg is part of a flight. For example, a flight can stop from Nice (NCE) to Paris (CDG) and go to New York (NYC). This flight has two sections: NCE-CDG and CDG-NYC. (It is noted that this flight includes three O and D, NCE-CDG, NCE-NYC and CDG-NYC.)

In the above example, the schedule information is stored in a relational database. The "mother" table has a flight-date primary key. One of the "child" tables has an interval-date primary key. Some records (e.g., updates) are performed at the flight level and other records are performed at the interval level. Locking at the flight level is used in both cases. This is used to prevent changes to the flight and to prevent any changes to the flight. Updates to flights can update all intervals and cause simultaneous updates, so locking can not be set at the interval-date level.

Thus, the data model of the database and the cache must match to ensure that the same index keys can be derived to access the cache and database records while locking the database records, if not strictly identical.

The architecture shown in FIG. 1 works with a cache of single-tier client-side distributed caches that supports full throughput and also greatly simplifies management of cache data consistency. The client-side distributed cache means that data distribution among the various cache nodes 30 that constitute the cache is known and operations are performed on the client side in the software application 10 layer. As a result, all of the cache nodes 30 are completely independent and the scalability of the system is not potentially potentially limited. However, actually acquiring more processing capability by adding a new cache node 30 to the storage layer is only achievable if balanced data distribution is also maintained at the nodes. To actually balance this distribution, the data is distributed based on the key characteristics. For example, flight-oriented data is distributed based on the number of flights. For example, any change that can trigger a change in distribution due to a change in the number of available cache nodes or the number of distribution parameters is also appropriate to keep the entire cache system online and remain operational during normal redistribution Redistribution procedures. To this end, a transient dual-feed for two cache configurations is described later in the description of the present invention.

The data storage system 100 of the present invention does not require any type of synchronization mechanism between the cache and the database. The cache is used by the software application 10 in an explicit manner, i.e., during the same user request, for example when using two data sources, such as a database or a cache, or both, Is at the layer of the software application 10. The direct effect of this approach is that the database is not fully aware of the presence of the cache and is not at all affected by the presence or absence of a cache in the data structure of the present invention. The reverse is also true: the cache is completely separate from the database. Both structures can be deployed completely independently if necessary.

It is necessary to not use the invalidation policy to write data in the cache. Every record immediately replaces the data in the cache. The hit ratio reaches 100% even when a very high level of concurrent recording occurs when the entire database content is eventually mapped to the cache and distributed through all available cache nodes 30. [

Cache data can always be considered valid and no extra processing is required to check this validity. In practice, not all cache misses triggers the addition of undetected values from the database to the cache. This is done once for all to ensure that the database is the lowest possible load, that is, fetch only once per data object to be retrieved. This is most likely to occur when the cache becomes operational, for example, power-on of the system after the addition of the cache node 30, failure of the cache node 30, maintenance operation, and the like. The present invention assumes that there is sufficient space in the distributed cache node 30 to receive the entire database content.

The absence of data requested by the end-user in the database is also recorded in the cache. If the data requested by the end user is neither found in the cache nor retrieved from the database, the absence of this data is recorded in the cache so that the next time the cache is queried and the fetching of the corresponding data is not attempted from the database, Limit the load further.

The architecture described in FIG. 1 is scalable to any type of data that may be key-value oriented. This architecture may also be applied to any process that may be key-value oriented. This architecture is particularly applicable to any process designed to check flight availability.

The following figure illustrates the operation performed by the software application 10 between the database and the cache to support all traffic generated by the software application 10, ultimately serving the user request.

As previously shown, the cache portion of the system is fairly simple and consists of one or more independent computers that provide a basic remote key / value protocol. Three basic operations for the software application 10 to update the cache, populate the cache from the database, and retrieve data from the cache are limited to the cache. These operations are as follows:

Settings (key, value): Updates the value associated with the key to the cache indefinitely

Addition (key, value): adds the value associated with the key when the key does not already exist in the cache

Acquisition (key): Returns the value associated with the key from the cache.

The present invention makes no assumption as to how it is actually implemented by the software application 10, as long as the expected performance level can be reached. Advantageously, a bulk operation is defined that allows several basic operations to be transmitted and processed together.

The main part of the system resides in a layer of software applications 10 that controls the distribution of data to all cache nodes 30. The key / value data is spread to the nodes constituting the cache. The characteristics of the key are extracted and the corresponding cache node 30 is computed with the following formula so that the distribution can spread as uniformly as possible across all nodes:

Number of nodes = number of nodes Number of modulo numbers

(node_number = key_property_as a_number MODULE the number_of_nodes)

Flight orientation data uses characteristics commonly used for flights where successive flight numbers have the same characteristics. In this case, the flight number is used directly as the basis for the distribution.

A hash value is computed for the sole O and D keys for the flight-oriented data based on the origin and destination of the flight (O and D).

As already mentioned, balancing the data distribution across all available nodes is an actual key that achieves unlimited scaleability.

Figures 2 and 3 illustrate how the cache is populated and maintained consistent with the database content under the sole control of the software application 10.

FIG. 2 describes a process that allows the software application 10 to ultimately obtain data requested by the end user and not yet in the cache. This situation occurs most often when the cache is being populated, for example, after powering on the system or when a new node is inserted or removed, and when rebalancing the cache node 30 content is in progress .

When the software application 10 needs to answer a user request, the cache is first read 210 via a "get" operation. In an example of an airline merchandise listing database, this is to answer one of a number of user requests issued by the end user of the database, for example, in order to find out if the seat is available on a particular flight, If the corresponding data is not present in the cache, i.e., generally if the corresponding data is not already in the cache by a previous read, then the cache returns "not detected" to the software application 10 (220). Otherwise, the information is explicitly returned directly from the cache to the software application 10 and the "acquire" operation is terminated. The software application 10 may meet the user request of the end-user. Eventually, the application collects the queried data with additional data and returns it in response to a request from the end-user. The additional data is typically other data that may need to be retrieved to satisfy the user request. For example, some data may be retrieved from the cache node, while other data needed to satisfy the same user request must be retrieved from and / or read from the other cache node.

When the queried data receives information that is not present in the cache, the software application 10 queries the database in a "read" operation (230). The undetected information is returned to the software application 10 (240). Reading data from the database takes place in the database-only interface 12 described previously. This is done by issuing a corresponding question from the software application 10 to a database management system (DBMS) used by the data storage system 100 of the present invention.

When receiving data not found in the cache from the database, the software application 10 performs an "add " operation 250 to cache the data. From this time on, the data resides in the cache (270) and is not reconfigured as long as the cache is running. When this operation is complete, a positive acknowledgment (OK) 260 is returned to the software application 10.

It is noted that this process occurs only once, while the cache is up and running for any given data stored in the database and cache node 30, which is the same or consistent. This occurs at a first time when data is requested by the software application 10 but not yet in the cache. The corresponding data may then be updated, for example, if the database content needs to be changed due to the sale of the airline seat. In this case, as will be described later, the software application 10 does not need to update both the cache and the database to re-execute the process of FIG.

3 illustrates a process for simultaneously updating the database and the cache from the software application 10. [

To keep the database and cache content consistent at all times, the software application 10 always updates both the cache and the database. The update of the cache is performed 310 in the previously described "set" operation. At the same time, the "update" 305 of the database is performed using the query language of the DBMS in use. This update is valid after the operation is committed 320 to the database by the application.

More precisely, this setting is not performed when the update is performed on the database, but is performed when the commit is performed. The application keeps the data set in memory until a commit is performed. There may be a number of steps between update 305 and configuration 310. [ However, the settings 310 and the commit 320 are intended to be performed in series.

In a steady state, i. E. After the system is up and running for a considerable period of time, the entire contents of the database eventually come to all the cache nodes 30 and are distributed to them; Subsequent update operations, i.e., content update, insertion and deletion, are the only operations that need to be performed on the database interface, thus further reducing the database load. The case of a delete operation that triggers a nullification of the corresponding data in the cache is described in FIG.

It should also be noted that the process of FIG. 3 does not assume that any particular condition needs to be met in order to be written to the cache, so the cache of the present invention is both populated from read and write operations. This significantly contributes to promoting population of the cache node 30 after power-up compared to a system that populates the cache using read only. This is accomplished because it is possible and simple to do so because both the database and the data objects stored in the cache are kept updated, as already mentioned, because the cache data objects passed to the software application 10 are extracted from various parts of the database Is not possible in other cache solutions where the database and cache contents can be quite different in an attempt to disassemble the data or attempt to keep cache storage requirements to a minimum in general.

Figure 4 describes the process of Figure 2 in a particular case where concurrent writing (e.g., updating) of the database is requested by the software application 10 to interfere with execution.

In the same manner as described in FIG. 2, the process begins with "fetching" 210 the data from the cache 210 followed by "not detected" 220 triggering fetching of non- . However, the undetected data is normally returned to the software application 10 (240), but the write query 410 for the same data is also received by the software application 10. This recording is performed as described in Fig. This recording is performed in the cache in the "set" operation 310 and in the database in the "update" The corresponding data is immediately available 420 when the "set" is issued to the cache, and becomes available in the database when the "commit" Before the setting is triggered, the application keeps the data in memory ("set to memory").

Thereafter, in this particular case, the cache content does not need to be updated further by a subsequent "add" 250 resulting from the fetch 230 of undetected data from the database because the fetch of non- It was updated in time. Then the "add" 252 is actually stopped. A negative acknowledgment (KO) 262 is returned to inform the software application 10 that the update of the cache was not actually performed by an "add" operation.

Thus, in order to update the data read from the database to the cache, the present invention can send data to the cache without locking the data in the database using additional commands. In fact, if this data is still not in the cache when you try to add data, this data can be added effectively. If the cache has been updated in the meantime by the update process, the addition may fail, but this is expected: the update process locks the database and makes the update to this key primacy, so that it is generally in the cache.

These features of the present invention are particularly advantageous because they allow the database system and cache to lock against each other or affect each other's performance while still ensuring that the data is not read more than once in the database, It enables very smooth integration with the process.

5 provides additional details on the timing of data updates performed simultaneously by the software application 10 on the database and the cache.

The software application 10 initiates an update transaction by issuing a corresponding query 510 to the database that retrieves the currently stored value. At the same time, a database management system (DBMS) locks the currently stored value to prevent simultaneous updates from occurring from other software applications 10. At the software application layer, the data is processed by the software application 10. An update is also performed in the buffer cache 540 of the software application 10 when the data is ready to be updated 530 already by the DBMS to hold new data to be stored or transferred to the cache.

The software application 10 may then commit the change 550 which may be performed directly in the cache 552 and committed to the database 554 in the "set" operation. Thus, it can be seen that new data is first available in the cache 556 (556) before being actually committed in the database (558). Reference numeral 556 denotes a time frame in which the update is not yet available in the database system 20 but is made available to the final user in the cache.

If for some reason the commit to successfully complete the previous write operation in the cache fails due to hardware and / or software failure, for example, the "set" operation 552 is rolled back, It will remain unchanged. Thus, if the commit fails, a "commit KO" 560 is raised to the application and the application issues a delete 562 to the cache to remove the added data. As a result, the erroneous value is present in the cache for a mean time 564.

Thus, the highest quality non-database related and affected data quality is provided to the cache: the update is propagated to the cache using a write ahead commit to the "commit request" data. If a delayed constraint on cached data is prohibited, this makes the data in the cache "at worse" ahead of the database, at no extra cost, especially at a very high cost of a conventional two-phase commit architecture. This quality meets the data quality requirements for availability requests and can even be considered advantageous from the end client's perspective.

6 illustrates a case where the questioned data does not exist in the cache nor in the database. This includes cases where the end-user requests information that the user does not have in the database.

When such a situation occurs, the absence of corresponding data is also recorded in the cache to prevent further queries of the database. Then, the next time the cache is queried from the software application 10, information that the queried data does not exist in the database is passed directly by the cache itself, further reducing the database load.

The process is similar to that described in Fig. The read 230 of the corresponding data in the database is also returned to the software application 10 after the "fetch" operation 210 issued to the cache returns "not detected" ≪ / RTI > Thereafter, the absence of data is added 650 to the cache. As with the data, the absence of data is available 270 to the cache, which in turn returns an acknowledgment 260 to the software application 10.

According to a non-limiting embodiment, each data is associated with a header to form a record, which indicates whether the content has not been detected in the database system 20. Thus, reading only the header of the record can tell if it is necessary to fetch the database system. According to an alternative embodiment, the cache node stores a particular value associated with the data, where the particular value indicates that the data does not exist in the database. Thus, reading only the value of a record will know if it is necessary to fetch the database system.

FIG. 7 shows a case already mentioned in FIG. 3 where a specific update operation from an application is to delete (705) data from a database. This operation is generally performed as described in FIG. 3, except that the erased data is not actually removed from the cache and replaced by an indication of "Absence of data ". When the deletion is committed 320 to the database by the application, the corresponding information is stored in the cache in a particular "set""Absence of data" is immediately available (330). Thus, as described previously, if a cache is later retrieved, this cache can directly provide information that the requested data is no longer in the cache nor in the database.

The following describes, for example, a case necessary for changing the configuration of the database system of the present invention to cope with traffic increase. Additional cache nodes may be added to extend the system configuration shown in FIG. 1 to provide more cache storage capacity and distribute increased traffic over a larger number of processing nodes. However, there is a key to uniquely address data at a node so that, with a larger number of nodes, generally speaking, whenever the number of active nodes is to be changed, the entire traffic can be actually uniformly spread across a whole new set of nodes Must be re-computed.

The present invention does not assume any particular way of computing the keys from the data objects that are stored and retrieved identically from the database and the cache. For the most part, depending on the type of data being processed by a particular application, some hash functions are used and the node address is derived directly from the hash key by additionally computing the number of nodes with a hash key module. Thus, when the number of nodes is changed, different results are obtained because it is necessary to search for and retrieve specific data objects at different nodes of the new configuration. The problem arises from the fact that configuration updates are not atomic and must be performed transparently while the database system is fully operational. Not all cache clients are aware of the new configuration at the same time. This means that some data recording can be performed based on the new configuration while another data recording still uses the old configuration. As a result, there may be inconsistencies in the dataset between the cache and the database.

The present invention addresses this by enabling a procedure referred to as "dual-feed ". Dual feeds are usually one extra configuration in addition to being used in the cache, thus keeping the name "dual-feed". The extra configuration is not used by default and can be activated at configuration changes. When a configuration is activated, all write operations are sent in a standard configuration and a dual-feed configuration. A time-to-live (TTL) is a characteristic associated with each item in the cache. As the name implies, this name corresponds to a valid time period entry. When this time period expires, this item can no longer be retrieved from the cache, resulting in cache miss detection as if no data were detected. This can be set by configuration: for standard configuration and for dual-feed configuration. If the presence time is not set, this item does not expire.

Since the activation of a dual-feed configuration is not atomic, this dual feed must first be activated in the short-lived time. Once the dual feed configuration is fully activated, the time of presence can be eliminated. The standard configuration and dual-feed configuration can only be swapped once the presence time has expired. When the configuration change is finished, the dual feed can be deactivated. During the phase in which the configuration is being propagated (dual-feed activation / deactivation), only some "invalid" data can be recorded where it is not read. Thus, the procedure is as follows:

- Create a dual-feed configuration in short TTL

- Activate the dual-feed configuration and wait for its propagation

- Remove short TTL from dual-feed configuration

- Exchange standard configuration and dual-feed configuration and wait for its propagation

- Disable dual-feed

A set of procedures that allow any change in the system on-line is described below.

The proposed architecture suggests a scalability that the entire system may not be in a position to operate properly without a cache. To address this situation, according to one embodiment of the present invention, all maintenance operations are performed on-line, and affect at most one node (or equivalence ratio of traffic) at a time (e. G. It is proposed to reduce the impact on the database by upgrading or replacing cache nodes one by one, or by performing global cache changes performed using a dual feed mechanism).

- Cache node upgrades or replacements are done one by one. The system preferably uses a database to retrieve data that should have been hosted by this node.

Global cache changes, in general, add, remove or change multiple cache nodes that can significantly change the global distribution performed using the dual feed mechanism described in the previous paragraph.

From the above detailed description, the present invention provides a mechanism that is non-strictly compliant with ACID, yet very scalable, does not affect the database, allows a 100% hit ratio, and above all, It is clearly understood that data can be matched between the cache and the database. Furthermore, while still benefiting from the offloading effect of the cache, the present invention is capable of caching data very dynamically, typically up to several dozen records per second per unitary data.

Claims (25)

A method for storing and retrieving data in a data storage system,
The data storage system comprising at least one computer implementing a middle tier, the at least one computer comprising: at least one data processor; and at least one data processor running on the at least one computer Including a software application,
The data storage system further includes a plurality of cache nodes and one or more database systems that implement a storage tier,
Wherein the intermediate layer is configured to interface a client layer and a storage layer of the data storage system,
The method comprises:
At the at least one computer in the middle layer,
Sending a read query to the plurality of cache nodes in response to receiving a first user request to request at least one reading of data from a user device of the client layer;
Responsive to receiving the first queried data from at least one cache node in response to the read query, to the at least one data processor using the first query response data to retrieve the first user request , ≪ / RTI >
Fetching the one or more database systems based on the first user request to the at least one data processor in response to receiving a miss from all cache nodes in response to the read query; Wow,
Processing the first user request using the second query response data from the one or more database systems in response to retrieving second query response data from the one or more database systems as a result of the fetching, Receiving from the one or more database systems in response to the undetected read query a command to add the second query response data to at least one cache node and sending the second query response data to the at least one cache node, Populating the second query response data with at least one cache node;
Responsive to receiving a second user request to fetch at least one of the updated data at the same time as fetching the second question and answer data from the one or more database systems, Sending a command to write a database system and sending a command to simultaneously write the at least one cache node with the updated data thereby causing each write query of the data storage system to be written to the plurality of And aborting subsequent additions of the second query response data to the at least one cache node such that the updated data is stored in the plurality of cache nodes.
A method for storing and retrieving data in a data storage system. The method according to claim 1,
Wherein the second user request comprises at least one of adding, updating and deleting data to the database system.
A method for storing and retrieving data in a data storage system. The method according to claim 1,
Further comprising receiving a positive acknowledgment when successfully completing adding the second query response data from the one or more database systems to the at least one cache node.
A method for storing and retrieving data in a data storage system. The method according to claim 1,
Wherein the at least one computer in the middle layer interfaces independently with the one or more database systems on a first dedicated interface,
Wherein the at least one computer in the middle layer interfaces with the plurality of cache nodes on a second dedicated interface.
A method for storing and retrieving data in a data storage system. The method according to claim 1,
Wherein the data model of the plurality of cache nodes and the data model of the one or more databases are consistent so that identical address keys can be derived to access the cache nodes and database data.
A method for storing and retrieving data in a data storage system. The method according to claim 1,
Wherein the at least one computer of the middle layer is an inventory system of a travel provider,
A method for storing and retrieving data in a data storage system. The method according to claim 1,
Wherein the first user request is sent by at least one of a travel agent, an online travel agent,
A method for storing and retrieving data in a data storage system. The method according to claim 1,
In response to transmitting an instruction for writing data in the one or more database systems and an instruction for simultaneously writing the at least one cache node,
Retrieving currently stored data to which the record is applied from the one or more database systems and locking the currently stored data;
Writing new data to be stored to the one or more database systems;
Writing to the cache buffer of the at least one computer of the intermediate layer to temporarily hold new data to be stored;
Forwarding and setting new data to be stored to the at least one cache node;
Further comprising committing a transaction to the one or more database systems.
A method for storing and retrieving data in a data storage system. Claim 9 has been abandoned due to the setting registration fee. 9. The method of claim 8,
Further comprising, in response to the commit failing, deleting the new data at the at least one cache node.
A method for storing and retrieving data in a data storage system. The method according to claim 1,
Determining the at least one cache node to which the second query response data is to be added or the instruction to write the at least one cache node to the updated data is transmitted from among the plurality of cache nodes Including,
A method for storing and retrieving data in a data storage system. Claim 11 has been abandoned due to the set registration fee. 11. The method of claim 10,
Wherein the at least one cache node among the plurality of cache nodes is determined based on load balancing.
A method for storing and retrieving data in a data storage system. The method according to claim 1,
In response to one or more database systems returning a miss associated with the requested data of the first user request, the data of absence is immediately available for all subsequent read queries To avoid the subsequent fetch of the one or more database systems to retrieve the requested data of the first user request, and to store the member data corresponding to the first user request for addition to the at least one cache node To at least one cache node,
A method for storing and retrieving data in a data storage system. The method according to claim 1,
Wherein each of the plurality of cache nodes stores a record including a header,
Wherein the header of the at least one cache node indicates that the requested data is not detected in the at least one database system or that the value of the requested data is set to a value representing the requested member data.
A method for storing and retrieving data in a data storage system. The method according to claim 1,
Wherein the records of the plurality of cache nodes and the records of the one or more database systems are stored such that the associated records of the plurality of cache nodes and the one or more database systems are addressed consistently.
A method for storing and retrieving data in a data storage system. Claim 15 is abandoned in the setting registration fee payment. 15. The method of claim 14,
Wherein a key associated with the record causes a record stored in the one or more database systems to be locked.
A method for storing and retrieving data in a data storage system. Claim 16 has been abandoned due to the setting registration fee. 15. The method of claim 14,
Wherein each record of the plurality of cache nodes and each record of the one or more database systems are grouped by a functional entity and the key is stored in the one or more database systems and the plurality of cache nodes Which makes the record immediately accessible to the user.
A method for storing and retrieving data in a data storage system. Claim 17 has been abandoned due to the setting registration fee. 17. The method of claim 16,
Each functional entity is a flight-date,
Each key is a flight date key,
A method for storing and retrieving data in a data storage system. A method for storing and retrieving data in a data storage system,
The data storage system comprising at least one computer implementing a middle tier, the at least one computer comprising: at least one data processor; and at least one data processor running on the at least one computer Including a software application,
The data storage system further includes a plurality of cache nodes and one or more database systems that implement a storage tier,
Wherein the intermediate layer is configured to interface a client layer and a storage layer of the data storage system,
The method comprises:
At the at least one computer in the middle layer, sending a read query only to the plurality of cache nodes in response to receiving a first user request to request reading of data,
Processing the first user request with the first query response data in response to receiving first queried data from at least one cache node in response to the read query;
Fetching the one or more database systems based on the first user request in response to receiving a miss from all cache nodes in response to the read query;
Responsive to retrieving second query response data from the one or more database systems as a result of the fetching, processing the first user request, and processing the second query response data and the second query response data to the at least one cache node, Transmitting the query response data from the one or more database systems to the at least one cache node in response to the undetected read query by sending an instruction to the at least one cache node to add query response data a populate step,
In response to the non-detection from all cache nodes in response to the read query and in response to the one or more database systems returning undetected associated with the requested data of the first user request, Absence data indicating that the requested data of the first user request is not stored in the one or more database systems of the data storage system to avoid subsequent fetches of the one or more database systems for retrieving the data ) To the plurality of cache nodes.
A method for storing and retrieving data in a data storage system. Claim 19 is abandoned in setting registration fee. 19. The method of claim 18,
Wherein the data storage system is an airline inventory system,
Wherein the one or more database systems store availability for flights managed by the airline inventory system,
The plurality of cache nodes storing availability for a flight managed by the airline inventory system,
Wherein the first user request is for availability regarding at least one flight managed by the airline inventory system,
A method for storing and retrieving data in a data storage system. Claim 20 has been abandoned due to the setting registration fee. 20. The method of claim 19,
In response to receiving a second user request requesting a write to modify availability for at least one flight, sending a command to write the one or more database systems, Further comprising populating the plurality of cache nodes in response to each record query of the data storage system by sending a command to simultaneously write the plurality of cache nodes.
A method for storing and retrieving data in a data storage system. Claim 21 has been abandoned due to the setting registration fee. 21. The method of claim 20,
Wherein the second user request corresponds to at least one of purchasing a seat, canceling a seat, changing a seat,
A method for storing and retrieving data in a data storage system. In a data storage system,
One or more database systems;
A plurality of cache nodes;
At least one data processor; And
A memory for storing a software application,
Wherein the execution of the software application by the at least one data processor causes the at least one processor to:
In response to receiving a first user request of data from a user device, sending a read query to the plurality of cache nodes,
Processing the first user request using the first query response data in response to receiving first queried data from the plurality of cache nodes in response to the read query,
In response to receiving a miss from the plurality of cache nodes in response to the read query, fetching the one or more database systems based on the first user request,
Processing the first user request using the second query response data in response to retrieving second query response data from the one or more database systems as a result of the fetching, Sending a second query response data to the plurality of cache nodes by sending an instruction to the plurality of cache nodes to the plurality of cache nodes to send the second query response data from the one or more database systems to the plurality of cache nodes in response to the non- Populating the response data;
Responsive to fetching the second query response data from the one or more database systems and receiving a second user request to request at least one record of updated data, Transmitting a write query of the data storage system to the plurality of cache nodes by sending an instruction to write the at least one cache node with the updated data, And aborting subsequent additions of the second query response data to the plurality of cache nodes such that the updated data is stored in the plurality of cache nodes.
Data storage system. Claim 23 has been abandoned due to the setting registration fee. 23. The method of claim 22,
Wherein the number of cache nodes is configured to hold all content of the database system.
Data storage system. Claim 24 is abandoned in setting registration fee. 23. The method of claim 22,
Wherein some data in the data storage system is stored in more than one cache node.
Data storage system. Claim 25 is abandoned in setting registration fee. 23. The method of claim 22,
Wherein the data storage system corresponds to an inventory system of a travel provider,
Data storage system.

Images