Applying database replication to multi-player online games

ABSTRACT

Multi-player Online Games (MOGs) have emerged as popular data intensive applications in recent years. Being used by many players simultaneously, they require a high degree of fault tolerance, scalability and performance. In this paper we analyze how database replication can be used in MOGs to achieve these goals. In data replication, clients can read data from any database replica while updates have to be executed at all available replicas. Thus, reads can be distributed among the replicas leading to reduced response time and scalability. Furthermore, the system is fault-tolerant as long as a replica is available. However, we are not aware of any previous study on the application of database replication to MOG. In this paper, we present a system, MiddleSIR, which provides database replication support. We illustrate different replication protocols implemented in the system along an example, explaining how data consistency and fault tolerance can be achieved. From there, we design a small multi-player typing game to demonstrate how to apply database replication to MOG. We will discuss how different replication protocols affect the semantics of the game. Our experiments show that database replication can provide good scalability and performance in both Local Area Networks (LAN) and Wide Area Networks (WAN).

REFERENCES

• 1: Jin Chen , Baohua Wu , Margaret Delap , Björn Knutsson , Honghui Lu , Cristiana Amza, Locality aware dynamic load management for massively multiplayer games, Proceedings of the tenth ACM SIGPLAN symposium on Principles and practice of parallel programming, June 15-17, 2005, Chicago, IL, USA [doi>10.1145/1065944.1065982]
• 2: Emulab. http://www.emulab.net.
• 3: Jim Gray , Pat Helland , Patrick O'Neil , Dennis Shasha, The dangers of replication and a solution, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.173-182, June 04-06, 1996, Montreal, Quebec, Canada
• 4: Carsten Griwodz, State replication for multiplayer games, Proceedings of the 1st workshop on Network and system support for games, p.29-35, April 16-17, 2002, Bruanschweig, Germany [doi>10.1145/566500.566505]
• 5: R. Jiménez-Peris, M. Patiño-Martínez, B. Kemme, and G. Alonso. Improving Scalability of Fault Tolerant Database Clusters. In ICDCS'02.
• 6: Bjorn Knutsson, Honghui Lu, Wei Xu, and Bryan Hopkins. Peer-to-peer support for massy multiplayer games. In INFOCOM, Hong Kong, China, 2004.
• 7: Y. Lin, B. Kemme, R. Jiménez-Peris, and M. Patiño-Martínez. Consistent Data Replication: Is it feasible in WANs? In Euro-Par, Sep 2005.
• 8: Yi Lin , Bettina Kemme , Marta Patiño-Martínez , Ricardo Jiménez-Peris, Middleware based data replication providing snapshot isolation, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066205]
• 9: Y. Lin, B. Kemme, R. Jiménez-Peris, and M. Patiño-Martínez. Practical Database Replication in WANS. In Unpublished manuscript, Nov 2005.
• 10: Ian Lintault, A transaction execution engine architecture for multiplayer online games, Proceedings of 3rd ACM SIGCOMM workshop on Network and system support for games, August 30-30, 2004, Portland, Oregon, USA [doi>10.1145/1016540.1016563]
• 11: Marta Patiño-Martinez , Ricardo Jiménez-Peris , Bettina Kemme , Gustavo Alonso, MIDDLE-R: Consistent database replication at the middleware level, ACM Transactions on Computer Systems (TOCS), v.23 n.4, p.375-423, November 2005 [doi>10.1145/1113574.1113576]
• 12: I. Scott MacKenzie , Colin Ware, Lag as a determinant of human performance in interactive systems, Proceedings of the SIGCHI conference on Human factors in computing systems, p.488-493, April 24-29, 1993, Amsterdam, The Netherlands [doi>10.1145/169059.169431]
• 13: News. http://pc.gamespy.com/pc/world-of-warcraft/582134pl.html.
• 14: Christian Plattner , Gustavo Alonso, Ganymed: scalable replication for transactional web applications, Proceedings of the 5th ACM/IFIP/USENIX international conference on Middleware, October 18-22, 2004, Toronto, Canada
• 15: S. Cheshire. Latency and the quest for interactivity, 1996.
• 16: P. M. Sharkey , M. D. Ryan , D. J. Roberts, A Local Perception Filter for Distributed Virtual Environments, Proceedings of the Virtual Reality Annual International Symposium, p.242, March 14-18, 1998
• 17: Jouni Smed , Henrik Niinisalo , Harri Hakonen, Realizing the bullet time effect in multiplayer games with local perception filters, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.49 n.1, p.27-37, 15 September 2005 [doi>10.1016/j.comnet.2005.04.007]
• 18: António Sousa , Rui Oliveira , Francisco Moura , Fernando Pedone, Partial Replication in the Database State Machine, Proceedings of the IEEE International Symposium on Network Computing and Applications (NCA'01), p.298, October 08-10, 2001
• 19: Matthias Wiesmann , Andre Schiper, Comparison of Database Replication Techniques Based on Total Order Broadcast, IEEE Transactions on Knowledge and Data Engineering, v.17 n.4, p.551-566, April 2005 [doi>10.1109/TKDE.2005.54]

INDEX TERMS

Primary Classification:
  K. Computing Milieux
  K.8 PERSONAL COMPUTING
      K.8.0 General
          Subjects: Games

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems
          Subjects: Distributed databases; Distributed applications

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.2 Physical Design

General Terms:
Design, Experimentation, Performance, Reliability