Patent Description:
<CIT> discloses an order promising system including a commerce module that receives a product inquiry from a user.

Embodiments of the present invention provide techniques for performing order promising operations in an order promising system, including scheduling orders and responding to inquiries about availability of items and status of orders. Order promising operations are performed using multiple servers that share summary data, which is a read-only /summary of the state of the supply chain. Inquiries can be processed by multiple servers in parallel based upon the summary data, and the number of servers can be increased to achieve high throughput order promising.

Techniques are disclosed for high-throughput order promising using multiple servers. A method for providing item availability information in response to an inquiry requesting availability status of a specified item is provided in accordance with claim <NUM>. The summary data structure is shared among two or more availability servers and one or more scheduling servers using an one or more in-memory database instances, and is partitioned between the two or more availability servers, such that each of the two or more availability servers is assigned to different partitions of the summary data structure. A request broker of the computer system then determines, by evaluating routing rules, which of the two or more availability servers is assigned to the summary data associated with the specified item. The assigned availability server determines availability data for the specified item based upon the summary data and an inquiry response is sent indicating the availability of the item based upon the determined availability data. Order scheduling is provided by a method in accordance with claim <NUM>. Storing the availability information may cause the in-memory database to generate a notification indicating that updated availability information is available, and the notification may be received at an availability server, which can update the summary data structure accordingly.

In some embodiments, retrieving the summary data includes querying the one or more in-memory database instances for the summary data associated with the item. Retrieving the summary data may be done without obtaining exclusive access to the in-memory database. The summary data may include one or more item identifiers and associated availability information. The availability information may include one or more dates of availability of the items. Determining the availability data may include retrieving a date of availability associated with the item by the summary data.

In one aspect, a notification may be received indicating that updated availability information is available. The updated availability information may be stored in the summary data structure. In another aspect, the summary data structure may be optimized for fast insertion and retrieval of data.

In further embodiments, a scheduling request is received by the request broker of the computer system that identifies an item to be scheduled. A schedule for the item may be determined by the request broker of the computer system and availability information stored by the request broker of the computer system for the item in an in-memory database. The availability information may be derived from the schedule and a scheduling response based upon the schedule may be sent or delivered by the request broker of the computer system. In one aspect, storing availability information in an in-memory database is performed by a separate thread. Storing may cause the one or more in-memory database instances to generate a notification indicating that updated availability information is available. Thereafter, the notification indicating that updated availability information is available may be received and updated availability information may be stored at the availability server in the summary data structure.

Specific details are given in the following description to provide a thorough understanding of the embodiments. However, it will be understood by one of ordinary skill in the art that the embodiments may be practiced without these specific details. For example, circuits, systems, networks, processes, and other components may be shown as components in block diagram form in order not to obscure the embodiments in unnecessary detail.

Also, it is noted that individual embodiments may be described as a process which is depicted as a flowchart, a flow diagram, a data flow diagram, a structure diagram, or a block diagram. Although a flowchart may describe the operations as a sequential process, many of the operations can be performed in parallel or concurrently. A process is terminated when its operations are completed, but could have additional steps not included in a figure. A process may correspond to a method, a function, a procedure, a subroutine, a subprogram, etc. When a process corresponds to a function, its termination can correspond to a return of the function to the calling function or the main function.

The term "machine-readable medium" includes, but is not limited to portable or fixed storage devices, optical storage devices, wireless channels and various other mediums capable of storing, containing or carrying instruction(s) and/or data. A code segment or machine-executable instructions may represent a procedure, a function, a subprogram, a program, a routine, a subroutine, a module, a software package, a class, or any combination of instructions, data structures, or program statements. A code segment may be coupled to another code segment or a hardware circuit by passing and/or receiving information, data, arguments, parameters, or memory contents. Information, arguments, parameters, data, etc. may be passed, forwarded, or transmitted via any suitable means including memory sharing, message passing, token passing, network transmission, etc..

Furthermore, embodiments may be implemented by hardware, software, firmware, middleware, microcode, hardware description languages, or any combination thereof. When implemented in software, firmware, middleware or microcode, the program code or code segments to perform the necessary tasks may be stored in a machine-readable medium.

<FIG> is a block diagram illustrating components of an exemplary operating environment The system <NUM> can include one or more user computers <NUM>, <NUM>, which may be used to operate a client, whether a dedicated application, web browser, etc. The user computers <NUM>, <NUM> can be general purpose personal computers (including, merely by way of example, personal computers and/or laptop computers running various versions of Microsoft Corp. 's Windows and/or Apple Corp. 's Macintosh operating systems) and/or workstation computers running any of a variety of commercially-available UNIX or UNIX-like operating systems (including without limitation, the variety of GNU/Linux operating systems). These user computers <NUM>, <NUM> may also have any of a variety of applications, including one or more development systems, database client and/or server applications, and web browser applications. Alternatively, the user computers <NUM>, <NUM> may be any other electronic device, such as a thin-client computer, Internet-enabled mobile telephone, and/or personal digital assistant, capable of communicating via a network (e.g., the network <NUM> described below) and/or displaying and navigating web pages or other types of electronic documents. Although the exemplary system <NUM> is shown with two user computers, any number of user computers may be supported.

In some embodiments, the system <NUM> may also include a network <NUM>. The network may be any type of network familiar to those skilled in the art that can support data communications using any of a variety of commercially available protocols, including without limitation TCP/IP, SNA, IPX, AppleTalk, and the like. Merely by way of example, the network <NUM> maybe a local area network ("LAN"), such as an Ethernet network, a Token-Ring network and/or the like; a wide-area network; a virtual network, including without limitation a virtual private network ("VPN"); the Internet; an intranet; an extranet; a public switched telephone network ("PSTN"); an infra-red network; a wireless network (e.g., a network operating under any of the IEEE <NUM> suite of protocols, the Bluetooth protocol known in the art, and/or any other wireless protocol); and/or any combination of these and/or other networks such as GSM, GPRS, EDGE, UMTS, <NUM>, <NUM>, CDMA, CDMA2000, WCDMA, EVDO etc..

The system may also include one or more server computers <NUM>, <NUM>, <NUM> which can be general purpose computers and/or specialized server computers (including, merely by way of example, PC servers, UNIX servers, mid-range servers, mainframe computers rack-mounted servers, etc.). One or more of the servers (e.g., <NUM>) may be dedicated to running applications, such as a business application, a web server, application server, etc. Such servers may be used to process requests from user computers <NUM>, <NUM>. The applications can also include any number of applications for controlling access to resources of the servers <NUM>, <NUM>, <NUM>.

The web server can be running an operating system including any of those discussed above, as well as any commercially available server operating systems. The web server can also run any of a variety of server applications and/or mid-tier applications, including HTTP servers, FTP servers, CGI servers, database servers, Java servers, business applications, and the like. The server(s) also may be one or more computers that can be capable of executing programs or scripts in response to the user computers <NUM>, <NUM>. As one example, a server may execute one or more web applications. The web application may be implemented as one or more scripts or programs written in any programming language, such as JavaTM, C, C #, or C++, and/or any scripting language, such as Perl, Python, or TCL, as well as combinations of any programming/scripting languages. The server(s) may also include database servers, including without limitation those commercially available from Oracle®, Microsoft®, Sybase®, IBM® and the like, which can process requests from database clients running on a user computer <NUM>, <NUM>.

In some embodiments, an application server may create web pages dynamically for displaying on an end-user (client) system. The web pages created by the web application server may be forwarded to a user computer <NUM> via a web server. Similarly, the web server can receive web page requests and/or input data from a user computer and can forward the web page requests and/or input data to an application and/or a database server. Those skilled in the art will recognize that the functions described with respect to various types of servers may be performed by a single server and/or a plurality of specialized servers, depending on implementation-specific needs and parameters.

The system <NUM> may also include one or more databases <NUM>. The database(s) <NUM> may reside in a variety of locations. By way of example, a database <NUM> may reside on a storage medium local to (and/or resident in) one or more of the computers <NUM>, <NUM>, <NUM>, <NUM>, <NUM>. Alternatively, it may be remote from any or all of the computers <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, and/or in communication (e.g., via the network <NUM>) with one or more of these. In a particular set of embodiments, the database <NUM> may reside in a storage-area network ("SAN") familiar to those skilled in the art. Similarly, any necessary files for performing the functions attributed to the computers <NUM>, <NUM>, <NUM>, <NUM>, <NUM> may be stored locally on the respective computer and/or remotely, as appropriate. In one set of embodiments, the database <NUM> may be a relational database, such as Oracle <NUM>, which is adapted to store, update, and retrieve data in response to SQL-formatted commands.

<FIG> illustrates an exemplary computer system <NUM>. The system <NUM> may be used to implement any of the computer systems described above. The computer system <NUM> is shown comprising hardware elements that may be electrically coupled via a bus <NUM>. The hardware elements may include one or more central processing units (CPUs) <NUM>, one or more input devices <NUM> (e.g., a mouse, a keyboard, etc.), and one or more output devices <NUM> (e.g., a display device, a printer, etc.). The computer system <NUM> may also include one or more storage device <NUM>. By way of example, storage device(s) <NUM> may be disk drives, optical storage devices, solid-state storage device such as a random access memory ("RAM") and/or a read-only memory ("ROM"), which can be programmable, flash-updateable and/or the like.

The computer system <NUM> may additionally include a computer-readable storage media reader 225a, a communications system <NUM> (e.g., a modem, a network card (wireless or wired), an infrared communication device, etc.), and working memory <NUM>, which may include RAM and ROM devices as described above. In some embodiments, the computer system <NUM> may also include a processing acceleration unit <NUM>, which can include a DSP, a special-purpose processor, and/or the like.

The computer-readable storage media reader 225a can further be connected to a computer-readable storage medium 225b, together (and, optionally, in combination with storage device(s) <NUM>) comprehensively representing remote, local, fixed, and/or removable storage devices plus storage media for temporarily and/or more permanently containing computer-readable information. The communications system <NUM> may permit data to be exchanged with the network <NUM> and/or any other computer described above with respect to the system <NUM>.

The computer system <NUM> may also comprise software elements, shown as being currently located within a working memory <NUM>, including an operating system <NUM> and/or other code <NUM>, such as an application program (which may be a client application, web browser, mid-tier application, RDBMS, etc.). It should be appreciated alternate embodiments of a computer system <NUM> may have numerous variations from that described above. For example, customized hardware might also be used and/or particular elements might be implemented in hardware, software (including portable software, such as applets), or both. Software of computer system <NUM> may include code <NUM> for implementing embodiments of the present invention as described herein.

<FIG> is a block diagram illustrating an exemplary high throughput global order promising system <NUM> using a shared in-memory database instance <NUM> according to one embodiment of the present invention. The order promising system <NUM> may be implemented as, for example, computer program code executable on a processor of a computer system. The order promising system <NUM> performs high-throughput order promising operations, which include tracking orders and availability of items such as products or services, and providing promises about the dates by which ordered items can be delivered. Order promising requests, such as item availability inquiries <NUM>, order scheduling requests <NUM>, or other types of requests, are generated by an online store <NUM> or other source, and sent to a request broker <NUM>, which distributes the requests to multiple different types of servers, including availability servers <NUM> and scheduling servers <NUM>, according to the types of the requests <NUM>, <NUM> and other criteria defined by routing rules <NUM>. Scheduling servers <NUM> use a persistent database <NUM> to store detailed data <NUM> that represents the state of the order processing system <NUM>, including the orders, inventory information, promised dates, order promising workflow configuration, and so on. The scheduling servers <NUM> share portions of the detailed data <NUM> with other types of servers, such as the availability servers <NUM> and shipping options servers <NUM>. The shared data is referred to herein as summary data <NUM>, and includes item status information <NUM>, item availability information <NUM>, and other information that may be needed by the other types of servers <NUM>, <NUM>. The summary data <NUM> is shared among the servers <NUM>, <NUM>, <NUM> using an in-memory database <NUM> or other high-speed shared database.

Sharing the summary data <NUM> via the in-memory database <NUM> enables the order promising operations to be performed more efficiently, because the different types of servers can perform operations in parallel (i.e., concurrently). System throughput, e.g., the rate of processing of order promising requests, can be increased by adding more servers <NUM>, <NUM>, <NUM>, and dividing, i.e., partitioning, the items among the servers, so that multiple scheduling servers can process orders for items in different partitions in parallel. The availability servers <NUM> can similarly be assigned to different partitions of the data, and/or load balanced by other means, since the inquiry operations performed by the availability servers <NUM> read but do not write to the summary data <NUM>. Thus, multiple availability servers <NUM> can perform inquiry operations on the same portion(s) of the summary data <NUM> (e.g., the same items) in parallel. Each of the availability servers <NUM> can maintain its own copy of the summary data <NUM> in a summary structure <NUM>, which can be used when processing availability inquiries <NUM>. An availability server <NUM> modifies the summary structure <NUM> in response to notifications received from the in-memory database <NUM> indicating that the summary data has changed. In other embodiments, the availability servers <NUM> can read the summary data <NUM> directly using the in-memory database <NUM> when processing availability inquiries, instead of maintaining the summary structure <NUM>.

In one set of embodiments, the front end <NUM>, which can be, for example, a web page or other user interface for ordering items in an online store, receives requests to place orders, check item availability, change or cancel orders, and the like, from users <NUM>. The front end <NUM> may be provided by a web server that implements the online store and sends order-related requests to an order request broker <NUM>, which distributes the requests to the availability servers <NUM> and the scheduling servers <NUM>. Each of the scheduling servers <NUM> uses an order processing engine <NUM> to perform the actual order promising operations, such as scheduling orders, completion date promising, and so on. The engine <NUM> may be, for example, implemented in computer program code in a language such as C, C++, JAVA, or the like. In one example, the order processing engine <NUM> constructs and maintains order processing data structures in a memory of the computer system, e.g., random access memory ("RAM") or the like, that contain order processing data representing orders and related information needed to perform the order processing operations. The engine <NUM> can transfer the order processing data between system memory and a persistent storage medium such as the database <NUM>. In one example, when the engine <NUM> is started, it loads existing order data from detailed data <NUM> stored in the database <NUM> into system memory, so that order promising operations are performed using memory access operations on order processing data stored in memory. The database <NUM> may be, for example, a relational database, such as the Oracle® relational database management system, or the like.

In one or more embodiments, the engine <NUM> stores and retrieves order information in the database <NUM> as information is consumed and generated by the processing logic. For example, when a new order <NUM> is placed, the engine <NUM> retrieves information about the availability of the ordered item from the database <NUM> and/or source systems <NUM>, determines a promised date for completion of the order, stores information representing the order in the database <NUM> as detailed data <NUM>, and provides the promised date and status of the order, which are returned to the front end <NUM> in an order scheduling result <NUM>. The source systems <NUM> provide information used in order promising, such as inventory details, which can be loaded into the database <NUM>. Thus, the database <NUM> contains information needed by the order promising system <NUM>, including information about the orders, which is updated as orders are created, modified, and completed. The detailed data <NUM> in the database <NUM> is stored persistently, e.g., on a storage medium such as a disk, so that the information about the state of the orders, processing times, and so on, is not lost if the order processing service <NUM> is shut down, e.g., to perform system maintenance, or as a result of a power failure or crash.

In one aspect, the web front end <NUM> can receive requests for orders at high rates, which can result in corresponding high rates of requests to the engine <NUM>. For example, online stores operated by retailers or distributors with very high volumes, particularly with extreme peaks during the introduction of new products, generate requests at high rates that can exceed the capabilities of a single instance of the engine <NUM>. If the user interface front end <NUM> generates incoming order promising operation requests <NUM>, <NUM> at a rate greater than the maximum processing rate of the engine <NUM>, problems such as delays in responding to user order requests can ensue.

In one set of embodiments, the order promising system <NUM> uses availability servers <NUM> and scheduling servers <NUM> to increase the throughput performance (e.g., orders processed per second) of the system <NUM> beyond that provided by a single instance of the engine <NUM>. This system architecture allows for dynamic scalability combined with monitoring of response time and other performance metrics to target. The system <NUM> allows for rules and thresholds that automatically guide the administrative components to scale up or down to adjust for the varying system loads. The architecture allows for 24X7 system availability while providing elasticity in terms of throughput and load balancing.

In one set of embodiments, as introduced above, the order promising system <NUM> receives, processes, and responds to requests to perform order promising operations using multiple types of servers that share order summary data. The order promising operations are divided into multiple different types, including the availability inquiry operation that checks if items are available for ordering, and the order scheduling operation. Availability inquiry operations are processed by the availability servers <NUM>. The order scheduling operation creates and schedules a new order for an item, and provides a promise as to when the order will be completed. Order scheduling operations are processed by the scheduling servers <NUM>. Other types of operations include a shipping options inquiry operation, which inquires about the options available for shipping an order. Shipping options operations can be processed by a shipping options server <NUM>. Thus, orders or other operations that can be treated differently can be associated with a type and processed by a particular type of server, which can be optimized to process orders of that type efficiently. For example, each type of server can maintain and use a different portion or copy of the detail data <NUM> that represents the state of the order processing system. The different types of servers can then access their portions or copies of the data more efficiently than they can access the detail data, because, for example, a particular type of server may perform a limited set of operations, such as reading but not writing the data, or may access only certain portions of the data, or may otherwise be able to use knowledge about the behavior of the particular type of operations implemented by the server to access data more efficiently.

In one or more embodiments, there can be multiple instances of each type of server <NUM>, <NUM>, <NUM>, e.g., there can be more than one server of each type can be running, and the work load for each type of operation can be divided among the servers that perform that type of operation. The servers <NUM>, <NUM>, <NUM> can be distributed across one or more hosts (e.g., computer processors), with one or more servers of the same or different types executing on each host. For example, each server can be located on a different host, in which case the servers access shared data via network communication between the hosts. In another example, several servers can be located on a single host, in which case the servers can access shared data via faster communication pathways, such as shared memory or inter-process communication. A single host can ordinarily handle a limited number of servers, so expanding the order promising system's processing capacity and/or performance is achieved, in one or more embodiments, by adding additional hosts running additional server instances, and servers on different hosts access shared data via network communication.

In one or more embodiments, efficient access to shared data is achieved using an in-memory database <NUM>, e.g., Oracle® TimesTen® or the like. The shared data is stored in a shared memory region that can be accessed by multiple servers located on the same host. TimesTen also enables servers that are not located on the same host to access shared data, with the shared data and data updates being exchanged between the servers' hosts via a communication network. The in-memory database can be configured and accessed in at least two different ways, corresponding to <FIG> and <FIG>, respectively. <FIG> illustrates a shared in-memory database instance <NUM> according to one embodiment, and <FIG> illustrates multiple distributed in-memory database instances <NUM>, <NUM>, <NUM>, and <NUM> that communicate via a network <NUM> according to another embodiment.

<FIG> and <FIG> show multiple servers <NUM>, <NUM>, <NUM>, but do not show a particular assignment of servers to host computers. Thus, the servers <NUM>, <NUM>, <NUM> can be understood as server processes that can execute on host computers. Each of the servers <NUM>, <NUM>, <NUM> can correspond to a host computer in one or more examples, but in other examples, the servers <NUM>, <NUM>, <NUM> can share host computers, i.e., multiple servers can execute on a host computer. A host computer can have one or more processors (e.g., processing units, cores, or the like) that access the same memory space. Two or more of the servers <NUM>, <NUM>, <NUM> can execute on the multiprocessor or multicore host and access the in-memory database <NUM> of <FIG>, including the summary data <NUM>, in shared memory using memory access operations, which are more efficient than using a communication network <NUM> (e.g., TCP/IP, Ethernet, or the like) as shown in <FIG>. However, if a multiprocessor or multi core computer is not being used, or the number of servers needed is greater than the number of processors or cores available in multiprocessor or multicore hosts, then the network communication arrangement shown in <FIG> may be preferred, because the number of hosts can be increased by adding more hosts.

In one example, the servers <NUM>, <NUM>, <NUM> can execute on the same host computer, but the host should have a sufficient number of processors or cores to handle the order promising workload. If the workload exceeds the capacity of a single host computer, then additional hosts can be added as needed to process the additional workload, with the workload being distributed among the hosts by the request broker <NUM>. Conversely, if the computing capacity of the host computer(s) exceeds that needed to handle the workload, the one or more host computers, processors, or cores can be removed and allocated to other tasks, with the request broker being reconfigured to distribute the incoming order promising requests to the remaining host computers.

Thus, <FIG> shows a single in-memory database instance (e.g., a database server) <NUM> in accordance with one or more embodiments. The in-memory database instance <NUM> is accessed in a client-server-like arrangement, in which the order promising servers act as clients of the in-memory database server <NUM>. In <FIG>, if one or more of the order promising servers, such as the availability servers <NUM> and/or the scheduling servers <NUM>, are located on different hosts, then each server that is not on the same host as the in-memory database server <NUM> establishes a network connection to the in-memory database server <NUM>. Servers that are located on the same host as the in-memory database server <NUM> can communicate with the in-memory database server <NUM> using shared memory instead of a network connection.

As introduced above, the system <NUM> includes a request broker <NUM>, which receives inquiry messages <NUM> and order scheduling messages <NUM> from a source such as an online store that sells the items being ordered, and forwards the messages to the appropriate servers. The request broker may be, for example, a server that runs as an independent process or as part of a process that also provides other services. The request broker <NUM> examines each incoming message, determines which of the servers <NUM>, <NUM>, <NUM> will process the message, and forwards the message to the determined server. The determination of which server to use is based upon information in the message, message routing rules <NUM> and/or in-memory summary data <NUM>, which is described below. An availability server is selected if the message is an inquiry message, or a scheduling server is selected if the message is a scheduling message.

In one set of embodiments, the particular availability server or scheduling server is selected from a set of availability servers <NUM> or scheduling servers <NUM> using the routing rules <NUM>. Each rule can have a condition and an action. If the condition is satisfied (i.e., met) by the incoming message, then the action associated with the rule is performed. The action can, for example, determine a server to which the message is to be forwarded. If the condition is not satisfied, another rule is selected and evaluated in the same way, or, if all rules have been evaluated, a default action can be performed, such as forwarding the message to a randomly selected server. The rules can be user-defined and/or provided by the system. The incoming messages <NUM>, <NUM> reference items such as products, and the conditions can be based on the product identity, product attributes, product category, product grouping, product relationships, inventory thresholds, and so on. The rules can be updated by users to modify routing behavior. The request broker <NUM> can split an incoming request message <NUM> into multiple sub-requests and route each sub-request to a different server, so that the sub-requests can be processed in parallel. The request broker can then consolidate the results from the sub-requests into a single result message that is returned as a response to the request message.

In one set of embodiments, the availability server <NUM> generates responses to queries for order-related information, such as requests for current and future stock availability at a specified location. The availability server <NUM> determines the requested availability information using a representation of summary data stored in a summary structure <NUM>. The summary structure <NUM> can include, for example, time-phased availability information, product status, and the like. The availability server <NUM> reads summary data from the summary structure <NUM>, determines the desired result, such as the earliest availability date for a specified item quantity, and sends the result as a response to the received request, e.g., as a response message sent to the brokering server from which the request was received.

In one set of embodiments, the summary data is created and stored by the scheduling server as summary data <NUM> in an in-memory database <NUM>, e.g., Oracle® TimesTen® or the like, to achieve faster query performance than ordinary databases, which perform disk input/output operations when updating the database and executing queries. A data manager <NUM> of a scheduling server <NUM> performs the actions involved in storing the summary data <NUM> in the in-memory database <NUM>. Each of the servers <NUM>, <NUM>, <NUM> illustrated in <FIG> includes an associated engine <NUM>, <NUM>, <NUM> and data manager <NUM>, <NUM>, <NUM>. The in-memory database <NUM> does not ordinarily perform disk input/output operations when updating the database or executing queries. Instead, the in-memory database maintains the database contents in random-access memory (RAM) or the like, with the data being loaded into memory when the in-memory database is started, and the data being written to disk when the in-memory database is stopped or a disk commit operation is performed.

In one or more embodiments, the summary data is represented using the summary structure <NUM> that includes a copy of the summary data <NUM> stored in the in-memory database by the scheduling servers. This arrangement of the availability server(s) is shown in <FIG> and <FIG>. In other embodiments, the availability server uses the in-memory database, instead of maintaining the summary structure <NUM>, in which case the availability server can establish a network connection to a shared instance of the in-memory database (similar to the connections from the scheduling servers to the in-memory database in <FIG>), or the availability server can access an instance of the in-memory database <NUM> of <FIG> via shared memory (similar to the arrangement shown for the scheduling servers in <FIG>).

In one set of embodiments, a summary process <NUM> in the availability server <NUM> updates the summary structure <NUM> to reflect updates made by the scheduling servers <NUM> to the summary data <NUM>. The summary process <NUM> performs these updates in response to notifications received from the in-memory database. These notifications may be, for example, TimesTen XLA notification events, which are generated by the TimesTen in-memory database when database data is modified. Each notification event identifies the data item (e.g., relational row and column) that has been updated. The availability server retrieves the item identified in the notification from the in-memory database, and stores the item in the summary structure <NUM>. Thus, the availability server modifies the summary structure <NUM> in response to updates to the in-memory summary data <NUM>.

In one embodiment, the summary process <NUM> of the availability server <NUM> uses a synchronization operation such as a mutual exclusion lock to prevent multiple servers from writing to the summary structure <NUM>. In other embodiments, the availability servers are associated with different portions of the summary data <NUM> and need not perform synchronization operations when updating the summary structure <NUM>. Two availability servers <NUM>, <NUM> are shown, each including a summary structure <NUM>, <NUM> and a summary process <NUM>, <NUM>. Any number of availability servers may be used, as needed to handle the workload of incoming requests generated by the web front end <NUM>.

The availability inquiry operations read but do not modify the summary data in the summary structure <NUM>, and therefore the availability server <NUM> need not prevent other servers from simultaneously performing availability inquiry operations. In contrast, in servers that modify the order promising system state data, precautions are taken to avoid simultaneous access to the state data by multiple servers. These precautions, such as obtaining mutual exclusion locks on the state data or portions thereof, are time-consuming, and can result in low throughput at the read/write servers, because one request is processed at a time by a server. The availability server performs a read-only check on the in-memory summary data and does not modify inventory levels or other state data. The results of this check may be sufficient to satisfy the user's request, e.g., if the user is checking if an item is available, and does not wish to order the item. Thus, the availability server performs a first level availability check that can increase performance by reducing the request load on the scheduling server. Multiple availability servers can run simultaneously, and the number of availability servers in the pool of running servers can be dynamically configured while the system is running to adapt to system loads.

In one or more embodiments, a summary data structure <NUM> stores a summary of order promising data. The summary structure <NUM> is used by, for example, the request broker with a user-configurable model to route requests, and by the availability server to determine item availability. The summary data is summarized and organized to reduce the volume of data that is stored in memory, compared to the volume of data stored in the data details database. The summary data can be, for example, product, product category, product relationship, current and projected inventory by warehouse/location.

The brokering layer <NUM> uses rules <NUM>, e.g., product to server node mappings <NUM>, or condition-based rules as described elsewhere herein, to select a server to which each request will be sent. For example, the requests <NUM> and <NUM> can be partitioned according to one or more of their attributes, such as the geographical area from which the requests originate, the time at which the request is received, the type of item being ordered, and the like. Each server can be associated with a partition. In <FIG>, a first scheduling server <NUM> is associated with a first partition <NUM>. A second scheduling server <NUM> and an Nth scheduling server <NUM> are associated with a second partition <NUM>. Order scheduling requests <NUM> for items having item numbers in a first range associated with the first partition <NUM> are sent to the first server <NUM> by the request broker <NUM>. Order scheduling requests <NUM> for items having item numbers in a second range associated with the second partition <NUM> are sent to the second server <NUM> or the Nth server <NUM> by the request broker <NUM>. The association between servers and partitions can be changed dynamically, e.g., while the system <NUM> is operating and the servers are running, by a user or administrator, or in response to changing workload levels and/or server load levels, availability, and the like. In one or more embodiments, the system includes other types of servers, such as a shipping option server <NUM>, and the request broker <NUM> can route shipping option request messages to the shipping option server <NUM>.

In one set of embodiments, a system metric and administration module (not shown) can control and monitor the various types of servers in the system, including the availability servers, scheduling servers, and shipping option servers. The administration module provides control operations, e.g., start/stop, for a server cluster <NUM> or for individual nodes <NUM>, and can also provide statistical information for metrics such as memory load, CPU load, active thread information, request throughput, and min/max/average request processing times. The administration module can support dynamic scalability by automatically starting/stopping server nodes to maintain average system throughput within predefined limits. 24x7 support can be provided by a hot-swap capability, in which a server node can be launched and updated with the latest detail data <NUM> in the background, and then the server node can take over the active server node's request channel. The previously active server can then be shutdown. This server swap can be achieved seamlessly from an end-user perspective, and no requests are dropped.

<FIG> is a block diagram illustrating an exemplary brokering layer of a high throughput global order promising system according to one embodiment of the present invention. The brokering layer includes a request broker <NUM>, which can have user defined rules <NUM> on products and product grouping and relationship. A decomposition component <NUM> of the request broker <NUM> can split an incoming request message <NUM> into multiple sub-requests. An orchestration component <NUM> can route each request or sub-request to a different server according to the rules <NUM>, so that the requests (and sub-requests) can be processed in parallel. A product-server map <NUM> can be used in addition to or instead of the rules <NUM> to select a server to which the request is to be sent. The available servers can be included in an engine server pool <NUM>, which the decomposition component <NUM> can consult to determine which servers are available. A consolidation component <NUM> can then consolidate the results from the sub-requests into a single result message that is returned as a response to the request message. The rules <NUM> can be configurable, and can be based on inventory threshold, product category or family, product relationship etc. The rules <NUM> can be updated, so that the updated rules are used for future requests. Based on a received inquiry request message <NUM> or scheduling request message <NUM>, the request broker <NUM> checks the in memory summary data structure and user-defined rules, and dynamically determines which in memory availability inquiry or scheduling server(s) to route the request to. The request broker <NUM> can also route the request to an in memory shipping option engine <NUM>, and determine which of multiple in memory shipping option servers <NUM> to use.

<FIG> is a block diagram illustrating an exemplary availability inquiry server pool (i.e., cluster) <NUM> of a high throughput global order promising system according to one embodiment of the present invention. The availability servers <NUM> can provide quick visibility into current and future stock availability by location. An availability server <NUM> can take as an input customer material availability inquiries <NUM> routed from the web store <NUM> through the brokering layer <NUM>. Using summary data information such as time phased availability, product status, and so on, the availability server <NUM> can return a response <NUM> that includes an earliest availability date <NUM> for a requested quantity <NUM> of an item <NUM>. The summary data <NUM> is stored in an in-memory database <NUM>, which can be accessed via shared memory or network communication, as described above with reference to <FIG>.

An availability server <NUM> can perform a read-only check on the in-memory summary data structures, and does not decrease inventory levels. The availability server <NUM> can perform a first-level type of availability check, in order to maximize performance. Because of the read-only characteristics of the queries that the availability server <NUM> performs on internal summary data, the operations of the availability servers <NUM> need not bottleneck the scheduling servers <NUM>. The number of servers in the availability server pool <NUM> can be dynamically configured to adapt to changing system loads.

In one example, rules <NUM> can be defined to route requests for different types of products to different servers <NUM>. Suppose that requests for a product A or related products B and C are to be routed to a first availability server <NUM>, and requests for product X or related products Y and Z are to be routed to a second availability server <NUM>. The first server <NUM> can then be configured with an items list <NUM> that indicates which items the server <NUM> will process. The items list <NUM> includes product A, and also indicates that product A is related to products B and C. The items list <NUM> therefore indicates that the server <NUM> is assigned to products A, B, and C, and should process any requests that it receives for those products. In one example, the server <NUM> can ignore requests for items that are not in the items list <NUM>, although the broker <NUM> should ordinarily not send requests for non-assigned items to the server <NUM>. The item list <NUM> can also be stored in or accessible to the request broker <NUM>, or a corresponding routing rule can be added to the routing rules list <NUM> of the request broker <NUM>. In this example, a first routing rule can be defined having a condition such as "product is A, B, or C" and an action such as "route to server node <NUM>. " In other embodiments, this rule can be stored in the server <NUM> as an alternative to the items list <NUM>.

Similarly, the second server <NUM> can be configured with an items list <NUM> (or corresponding rule) that indicates which items the server <NUM> will process. The items list <NUM> includes product X, and also indicates that product X is related to products Y and Z, so that the server <NUM> will process requests that reference or include at least one of products X, Y, and Z. Similarly, a second routine rule can have a condition such as "product is X, Y, or Z" and an action "route to server node <NUM>. " Other types of rules are contemplated as well, e.g., a rule that searches a data table for the product identifier, and an action that selects the server node associated with the product identifier in the data table.

<FIG> is a block diagram illustrating an exemplary in-memory shipping option server <NUM> of a high throughput global order promising system according to one embodiment of the present invention. The shipping option server <NUM> can provide a list of shipping options with corresponding expected arrival dates. The shipping option server <NUM> receives as an input an item code <NUM> and ship date <NUM>, and can derive an expected arrival date <NUM> based on the available shipping options for the particular item. The input to the shipping option server <NUM> can be a shipping option request <NUM> from the request broker <NUM>. In one example, a user to checks availability on the web store <NUM>, and if the queried material and quantity are available, then the next step can be to check for available shipping options. The shipping option server <NUM> can return a set of valid shipping options with expected arrival dates <NUM> for the requested item. The shipping option engine <NUM> can thus separate material promising and scheduling from shipping option selection.

<FIG> is a block diagram illustrating an exemplary in-memory summary data structure <NUM> of a high throughput global order promising system according to one embodiment of the present invention. The in-memory summary data structure <NUM> is stored in an in-memory database server <NUM>, e.g., in a shared memory region. The data structure <NUM> stores information such as product, product category, product relationship, and current and projected inventory by warehouse/location that can be used by the request broker <NUM> to route the request, and for use by the availability inquiry servers <NUM>. The summary data structure <NUM> can also contain the sourcing, manufacturing, supplier, and capacity information for use by the scheduling servers <NUM>. Data in the in-memory summary data structure <NUM> can be organized and summarized to reduce the volume of data and/or accesses. The summary data <NUM> can provide for configurable redundancy and columnar storage for fast access, and can be indexed to make search and access much efficient.

Any inventory change due to scheduling changes can be reflected dynamically in the memory data structure <NUM> using asynchronous and near real time updates. Inventory changes due to shipping, receiving, or others can be reflected dynamically in the memory data structure and close to real time update if users choose to. Setup-related changes (new items, new customers, new warehouse/location, and so on) can be brought into the memory structure <NUM> at a user's request.

In one or more embodiments, the availability server <NUM> maintains a copy of at least a portion of the summary data <NUM> in a summary structure <NUM>, which can include an association between items <NUM> and item availability <NUM>. As described above, the summary data <NUM> is a summary of portions of the detailed data <NUM>. A summary process <NUM> generates and updates the summary structure <NUM> to contain a copy of the information in the summary data <NUM> in response to notifications received from the in-memory database <NUM>. The summary process can construct the summary structure <NUM> using data structures and algorithms that provide for quick lookup and modification of data items. For example, the summary structure <NUM> may consist of a listing by product and location of the availability status (e.g., "Available," "Less Than <NUM> in Stock," "Out of Stock," or, alternatively, "Available" or "Available in [n] Days") of each Product-Location combination.

<FIG> is a block diagram illustrating an exemplary pool, i.e., cluster <NUM>, of scheduling servers <NUM>, <NUM>, <NUM> in a high throughput global order promising system <NUM> according to one embodiment of the present invention. Each scheduling server <NUM> includes an order promising engine <NUM> that can perform scheduling for requests <NUM> based on item availability. The scheduling servers receive the scheduling requests <NUM> from the request broker <NUM> or other source. Each order scheduling request <NUM> includes an item code <NUM> identifying the item to be scheduled, and a quantity <NUM> of the item to be scheduled. Based on the content of the request <NUM> and setup of scheduling engine <NUM>, single level inventory availability can be checked before scheduling, or multiple level availability can be checked, in which case information such as components, manufacturing resources, supplier capacities, and lead times can be considered. Product substitutions and component substitutions can be included as well. Eventually a ship date <NUM>, product, and ship from location <NUM> (e.g., warehouse or supplier site) can be returned in an order scheduling request message <NUM> to the brokering module <NUM>.

Each scheduling server <NUM> can access or store shared information, such as organization, calendar etc. A scheduling server can also have exclusive server-specific information such as a set of products, product categories/families, and availability information for those product/product categories/families or information needed to come up with availability information. Each scheduling server <NUM> can store portions of the scheduling results in the summary data <NUM> of the in-memory database <NUM>. With each of the scheduling servers <NUM> associated with a different partition of the ordering data, there is no conflict or contention between the scheduling servers <NUM>. Thus, requests for products that are in different product partitions can be processed in parallel on different scheduling nodes. Requests for products that are in the same product partitions can be processed in sequence on the scheduling node to which the products are assigned. The items that are to be processed by the scheduling server <NUM> can be specified in an items list <NUM>, which is similar to the items list <NUM> described above with reference to <FIG>. Similarly, the items that are to be processed by the scheduling server <NUM> can be specified in an items list <NUM>.

<FIG> is an illustrative flow diagram of a brokering process in accordance with embodiments of the invention. The process of <FIG> can be implemented by, for example, machine-readable instructions executed by a processor of a computer system, and can be executed by the request broker <NUM> of <FIG>. The process begins at block <NUM> by receiving an order promising request such as an order scheduling request <NUM>. Block <NUM> determines the type of request, as described above with reference to the request broker <NUM>. Block <NUM> determines if the request is of the availability request type. If so, block <NUM> evaluates the routing rules <NUM> to determine the server to which the request should be sent. Block <NUM> may consult a product-server map <NUM> to determine the server that corresponds to a product specified in the request. Block <NUM> forwards, e.g., sends, the request to the identified availability server using a communication network, shared memory, inter-process communication, or other form of communication. The availability server generates a response to the request, and block <NUM> receives and forwards the response to the web service or other entity that sent the request <NUM>.

If block <NUM> determines that the request is not an availability request, then block <NUM> determines whether the request is of a scheduling request type. If so, block <NUM> evaluates the routing rules <NUM> to determine the server to which the request should be sent. Block <NUM> evaluates the routing rules to identify a scheduling server, similar to block <NUM>, and block <NUM> forwards the request to the identified scheduling server. The scheduling server schedules the order and generates results, which block <NUM> receives and forwards to the invoking web service or other entity that sent the request <NUM>.

<FIG> is an illustrative flow diagram of an availability inquiry process in accordance with embodiments of the invention. The process of <FIG> can be implemented by, for example, machine-readable instructions executed by a processor of a computer system, and may be executed by one or more of the availability servers <NUM>. The process of <FIG> begins at block <NUM> by receiving an availability inquiry request <NUM> for an item. The request may be received from, for example, a web service, which in turn has forwarded the request from a request broker. Block <NUM> retrieves availability information for the item specified in the request from a summary structure <NUM>. Block <NUM> uses the availability information to determine the earliest availability date for the item. Block <NUM> sends the determined earliest availability date as a response to the inquiry request.

<FIG> is an illustrative flow diagram of a scheduling process in accordance with embodiments of the invention. The process of <FIG> can be implemented by, for example, machine-readable instructions executed by a processor of a computer system, and can be implemented by one or more of the scheduling servers <NUM> of <FIG>. The process begins at block <NUM> by receiving an order scheduling request for a particular item. Block <NUM> submits the request to the scheduling engine <NUM>, which determines a schedule and promised completion date for the item and stores the schedule and completion date in the order details database <NUM>. Block <NUM> starts a new (or uses an existing) separate thread of control to update the summary data <NUM> in the in-memory database <NUM> with the new schedule data. That is, the server thread does not wait for the in-memory database <NUM> to be updated before continuing to process additional messages. Block <NUM> sends a scheduling response <NUM>, <NUM> to the entity from which the scheduling request was received (e.g., the web service <NUM>). When the separate thread has updated the summary data <NUM>, the in-memory database <NUM> detects the update and notifies the summary process <NUM> in each availability server <NUM> of the change, as shown at block <NUM>. The summary process <NUM> retrieves the updates to the summary database <NUM> and stores the updates in the summary structure <NUM> at block <NUM>, after which the process ends.

Claim 1:
A method comprising:
receiving (<NUM>, <NUM>), by a request broker of a computer system, an inquiry requesting availability status of a specified item;
determining (<NUM>), by the request broker of the computer system, that the inquiry is an availability type request;
retrieving (<NUM>), by the request broker of the computer system from one or more of a plurality of in-memory database instances, summary data associated with the specified item from a summary data structure stored in a memory of the computer system wherein the summary data structure is shared among two or more availability servers and one or more scheduling servers using said one or more in-memory database instances, the summary data structure being partitioned between the two or more availability servers, such that each of the two or more availability servers is assigned to different partitions of the summary data structure;
determining (<NUM>), by the request broker of the computer system by evaluating routing rules, which of the two or more availability servers is assigned to the summary data associated with the specified item;
forwarding (<NUM>), by the request broker of the computer system, the inquiry to the assigned availability server;
determining ( <NUM>), by said assigned availability server, availability data for the specified item based upon the summary data; and
sending (<NUM>), by the request broker of the computer system, an inquiry response indicating the availability of the specified item based upon the determined availability data;
wherein the operations performed by the two or more availability servers may read but not write to the summary data and the operations performed by the one or more scheduling servers may read and/or write to the summary data;
wherein the plurality of in-memory database instances are distributed between the request broker of the computer system and the one or more scheduling servers.