skip to main content
10.1145/1247660.1247672acmconferencesArticle/Chapter ViewAbstractPublication PagesmobisysConference Proceedingsconference-collections
Article

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

Published: 13 June 2007 Publication History

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]
Acharya, S., Franklin, M., and Zdonik, S. Balancing push and pull for data broadcast. In SIGMOD '97: Proceedings of the 1997 ACM SIGMOD International Conference on Management of Data (May 1997), pp183--194.
[2]
Alonso, R., Barbara, D., and Garcia-Molina, H. Data caching issues in an information retrieval system. ACM Transaction on Database Systems 15, 3 (1990), 359--384.
[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]
Altinel, M., Luo, Q., Krishnamurthy, S., Mohan, C., Pirahesh, H., Lindsay, BG., Woo, H., and Brown, L. Dbcache: Database caching for web application servers. In Proceedings of the 2002 ACM SIGMOD International Conference on Management of Data (2002), pp612--612.
[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]
Badrinath, BR., and Phatak, SH. On clustering in database servers for supporting mobile clients. Cluster Computing 1, 2 (1998), 149--159.
[8]
Barbará, D. Mobile computing and databases--a survey. IEEE Transactions on Knowledge and Data Engineering 11, 1 (1999), 108--117.
[9]
Barbará, D., and Imielinski, T. Sleepers and workaholics: Caching strategies in mobile environments. In SIGMOD '94: Proceedings of the 1994 ACM SIGMOD International Conference on Management of Data (1994), pp1--12.
[10]
Bernstein, PA., and Goodman, N. Concurrency control in distributed database systems. ACM Computing Surveys 13, 2 (1981), 185--221.
[11]
Bernstein, PA., Hadzilacos, V., and Goodman, N. Concurrency Control and Recovery in Database Systems. Addison-Wesley, 1987.
[12]
Black, J. Compare-by-hash: A reasoned analysis. In Proc. 2006 USENIX Annual Technical Conference (Boston, MA, May 2006), pp85--90.
[13]
Bolosky, WJ., Corbin, S., Goebel, D., and Douceur, JR. Single instance storage in windows 2000. In Proceedings of the 4th USENIX Windows Systems Symposium (Seattle, WA, Aug. 2000), pp13--24.
[14]
Brewer, EA. Lessons from giant--scale services. IEEE Internet Computing 5, 4 (2001), 46--55.
[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]
Broder, A., Glassman, S., Manasse, M., and Zweig, G. Syntactic clustering of the web. In Proceedings of the 6th International WWW Conference (Santa Clara, CA, Apr. 1997), pp1157--1166.
[17]
Ceri, S., Negri, M., and Pelagatti, G. Horizontal data partitioning in database design. In SIGMOD '82: Proceedings of the 1982 ACM SIGMOD International Conference on Management of Data (June 1982), pp128--136.
[18]
Chakravorty, R., Banerjee, S., Rodriguez, P., Chesterfield, J., and Pratt, I. Performance optimizations for wireless wide--area networks: Comparative study and experimental evaluation. In MobiCom '04: Proceedings of the 10th Annual International Conference on Mobile Computing and Networking (2004), pp159--173.
[19]
Chan, BY., Si, A., and Leong, HV. A framework for cache management for mobile databases: Design and evaluation. Distributed and Parallel Databases 10, 1 (2001), 23--57.
[20]
Chan, MC., and Ramjee, R. Tcp/ip performance over 3g wireless links with rate and delay variation. Wireless Networks 11, 1--2 (2005), 81--97.
[21]
Corner, MD., and Noble, BD. Protecting applications with transient authentication. In MobiSys '03: Proceedings of the 1st International Conference on Mobile Systems, Applications and Services (2003), pp57--70.
[22]
Cox, LP., Murray, CD., and Noble, BD. Pastiche: Making backup cheap and easy. In OSDI: Symposium on Operating Systems Design and Implementation (2002).
[23]
Currion, P., de Silva, C., and de Walle, BV. Open source software for disaster management. Communications of the ACM 50, 3 (2007), 61--65.
[24]
Dabek, F., Kaashoek, MF., Karger, D., Morris, R., and Stoica, I. Wide--area cooperative storage with CFS. In Proceedings of the 18th ACM Symposium on Operating Systems Principles (SOSP '01) (Chateau Lake Louise, Banff, Canada, Oct. 2001).
[25]
Druschel, P., and Rowstron, A. PAST: A large--scale, persistent peer-to-peer storage utility. In HotOS VIII (Schloss Elmau, Germany, May 2001), pp75--80.
[26]
EMC Corporation. EMC Centera Content Addressed Storage System, 2003. http://www.emc.com/.
[27]
Gao, L., Dahlin, M., Nayate, A., Zheng, J., and Iyengar, A. Application specific data replication for edge services. In WWW '03: Proceedings of the Twelfth International Conference on World Wide Web (2003), pp449--460.
[28]
Gray, J., Helland, P., O'Neil, P., and Shasha, D. The dangers of replication and a solution. In SIGMOD '96: Proceedings of the 1996 ACM SIGMOD International Conference on Management of Data (June 1996), pp173--182.
[29]
Hacigumus, H., Iyer, B., Li, C., and Mehrotra, S. Executing sql over encrypted data in the database--service--provider model. In Proceedings of the 2002 ACM SIGMOD International Conference on Management of Data (2002), pp216--227.
[30]
Hemminger, S. Netem-emulating real networks in the lab. In Proceedings of the 2005 Linux Conference Australia (Canberra, Australia, Apr. 2005).
[31]
Henson, V. An analysis of compare-by-hash. In Proceedings of the 9th Workshop on Hot Topics in Operating Systems (HotOS IX) (May 2003), pp13--18.
[32]
Howard, J., Kazar, M., Menees, S., Nichols, D., Satyanarayanan, M., Sidebotham, R., and West, M. Scale and performance in a distributed file system. ACM Transactions on Computer Systems 6, 1 (Feb. 1988).
[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]
Kistler, JJ., and Satyanarayanan, M. Disconnected operation in the coda file system. ACM Transactions on Computing Systems 10, 1 (1992), 3--25.
[36]
Larson, P.-Å., Goldstein, J., and Zhou, J. Transparent mid-tier database caching in sql server. In Proceedings of the 2003 ACM SIGMOD International Conference on Management of Data (2003), pp661--661.
[37]
Lawton, G. What lies ahead for cellular technology? IEEE Computer 38, 6 (2005), 14--17.
[38]
Manber, U. Finding similar files in a large file system. In Proceedings of the {USENIX} Winter 1994 Technical Conference (San Fransisco, CA, 17--21 1994), pp1--10.
[39]
Menezes, AJ., Oorschot, P. CV., and Vanstone, SA. Handbook of Applied Cryptography. CRC Press, Inc., 2001.
[40]
Muthitacharoen, A., Chen, B., and Mazieres, D. A low--bandwidth network file system. In Proceedings of the 18th ACM Symposium on Operating Systems Principles (Chateau Lake Louise, Banff, Canada, Oct. 2001).
[41]
MySQL AB. MySQL 5.0 Reference Manual, Oct. 2006.
[42]
Navathe, SB., Ceri, S., Wiederhold, G., and Dou, J. Vertical partitioning algorithms for database design. ACM Transactions on Database Systems 9, 4 (1984), 680--710.
[43]
Ojala, T., Korhonen, J., Sutinen, T., Parhi, P., and Aalto, L. Mobile kärpät: A case study in wireless personal area networking. In MUM '04: Proceedings of the 3rd International Conference on Mobile and Ubiquitous Multimedia (2004), pp149--156.
[44]
Quinlan, S., and Dorward, S. Venti: A new approach to archival storage. In Proceedings of the FAST 2002 Conference on File and Storage Technologies (2002).
[45]
Rabin, M. Fingerprinting by random polynomials. In Harvard University Center for Research in Computing Technology Technical Report TR--15--81 (1981).
[46]
Rangan, M., Swierk, E., and Terry, DB. Contextual replication for mobile users. In Proceedings of the International Conference on Mobile Business (ICMB'05) (Synday, Australia, July 2005), pp457--463.
[47]
Riedel, E., Kallahalla, M., and Swaminathan, R. A framework for evaluating storage system security. In Proceedings of the FAST '02 Conference on File and Storage Technologies (Monterey, CA, Jan. 2002), pp15--30.
[48]
Satyanarayanan, M., Howard, JH., Nichols, DA., Sidebotham, RN., Spector, AZ., and West, MJ. The itc distributed file system: Principles and design. In SOSP '85: Proceedings of the Tenth ACM Symposium on Operating Systems Principles (1985), pp35--50.
[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]
Sidell, J., Aoki, PM., Sah, A., Staelin, C., Stonebraker, M., and Yu, A. Data replication in mariposa. In ICDE '96: Proceedings of the Twelfth International Conference on Data Engineering (New Orleans, LA, Feb. 1996), pp485--494.
[53]
Sivasubramanian, S., Alonso, G., Pierre, G., and van Steen, M. Globedb: Autonomic data replication for web applications. In WWW '05: Proceedings of the 14th International World--Wide Web conference (May 2005).
[54]
Snyder, M., and Steger, J. Working with Microsoft Dynamics CRM 3.0. Microsoft Press, Redmond, WA, USA, 2006.
[55]
Spring, NT., and Wetherall, D. A protocol--independent technique for eliminating redundant network traffic. In Proceedings of ACM SIGCOMM (Aug. 2000).
[56]
SQLite. http://www.sqlite.org/.
[57]
Terry, DB., Theimer, MM., Petersen, K., Demers, AJ., Spreitzer, MJ., and Hauser, CH. Managing update conflicts in bayou, a weakly connected replicated storage system. In SOSP '95: Proceedings of the Fifteenth ACM Symposium on Operating Systems Principles (Dec. 1995), pp172--182.
[58]
Tolia, N., Harkes, J., Kozuch, M., and Satyanarayanan, M. Integrating portable and distributed storage. In Proceedings of the 3rd USENIX Conference on File and Storage Technologies (San Francisco, CA, March 31--April 2, 2004).
[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]
Tolia, N., and Satyanarayanan, M. No-compromise caching of dynamic content from relational databases. In Proceedings of the 16th International World Wide Web Conference (WWW2007) (Banff, Canada, May 2007). To Appear.
[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]
Yuan, MJ. Enterprise J2ME: Developing Mobile Java Applications. Prentice Hall PTR, Upper Saddle River, NJ, USA, 2003.
[65]
Zaharioudakis, M., Carey, MJ., and Franklin, MJ. Adaptive, fine-grained sharing in a client-server oodbms: a callback-based approach. ACM Transactions on Database Systems 22, 4 (1997), 570--627.
[66]
Zenel, B., and Toy, A. Enterprise-grade wireless. ACM Queue 3, 4 (2005), 30--37.

Cited By

View all
  • (2015)Reliable, consistent, and efficient data sync for mobile appsProceedings of the 13th USENIX Conference on File and Storage Technologies10.5555/2750482.2750509(359-372)Online publication date: 16-Feb-2015
  • (2015)RACProceedings of the 19th Panhellenic Conference on Informatics10.1145/2801948.2801978(394-399)Online publication date: 1-Oct-2015
  • (2015)SimbaProceedings of the Tenth European Conference on Computer Systems10.1145/2741948.2741974(1-16)Online publication date: 17-Apr-2015
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
MobiSys '07: Proceedings of the 5th international conference on Mobile systems, applications and services
June 2007
310 pages
ISBN:9781595936141
DOI:10.1145/1247660
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 13 June 2007

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. bandwidth optimization
  2. content addressable storage
  3. database caching
  4. low bandwidth networks
  5. mobile database access
  6. relational database systems
  7. wide area networks
  8. wireless networks

Qualifiers

  • Article

Conference

Mobisys07
Sponsor:

Acceptance Rates

Overall Acceptance Rate 274 of 1,679 submissions, 16%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)2
  • Downloads (Last 6 weeks)0
Reflects downloads up to 07 Jan 2025

Other Metrics

Citations

Cited By

View all
  • (2015)Reliable, consistent, and efficient data sync for mobile appsProceedings of the 13th USENIX Conference on File and Storage Technologies10.5555/2750482.2750509(359-372)Online publication date: 16-Feb-2015
  • (2015)RACProceedings of the 19th Panhellenic Conference on Informatics10.1145/2801948.2801978(394-399)Online publication date: 1-Oct-2015
  • (2015)SimbaProceedings of the Tenth European Conference on Computer Systems10.1145/2741948.2741974(1-16)Online publication date: 17-Apr-2015
  • (2014)A lazy commit protocol for mobile transactions2014 IEEE International Advance Computing Conference (IACC)10.1109/IAdCC.2014.6779363(432-437)Online publication date: Feb-2014
  • (2012)MobiusProceedings of the 10th international conference on Mobile systems, applications, and services10.1145/2307636.2307650(141-154)Online publication date: 25-Jun-2012
  • (2012)Help Me: Opportunistic smart rescue application and system2012 The 11th Annual Mediterranean Ad Hoc Networking Workshop (Med-Hoc-Net)10.1109/MedHocNet.2012.6257129(98-105)Online publication date: Jun-2012
  • (2012)Implementing and Optimizing an Encryption Filesystem on AndroidProceedings of the 2012 IEEE 13th International Conference on Mobile Data Management (mdm 2012)10.1109/MDM.2012.31(52-62)Online publication date: 23-Jul-2012
  • (2009)A cross-layer method to improve mobile database synchronization performanceProceedings of the 5th International Conference on Wireless communications, networking and mobile computing10.5555/1738467.1738814(5540-5543)Online publication date: 24-Sep-2009
  • (2008)Low-bandwidth VM migration via opportunistic replayProceedings of the 9th workshop on Mobile computing systems and applications10.1145/1411759.1411779(74-79)Online publication date: 25-Feb-2008
  • (2008)A binary hybrid replication strategy for improving availability and maintaining consistency of data in large scale mobile environments2008 International Symposium on Information Technology10.1109/ITSIM.2008.4632007(1-9)Online publication date: Aug-2008
  • Show More Cited By

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media