|
ABSTRACT
Failure-resilient, scalable, and secure read-write access to shared information by mobile and static users over wireless and wired networks is a fundamental computing challenge. In this article, we describe how the Coda file system has evolved to meet this challenge through the development of mechanisms for server replication, disconnected operation, adaptive use of weak connectivity, isolation-only transactions, translucent caching, and opportunistic exploitation of hardware surrogates. For each mechanism, the article explains how usage experience with it led to the insights for another mechanism. It also shows how Coda has been influenced by the work of other researchers and by industry. The article closes with a discussion of the technical and nontechnical lessons that can be learned from the evolution of the system.
REFERENCES
Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.
| |
1
|
|
 |
2
|
Mary G. Baker , John H. Hartman , Michael D. Kupfer , Ken W. Shirriff , John K. Ousterhout, Measurements of a distributed file system, Proceedings of the thirteenth ACM symposium on Operating systems principles, p.198-212, October 13-16, 1991, Pacific Grove, California, United States
|
| |
3
|
Bartlett, J., Garcia, D., Gray, J., Horst, B., Lenoski, D., McGuire, D., and Worsencroft, K. 1988. Fault Tolerance in Tandem Computer Systems. Tandem Computer Corp.
|
 |
4
|
B. N. Bershad , S. Savage , P. Pardyak , E. G. Sirer , M. E. Fiuczynski , D. Becker , C. Chambers , S. Eggers, Extensibility safety and performance in the SPIN operating system, Proceedings of the fifteenth ACM symposium on Operating systems principles, p.267-283, December 03-06, 1995, Copper Mountain, Colorado, United States
|
 |
5
|
|
| |
6
|
Braam, P. J. and Nelson, P. A. 1999. Removing bottlenecks in distributed filesystems: Coda & InterMezzo as examples. In Proceedings of Linux Expo 1999 (Raleigh, N.C., May).
|
| |
7
|
Braam, P. J., Callahan, M. J., Satyanarayanan, M., and Schnieder, M. 1999. Porting the Coda file system to Windows. In Proceedings of the FREENIX Track: 1999 USENIX Annual Technical Conference (Monterey, Calif., June).
|
| |
8
|
Braam, P. J., Callahan, M. J., and Schwan, P. 1999. The InterMezzo filesystem. In The Perl Conference 3, O'Reilly Open Source Convention (Monterey, Calif., August).
|
 |
9
|
|
| |
10
|
|
| |
11
|
Cornsweet, T. N. 1971. Visual Perception. Academic Press.
|
 |
12
|
|
| |
13
|
Demers, A., Petersen, K., Spreitzer, M., Terry, D., Theimer, M., and Welch, B. 1994. The Bayou architecture: Support for data sharing among mobile users. In Proceedings of the Workshop on Mobile Computing Systems and Applications (Santa Cruz, Calif., Dec.).
|
| |
14
|
|
 |
15
|
|
 |
16
|
|
 |
17
|
D. R. Engler , M. F. Kaashoek , J. O'Toole, Jr., Exokernel: an operating system architecture for application-level resource management, Proceedings of the fifteenth ACM symposium on Operating systems principles, p.251-266, December 03-06, 1995, Copper Mountain, Colorado, United States
|
| |
18
|
|
| |
19
|
Eppinger, J. L., Mummert, L. B., and Spector, A. Z. 1991. Camelot and Avalon. Morgan Kaufmann, San Mateo, Calif.
|
 |
20
|
|
| |
21
|
Feeley, M. J., Chase, J. S., Narasayya, V. R., and Levy, H. M. 1994. Integrating coherency and recovery in distributed systems. In Proceedings of the First Usenix Symposium on Operating System Design and Implementation (Monterey, Calif., Nov.).
|
| |
22
|
Fidge, C. J. 1988. Timestamps in message-passing systems that preserve the partial ordering. In Proceedings of the Eleventh Australian Computer Science Conference (University of Queensland, Australia, Feb.).
|
| |
23
|
|
 |
24
|
|
| |
25
|
Gray, J. 1986. Why do computers stop and what can be done about it? In Proceedings of the Fifth Symposium on Reliability in Distributed Software and Database Systems.
|
| |
26
|
Gray, J. 1997. Windows NT to the max---Just how far can it scale up? In The USENIX Windows NT Workshop Proceedings (Seattle, Wash., August). Invited Talk Slides available at //www.usenix.org/publications/library/proceedings/usenix-nt97/presentations/index.html.
|
| |
27
|
|
| |
28
|
Guy, R. G. 1987. A replicated filesystem design for a distributed Unix system. Master's Thesis, Department of Computer Science, University of California, Los Angeles.
|
| |
29
|
|
| |
30
|
Guy, R. G. and Popek, G. J. 1990. Reconciling partially replicated name spaces. Tech. Rep. CSD-900010, University of California, Los Angeles, April.
|
| |
31
|
|
| |
32
|
|
 |
33
|
|
| |
34
|
Houghton, A. 1997. The Engineer's Error Coding Handbook. Chapman & Hall, London.
|
 |
35
|
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]
|
| |
36
|
Jordan, M. 1996. Early experiences with persistent Java. In M. Jordan and M. Atkinson, eds., Proceedings of the First International Workshop on Persistence and Java (Drymen, Scotland, Sept.).
|
| |
37
|
Kazar, M., Leverett, B., Anderson, O., Apostolides, V., Bottos, B., Chutani, S., Everhart, C., Mason, W., Tu, S., and Zayas, E. 1990. Decorum file system architectural overview. In Proceedings of the Summer 1990 Usenix Conference (Anaheim, Calif., June).
|
 |
38
|
|
| |
39
|
Kleiman, S. R. 1986. Vnodes: An architecture for multiple file system types in Sun UNIX. In Summer Usenix Conference Proceedings.
|
 |
40
|
|
| |
41
|
Kumar, P. 1994. Mitigating the effects of optimistic replication in a distributed file system. PhD Thesis, School of Computer Science, Carnegie Mellon University, December.
|
| |
42
|
|
| |
43
|
Kumar, P. and Satyanarayanan, M. 1993b. Supporting application-specific resolution in an optimistically replicated file system. In Proceedings of the Fourth IEEE Workshop on Workstation Operating Systems (Napa, Calif., Oct.).
|
| |
44
|
Kumar, P. and Satyanarayanan, M. 1995. Flexible and safe resolution of file conflicts. In Proceedings of the USENIX Winter 1995 Technical Conference (New Orleans, La., Jan.).
|
 |
45
|
|
| |
46
|
LeBlanc, O. 2000. Coda. In Linux 2000 UK Linux Developers Conference (Hammersmith, UK, July). Available at http://www.ukuug.org/events/linux2000/speaker-ol.shtml.
|
| |
47
|
|
| |
48
|
Lee, Y., Leung, K. S., and Satyanarayanan, M. 1999. Operation-based update propagation in a mobile file system. In Proceedings of the USENIX Annual Technical Conference. (Monterey, Calif., June).
|
| |
49
|
Long, D. E. 1990. Analysis of replication control protocols. In Proceedings of the IEEE Workshop on Management of Replicated Data (Houston, Tex, Nov.).
|
| |
50
|
LoVerso, J. R. and Mazer, M. S. 1997. Caubweb: Detaching the web with Tcl. In Proceedings of the Fifth Annual Tcl/Tk Workshop. Boston, Mass. July).
|
 |
51
|
|
| |
52
|
Lu, Q. 1996. Improving data consistency in mobile file access using isolation-only transactions. PhD Thesis, School of Computer Science, Carnegie Mellon University, May.
|
| |
53
|
|
| |
54
|
|
| |
55
|
|
| |
56
|
Lymn, B. 2001b. Coda---The disconnectable file system. SysAdmin 10, 7 (July).
|
| |
57
|
|
 |
58
|
L. B. Mummert , M. R. Ebling , M. Satyanarayanan, Exploiting weak connectivity for mobile file access, Proceedings of the fifteenth ACM symposium on Operating systems principles, p.143-155, December 03-06, 1995, Copper Mountain, Colorado, United States
|
 |
59
|
|
 |
60
|
James O'Toole , Scott Nettles , David Gifford, Concurrent compacting garbage collection of a persistent heap, Proceedings of the fourteenth ACM symposium on Operating systems principles, p.161-174, December 05-08, 1993, Asheville, North Carolina, United States
|
| |
61
|
|
 |
62
|
John K. Ousterhout , Hervé Da Costa , David Harrison , John A. Kunze , Mike Kupfer , James G. Thompson, A trace-driven analysis of the UNIX 4.2 BSD file system, Proceedings of the tenth ACM symposium on Operating systems principles, p.15-24, December 1985, Orcas Island, Washington, United States
|
| |
63
|
Paris, J.-F. 1986. Voting with witnesses: A consistency scheme for replicated files. In Proceedings of the Sixth IEEE International Conference on Distributed Computing Systems (Cambridge).
|
| |
64
|
Parker, D. S. Jr., Popek, G. J., Rudisin, G., Stoughton, A., Walker, B. J., Walton, E., Chow, J. M., Edwards, D., Kiser, S., and Kline, C. 1983. Detection of mutual inconsistency in distributed systems. IEEE Trans. Softw. Eng. SE-9, 3 (May).
|
| |
65
|
Pietrek, M. 1995. Windows 95 System Programming Secrets. IDG Books.
|
| |
66
|
|
 |
67
|
G. Popek , B. Walker , J. Chow , D. Edwards , C. Kline , G. Rudisin , G. Thiel, LOCUS a network transparent, high reliability distributed system, Proceedings of the eighth ACM symposium on Operating systems principles, p.169-177, December 14-16, 1981, Pacific Grove, California, United States
|
| |
68
|
|
| |
69
|
|
| |
70
|
Rashid, R., Baron, R., Forin, A., Golub, D., Jones, M., Julin, D., Orr, D., and Sanzi, R. 1989. Mach: A foundation for open systems. In Proceedings of the Second Workshop on Workstation Operating Systems (Pacific Grove, Calif., Sept.).
|
| |
71
|
Rivest, R. 1992. The MD5 message-digest algorithm, Internet RFC 1321. Available at http://theory.lcs.mit.edu/~rivest/publications.html.
|
| |
72
|
Sandberg, R., Goldberg, D., Kleiman, S., Walsh, D., and Lyon, B. 1985. Design and implementation of the Sun Network Filesystem. In Summer Usenix Conference Proceedings (Portland, Ore.).
|
| |
73
|
|
 |
74
|
|
| |
75
|
Satyanarayanan, M. 2001. Pervasive computing: Vision and challenges. IEEE Pers. Commun. 8, 4 (August).
|
| |
76
|
|
| |
77
|
Mahadev Satyanarayanan , James J. Kistler , Puneet Kumar , Maria E. Okasaki , Ellen H. Siegel , David C. Steere, Coda: A Highly Available File System for a Distributed Workstation Environment, IEEE Transactions on Computers, v.39 n.4, p.447-459, April 1990
[doi> 10.1109/12.54838]
|
| |
78
|
Satyanarayanan, M., Kistler, J. J., Mummert, L. B., Ebling, M. R., Kumar, P., and Lu, Q. 1993a. Experience with disconnected operation in a mobile computing environment. In Proceedings of the 1993 USENIX Symposium on Mobile and Location-Independent Computing (Cambridge, Mass., August).
|
 |
79
|
M. Satyanarayanan , Henry H. Mashburn , Puneet Kumar , David C. Steere , James J. Kistler, Lightweight recoverable virtual memory, Proceedings of the fourteenth ACM symposium on Operating systems principles, p.146-160, December 05-08, 1993, Asheville, North Carolina, United States
|
| |
80
|
Satyanarayanan, M., Kistler, J. J., and Siegel, E. H. 1987. Coda: A resilient distributed file system. In Proceedings of the IEEE Workshop on Workstation Operating Systems (Cambridge, Mass. Nov.).
|
| |
81
|
Schneier, B. 1996. Applied Cryptography. Wiley, New York.
|
 |
82
|
|
| |
83
|
Schulman, A. 1995. Unauthorized Windows 95. IDG Books.
|
 |
84
|
Margo I. Seltzer , Yasuhiro Endo , Christopher Small , Keith A. Smith, Dealing with disaster: surviving misbehaved kernel extensions, Proceedings of the second USENIX symposium on Operating systems design and implementation, p.213-227, October 29-November 01, 1996, Seattle, Washington, United States
|
| |
85
|
Short, R. 1997. What a tangled mess! Untangling user-visible complexity in windows systems. In The USENIX Windows NT Workshop Proceedings (Seattle, Wash., August). Invited Talk Slides available at //www.usenix.org/publications/library/proceedings/usenix-nt97/ presentations/index.html.
|
| |
86
|
|
| |
87
|
Steere, D. C., Kistler, J. J., and Satyanarayanan, M. 1990. Efficient user-level cache file management on the Sun Vnode interface. In Summer Usenix Conference Proceedings (Anaheim, Calif., June).
|
 |
88
|
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
|
 |
89
|
|
 |
90
|
|
 |
91
|
Bruce Walker , Gerald Popek , Robert English , Charles Kline , Greg Thiel, The LOCUS distributed operating system, Proceedings of the ninth ACM symposium on Operating systems principles, p.49-70, October 10-13, 1983, Bretton Woods, New Hampshire, United States
|
| |
92
|
Webster's Ninth New Collegiate Dictionary. 1988. Merriam-Webster, Springfield, Mass.
|
CITED BY 25
|
|
Geoffrey H. Kuenning , Wilkie Ma , Peter Reiher , Gerald J. Popek, Simplifying automated hoarding methods, Proceedings of the 5th ACM international workshop on Modeling analysis and simulation of wireless and mobile systems, September 28-28, 2002, Atlanta, Georgia, USA
|
|
|
|
|
|
|
|
|
|
|
|
Rajesh Krishna Balan , Mahadev Satyanarayanan , So Young Park , Tadashi Okoshi, Tactics-based remote execution for mobile computing, Proceedings of the 1st international conference on Mobile systems, applications and services, p.273-286, May 05-08, 2003, San Francisco, California
|
|
|
|
|
|
Ramón Cáceres , Casey Carter , Chandra Narayanaswami , Mandayam Raghunath, Reincarnating PCs with portable SoulPads, Proceedings of the 3rd international conference on Mobile systems, applications, and services, June 06-08, 2005, Seattle, Washington
|
|
|
Francisco Alvarez-Cavazos , Roberto Garcia-Sanchez , David Garza-Salazar , Juan C. Lavariega , Lorena G. Gomez , Martha Sordia, Universal access architecture for digital libraries, Proceedings of the 2005 conference of the Centre for Advanced Studies on Collaborative research, p.12-28, October 17-20, 2005, Toranto, Ontario, Canada
|
|
|
Alessandra A. Macedo , Laércio Baldochi, Jr. , José A. Camacho-Guerrero , Renan G. Cattelan , Maria Da Pimentel, Automatically linking live experiences captured with a ubiquitous infrastructure, Multimedia Tools and Applications, v.37 n.2, p.93-115, April 2008
|
|
|
|
|
|
Rajesh Balan , Jason Flinn , M. Satyanarayanan , Shafeeq Sinnamohideen , Hen-I Yang, The case for cyber foraging, Proceedings of the 10th workshop on ACM SIGOPS European workshop: beyond the PC, July 01-01, 2002, Saint-Emilion, France
|
|
|
|
|
|
|
|
|
Hyunbin Lee , YongJoo Song , Kyungbaek Kim , Donggook Kim , Daeyeon Park, CriStore: dynamic storage system for heterogeneous devices in off-site ubiquitous communities, Proceedings of the 2007 ACM symposium on Applied computing, March 11-15, 2007, Seoul, Korea
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Mahadev Satyanarayanan , Benjamin Gilbert , Matt Toups , Niraj Tolia , Ajay Surie , David R. O'Hallaron , Adam Wolbach , Jan Harkes , Adrian Perrig , David J. Farber , Michael A. Kozuch , Casey J. Helfrich , Partho Nath , H. Andres Lagar-Cavilla, Pervasive Personal Computing in an Internet Suspend/Resume System, IEEE Internet Computing, v.11 n.2, p.16-25, March 2007
|
|
|
|
|
|
Brandon Salmon , Steven W. Schlosser , Lorrie Faith Cranor , Gregory R. Ganger, Perspective: semantic data management for the home, Proccedings of the 7th conference on File and stroage technologies, p.167-182, February 24-27, 2009, San Francisco, California
|
|
|
|
|
|
H. Andrés Lagar-Cavilla , Niraj Tolia , Eyal de Lara , M. Satyanarayanan , David O'Hallaron, Interactive resource-intensive applications made easy, Proceedings of the ACM/IFIP/USENIX 2007 International Conference on Middleware, November 26-30, 2007, Newport Beach, California
|
|
|
|
|
|
|
INDEX TERMS
Primary Classification:
D.
Software
D.4
OPERATING SYSTEMS
D.4.3
File Systems Management
Subjects:
Distributed file systems
Additional Classification:
C.
Computer Systems Organization
C.2
COMPUTER-COMMUNICATION NETWORKS
C.2.1
Network Architecture and Design
Subjects:
Wireless communication
C.2.4
Distributed Systems
Subjects:
Client/server
D.
Software
D.2
SOFTWARE ENGINEERING
D.2.11
Software Architectures
D.2.13
Reusable Software
D.2.7
Distribution, Maintenance, and Enhancement
D.4
OPERATING SYSTEMS
D.4.5
Reliability
Subjects:
Fault-tolerance
E.
Data
E.5
FILES
Subjects:
Backup/recovery
General Terms:
Design,
Experimentation,
Performance,
Reliability
Keywords:
Adaptation,
Linux,
UNIX,
Windows,
caching,
conflict resolution,
continuous data access,
data staging,
disaster recovery,
disconnected operation,
failure,
high availability,
hoarding,
intermittent networks,
isolation-only transactions,
low-bandwidth networks,
mobile computing,
optimistic replica control,
server replication,
translucent cache management,
weakly connected operation
|