request load. Dynamo allows service owners to customize their
storage system to meet their desired performance, durability and
consistency SLAs by allowing them to tune the parameters N, R,
and W.
The production use of Dynamo for the past year demonstrates that
decentralized techniques can be combined to provide a single
highly-available system. Its success in one of the most
challenging application environments shows that an eventual-
consistent storage system can be a building block for highly-
available applications.
ACKNOWLEDGEMENTS
The authors would like to thank Pat Helland for his contribution
to the initial design of Dynamo. We would also like to thank
Marvin Theimer and Robert van Renesse for their comments.
Finally, we would like to thank our shepherd, Jeff Mogul, for his
detailed comments and inputs while preparing the camera ready
version that vastly improved the quality of the paper.
REFERENCES
[1] Adya, A., Bolosky, W. J., Castro, M., Cermak, G., Chaiken,
R., Douceur, J. R., Howell, J., Lorch, J. R., Theimer, M., and
Wattenhofer, R. P. 2002. Farsite: federated, available, and
reliable storage for an incompletely trusted environment.
SIGOPS Oper. Syst. Rev. 36, SI (Dec. 2002), 1-14.
[2] Bernstein, P.A., and Goodman, N. An algorithm for
concurrency control and recovery in replicated distributed
databases. ACM Trans. on Database Systems, 9(4):596-615,
December 1984
[3] Chang, F., Dean, J., Ghemawat, S., Hsieh, W. C., Wallach,
D. A., Burrows, M., Chandra, T., Fikes, A., and Gruber, R.
E. 2006. Bigtable: a distributed storage system for structured
data. In Proceedings of the 7th Conference on USENIX
Symposium on Operating Systems Design and
Implementation - Volume 7 (Seattle, WA, November 06 - 08,
2006). USENIX Association, Berkeley, CA, 15-15.
[4] Douceur, J. R. and Bolosky, W. J. 2000. Process-based
regulation of low-importance processes. SIGOPS Oper. Syst.
Rev. 34, 2 (Apr. 2000), 26-27.
[5] Fox, A., Gribble, S. D., Chawathe, Y., Brewer, E. A., and
Gauthier, P. 1997. Cluster-based scalable network services.
In Proceedings of the Sixteenth ACM Symposium on
Operating Systems Principles (Saint Malo, France, October
05 - 08, 1997). W. M. Waite, Ed. SOSP '97. ACM Press,
New York, NY, 78-91.
[6] Ghemawat, S., Gobioff, H., and Leung, S. 2003. The Google
file system. In Proceedings of the Nineteenth ACM
Symposium on Operating Systems Principles (Bolton
Landing, NY, USA, October 19 - 22, 2003). SOSP '03. ACM
Press, New York, NY, 29-43.
[7] Gray, J., Helland, P., O'Neil, P., and Shasha, D. 1996. The
dangers of replication and a solution. In Proceedings of the
1996 ACM SIGMOD international Conference on
Management of Data (Montreal, Quebec, Canada, June 04 -
06, 1996). J. Widom, Ed. SIGMOD '96. ACM Press, New
York, NY, 173-182.
[8] Gupta, I., Chandra, T. D., and Goldszmidt, G. S. 2001. On
scalable and efficient distributed failure detectors. In
Proceedings of the Twentieth Annual ACM Symposium on
Principles of Distributed Computing (Newport, Rhode
Island, United States). PODC '01. ACM Press, New York,
NY, 170-179.
[9] Kubiatowicz, J., Bindel, D., Chen, Y., Czerwinski, S., Eaton,
P., Geels, D., Gummadi, R., Rhea, S., Weatherspoon, H.,
Wells, C., and Zhao, B. 2000. OceanStore: an architecture
for global-scale persistent storage. SIGARCH Comput.
Archit. News 28, 5 (Dec. 2000), 190-201.
[10] Karger, D., Lehman, E., Leighton, T., Panigrahy, R., Levine,
M., and Lewin, D. 1997. Consistent hashing and random
trees: distributed caching protocols for relieving hot spots on
the World Wide Web. In Proceedings of the Twenty-Ninth
Annual ACM Symposium on theory of Computing (El Paso,
Texas, United States, May 04 - 06, 1997). STOC '97. ACM
Press, New York, NY, 654-663.
[11]
Lindsay, B.G., et. al., “Notes on Distributed Databases”,
Research Report RJ2571(33471), IBM Research, July 1979
[12] Lamport, L. Time, clocks, and the ordering of events in a
distributed system. ACM Communications, 21(7), pp. 558-
565, 1978.
[13] Merkle, R. A digital signature based on a conventional
encryption function. Proceedings of CRYPTO, pages 369–
378. Springer-Verlag, 1988.
[14] Ramasubramanian, V., and Sirer, E. G. Beehive: O(1)lookup
performance for power-law query distributions in peer-to-
peer overlays. In Proceedings of the 1st Conference on
Symposium on Networked Systems Design and
Implementation, San Francisco, CA, March 29 - 31, 2004.
[15] Reiher, P., Heidemann, J., Ratner, D., Skinner, G., and
Popek, G. 1994. Resolving file conflicts in the Ficus file
system. In Proceedings of the USENIX Summer 1994
Technical Conference on USENIX Summer 1994 Technical
Conference - Volume 1 (Boston, Massachusetts, June 06 - 10,
1994). USENIX Association, Berkeley, CA, 12-12..
[16] Rowstron, A., and Druschel, P. Pastry: Scalable,
decentralized object location and routing for large-scale peer-
to-peer systems. Proceedings of Middleware, pages 329-350,
November, 2001.
[17] Rowstron, A., and Druschel, P. Storage management and
caching in PAST, a large-scale, persistent peer-to-peer
storage utility. Proceedings of Symposium on Operating
Systems Principles, October 2001.
[18] Saito, Y., Frølund, S., Veitch, A., Merchant, A., and Spence,
S. 2004. FAB: building distributed enterprise disk arrays
from commodity components. SIGOPS Oper. Syst. Rev. 38, 5
(Dec. 2004), 48-58.
[19] Satyanarayanan, M., Kistler, J.J., Siegel, E.H. Coda: A
Resilient Distributed File System. IEEE Workshop on
Workstation Operating Systems, Nov. 1987.
[20] Stoica, I., Morris, R., Karger, D., Kaashoek, M. F., and
Balakrishnan, H. 2001. Chord: A scalable peer-to-peer
lookup service for internet applications. In Proceedings of
the 2001 Conference on Applications, Technologies,
Architectures, and Protocols For Computer Communications
(San Diego, California, United States). SIGCOMM '01.
ACM Press, New York, NY, 149-160.
209219