The existing architecture for massively multiplayer online role-playing games (MMORPG) based on RDBMS limits the availability and scalability. With increasing numbers of players, the storage systems become bottlenecks. Although a Cloud-based architecture has the ability to solve these speci c issues, the support for data consistency becomes a new open issue. In this paper, we will analyze the data consistency requirements in MMORPGs from the storage system point of view, and highlight the drawbacks of Cassandra to support of game consistency. A timestamp-based solution will be proposed to address this issue. Accordingly, we will present data replication strategies, concurrency control, and system reliability as well.
In massively multiplayer online role-playing games (MMORPG) thousands of players can cooperate with other players in a virtual game world. To support such a huge game world following often complex application logic and speci c requirements. Additionally, we have to bear the burden of managing large amounts of data. The root of the issue is that the existing architectures of MMORPGs use RDBMS to manage data, which limits the availability and scalability.
Cloud data storage systems are designed for internet
applications, and are complementary to RDBMS. For example,
Cloud systems are able to support system availability and
scalability well, but not data consistency. In order to take
advantages of these two types of storage systems, we have
classi ed data in MMORPGs into four data sets according
to typical data management requirements (e.g., data
consistency, system availability, system scalability, data model,
security, and real-time processing) in [
Client Cloud(SSttaotreaDgeatSay)stem (e.g., log data and state data) that requires scalability and availability is stored in a Cloud data storage system (Cassandra, in this paper). Figure 1 shows the new architecture.
Unfortunately, there are still some open issues, such as
the support of data consistency. According to the CAP
theorem, in a partition tolerant distributed system (e.g.,
an MMORPG), we have to sacri ce one of the two
properties: consistency or availability [
Although there has been some research work focused on
the data consistency model of online games, the researchers
generally discussed it from players' or servers' point of view
[
Due to di erent application scenarios, the four data sets have distinct data consistency requirements. For this reason, we need to apply di erent consistency models to ful ll them.
Account data: is stored on the server side, and is created, accessed as well as deleted when players log in to or log out of a game. It includes player's private data and some other sensitive information (e.g., user ID, password, and recharge records). The inconsistency of account data might bring troubles to a player as well as the game provider, or even lead to an economic or legal dispute. Imagine the following two scenarios: a player has changed the password successfully. However, when this player log in to the game again, the new password is not e ective; a player has transferred to the game account, or the player has consumed in the game, but the account balance is somehow not properly presented in the game system. Both cases would in uence on the player's experience, and might result in the customer or the economic loss of a game company. Hence, we need to access account data under strong consistency guarantees, and manage it with transactions. In a distributed database system, it means that each copy should hold the same view on the data value.
Game data: such as world appearance, metadata (name, race, appearance, etc.) of NPC (Non Player Character), system con guration les, and game rules, is used by players and game engine in the entire game, which can only be modi ed by game developers. Players are not as sensitive to game data as to account data. For example, the change of an NPC's appearance or name, the duration of a bird animation, and the game interface may not catch the players' attention and have no in uence on players' operations. As a result, it seems that strong consistency for game data is not so necessary. On the other hand, some changes of the game data must be propagated to all online players synchronously, for instance, the change of the game world's appearance, the power of a weapon or an NPC, game rules as well as scripts, and the occurrence frequency of an object during the game. The inconsistency of these data will lead to errors on the game display and logic, unfair competition among players, or even a server failure. For this reason, we also need to treat data consistency of game data seriously. Game data could be stored on both the server side and the client side, so we have to deal with it accordingly.
Game data on the client side could only synchronize with
servers when a player logs in to or starts a game. For this
reason, causal consistency is required [
Although both client side and server side store the game data, only the game server maintains the authority of it. Furthermore, players in di erent game worlds cannot communicate to each other. Therefore, we only need to ensure that the game data is consistent in one zone server so that players in the same game world could be treated equally. It is noteworthy that a zone server accesses data generally from one data center. Hence, we guarantee strong consistency within one data center, and causal consistency among data centers. In other words, when game developers modify the game data, the updated value should be submitted synchronously to all replicas within the same data center, and then propagated asynchronously across data centers.
State data: for instance, metadata of PCs (Player Characters) and state (e.g., position, task, or inventory) of characters, is modi ed by players frequently during the game. The change of state data must be perceived by all relevant players synchronously, so that players and NPCs can respond correctly and timely. An example for the necessity of data synchronization is that players cannot tolerate that a dead character can continue to attack other characters. Note that players only access data from the in-memory database during the game. Hence, we need to ensure strong consistency in the in-memory database.
Another point about managing state data is that updated
values must be backed up to the disk-resident database
asynchronously. Similarly, game developers also need to take
care of data consistency and durability in the disk-resident
database, for instance, it is intolerable for a player to nd
that her/his last game record is lost when she/he starts the
game again. In contrast to that in the in-memory database,
we do not recommend ensuring strong consistency to state
data. The reason is as follows: according to the CAP
theorem, a distributed database system can only simultaneously
satisfy two of three the following desirable properties:
consistency, availability, and partition tolerance. Certainly, we
hope to satisfy both consistency and availability guarantees.
However, in the case of network partition or under high
network latency, we have to sacri ce one of them. Obviously,
we do not want all update operations to be blocked until the
system recovery, which may lead to data loss. Consequently,
the level of data consistency should be reduced. We propose
to ensure read-your-writes consistency guarantee [
Log data: (e.g., player chat history and operation logs)
is created by players, but used by data analysts for the
purpose of data mining. This data will be sorted and cached
on the server side during the game, and then bulk stored
into the database, thereby reducing the con ict rate as well
as the I/O workload, and increasing the total simultaneous
throughput [
In our previous work, we have already presented the
capability of the given Cloud-based architecture to support
the corresponding consistency model for each data set in
MMORPGs [
Through customizing the quorum of replicas in response to
read and write operations, Cassandra provides tunable
consistency, which is an inherent advantage to support MMORPGs
[
On the other hand, Cassandra fails to implement tunable consistency e ciently according to MMORPG requirements. For example, M-N+1 replicas of state data have to be compared so as to guarantee read-your-writes consistency. However, state data has typically hundreds of attributes, the transmission and comparison of which a ect the read performance. Opposite to update a quorum of replicas, we update all replicas while executing write operations. In this case, data in Cassandra is consistent, and we can obtain the up-to-date data from the closest replica directly. Unfortunately, this replication strategy signi cantly increases the network tra c as well as the response time of write operations, and sacri ces system availability. As a result, to implement read-your-writes consistency e ciently becomes an open issue.
Another drawback is that Cassandra makes all replicas eventually consistent, which sometimes does not match the application scenarios of MMORPG, and reduce the e ciency of the system. The reasons are as follows.
Unnecessary for State data: state data of a PC is read by a player from the Cloud storage system only once during the game. The subsequent write operations do not depend on values in the Cloud any more. Hence, after obtaining the up-to-date data from the Cloud, there is no necessity to ensure that all replicas reach a consensus on these values.
Increase network tra c: Cassandra utilizes Read
Repair functionality to guarantee eventual consistency
[
A common method for solving the consistency problem of
Cloud storage system is to build an extra transaction layer
on top of the system [
Data access servers are responsible for data exchange between the in-memory database and the Cloud storage system. They ensure the consistency of state data, maintain timestamp tables, and play the role of global counters as well. In order to balance the workload and prevent server failures, several data access servers run in one zone server in parallel. Data access servers need to synchronize their system clock with each other automatically. However, a complete synchronization is not required. A time di erence less than the frequency of data backup is acceptable.
An important component in data access servers is the timestamp table, which stores the ID as well as the last modi ed time (LMT) of state data, and the log status (LS). If a character or an object in the game is active, its value of LS is \login". Otherwise, the value of LS is \logout". We utilize a hash function to map IDs of state data to distinct timestamp tables, which are distributed and partitioned in data access servers. It is noteworthy that timestamp tables are partitioned and managed by data access servers in parallel and data processing is simple, so that accessing timestamp tables will not become a bottleneck of the game system.
Note that players can only interact with each other in the same game world, which is managed by one zone server. Moreover, a player cannot switch the zone server freely. Therefore, data access servers as well as timestamp tables across zone servers are independent. 4.2
In this subsection, we discuss the data access without considering data replication and concurrency con icts.
In Figure 2, we show the storage process of state data in the new Cloud-based architecture: the in-memory database takes a consistent snapshot periodically. Though using the same hash function employed by timestamp tables, each Read request (RR) State data State data
RR
RR State data
(Login) State data (TS,Login)
RR State data (Logout)
LMT & RR
State data (LMT,Login)
RR State data
Check Version ID data access server obtains the corresponding state data from the snapshot periodically. In order to reduce the I/O workload of the Cloud, a data access server generates one message including all its responsible state data as well as a new timestamp TS, and then sends it to the Cloud storage system. In the Cloud, this message is divided based on the ID of state data into several messages, each of which still includes TS. In this way, the update failure of one state data won't block the submission of other state data. Then, these messages are routed to appropriate nodes. When a node receives a message, it writes changes immediately into the commit log, updates data, and records TS as version ID in each column. If an update is successful and TS is higher than the existing LMT of this state data, then the data access server uses TS to replace the LMT. Note that if a player has quit the game and the state data of the relevant PC has backed up into the Cloud storage system, the LS of this PC needs to be modi ed form \login" to \logout", and the relevant state data in the in-memory database needs to be deleted.
Data access servers obtain log data not from the in-memory database, but from the client side. Log data also updates in batch, and gets timestamp from a data access server. When a node in the Cloud receives log data, it inserts log data into its value list according to the timestamp. However, timestamp tables are not modi ed when the update is complete.
Figure 3 presents executions of read operations. When a player starts the game, a data access server rstly obtains the LS information from the timestamp table. If the value is \login", that means the previous backup operation is not completed and the state data is still stored in the in-memory database. In this case, the player gets the state date from the in-memory database directly, and the data access server needs to generate a new timestamp to replace the LMT of the relevant state data; if the value is \logout", the data access server then gets the LMT, and sends it with a read request to the Cloud storage system. When the relevant node receives the request, it compares the LMT with its local version ID. If they match, the replica responds the read request immediately. If not match, this read request will be sent to other replicas (we will discuss it in detail in the section 5). When the data access server receives the state data, it sends it to the in-memory database as well as the relevant client sides, and modi es the LS from \logout" to \login" in the timestamp table. Note that state data may also be read by the game engine for the purpose of statistics. In this case, the up-to-date data is not necessary, so that we do not need to compare the LMT with the Version ID.
Data analysts read data also through data access servers. If a read request contains a timestamp T, the cloud storage system only returns log data until T-4 because it only guarantees log data timed consistency. 4.3
Concurrency con icts appear rarely in the storage layer of MMORPGs: the probability of read-write con icts is low because only state data with a speci c version ID (the same as its LMT) will be read by players during the game, and a read request to log data does not return the up-to-date data. Certain data is periodically updated by only one data access server simultaneously. Therefore, write-write con icts occur only when the per-update is not completed for some reason, for example, serious network latency, or a node failure. Fortunately, we can solve these con icts easily by comparing timestamps. If two processes attempt to update the same state data, the process with higher timestamp wins, and another process should be canceled because it is out of date. If two processes intend to update the same log data, the process with lower timestamp wins, and another process enters the wait queue. The reason is that values contained in both processes must be stored in correct order.
Data in the Cloud typically has multiple replicas for the purpose of increasing data reliability as well as system availability, and balancing the node workload. On the other hand, data replication increases the response time and the network tra c as well, which cannot be handled well by Cassandra. For most of this section, we focus on resolving this contradiction according to access features of state data and log data. 5.1
Although state data is backed up periodically into the Cloud, only the last updated values will be read when players start the game again. It is noteworthy that the data loss in the server layer occurs infrequently. Therefore, we propose to synchronize only a quorum of replicas during the game, so that an update can complete e ectively and won't block the subsequent updates. In addition, players usually start a game again after a period of time, so the system has enough time to store state data. For this reason, we propose to update all replicas synchronously when players quit the game. As a result, the subsequent read operation can obtain the updated values quickly.
While using our replication strategies, a replica may contain outdated data when it receives a read request. Though comparing LMT held by the read request with the Version ID in a replica, this case can be detected easily. Contrary to the existing approach of Cassandra (compares M-N+1 replicas and utilizes Read Repair), only the read request will be sent to other replicas until the lasted values was found. In this way, the network tra c will not be increased signi cantly, and the up-to-date data can also be found easily. However, if the read request comes from the game engine, the replica will respond immediately. These strategies ensure that this Cloud-based architecture can manage state data under read-your-writes consistency guarantees.
Similar to state data, a write request to log data is also
accepted by a quorum of replicas at rst. However, the
updated values then must be propagated to other replicas
asynchronously when the Cloud storage system is not busy,
and arranged in order of timestamp within a predetermined
time (4), which can be done with the help of Anti-Entropy
functionality in Cassandra [
When the Cloud storage system detected a version con ict between two replicas: if it is state data, the replica with higher version ID wins, and values of another replica will be replaced by new values; if it is log data, these two replicas perform a sort-merge join by timestamps for the purpose of synchronization.
Our Cloud-based architecture for MMORPGs requires a mutual cooperation of multiple components. Unfortunately, each component has the possibility of failure. In the following, we discuss measures to deal with di erent failures.
Cloud storage system failure: the new architecture for MMORPGs is built based on Cassandra, which has the ability to deal with its own failure. For example, Cassandra applies comment logs to recover nodes. It is noteworthy that by using our timestamp-based solution, when a failed node comes back up, it could be regarded as an asynchronous node. Therefore, the node recovery as well as response to write and read requests can perform simultaneously.
In-memory database failure: similarly, we can also apply comment logs to handle this kind of failure so that there is no data loss. However, writing logs a ects the real-time response. Moreover, logs are useless when changes are persisted in the Cloud. Hence, we have to nd a solution in our future work.
Data access server failure: If all data access servers crash, the game can still keep running, whereas data cannot be backed up to the Cloud until servers restart, and only players already in the game can continue to play; Data access servers have the same functionality and their system clocks are relatively synchronized, so if one server is down, any other servers can replace it.
Timestamp table failure: We utilize the primary/secondary model and the synchronous replication mechanism to maintain the reliability of timestamp tables. In the case of all replicas failure, we have to apply the original feature of Cassandra to obtain the up-to-date data. In other words, MN+1 replicas need to be compared. In this way, we can rebuild timestamp tables as well.
When a data access server updates state data in the Cloud,
it propagates a snapshot of state data to multiple replicas.
Note that state data has hundreds of attributes, so the
transmission of a large volume of state data may block the
network. Therefore, we proposed two optimization strategies
in our previous work [
It is noteworthy that a data access server stores a timestamp repeatedly into the timestamp table, which increases the workload. A possible optimization program is as follows: If a batch write is successful, data access server caches the timestamp (TS) of this write request. Accordingly, in the timestamp table, we add a new column to each row to maintain a pointer. If a row is active (the value of LS is \login"), the pointer refers to the memory location of TS; if not, it refers to its own LMT. When a row becomes inactive, it uses TS to replace its LMT. In this way, the workload of a timestamp table will reduce signi cantly. However, LMT and Version ID of state data may be inconsistent due to the failure of the Cloud storage system or the data access server.
Our Cloud-based architecture of MMORPGs can cope with data management requirements regarding availability and scalability successfully, while supporting data consistency becomes an open issue. In this paper, we detailed our timestamp-based solution in theory, which will guide the implementation work in the future. We analyzed the data consistency requirements of each data set from the storage system's perspective, and studied methods of Cassandra to guarantee tunable consistency. We found that Cassandra cannot ensure read-your-writes consistency for state data and timed consistency for log data e ciently. Hence, we proposed a timestamp-based solution to improve it, and explained our idea for concurrency control, data replication strategies, and fault handling in detail. In our future work, we will implement our proposals and the optimization strategies.
Thanks to Eike Schallehn for his comments. 10.