Patent application title: Scalable Game Primitives / Distributed Real-Time Aggregation Of Player Data
Felix Livni (Seattle, WA, US)
Lowell Manners (Kirkland, WA, US)
Gary William Hall (Kirkland, WA, US)
Jay Thaler (Kirkland, WA, US)
Tony Chen (Bellevue, WA, US)
IPC8 Class: AA63F924FI
Class name: Including means for processing electronic data (e.g., computer/video game, etc.) with communication link (e.g., television broadcast, etc.) network type (e.g., computer network, etc.)
Publication date: 2010-06-24
Patent application number: 20100160047
Disclosed herein is a set of coordinated game service primitives that
allows for custom, per-game, logic. A new game with new custom logic can
be added without needing to change any public api or database schema or
write any new server code. The same hardware may be shared across many
games. And the system scales linearly. That is, if the number of servers
is doubled, then so is the number of concurrent users that can be
supported. Also disclosed are systems and methods for two-stage
aggregation. Pre-aggregation may take place on a plurality of front-end
server. Final aggregation may take place on one or more back-end servers.
A name value store may be used to reliably store state.
1. A network-based gaming system, comprising:a plurality of front-end
servers, each said front-end server executing thereon respective
front-end controllers;a back-end server; anda partitioned name/value
store,wherein users are enabled to post messages to the front-end
controllers, each said message having a respective name and body,
messages are routed by name to the appropriate front-end controllers, the
front-end controllers aggregate values from a batch of messages, and
write the aggregated values to a persistent data store, andwherein the
back-end servers periodically read aggregated values from the data store,
and write to the data store final values aggregated over the plurality of
2. The system of claim 1, wherein the front-end servers perform primitive logic on the incoming messages, store results in the data store, read from the data store, and supply aggregated results back to the users.
3. The system of claim 1, wherein the front-end servers are adapted to process incoming messages from users, to perform custom game logic on the incoming messages, to store results in the name/value store, and to read from the name/value store.
4. The system of claim 1, wherein the back-end servers are adapted to perform time-based operations and other custom game logic, and to read and write from the name/value store.
5. The system of claim 1, wherein the data store is a partitioned name/value store with a single-table schema.
6. The system of claim 5, wherein the single table is a name/value table having a first column for name and a second column for value.
7. In network-based gaming system comprising a plurality of front-end servers, each front-end server being associated with a respective plurality of game consoles, a single back-end server associated with the plurality of front-end servers, and a partitioned name/value store, a method comprising:receiving at each of the front-end servers, a set of messages from the respective plurality of game consoles associated therewith, each said message having a respective name and XML body;aggregating at each of the front-end servers values from the received messages;writing the aggregated values from the front-end servers to the name/value store;periodically reading the aggregated values at the back-end server from the name/value store; andwriting from the back-end server to the name/value store a final value aggregated over the plurality of front-end servers.
8. The method of claim 7, further comprising:routing the messages by name to the front-end controllers.
9. The method of claim 7, further wherein data is tracked in the system in accordance with name/value pairs.
10. The method of claim 7, wherein each front-end server performs pre-aggregation of input data provided by each of the plurality of clients associated with the front-end server.
11. The method of claim 10, wherein the back-end server aggregates the data globally.
12. The method of claim 11, wherein the aggregation is performed using a set of basic primitives.
13. A network-based gaming system, comprising:a plurality of front-end servers, each said front-end server executing thereon respective front-end controllers;a back-end server; anda partitioned name/value store,wherein each front-end server performs pre-aggregation of input data provided by each of a plurality of clients associated with the front-end server,wherein the back-end server aggregates the data globally, andwherein the aggregation is performed using a set of basic primitives.
14. The system of claim 13, wherein users are enabled to post messages to the front-end servers, each said message having a respective name and XML body.
15. The system of claim 14, wherein each message contains a respective value associated with said name, and the back-end server aggregates the data by summing the values over a set of messages containing the name.
16. The system of claim 13, wherein the set of primitives includes at least get and set primitives.
17. The system of claim 13, wherein the set of primitives includes at least sum and get primitives.
18. The system of claim 13, wherein the front-end server communicates pre-aggregated values to the name/value store, and does not communicate directly with the back-end server.
19. The system of claim 18, wherein the back-end server picks up pre-aggregated values from the name/value store, and writes aggregated values back to the name/value store.
20. The system of claim 19, wherein the back-end server picks up the aggregated values from the name/value store for communication to the users.
In a console game designed to support many users all posting messages to a server or servers, where each message contains data that needs to be aggregated and made available back to those users, common "primitive" aggregation logic, such as summation and top-n, as well as custom game-specific aggregation logic can be used to drive custom game logic. For example, each user might belong to a team and post a score. The scores might need to be summed to get the total score for each team. The aggregate score might need to be made available quickly to the users. Writing custom server code is expensive, however, and custom servers are expensive to maintain.
Also, in such a console game, due to the volume of posted messages, all the posts may not be able to be handled on a single front end server. Accordingly, it would be desirable to provide a mechanism for aggregating values posted across many front end servers.
In a platform that supports many massively multi-player games, which tend to have a high number of concurrent users during just a few hours a week, many servers may be needed to support peak load, which may be on the order of about 200,000 internet accesses/second, with peak data transfer rates on the order of Gigabits/second. For this reason and others, it may be desirable to share a single game service across many different games.
It would be particularly desirable if a single infrastructure that scales to peak could be used across many games, with a standard service that need not be extended every time a new game is built. Such a service should be sufficiently fault tolerant such that it can tolerate and recover from any single component failure automatically and within seconds.
Disclosed herein is a set of coordinated game service primitives that allows for custom, per-game, logic. The functionality of the primitives does not change from game-to-game, custom, client-side game logic can be built on top of these primitives in much the same way that custom reports can be generated using SQL primitives. For example, a new game with new custom logic can be added without needing to change any public application programming interface (API) or database schema, nor to write any new service or server-side code. The same hardware may be shared across many games. And the system scales linearly. That is, if the number of servers is doubled, then so is the number of concurrent users that can be supported.
Also disclosed are systems and methods for two-stage aggregation. Pre-aggregation may take place on a plurality of front-end servers. Final aggregation may take place on one or more back-end servers. A name value store may be used to reliably store state.
BRIEF DESCRIPTION OF THE DRAWINGS
FIG. 1 depicts an example network-based game service.
FIG. 2 is a flowchart for employing scalable game service primitives in a network-based game service.
FIG. 3 is a block diagram of an example computing environment in which example embodiments and aspects of the present invention may be implemented.
FIG. 4 is an example network configuration in which aspects of the invention may be implemented.
DETAILED DESCRIPTION OF ILLUSTRATIVE EMBODIMENTS
As shown in FIG. 1, an example network-based game service may include a plurality of front-end servers, one or more back-end servers, and a partitioned name/value store.
The front-end servers may be TCP/IP Socket Servers that dynamically load the pre-aggregation primitive code and custom game logic that may be referred to as "front-end controllers." These front-end controllers process incoming messages from users and perform custom game logic on them, often storing the results in the name/value store. Front-End controllers may read and write from the name/value store.
The back-end servers similarly load back-end controllers. Back-end controllers do the final aggregation of pre-aggregated data (e.g., aggregating a sum for some data pre-aggregated and set by a plurality of front end servers) and performing other custom game logic including advancing a round. Back-end controllers read and write from the name/value store.
The name/value store is a partitioned sql database with a simple, single-table schema. The name/value table has two columns, one for name and one for value. The name is a string and the value is a binary blob, which may be an xml blob, for example. The store is partitioned on name. The name/value store does not provide transactions or record locking.
As shown in FIG. 2, users may post messages to the front end controllers at 52. The messages, each of which may have a name and an XML body, are pre-aggregated on the front-end servers.
At 54, messages are routed by name to the appropriate front end controllers.
At 56, the front end controllers execute on all the messages in a batch, often aggregating and writing the aggregate value to the name/value store.
At 58, the back-end servers run their controllers, periodically reading values from the name/value store and perhaps further aggregating the results and writing out the final values. So that the back end servers know which values to aggregate, a queuing mechanism may be employed to signal the back end server. The queuing mechanism may be polled periodically.
Consider an example of 200,000 game consoles playing a quiz-show game all at the same time. Each game console may connect to the data center through a secure gateway, and communicate using encrypted traffic. The game consoles may tunnel through the secure gateway to the plurality of front-end servers. The game consoles may connect using persistent TCP/IP connections rather than web service calls. To handle 200,000 game consoles, the system may include, say, 20 front-end servers, each to handle 10,000 game console clients.
Suppose that each of the 200,000 game consoles is answering the same question at the same time. Each game console submits its respective answer, and each front end gets 10,000 messages at same time.
Typically, each user will want to know whether he or she got the right answer. But the users might also want feedback that relies on answers provided by other users. For example, the users might want to know what percentage of respondents got the right answer, or who was first to answer correctly.
The individual game consoles may be programmed to determine whether the user got an answer right or wrong, and provide such an indication to the user. Each game console may keep score of how many answers the user of that console got right. Each game console may then communicate to the associated front-end server whether the user got the answer right or wrong. Data may then be aggregated on the back-end server.
Data is tracked in the system in accordance with name/value pairs. That is, every datum may have a name and a value associated with it. An example of a name might be game title, such as "trivia.quest.sessionid.questionno.right/wrong." Values for this datum might be "right" and "wrong," which could be represented as "0" and "1," respectively.
Each front-end server does pre-aggregation (e.g., a summation for their subset of users), and writes the pre-aggregated value (e.g., a sum) out to the store. This process may be referred to as "pre-aggregation," i.e., aggregation by the front-end server of input data provided by each of a plurality of clients associated with the front-end server. The back-end server grabs the list of sums and sums the sums to get a final sum of sums. Thus, the back-end server aggregates the data globally.
To accomplish this, the back-end servers need understand only a set of basic primitives. The console sends a name and value, and the back-end server sums all the values over that name. For example, a console might send a message with a name such as "question 7 right?" and a value of "1" or "0" (depending on whether the user got it right or not). The action (i.e., primitive) may be "sum." After a prescribed period of wait time (e.g., six seconds), the game console may ask the front-end server to report back an aggregation from the universe of consoles. For example, the game console may send a message with name ="question 7 right?" and action (primitive)="get." In response, the back-end server may provide the aggregate value for that name (which, in this example, is the summation of the number right).
Note that the front-end server need not communicate directly with the back-end server. The front-end server may communicate values to the name/value store. The back-end server may pick up pre-aggregated values from the name/value store, and write aggregated values back. The back-end server may pick up aggregated values from the name/value store.
Example Computing Environment
FIG. 3 shows an exemplary computing environment in which example embodiments and aspects may be implemented. The computing system environment 100 is only one example of a suitable computing environment and is not intended to suggest any limitation as to the scope of use or functionality. Neither should the computing environment 100 be interpreted as having any dependency or requirement relating to any one or combination of components illustrated in the exemplary operating environment 100.
Numerous other general purpose or special purpose computing system environments or configurations may be used. Examples of well known computing systems, environments, and/or configurations that may be suitable for use include, but are not limited to, personal computers, server computers, hand-held or laptop devices, multiprocessor systems, microprocessor-based systems, set top boxes, programmable consumer electronics, network PCs, minicomputers, mainframe computers, embedded systems, distributed computing environments that include any of the above systems or devices, and the like.
Computer-executable instructions, such as program modules, being executed by a computer may be used. Generally, program modules include routines, programs, objects, components, data structures, etc. that perform particular tasks or implement particular abstract data types. Distributed computing environments may be used where tasks are performed by remote processing devices that are linked through a communications network or other data transmission medium. In a distributed computing environment, program modules and other data may be located in both local and remote computer storage media including memory storage devices.
With reference to FIG. 3, an exemplary system includes a general purpose computing device in the form of a computer 110. Components of computer 110 may include, but are not limited to, a processing unit 120, a system memory 130, and a system bus 121 that couples various system components including the system memory to the processing unit 120. The processing unit 120 may represent multiple logical processing units such as those supported on a multi-threaded processor. The system bus 121 may be any of several types of bus structures including a memory bus or memory controller, a peripheral bus, and a local bus using any of a variety of bus architectures. By way of example, and not limitation, such architectures include Industry Standard Architecture (ISA) bus, Micro Channel Architecture (MCA) bus, Enhanced ISA (EISA) bus, Video Electronics Standards Association (VESA) local bus, and Peripheral Component Interconnect (PCI) bus (also known as Mezzanine bus). The system bus 121 may also be implemented as a point-to-point connection, switching fabric, or the like, among the communicating devices.
Computer 110 typically includes a variety of computer readable media. Computer readable media can be any available media that can be accessed by computer 110 and includes both volatile and nonvolatile media, removable and non-removable media. By way of example, and not limitation, computer readable media may comprise computer storage media and communication media. Computer storage media includes both volatile and nonvolatile, removable and non-removable media implemented in any method or technology for storage of information such as computer readable instructions, data structures, program modules or other data. Computer storage media includes, but is not limited to, RAM, ROM, EEPROM, flash memory or other memory technology, CDROM, digital versatile disks (DVD) or other optical disk storage, magnetic cassettes, magnetic tape, magnetic disk storage or other magnetic storage devices, or any other medium which can be used to store the desired information and which can accessed by computer 110. Communication media typically embodies computer readable instructions, data structures, program modules or other data in a modulated data signal such as a carrier wave or other transport mechanism and includes any information delivery media. The term "modulated data signal" means a signal that has one or more of its characteristics set or changed in such a manner as to encode information in the signal. By way of example, and not limitation, communication media includes wired media such as a wired network or direct-wired connection, and wireless media such as acoustic, RF, infrared and other wireless media. Combinations of any of the above should also be included within the scope of computer readable media.
The system memory 130 includes computer storage media in the form of volatile and/or nonvolatile memory such as read only memory (ROM) 131 and random access memory (RAM) 132. A basic input/output system 133 (BIOS), containing the basic routines that help to transfer information between elements within computer 110, such as during start-up, is typically stored in ROM 131. RAM 132 typically contains data and/or program modules that are immediately accessible to and/or presently being operated on by processing unit 120. By way of example, and not limitation, FIG. 3 illustrates operating system 134, application programs 135, other program modules 136, and program data 137.
The computer 110 may also include other removable/non-removable, volatile/nonvolatile computer storage media. By way of example only, FIG. 3 illustrates a hard disk drive 140 that reads from or writes to non-removable, nonvolatile magnetic media, a magnetic disk drive 151 that reads from or writes to a removable, nonvolatile magnetic disk 152, and an optical disk drive 155 that reads from or writes to a removable, nonvolatile optical disk 156, such as a CD ROM or other optical media. Other removable/non-removable, volatile/nonvolatile computer storage media that can be used in the exemplary operating environment include, but are not limited to, magnetic tape cassettes, flash memory cards, digital versatile disks, digital video tape, solid state RAM, solid state ROM, and the like. The hard disk drive 141 is typically connected to the system bus 121 through a non-removable memory interface such as interface 140, and magnetic disk drive 151 and optical disk drive 155 are typically connected to the system bus 121 by a removable memory interface, such as interface 150.
The drives and their associated computer storage media discussed above and illustrated in FIG. 3, provide storage of computer readable instructions, data structures, program modules and other data for the computer 110. In FIG. 3, for example, hard disk drive 141 is illustrated as storing operating system 144, application programs 145, other program modules 146, and program data 147. Note that these components can either be the same as or different from operating system 134, application programs 135, other program modules 136, and program data 137. Operating system 144, application programs 145, other program modules 146, and program data 147 are given different numbers here to illustrate that, at a minimum, they are different copies. A user may enter commands and information into the computer 20 through input devices such as a keyboard 162 and pointing device 161, commonly referred to as a mouse, trackball or touch pad. Other input devices (not shown) may include a microphone, joystick, game pad, satellite dish, scanner, or the like. These and other input devices are often connected to the processing unit 120 through a user input interface 160 that is coupled to the system bus, but may be connected by other interface and bus structures, such as a parallel port, game port or a universal serial bus (USB). A monitor 191 or other type of display device is also connected to the system bus 121 via an interface, such as a video interface 190. In addition to the monitor, computers may also include other peripheral output devices such as speakers 197 and printer 196, which may be connected through an output peripheral interface 195.
The computer 110 may operate in a networked environment using logical connections to one or more remote computers, such as a remote computer 180. The remote computer 180 may be a personal computer, a server, a router, a network PC, a peer device or other common network node, and typically includes many or all of the elements described above relative to the computer 110, although only a memory storage device 181 has been illustrated in FIG. 3. The logical connections depicted in FIG. 3 include a local area network (LAN) 171 and a wide area network (WAN) 173, but may also include other networks. Such networking environments are commonplace in offices, enterprise-wide computer networks, intranets and the Internet.
When used in a LAN networking environment, the computer 110 is connected to the LAN 171 through a network interface or adapter 170. When used in a WAN networking environment, the computer 110 typically includes a modem 172 or other means for establishing communications over the WAN 173, such as the Internet. The modem 172, which may be internal or external, may be connected to the system bus 121 via the user input interface 160, or other appropriate mechanism. In a networked environment, program modules depicted relative to the computer 110, or portions thereof, may be stored in the remote memory storage device. By way of example, and not limitation, FIG. 3 illustrates remote application programs 185 as residing on memory device 181. It will be appreciated that the network connections shown are exemplary and other means of establishing a communications link between the computers may be used.
FIG. 4 illustrates an example network environment in which the present invention may be employed. Of course, actual network and database environments may be arranged in a variety of configurations; however, the example environment shown here provides a framework for understanding the type of environment in which an embodiment may operate.
The example network may include one or more client computers 200a, a server computer 200b, data source computers 200c, and/or databases 270, 272a, and 272b. The client computers 200a and the data source computers 200c may be in electronic communication with the server computer 200b by way of the communications network 280 (e.g., an intranet, the Internet or the like). The client computers 200a and data source computers 200c may be connected to the communications network by way of communications interfaces 282. The communications interfaces 282 can be any type of communications interfaces such as Ethernet connections, modem connections, wireless connections and so on.
The server computer 200b may provide management of the database 270 by way of database server system software such as MICROSOFT®'s SQL SERVER or the like. As such, server 200b may act as a storehouse of data from a variety of data sources and provides that data to a variety of data consumers.
In the example network environment of FIG. 4, a data source may be provided by data source computer 200c. Data source computer 200c may communicate data to server computer 200b via communications network 280, which may be a LAN, WAN, Intranet, Internet, or the like. Data source computer 200c may store data locally in database 272a, which may be database server or the like. The data provided by data source 200c can be combined and stored in a large database such as a data warehouse maintained by server 200b.
Client computers 200a that desire to use the data stored by server computer 200b can access the database 270 via communications network 280. Client computers 200a access the data by way of, for example, a query, a form, etc. It will be appreciated that any configuration of computers is equally compatible with an embodiment of the present invention.
Patent applications by Felix Livni, Seattle, WA US
Patent applications by Jay Thaler, Kirkland, WA US
Patent applications by Microsoft Corporation
Patent applications in class Network type (e.g., computer network, etc.)
Patent applications in all subclasses Network type (e.g., computer network, etc.)