Improving mobile database access over wide-area networks without degrading consistency

ABSTRACT

We report on the design, implementation, and evaluation of a system called Cedar that enables mobile database access with good performance over low-bandwidth networks. This is accomplished without degrading consistency. Cedar exploits the disk storage and processing power of a mobile client to compensate for weak connectivity. Its central organizing principle is that even a stale client replica can be used to reduce data transmission volume from a database server. The reduction is achieved by using content addressable storage to discover and elide commonality between client and server results. This organizing principle allows Cedar to use an optimistic approach to solving the difficult problem of database replica control. For laptop-class clients, our experiments show that Cedar improves the throughput of read-write workloads by 39% to as much as 224% while reducing response time by 28% to as much as 79%.

REFERENCES

• 1: Swarup Acharya , Michael Franklin , Stanley Zdonik, Balancing push and pull for data broadcast, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.183-194, May 11-15, 1997, Tucson, Arizona, United States
• 2: Rafael Alonso , Daniel Barbara , Hector Garcia-Molina, Data caching issues in an information retrieval system, ACM Transactions on Database Systems (TODS), v.15 n.3, p.359-384, Sept. 1990 [doi>10.1145/88636.87848]
• 3: Altinel, M., Bornhövd, C., Krishnamurthy, S., Mohan, C., Pirahesh, H., and Reinwald, B. Cache tables: Paving the way for an adaptive database cache. In Proceedings of 29th International Conference on Very Large Data Bases (Berlin, Germany, 2003), pp718--729.
• 4: Mehmet Altinel , Qiong Luo , Sailesh Krishnamurthy , C. Mohan , Hamid Pirahesh , Bruce G. Lindsay , Honguk Woo , Larry Brown, DBCache: database caching for web application servers, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564765]
• 5: Amiri, K., Park, S., Tewari, R., and Padmanabhan, S. Dbproxy: A dynamic data cache for web applications. In Proceedings of the IEEE International Conference on Data Engineering (ICDE) (Mar. 2003).
• 6: Amza, C., Cecchet, E., Chanda, A., Cox, A., Elnikety, S., Gil, R., Marguerite, J., Rajamani, K., and Zwaenepoe, W. Specification and implementation of dynamic web site benchmarks. In Proceedings of the Fifth Annual IEEE International Workshop on Workload Characterization (WWC--5) (Austin, TX, Nov. 2002), pp3--13.
• 7: B. R. Badrinath , Shirish H. Phatak, On clustering in database servers for supporting mobile clients, Cluster Computing, v.1 n.2, p.149-159, 1998 [doi>10.1023/A:1019081315033 ]
• 8: Daniel Barbará, Mobile Computing and Databases-A Survey, IEEE Transactions on Knowledge and Data Engineering, v.11 n.1, p.108-117, January 1999 [doi>10.1109/69.755619 ]
• 9: Daniel Barbará , Tomasz Imieliński, Sleepers and workaholics: caching strategies in mobile environments, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.1-12, May 24-27, 1994, Minneapolis, Minnesota, United States
• 10: Philip A. Bernstein , Nathan Goodman, Concurrency Control in Distributed Database Systems, ACM Computing Surveys (CSUR), v.13 n.2, p.185-221, June 1981 [doi>10.1145/356842.356846]
• 11: Philip A. Bernstein , Vassco Hadzilacos , Nathan Goodman, Concurrency control and recovery in database systems, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1987
• 12: J. Black, Compare-by-hash: a reasoned analysis, Proceedings of the Annual Technical Conference on USENIX'06 Annual Technical Conference, p.7-7, May 30-June 03, 2006, Boston, MA
• 13: William J. Bolosky , Scott Corbin , David Goebel , John R. Douceur, Single instance storage in Windows® 2000, Proceedings of the 4th conference on USENIX Windows Systems Symposium, p.2-2, August 03-04, 2000, Seattle, Washington
• 14: Eric A. Brewer, Lessons from Giant-Scale Services, IEEE Internet Computing, v.5 n.4, p.46-55, July 2001 [doi>10.1109/4236.939450 ]
• 15: Bright, L., and Raschid, L. Using latency--recency profiles for data delivery on the web. In Proceedings of 28th International Conference on Very Large Data Bases (Hong Kong, China, Aug. 2002), pp550--561.
• 16: Andrei Z. Broder , Steven C. Glassman , Mark S. Manasse , Geoffrey Zweig, Syntactic clustering of the Web, Selected papers from the sixth international conference on World Wide Web, p.1157-1166, September 1997, Santa Clara, California, United States
• 17: S. Ceri , M. Negri , G. Pelagatti, Horizontal data partitioning in database design, Proceedings of the 1982 ACM SIGMOD international conference on Management of data, June 02-04, 1982, Orlando, Florida [doi>10.1145/582353.582376]
• 18: Rajiv Chakravorty , Suman Banerjee , Pablo Rodriguez , Julian Chesterfield , Ian Pratt, Performance optimizations for wireless wide-area networks: comparative study and experimental evaluation, Proceedings of the 10th annual international conference on Mobile computing and networking, September 26-October 01, 2004, Philadelphia, PA, USA [doi>10.1145/1023720.1023737]
• 19: Boris Y. Chan , Antonio Si , Hong V. Leong, A Framework for Cache Management for Mobile Databases: Design and Evaluation, Distributed and Parallel Databases, v.10 n.1, p.23-57, July 2001 [doi>10.1023/A:1019297705159 ]
• 20: Mun Choon Chan , Ramachandran Ramjee, TCP/IP Performance over 3G wireless links with rate and delay variation, Wireless Networks, v.11 n.1-2, p.81-97, January 2005 [doi>10.1007/s11276-004-4748-7]
• 21: Mark D. Corner , Brian D. Noble, Protecting applications with transient authentication, Proceedings of the 1st international conference on Mobile systems, applications and services, p.57-70, May 05-08, 2003, San Francisco, California [doi>10.1145/1066116.1066117]
• 22: Landon P. Cox , Christopher D. Murray , Brian D. Noble, Pastiche: making backup cheap and easy, Proceedings of the 5th symposium on Operating systems design and implementation

  Due to copyright restrictions we are not able to make the PDFs for this conference available for downloading

  , December 09-11, 2002, Boston, Massachusetts [doi>10.1145/1060289.1060316]
• 23: Paul Currion , Chamindra de Silva , Bartel Van de Walle, Open source software for disaster management, Communications of the ACM, v.50 n.3, March 2007 [doi>10.1145/1226736.1226768]
• 24: Frank Dabek , M. Frans Kaashoek , David Karger , Robert Morris , Ion Stoica, Wide-area cooperative storage with CFS, Proceedings of the eighteenth ACM symposium on Operating systems principles, October 21-24, 2001, Banff, Alberta, Canada
• 25: Peter Druschel , Antony Rowstron, PAST: A Large-Scale, Persistent Peer-to-Peer Storage Utility, Proceedings of the Eighth Workshop on Hot Topics in Operating Systems, p.75, May 20-22, 2001
• 26: EMC Corporation. EMC Centera Content Addressed Storage System, 2003. http://www.emc.com/.
• 27: Lei Gao , Mike Dahlin , Amol Nayate , Jiandan Zheng , Arun Iyengar, Application specific data replication for edge services, Proceedings of the 12th international conference on World Wide Web, May 20-24, 2003, Budapest, Hungary [doi>10.1145/775152.775217]
• 28: 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
• 29: Hakan Hacigümüş , Bala Iyer , Chen Li , Sharad Mehrotra, Executing SQL over encrypted data in the database-service-provider model, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564717]
• 30: Hemminger, S. Netem-emulating real networks in the lab. In Proceedings of the 2005 Linux Conference Australia (Canberra, Australia, Apr. 2005).
• 31: Val Henson, An analysis of compare-by-hash, Proceedings of the 9th conference on Hot Topics in Operating Systems, p.3-3, May 18-21, 2003, Lihue, Hawaii
• 32: John H. Howard , Michael L. Kazar , Sherri G. Menees , David A. Nichols , M. Satyanarayanan , Robert N. Sidebotham , Michael J. West, Scale and performance in a distributed file system, ACM Transactions on Computer Systems (TOCS), v.6 n.1, p.51-81, Feb. 1988 [doi>10.1145/35037.35059]
• 33: Hu, N., and Steenkise, P. Evaluation and characterization of available bandwidth probing techniques. IEEE Journal on Selected Areas in Communications (J--SAC) 21, 6 (Aug. 2003), 879--894.
• 34: Iperf: The tcp/udp bandwidth measurement tool. http://dast.nlanr.net/Projects/Iperf/.
• 35: James J. Kistler , M. Satyanarayanan, Disconnected operation in the Coda File System, ACM Transactions on Computer Systems (TOCS), v.10 n.1, p.3-25, Feb. 1992 [doi>10.1145/146941.146942]
• 36: Per-Åke Larson , Jonathan Goldstein , Jingren Zhou, Transparent mid-tier database caching in SQL server, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872848]
• 37: George Lawton, What Lies Ahead for Cellular Technology?, Computer, v.38 n.6, p.14-17, June 2005 [doi>10.1109/MC.2005.207]
• 38: Udi Manber, Finding similar files in a large file system, Proceedings of the USENIX Winter 1994 Technical Conference on USENIX Winter 1994 Technical Conference, p.2-2, January 17-21, 1994, San Francisco, California
• 39: Alfred J. Menezes , Scott A. Vanstone , Paul C. Van Oorschot, Handbook of Applied Cryptography, CRC Press, Inc., Boca Raton, FL, 1996
• 40: Athicha Muthitacharoen , Benjie Chen , David Mazières, A low-bandwidth network file system, Proceedings of the eighteenth ACM symposium on Operating systems principles, October 21-24, 2001, Banff, Alberta, Canada
• 41: MySQL AB. MySQL 5.0 Reference Manual, Oct. 2006.
• 42: Shamkant Navathe , Stefano Ceri , Gio Wiederhold , Jinglie Dou, Vertical partitioning algorithms for database design, ACM Transactions on Database Systems (TODS), v.9 n.4, p.680-710, Dec. 1984 [doi>10.1145/1994.2209]
• 43: Timo Ojala , Jani Korhonen , Tiia Sutinen , Pekka Parhi , Lauri Aalto, Mobile kärpät: a case study in wireless personal area networking, Proceedings of the 3rd international conference on Mobile and ubiquitous multimedia, p.149-156, October 27-29, 2004, College Park, Maryland [doi>10.1145/1052380.1052401]
• 44: Sean Quinlan , Sean Dorward, Venti: A New Approach to Archival Storage, Proceedings of the Conference on File and Storage Technologies, p.89-101, January 28-30, 2002
• 45: Rabin, M. Fingerprinting by random polynomials. In Harvard University Center for Research in Computing Technology Technical Report TR--15--81 (1981).
• 46: Murali Rangan , Ed Swierk , Douglas B. Terry, Contextual Replication for Mobile Users, Proceedings of the International Conference on Mobile Business (ICMB'05), p.457-463, July 11-13, 2005 [doi>10.1109/ICMB.2005.32]
• 47: Erik Riedel , Mahesh Kallahalla , Ram Swaminathan, A Framework for Evaluating Storage System Security, Proceedings of the Conference on File and Storage Technologies, p.15-30, January 28-30, 2002
• 48: M. Satyanarayanan , John H. Howard , David A. Nichols , Robert N. Sidebotham , Alfred Z. Spector , Michael J. West, The ITC distributed file system: principles and design, Proceedings of the tenth ACM symposium on Operating systems principles, p.35-50, December 1985, Orcas Island, Washington, United States
• 49: Tech. Rep. FIPS PUB 180--1, NIST, 1995.
• 50: Tech. Rep. FIPS PUB 180--2, NIST, Aug. 2002.
• 51: Siau, K., Lim, E.-P., and Shen, Z. Mobile commerce: Promises, challenges and research agenda. Journal of Database Management 12, 3 (2001), 4--13.
• 52: Jeff Sidell , Paul M. Aoki , Adam Sah , Carl Staelin , Michael Stonebraker , Andrew Yu, Data Replication in Mariposa, Proceedings of the Twelfth International Conference on Data Engineering, p.485-494, February 26-March 01, 1996
• 53: Swaminathan Sivasubramanian , Gustavo Alonso , Guillaume Pierre , Maarten van Steen, GlobeDB: autonomic data replication for web applications, Proceedings of the 14th international conference on World Wide Web, May 10-14, 2005, Chiba, Japan [doi>10.1145/1060745.1060756]
• 54: Mike Snyder , Jim Steger, Working with Microsoft Dynamics(TM) CRM 3.0, Microsoft Press, Redmond, WA, 2006
• 55: Neil T. Spring , David Wetherall, A protocol-independent technique for eliminating redundant network traffic, Proceedings of the conference on Applications, Technologies, Architectures, and Protocols for Computer Communication, p.87-95, August 28-September 01, 2000, Stockholm, Sweden
• 56: SQLite. http://www.sqlite.org/.
• 57: D. B. Terry , M. M. Theimer , Karin Petersen , A. J. Demers , M. J. Spreitzer , C. H. Hauser, Managing update conflicts in Bayou, a weakly connected replicated storage system, Proceedings of the fifteenth ACM symposium on Operating systems principles, p.172-182, December 03-06, 1995, Copper Mountain, Colorado, United States
• 58: Niraj Tolia , Jan Harkes , Michael Kozuch , M. Satyanarayanan, Integrating Portable and Distributed Storage, Proceedings of the 3rd USENIX Conference on File and Storage Technologies, March 31-31, 2004, San Francisco, CA
• 59: Tolia, N., Kozuch, M., Satyanarayanan, M., Karp, B., Perrig, A., and Bressoud, T. Opportunistic use of content addressable storage for distributed file systems. In Proceedings of the 2003 USENIX Annual Technical Conference (San Antonio, TX, June 2003), pp127--140.
• 60: Niraj Tolia , M. Satyanarayanan, Consistency-preserving caching of dynamic database content, Proceedings of the 16th international conference on World Wide Web, May 08-12, 2007, Banff, Alberta, Canada [doi>10.1145/1242572.1242615]
• 61: Transaction Processing Performance Council. TPC Benchmark App (Application Server): Specification, 1.1.1 ed. San Francisco, CA, Aug. 2005.
• 62: Tridgell, A., and Mackerras, P. The rsync algorithm. Tech. Rep. TR-CS-96-05, Department of Computer Science, The Australian National University, Canberra, Australia, 1996.
• 63: Yao, Q., An, A., and Huang, X. Finding and analyzing database user sessions. In 10th International Conference Database Systems for Advanced Applications (Beijing, China, Apr. 2005), pp851--862.
• 64: Michael Juntao Yuan, Enterprise J2ME: Developing Mobile Java Applications, Prentice Hall PTR, Upper Saddle River, NJ, 2003
• 65: Markos Zaharioudakis , Michael J. Carey , Michael J. Franklin, Adaptive, fine-grained sharing in a client-server OODBMS: a callback-based approach, ACM Transactions on Database Systems (TODS), v.22 n.4, p.570-627, Dec. 1997 [doi>10.1145/278245.278249]
• 66: Bruce Zenel, Enterprise-grade wireless, Queue, v.3 n.4, May 2005 [doi>10.1145/1066051.1066065]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems

General Terms:
Design, Performance

Keywords:
bandwidth optimization, content addressable storage, database caching, low bandwidth networks, mobile database access, relational database systems, wide area networks, wireless networks