The Zebra striped network file system

ABSTRACT

Zebra is a network file system that increases throughput by striping the file data across multiple servers. Rather than striping each file separately, Zebra forms all the new data from each client into a single stream, which it then stripes using an approach similar to a log-structured file system. This provides high performance for writes of small files as well as for reads and writes of large files. Zebra also writes parity information in each stripe in the style of RAID disk arrays; this increases storage costs slightly, but allows the system to continue operation while a single storage server is unavailable. A prototype implementation of Zebra, built in the Sprite operating system, provides 4–5 times the throughput of the standard Sprite file system or NFS for large files and a 15–300% improvement for writing small files.

REFERENCES

• 1: Thomas E. Anderson , David E. Culler , David A. Patterson , and the NOW team, A Case for NOW (Networks of Workstations), IEEE Micro, v.15 n.1, p.54-64, February 1995 [doi>10.1109/40.342018]
• 2: BAKER, M. AND SULLIVAN, M. 1992. The Recovery Box: Using fast recovery to provide high availability in the UNIX environment. In Proceedings of the Summer 1992 USENIX Conference (June). USENIX Assoc., Berkeley, Calif., 31-43.
• 3: Mary Baker , Satoshi Asami , Etienne Deprit , John Ouseterhout , Margo Seltzer, Non-volatile memory for fast, reliable file systems, Proceedings of the fifth international conference on Architectural support for programming languages and operating systems, p.10-22, October 12-15, 1992, Boston, Massachusetts, United States
• 4: Mary G. Baker , John H. Hartman , Michael D. Kupfer , Ken W. Shirriff , John K. Ousterhout, Measurements of a distributed file system, ACM SIGOPS Operating Systems Review, v.25 n.5, p.198-212, Oct. 1991
• 5: 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]
• 6: Andrew D. Birrell , Roy Levin , Michael D. Schroeder , Roger M. Needham, Grapevine: an exercise in distributed computing, Communications of the ACM, v.25 n.4, p.260-274, April 1982 [doi>10.1145/358468.358487]
• 7: CABRE~, L.-F. AND LONG, D. D. E. 1991. Swift: Using distributed disk striping to provide high I/O data rates. Comput. Syst. 4, 4 (Fall), 405-436.
• 8: Pei Cao , Swee Boon Lim , Shivakumar Venkataraman , John Wilkes, The TickerTAIP parallel RAID architecture, Proceedings of the 20th annual international symposium on Computer architecture, p.52-63, May 16-19, 1993, San Diego, California, United States
• 9: Peter M. Chen , David A. Patterson, Maximizing performance in a striped disk array, Proceedings of the 17th annual international symposium on Computer Architecture, p.322-331, May 28-31, 1990, Seattle, Washington, United States
• 10: CHUTANI, S., ANDERSON, O. T., KAZAR, M. L., LEVERETT, B. W., MASON, W. A.~ AND SIDEBOTHAM, R. N. 1992. The Episode Ffie System. In Proceedtngs of the Winter 1992 USENIX Conference (Jan.). USENIX Assoc, Berkeley, Calif., 43-60.
• 11: DIBBLE, P. C., SCOTT, M. L., AND ELLIS, C. S. 1988. Bridge: A high-performance file system for parallel processors. In Proceedings of the 8th International Conference on D~str~buted Computing Systems (ICDCS). IEEE. New York, 154-161.
• 12: A. L. Drapeau , K. W. Shirriff , J. H. Hartman , E. L. Miller , S. Seshan , R. H. Katz , K. Lutz , D. A. Patterson , E. K. Lee , P. M. Chen , G. A. Gibson, RAID-II: a high-bandwidth network file server, Proceedings of the 21ST annual international symposium on Computer architecture, p.234-244, April 18-21, 1994, Chicago, Illinois, United States
• 13: R. A. Floyd , C. Schlatter Ellis, Directory Reference Patterns in Hierarchical File Systems, IEEE Transactions on Knowledge and Data Engineering, v.1 n.2, p.238-247, June 1989 [doi>10.1109/69.87963]
• 14: FREEH, V. W., LOWENTHAL, D. K., AND ANDREWS, G. R. 1994. Distributed filaments: Efficient fine-grain parallehsm on a cluster of workstations. In Proceedings of the 1st USENIX Symposium on Operating' Systems Design and Implementation (OSDI) (Nov.). USENIX Assoc., Berkeley, Calif., 201-213.
• 15: GuY, R. G., HEIDEMANN, J. S., MAK, W., PAGE, T. W., JR., POPEK, G. J., AND ROTHMEIER, D. 1990. Implementation of the Ficus replicated file system. In Proceedings of the Summer 1990 USENIX Conference (Anaheim, Calif., June). USENIX Assoc., Berkeley, Calif., 63-71.
• 16: R. Hagmann, Reimplementing the Cedar file system using logging and group commit, ACM SIGOPS Operating Systems Review, v.21 n.5, p.155-162, Nov. 1987
• 17: HARTMAN, J. H. AND OUSTERHOUT, J. K. 1993. Letter to the editor. ACM SIGOPS Oper. Syst. Rev. 27, i (Jan.), 7-10.
• 18: HISGEN, A., BIRRELL, A., MANN, T., SCHROEPER, M., AND SWART, G. 1989. Availability and consistency tradeoffs in the Echo distributed file system. In Proceedings of the 2nd Workshop on Workstation Operating Systems (Sept.). IEEE, New York, 49-54.
• 19: 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]
• 20: Barbara Liskov , Sanjay Ghemawat , Robert Gruber , Paul Johnson , Liuba Shrira, Replication in the harp file system, ACM SIGOPS Operating Systems Review, v.25 n.5, p.226-238, Oct. 1991
• 21: Darrell D. E. Long , Bruce R. Montague , Luis-Felipe Cabrera, Swift/RAID: a distributed RAID system, Computing Systems, v.7 n.3, p.333-359, Summer 1994
• 22: Lo VERSO, S. J., ISMAN, M., NANOPOULOS, A., NESHEIM, W., MILNE, E. D., AND WHEELER, R. 1993. sfs: A parallel file system for the CM-5. In Proceedings of the Summer 1993 USENIX Conference (Cincinnati, Ohio, June). USENIX Assoc., Berkeley, Calif., 291-305.
• 23: Marshall K. McKusick , William N. Joy , Samuel J. Leffler , Robert S. Fabry, A fast file system for UNIX, ACM Transactions on Computer Systems (TOCS), v.2 n.3, p.181-197, Aug. 1984 [doi>10.1145/989.990]
• 24: McVoY, L. W. AND KLEIMAN, S. R. 1991. Extent-like performance from a UNIX file system. In Proceedings of the Winter 1991 USENIX Conference (Dallas, Tex., Jan.). USENIX Assoc., Berkeley, Calif., 33-43.
• 25: Michael N. Nelson , Brent B. Welch , John K. Ousterhout, Caching in the Sprite network file system, ACM Transactions on Computer Systems (TOCS), v.6 n.1, p.134-154, Feb. 1988 [doi>10.1145/35037.42183]
• 26: OUSTERHOUT, J. 1995. A critique of Seltzer's 1993 USENIX paper. Available as http://www.smli.com/~ ouster/seltzer93.html.
• 27: John K. Ousterhout , Andrew R. Cherenson , Frederick Douglis , Michael N. Nelson , Brent B. Welch, The Sprite Network Operating System, Computer, v.21 n.2, p.23-36, February 1988 [doi>10.1109/2.16]
• 28: David A. Patterson , Garth Gibson , Randy H. Katz, A case for redundant arrays of inexpensive disks (RAID), Proceedings of the 1988 ACM SIGMOD international conference on Management of data, p.109-116, June 01-03, 1988, Chicago, Illinois, United States
• 29: PIERCE, P. 1989. A concurrent file system for a highly parallel mass storage subsystem. In Proceedings of the 4th Conference on Hypercubes (Monterey, Calif., Mar.). ACM, New York, 155-160.
• 30: Mendel Rosenblum , John K. Ousterhout, The design and implementation of a log-structured file system, ACM SIGOPS Operating Systems Review, v.25 n.5, p.1-15, Oct. 1991
• 31: 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]
• 32: SCHLOSS, G. A. AND STONEBRAKER, M. 1990. Highly redundant management of distributed data. In Proceedings of the IEEE Workshop on the Management of Replicated Data (Nov.). IEEE, New York, 91-95.
• 33: SELTZER, M, BOSTIC, K., McKusICK, M. K., AND STAELIN, C. 1993. An implementation of a log~structured file system for UNIX In Proceedings of the W~nter 1993 USENIX Conference (San Diego, Calif., Jan.). USENIX Assoc., Berkeley, Calif., 307-326.
• 34: SELTZER, M., SMITH, K. A., BALAKRISHNAN, H., CHANG, J., MCMAINS~ S., AND PADMANABHAN, V. 1995. File system logging versus clustering: A performance comparison. In Proceedings of the W~nter 1995 USENIX Conference (Jan.). USENIX Assoc., Berkeley, Calif., 249-264.
• 35: SHELTZER, A. B., LINDELL, R., AND POPEK, G. J. 1986. Name service locality and cache design in a distributed operating system. In Proceedings of the 6th International Conference on Distr~buted Computing Systems (ICDCS) (May). IEEE, New York, 515-522.
• 36: SHIRRIFF, K. AND OUSTERHOUT, J. 1992. A trace-driven analysis of name and attribute caching in a distributed file system In Proceedings of the W~nter 1992 USENIX Conference (Jan.). USENIX Assoc, Berkeley, Calif., 315-331.
• 37: SIEGEL, A., BIRMAN, K., AND MARZULLO, K. 1990. Deceit: A flexible distributed file system. In Proceedings of the Summer 1990 USENIX Conference (Anaheim, Calif., June). USENIX Assoc., Berkeley, Calif., 51-61.
• 38: 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
• 39: WILKES, J. 1992. DataMesh research project, phase 1. In Proceedings of the USENIX Fde Systems Workshop (May). USENIX Assoc, Berkeley, Calif., 63 69.

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.3 File Systems Management
          Subjects: File organization

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.2 Storage Management
          Subjects: Allocation/deallocation strategies; Secondary storage
      D.4.3 File Systems Management
          Subjects: Distributed file systems; Access methods
      D.4.5 Reliability
          Subjects: Fault-tolerance
      D.4.7 Organization and Design
          Subjects: Distributed systems
      D.4.8 Performance
          Subjects: Measurements

  E. Data
  E.5 FILES
      Subjects: Organization/structure

General Terms:
Design, Measurement, Performance, Reliability

Keywords:
RAID, log-based striping, log-structured file system, parity computation