(12) United States Patent
`Menage
`
`USOO6618736B1
`(10) Patent No.:
`US 6,618,736 B1
`(45) Date of Patent:
`Sep. 9, 2003
`
`(54) TEMPLATE-BASED CREATION AND
`ARCHIVAL OF FILE SYSTEMS
`
`(75) Inventor: Paul Menage, Sunnyvale, CA (US)
`(73) Assignee: Ensim Corporation, Sunnyvale, CA
`(US)
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 0 days.
`
`(*) Notice:
`
`5,845,129 A 12/1998 Wendorf et al. ............ 395/726
`5,913,024 A 6/1999 Green et al. ................ 395/186
`5,915,085. A
`6/1999 Koved ........................ 395/186
`5,918,018 A 6/1999 Gooderum et al. .... 395/200.55
`5.937,159 A
`8/1999 Meyers et al. ......... 395/187.01
`: A Rio Wilhelm:
`6,023,721 A 2/2000 Cummings .................. 709/201
`6.065,118 A 5/2000 Bull et al. .................. 713/200
`6,075938 A 38 Eugin et al. ....... 3955. 48
`6,108,759 A
`8/2000 Orcutt et al. ............... 711/173
`6,125,367 A
`9/2000 NA ............................ 707/104
`6,167,520 A 12/2000 Touboul ..................... 713/200
`6,192,389 B1
`2/2001 Ault et al. .................. 709/101
`6,192,512 B1
`2/2001 Chess ............................ 717/5
`6,353,837 B1
`3/2002 Blumenau ................... 707/205
`FOREIGN PATENT DOCUMENTS
`WO 99/39261
`8/1999
`OTHER PUBLICATIONS
`Boehm, B., “Managing Software Productivity and Reuse,”
`IEEE Computer, vol. 32, No. 9, Sep. 1999, 3 pages.
`Corbato, F. J. et al. “An Experimental Timesharing System,”
`References Cited
`Proceedings of the American Federation Of Information
`U.S. PATENT DOCUMENTS
`Processing Societies Spring Joint Computer Conference,
`San Francisco, CA, May 1–3, 1962, pp. 335-344.
`Zg. A ...E. N s al
`5,088026 A * 2/1992 EN al - - - - - - - - - - - - - - - 395/425
`Deutsch, P. and Grant, C.A., “A Flexible Measurement Tool
`5.226160 A 7/1993 Waldron et ir for Software Systems.” Information Processing 71 (Proc. of
`5,263,147 A 11/1993 Francisco et al. ........... 395,42s
`the IFIP Congress), 1971, pp. 320–326.
`5,528,753 A
`6/1996 Fortin
`5,603,020 A 2/1997 Hashimoto et al. ......... 395/616
`(List continued on next page.)
`
`(21) Appl. No.: 09/802,613
`
`Mar. 9, 2001
`(22) Filed:
`(51) Int. Cl." .......................... G06F 17/30; G06F 12/00
`(52) U.S. Cl. ....................... 707/204; 707/202; 707/203;
`707/8
`(58) Field of Search ................................. 707/202, 201,
`707/203, 204, 8
`
`wo
`
`(56)
`
`SE A E. Mimi - - - - - - - - - - - - - - - - - - - - - - - 35
`Y/ -- 12
`CIVlalls . . . . . . . . . . . . . . . . . . . . . . .
`5,706,097 A
`1/1998 Schelling et al. ........... 358/296
`5,706504 A * 1/1998 Atkinson et al. ........... 707/100
`5,715,441. A
`2/1998 Atkinson et al. .............. 707/1
`5,761,477 A 6/1998 Wahbe et al............ 395/406 A
`5,781,550 A
`7/1998 Templin et al. ............. 370/401
`5,809,527 A 9/1998 Cooper et al. .............. 711/133
`5,819,292 A 10/1998 Hitz et al. .....
`... 707/203
`5,828.893 A 10/1998 Weid et al. ....
`... 395/800
`5,838,916 A 11/1998 Domenikos et al. ... 395/200.49
`5,842,002 A 11/1998 Schnurer et al. ............ 395/500
`
`Primary Examiner Frantz Coby
`(74) Attorney, Agent, or Firm-Fenwick & West LLP
`(57)
`ABSTRACT
`File systems are created and archived by providing a set of
`shared Storage units and one or more templates, each tem
`plate including a Set of private Storage units and a corre
`Sponding usage ma
`ponding uSage map.
`
`53 Claims, 12 Drawing Sheets
`
`
`
`115
`YA
`
`
`
`
`
`
`
`
`
`Map
`
`
`
`E.
`
`
`
`Private Storage
`Units
`1001
`data1002
`1003
`
`
`
`Docker EX1004
`Page 1 of 24
`
`

`

`US 6,618,736 B1
`Page 2
`
`OTHER PUBLICATIONS
`Edlali, G., et al., “History-based Access Control for Mobile
`Code,” Fifth ACM Conference on Computer and Commu
`nication Security, Nov. 3-5, 1998, 19 pages.
`Erlingsson, U. and Schneider, F. B., “SASI Enforcement of
`Security Policies: A Retrospective,” Proc. New Security
`Paradigms Workshop, Apr. 2, 1999, pp. 1-17.
`Erlingsson, U. and Schneider, F. B., IRM Enforcement of
`Java Stack Inspection, online, Feb. 19, 2000, retrieved on
`Apr. 2, 2002). Retrieved from the Internet: <URL: tr.cs.cor
`nell.edu/Diens/U12.0/Show
`Page/ncStrl.cornell/
`TR2000-1786.
`Evans, D. and Twyman, A., “Flexible Policy-Directed Code
`Safety,” Proc. of 1999 IEEE Symposium on Security and
`Privacy, Oakland, CA, May 9-12, 1999, pp. 1-14.
`Fraser, T. et al., “Hardening COTS Software with Generic
`Software Wrappers,” Proc. of 1999 IEEE Symposium on
`Security and Privacy, 1999, 15 pages.
`Goldberg, I. et al., “A Secure Environment For Untrusted
`Helper Applications (Confining the Wily Hacker).” Proc. of
`the Sixth USENIX UNIX Security Symposium, San Jose,
`CA, Jul. 1996, 14 pages.
`Goldberg, R.P., “Survey of Virtual Machine Research,”
`IEEE Computer, Jun. 1974, pp. 34-45.
`Pandey, R. and Hashii, B., “Providing Fine-Grained Access
`Control For Mobile Programs Through Binary Editing.”
`Technical Report TR98 08, University of California, Davis,
`CA, 1998, pp. 1-22.
`Ritchie, D. M., “The Evolution of the Unix Time-Sharing
`System.” AT&T Bell Laboratories Technical Journal 63, No.
`6, Part 2, Oct. 1984, (originally presented 1979), 11 pages.
`Saltzer, J., H. and Schroeder, M.D., The Protection of
`Information in Computer Systems, online, 1973, retrieved
`on Apr. 2, 2002). Retrieved from the Internet:<URL:
`cS.Virginia.edu-evans/cS551/Saltzer/>.
`Wahbe, R., et al., “Efficient Software-Based Fault Isola
`tion,” Proc. of the Symposium on Operating System Prin
`ciples, 1993, 14 pages.
`Keshav, S., An Engineering Approach to Computer Net
`working: ATM Networks, the Internet, and the Telephone
`Network, Reading, MA, Addison-Wesley, 1997, pp. vii-xi,
`85-115, 209-355, 395-444.
`Stevens, R. W., UNIX Network Programming vol. 1 Net
`working APIs: Sockets and XTI, Upper Saddle River, NJ,
`Prentice hall, 1998, pp. v-xiv, 29-53, 85-110, 727–760.
`Tanenbaum, A. S. and Woodhull, A. S., Operating Systems:
`Design and Implementation, Upper Saddle River, NJ, Pren
`tice Hall, 1997, pp. vii-xiv, 1-46, 401–454.
`Rubini, A., LINUX Device Drivers, Sebastopol, CA,
`O'Reilly & Associates, Inc., 1998, pp. v-x, 13-40.
`Goyal, P., et al., “A Hierarchical CPU Scheduler for Mul
`timedia Operating Systems,” Proceedings of the Second
`Symposium on Operating Design and Implementations
`(OSDI'96), Seattle, WA, Oct. 1996, 15 pages.
`Laurie, B. and Laurie, P., Apache The Definitive Guide,
`Sebastopol, CA, O’Reilly & Associates, Inc., Feb. 1999, pp.
`v-viii, 43-74.
`Aho, A.V. and Ullman J. D.Principles of Complier Design,
`Reading, MA, 1977, pp. vii-X, 359-362, 519–522.
`Jonsson, J., “Exploring the Importance of Preprocessing
`Operations in Real-Time Multiprocessor Scheduling.” Proc.
`of the IEEE Real-Time Systems Symposium- Work-in
`Progress Session, San Francisco, CA, Dec. 4, 1997, pp.
`31-34.
`
`Rusling, D. A., Processes, online, retrieved on Dec. 7,
`1999). Retrieved from the Internet: <URL: cebaf.gov/-saw/
`linux/tlk-htm/node44.html>.
`Rusling, D.A., Linux Processes, online, retrieved on Dec.
`7, 1999). Retrieved from the Internet: cebaf.gov/-saw/linux/
`tlk-htm/node45.html>.
`Rusling, D. A., Identifiers, online, retrieved on Dec. 7,
`1999). Retrieved from the Internet: cebaf.gov/linux/tlk-htm/
`node46.html>.
`Rusling, D. A., Scheduling, online, retrieved on Dec. 7,
`1999). Retrieved from the Internet: <URL: cebaf.gov/-saw/
`linux/tlk-htm/node47.html>.
`Rusling, D. A., Scheduling in Multiprocessor Systems,
`online, retrieved on Dec. 7, 1999). Retrieved from the
`Internet: cebaf.gov/-Saw/linux/tlk-htm/node48.html>.
`Rusling, D. A., Files, online, retrieved on Dec. 7, 1999).
`Retrieved from the Internet: <URL: cebaf.gov/-saw/linux/
`tlk-htm/node49.html>.
`Plummer, D.C., An EthernetAddress Resolution Protocol
`or-Converting Network Protocol Addresses to 48.bit Eth
`ernetAddress for Transmission on Ethernet Hardware, Nov.
`1982, online, retrieved on Jan. 17, 2000). Retrieved from
`the Internet: <URL: msg.net/kadow/answers/extras/rfc/
`rfc826.txt>.
`Huang, X. W. et al., “The ENTRAPID Protocol Develop
`ment Environment,” Proceedings of IEEE Infocom '99, Mar.
`1999, nine pages.
`Duffield, N.G., et al., “A Flexible Model for Resource
`Management in Virtual Private Networks,” Computer Com
`munication Review Conference, Computer Communication,
`ACM SIGCOMM 99 Conference, Cambridge, MA, Aug.
`30, 1999–Sep. 3, 1999, pp. 95-108.
`Campbell, A. T. and Keshav, S., “Quality of Service in
`Distributed Systems.” Computer Communications 21, 1998,
`pp. 291-293.
`Bach, M. J., The Design of the Unix(R Operating System,
`New Delhi, Prentice-Hall of India, 1989, pp. v.-X, 19-37.
`McDougall, R., et al., Resource Management, Upper Saddle
`River, NJ, Prentice-Hall, 1999, pp. iii-xix., 135-191.
`Risinghani, A., RFC 1624, May 1994, online, retrieved
`Feb. 2, 2000. retrived from the internet: fads.org/rfcs/
`rfc1624.html>.
`Mallory, T and Kullberg, A., RFC 1141, Jan. 1990 online,
`retrieved Feb. 2, 2000. retrieved from the Internet: fad
`S.org/rfcs/rfc1141.html>.
`Egevang, K. and Francis P., RFC 1631, May 1994 online,
`retrieved Feb. 2, 2000. retrieved from the internet: fad
`S.org/rfcs/rfc1631.html>.
`Goyal, P. et al., “Start-time Fair Queuing: A Scheduling
`Algorithm for Integrated Services Packet Switching Net
`works,” Proceedings of ACM SIGCOMM 96, San Fran
`cisco, CA, Aug. 1996, 14 pages.
`Jánosi, T., “Notes on A Hierarchical CPU Scheduler for
`Multimedia Operating Systems by Pawan Goyal, Xingang
`Guo and Harrick Vin,” online, retrieved on May 8, 2000).
`Retrieved fromt the Internet: <URL:http://cs.cornell.edu/
`Info/Courses/Spring-97/CS614/goy.html>.
`Goyal, P., “Packet Scheduling Algorithms for Integrated
`Services Networks, PhD Dissertation, University of Texas,
`Austin, TX, Aug. 1997.
`Pending United States patent application entitled “Providing
`Quality of Service Guarantees to Virtual Hosts,” serial No.
`09/452,286, filing date Nov. 30, 1999.
`
`Docker EX1004
`Page 2 of 24
`
`

`

`US 6,618,736 B1
`Page 3
`
`Pending United States patent application entitled “Selective
`Interception of System Calls,” serial No. 09/499,098, filing
`date Feb. 4, 2000.
`Pending United States patent application entitled “Dynamic
`Scheduling of Task Streams in a Multiple-Resource System
`to Ensure Task Stream Quality of Service,” serial No.
`09/498,450, filing date Feb. 4, 2000.
`Pending United States patent application entitled “Disam
`biguating File Descriptors,” serial No. 09/500,212, filing
`date Feb. 8, 2000.
`Pending United States patent application entitled “Restrict
`ing Communication Between Network Devices on a Com
`mon Network,” serial No. 09/502,155, filing date Feb. 11,
`2OOO.
`Pending United States patent application entitled “Enabling
`a Service Provider to Provide Intranet Services,” serial No.
`09/526,980, filing date Mar. 15, 2000.
`Pending United States patent application entitled “Dynami
`cally Modifying the Resources of a Virtual Server,” serial
`No. 09/569,371, filing date May 11, 2000.
`Pending United States patent application entitled "Regulat
`ing File Access Rates According to File Type,” serial No.
`09/572,672, filing date May 16, 2000.
`Pending United States patent application entitled “Modify
`ing Internal Components of a Running Operating System,”
`serial No. 09/576,393, filing date May 22, 2000.
`Pending United States patent application entitled "ASSoci
`ating Identifiers With Virtual Processes,” serial No. 09/611,
`877, filing date Jul. 7, 2000.
`Pending United States patent application entitled “Fairly
`Partitioning Resources While Limiting the Maximum Fair
`Share,” serial No. 09/633,575, filing date Aug. 7, 2000.
`Pending United States patent application entitled “Intercept
`ing I/O Multiplexing Operation Involving Cross Domain
`File Descriptor Sets,” serial No. 09/664,914, filing date Sep.
`18, 2000.
`
`Pending United States patent application entitled “Virtual
`izing Port Addresses for Non-Conflicting Use by Multiple
`Virtual Processes,” serial No. 09/679,396, filing date Oct. 3,
`2OOO.
`Pending United States patent application entitled “Intercept
`ing Calls to Non-Local Procedures,” serial No. 09/687,031,
`filing date Oct. 12, 2000.
`Pending United States patent application entitled “Virtual
`izing Super-User Privileges for Multiple Virtual Processes.”
`serial No. 09/747,687, filing date Dec. 22, 2000.
`Pending United States patent application entitled “Virtual
`izing Resource Ownership For Multiple Virtual Processes.”
`serial No. 09/747,664, filing date Dec. 22, 2000.
`Brown, K. et al., SnapMirrr and SnapRestore: Advances in
`Snapshot Technology, online, retrieved on Jul. 2, 2001).
`Retrieved from the Internet: <URL:http://www.netapp.com/
`tech library/3043.print>.
`HOWTO: Multi Disk system Tuning: Technologies, on
`line, retrieved Jul. 2, 2001). Retrieved from the Internet:
`linux.com/howto/Multi-Disk-HOWTO-6.html?printable=
`yeS>.
`Almesberger, W., The truth about IFS, Mar. 3, 1998, on
`line, retrieved Jun. 6, 2001). Retrieved from the Internet:
`epfl.ch/-almesber/ifs.html>.
`Hendricks, D., The Translucent File Service, online, re
`trieved Jun. 6, 2001). Retrieved from the Internet: Sun.com/
`Smcc/Solaris-migration/docs/postScript/tfs.pS>.
`
`* cited by examiner
`
`Docker EX1004
`Page 3 of 24
`
`

`

`U.S. Patent
`
`Sep. 9, 2003
`
`Sheet 1 of 12
`
`US 6,618,736 B1
`
`
`
`soves'ssancov
`
`?uepueosed
`
`€ SS3OOJA
`
`Docker EX1004
`Page 4 of 24
`
`

`

`U.S. Patent
`U.S. Patent
`
`Sep. 9, 2003
`Sep. 9, 2003
`
`Sheet 2 of 12
`Sheet 2 of 12
`
`US 6,618,736 B1
`US 6,618,736 B1
`
`
`
`ic
`
`FIG.2
`
`©
`N
`-
`®
`
`Q|3 Ess +
`
`o
`&
`Ee
`£
`Oo
`|2
`2
`2
`©
`o
`2)
`“a
`D
`>
`>
`>
`ge
`1”
`”
`o
`o
`|2
`@
`@
`a
`iL
`iL
`
`
`
`Docker EX1004
`Page 5 of 24
`
`Docker EX1004
`Page 5 of 24
`
`

`

`U.S. Patent
`U.S. Patent
`
`Sep. 9, 2003
`Sep. 9, 2003
`
`Sheet 3 of 12
`Sheet 3 of 12
`
`US 6,618,736 B1
`US 6,618,736 B1
`
`
`
`LOL
`
`renui,
`
`SS800!q
`
`L#
`
`|(©)€00)|)zoor||)4001|@BEIO}S
`
`aBelojsgpoueys
`SBA
`
`ao1negqabeicjs
`
`eeemeemeeeeey
`
`Docker EX 1004
`Page 6 of 24
`
`Docker EX1004
`Page 6 of 24
`
`
`
`
`

`

`U.S. Patent
`
`Sep. 9, 2003
`
`Sheet 4 of 12
`
`US 6,618,736 B1
`
`90€N®
`
` jeDwayshs|eset_zas09wasp(9972
`e6es,
`
`2 w
`
`i
`
`LOL
`
`
`
`SS900!q|ENLIA
`
`
`
`aBelojgayeAuid
`
`syun
`
`£001
`
`
`
` ZOO}leyep|LOOL
`
`vySis
`
`Bunepdydewebesn
`
`ainpoy
`
`sJaddeipj
`
`BunwaawunaBesojg
`
`einpoyy
`
`Docker EX 1004
`Page 7 of 24
`
`Docker EX1004
`Page 7 of 24
`
`
`
`
`
`

`

`U.S. Patent
`
`Sep. 9, 2003
`
`Sheet 5 of 12
`
`US 6,618,736 B1
`
`
`
`|eO uue|SÁS
`
`Jedde.JNA
`
`
`709
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Docker EX1004
`Page 8 of 24
`
`

`

`U.S. Patent
`
`Sep. 9, 2003
`
`Sheet 6 of 12
`
`US 6,618,736 B1
`
`
`
`|eO uue?SÁS
`
`Jedde.JNA
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Docker EX1004
`Page 9 of 24
`
`

`

`U.S. Patent
`
`Sep. 9, 2003
`
`Sheet 7 of 12
`
`US 6,618,736 B1
`
`
`
`
`
`|- – – – + – – – –)
`
`z# ºleiduel ||
`
`|
`
`
`
`Docker EX1004
`Page 10 of 24
`
`

`

`U.S. Patent
`U.S. Patent
`
`Sep. 9, 2003
`Sep. 9, 2003
`
`Sheet 8 of 12
`Sheet 8 of 12
`
`US 6,618,736 B1
`US 6,618,736 B1
`
`
`
`(onjoy)z#Se\dws]
`
`
`
`@HeIOISOJAI
`
`c#SHUN
`
`
`
`BHe1O}SSEAL
`
`L#Sun
`
`
`
`abelojspareys
`
`sun
`
`8‘Sls
`
`—eeeeeEEeSJ
`
`J
`
`LOL
`
`
`
`SS800/qJENUIA
`
`
`
`
`
`
`
`
`
`Docker EX 1004
`Page 11 of 24
`
`Docker EX1004
`Page 11 of 24
`
`
`
`
`

`

`U.S. Patent
`U.S. Patent
`
`Sep. 9, 2003
`Sep. 9, 2003
`
`Sheet 9 of 12
`Sheet 9 of 12
`
`US 6,618,736 B1
`US 6,618,736 B1
`
`
`
`
`
`+6BINPoW\#oe|de|OLE|BAIyUY
`
`(dny9eg)
`
`aBelojgdnyoeg
`
`
`
`
`
`Z0abelojgpaieys
`
`a01A0q
`
`sun
`
`6‘Sis
`
`Docker EX 1004
`Page 12 of 24
`
`0
`0
`
`C
`Z
`
`L#oyejdwe)
`
`(BAY)
`
`
`
`aBelolspaieys
`
`sur)
`
`Oo
`
`©o
`
`a
`
`C#aye|dwe]
`
`(9AnoY)
`
`
`
`SS800/qJENNI
`
`
`
`SSO00Jq[ENA
`
`LOL
`
`
`
`
`
`
`
`
`
`
`
`Docker EX1004
`Page 12 of 24
`
`
`
`
`
`

`

`U.S. Patent
`
`Sep. 9, 2003
`
`Sheet 10 of 12
`
`US 6,618,736 B1
`
`O
`
`w so
`
`
`
`
`
`
`
`|peldoo ?ON|
`
`| peldoo ?oN |
`
`|
`
`| peldoo ?oN |
`
`Docker EX1004
`Page 13 of 24
`
`

`

`U.S. Patent
`
`Sep. 9, 2003
`
`Sheet 11 of 12
`
`US 6,618,736 B1
`
`#706
`
`Z06
`
`(
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Docker EX1004
`Page 14 of 24
`
`

`

`U.S. Patent
`U.S. Patent
`
`Sep. 9, 2003
`Sep. 9, 2003
`
`Sheet 12 of 12
`Sheet 12 of 12
`
`US 6,618,736 B1
`US 6,618,736 B1
`
`LOLLOLLOL
`
`LOL
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`OLEOLEOLe
`PHSSOD01g|eENWIA||e#SSeD0/g|ENUIA
`
`
`
`ayeAlid CHSS9DOl]
`
`[ENLIA
`
`L#SS800Jq|ENHIA
`
`Ole
`
`ayejdwa|ajeAud
`
`
`aye|dwa]ajeAud
`aye|dwa)
`
`ayeydlue]a}JeAud
`
`Ole
`
`
`
` qayejdwe]aqNd
`
`OLE
`
`a}e\d
`
`\/
`
`Vweoqnd
`
`cOE—~¥|aBesoigpaleus
`
`sun
`
`
`
`
`
`cb‘Sis
`
`Docker EX 1004
`Page 15 of 24
`
`Docker EX1004
`Page 15 of 24
`
`
`
`
`
`
`
`
`
`

`

`1
`TEMPLATE-BASED CREATION AND
`ARCHIVAL OF FILE SYSTEMS
`
`US 6,618,736 B1
`
`2
`Unfortunately, providing a separate physical device for
`Storing the file System of each Virtual private Server would
`be expensive and inefficient. Accordingly, it would be desir
`able to store the file systems of multiple virtual private
`Servers within the Same physical device or comparatively
`Small Set of devices.
`ServerXchange(E), a product of Ensim Corporation, pro
`vides multiple Virtual processes, Such as Virtual private
`Servers, with Separate file Systems. Each file System is Stored
`in a linear Set of equal-sized Storage units within the same
`physical Storage device.
`This approach Still presents a number of difficulties,
`however. For example, an initial file System, including
`Standard applications, utilities, databases, etc., must be
`duplicated for each Virtual private Server. Such a duplication
`process results in copying large amounts of data from one
`disk location to another, consuming Significant amounts of
`time and placing Substantial memory and disk load on the
`physical Server. Such extensive duplication also results in
`wasted Storage Space, Since all or part of the resulting file
`Systems are identical.
`The above approach also presents difficulties when
`archiving (e.g., backing up) the file Systems. For example,
`Since the file Systems are being constantly changed by
`activity within the virtual private Servers, it is impossible to
`obtain a backup that is a "Snapshot' of the files Systems at
`a particular time. By the time the backup proceSS is complete
`(which may take several hours), the file systems will have
`changed Substantially. In addition, backing up Such file
`Systems may result in a Substantial waste of time and Storage
`Space due to the archival of duplicate data for each file
`System.
`Accordingly, What is needed is a technique for creating
`Separate file Systems for a plurality of virtual private Servers
`that does not require extensive copying or wasted Storage
`Space. What is also needed is a technique for efficiently
`backing up a file System of a virtual private Server in which
`a Snapshot of the file System may be obtained at a particular
`point in time.
`SUMMARY OF THE INVENTION
`The present invention relates to Systems and methods for
`file System creation and archival. In one embodiment, first
`and Second Sets of Storage units are provided, each Storage
`unit of the first Set corresponding to a storage unit of the
`Second Set. The Sets of Storage units may be contained within
`a single Storage device or within a comparatively Small Set
`of devices.
`In addition, a usage map is provided for indicating which
`Storage units of the Second Set contain valid data. The usage
`map is initially reset or “initialized” to indicate that none of
`the Storage units of the Second Set contain valid data.
`An attempt to write a data item to a storage unit of the first
`Set is then intercepted. Rather than writing the data item to
`the Storage unit of the first Set, however, the data item is
`written to the corresponding Storage unit of the Second Set.
`Thereafter, an indication is Stored in the usage map that the
`corresponding Storage unit of the Second Set contains valid
`data.
`Additionally, an attempt to read a data item from a storage
`unit of the first Set is intercepted. If the usage map indicates
`that the corresponding Storage unit of the Second Set contains
`valid data, the data item is read from the corresponding
`Storage unit of the Second Set. If, however, the usage map
`indicates that the corresponding Storage unit of the Second
`Set does not contain valid data, the data item is read from the
`Specified Storage unit of the first Set.
`
`BACKGROUND
`1. Field of the Invention
`The present invention relates generally to computer oper
`ating Systems and, more particularly, to techniques for
`template-based creation and archival of file Systems.
`2. Description of the Background Art
`With the popularity and success of the Internet, server
`technologies are of great commercial importance today. An
`individual Server application typically executes on a Single
`physical host computer, Servicing client requests. However,
`providing a unique physical host for each Server application
`is expensive and inefficient.
`For example, commercial hosting Services are often pro
`vided by an Internet Service Provider (ISP), which generally
`provides a separate physical host computer for each cus
`tomer on which to execute a Server application. However, a
`customer purchasing hosting Services will often neither
`require nor be amenable to paying for use of an entire host
`computer. In general, an individual customer will only
`require a fraction of the processing power, Storage, and other
`resources of a host computer.
`Accordingly, hosting multiple Server applications on a
`Single physical computer would be desirable. In order to be
`commercially viable, however, every Server application
`would need to be isolated from every other Server applica
`tion running on the same physical host. Clearly, it would be
`unacceptable to customers of an ISP to purchase hosting
`Services, only to have another Server application program
`(perhaps belonging to a competitor) access the customer's
`data and client requests. Thus, each Server application pro
`gram needs to be isolated, receiving requests only from its
`own clients, transmitting data only to its own clients, and
`being prevented from accessing data associated with other
`Server applications.
`Furthermore, it is desirable to allocate varying Specific
`levels of System resources to different Server applications,
`depending upon the needs of, and amounts paid by, the
`various customers of the ISP. In effect, each server applica
`tion needs to be a "virtual private Server,” Simulating a
`Server application executing on a dedicated physical host
`computer.
`Such functionality is unavailable on traditional server
`technology because, rather than comprising a single, discrete
`process, a virtual private Server must include a plurality of
`Seemingly unrelated processes, each performing various
`elements of the sum total of the functionality required by the
`customer. Because each virtual private Server includes a
`plurality of processes, it has been impossible using tradi
`tional Server technology for an ISP to isolate the processes
`asSociated with one virtual private Server from those pro
`ceSSes associated with other virtual private Servers.
`Another difficulty in implementing multiple virtual pri
`Vate Servers within a Single physical host involves providing
`each Server with a separate file System. A file System is an
`organized accumulation of data within one or more physi
`cal. Storage devices, Such as a hard disk drive or RAID
`(redundant array of inexpensive disks). The data is typically
`organized into “files,” Such as word processing documents,
`Spreadsheets, executable programs, and the like. The files
`are Stored within a plurality of “storage units of the Storage
`device, Sometimes referred to as "disk blocks” or “allocation
`units.”
`
`15
`
`25
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`Docker EX1004
`Page 16 of 24
`
`

`

`US 6,618,736 B1
`
`3
`Each Set of private Storage units and corresponding usage
`map are referred to herein as a “template.” In accordance
`with the present invention, file Systems are represented as
`"Stacks of templates, in which all data is written to an
`“active” template at the “top” of the stack, and all data is
`read from the topmost template in the Stack for which an
`indication of valid data is found in the corresponding usage
`map.
`Private Storage units of a template that is not currently the
`active template may be backed up to a storage device in
`order to obtain a "Snapshot' of the changes to an initial file
`System at a particular point in time.
`The features and advantages described in this Summary
`and the following detailed description are not all-inclusive,
`and particularly, many additional features and advantages
`will be apparent to one of ordinary skill in the art in view of
`the drawings, specification, and claims hereof. Moreover, it
`should be noted that the language used in the Specification
`has been principally Selected for readability and instruc
`tional purposes, and may not have been Selected to delineate
`or circumscribe the inventive Subject matter, resort to the
`claims being necessary to determine Such inventive Subject
`matter.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`FIG. 1 is a block diagram of a System for associating
`identifiers with Virtual processes;
`FIG. 2 is a block diagram of a storage device including the
`file Systems of multiple virtual processes,
`FIG. 3 is a block diagram of a Storage device including a
`Set of shared Storage units, a set of private Storage units, and
`a usage map.
`FIGS. 4-6 are block diagrams of a system for creating and
`managing a file System;
`FIG. 7 is a block diagram of templates corresponding to
`different Virtual processes;
`FIG. 8 is a block diagram of a stack of templates;
`FIG. 9 is a block diagram an archival system;
`FIG. 10 is a block diagram illustrating a process of
`merging two templates,
`FIG. 11 is a block diagram of an archival system; and
`FIG. 12 is a block diagram of private and public tem
`plates.
`The Figures depict embodiments of the present invention
`for purposes of illustration only. Those skilled in the art will
`readily recognize from the following discussion that alter
`native embodiments of the illustrated structures and methods
`may be employed without departing from the principles of
`the invention described herein.
`
`DETAILED DESCRIPTION OF THE
`PREFERRED EMBODIMENTS
`The present invention relates to file System creation and
`archival, particularly in the context of multiple virtual pri
`Vate Servers running on a single physical host machine.
`AS previously noted, implementing a virtual private
`Server using traditional Server technologies has been impos
`Sible because, rather than comprising a single, discrete
`process, a virtual private Server must include a plurality of
`Seemingly unrelated processes, each performing various
`elements of the Sum total of the functionality required by a
`customer. A virtual private Server is an example of a “virtual
`process,” which is a set of processes isolated partially or
`totally from other processes of the System.
`
`4
`Accordingly, one aspect of the present invention relates to
`a System and method for associating identifiers with Virtual
`processes (e.g., virtual private Servers) as described imme
`diately below. Thereafter, a system and method are
`described for file System creation and archival in the context
`of multiple virtual private Servers.
`I. Associating Identifiers With Virtual Processes
`FIG. 1 is a high-level schematic block diagram of a
`system 100 for associating identifiers with virtual processes
`101 according to one embodiment of the present invention.
`A computer memory 102 includes a user address space 103
`and an operating System address Space 105. Multiple ini
`tialization processes 107 execute in the user address Space
`103. Although FIG. 1 illustrates only two initialization
`processes 107 executing in the user address space 103, those
`skilled in the art will understand that more than two initial
`ization processes 107 can execute Simultaneously within a
`given computer memory 102.
`Also executing in the user address Space 103 are one or
`more descendent processes 108 originating from the initial
`ization processes 107. A descendent process 108 is a child
`process of an initialization proceSS 107, or a child proceSS
`thereof, extended to any number of generations of Subse
`quent child processes. Although FIG. 1 illustrates only two
`descendent processes 108 for each initialization process 107,
`fewer or more than two descendent processes 108 per
`initialization process 107 can execute simultaneously within
`a given computer memory 102.
`In one embodiment, a virtual process table 127 or other
`Suitable data Structure for Storing associations 129 between
`executing processes 107,108 and virtual processes 101 is
`inserted into the operating System 117. Of course, other data
`Structures may be used to Store associations 129, one
`example of which is a linked list.
`In various embodiments, the virtual process table 127 (or
`other data structure) is dynamically loaded into the operating
`system kernel 109 while the kernel 109 is active. In another
`embodiment, the virtual process table 127 is stored in the
`user address Space 103. The maintenance and use of the
`virtual process table 127 is discussed in detail below.
`Those skilled in the art will recognize that a virtual
`process 101 is not an actual process that executes in the
`computer memory 102. Instead, the term “virtual process”
`describes a collection of associated functionality. For
`example, a virtual proceSS 101 is not actually a discrete
`process, but instead, comprises a plurality of actual pro
`cesses that together provide the desired functionality,
`thereby simulating the existence of a Single application
`executing on a dedicated physical host. Each actual process
`that performs. Some of the functionality of the application is
`a part of the virtual process 101. As shown in FIG. 1, for
`example, initialization proceSS 1 and descendent processes 1
`and 2 together comprise one virtual process 101, whereas
`initialization process 2 and descendent processes 3 and 4
`together comprise another.
`In order to associate a specific identifier with each actual
`process that is a member of a virtual proceSS 101, a Separate
`system initialization process 107 is started for each virtual
`process 101. Normally, each process executing on a multi
`tasking operating System Such as UNIXE) is descended from
`a single System initialization process 107 that is Started when
`the operating system 117 is booted. However, the system
`100 uses techniques described in detail below to start a
`separate system initialization process 107 for each virtual
`process 101. When each system initialization process 107 is
`
`15
`
`25
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`Docker EX1004
`Page 17 of 24
`
`

`

`S
`Started, an association 129 between the System initialization
`process 107 and the virtual process 101 is stored in the
`virtual process table 127. All additional processes that are
`descended from a given initialization process are thus iden
`tified with the virtual process 101 associated with that
`initialization process.
`In one embodiment, rather than Starting a separate System
`initialization process 107 for each virtual process 101, a
`custom initialization proceSS is started. In this embodiment,
`all processes that are a members of a specific virtual proceSS
`101 are descended from the associated custom initialization
`process, and are associated with the virtual proceSS 101 with
`which the custom initialization proceSS is associated. The
`exact functionality included in the custom initialization
`proceSS is a design choice that can be made by, for example,
`a System administrator.
`System calls 115 that generate child processes (e.g., the
`UNIX(R) fork() and clone() functions) are intercepted so that
`the child processes can be associated with the virtual proceSS
`101 with which the parent process is associated. In one
`embodiment, a System call wrapper 111 is used to intercept
`system calls 115, which is dynamically loaded into the
`operating system kernel 109 while the kernel 109 is active.
`In another embodiment, the System call wrapper 111 is
`loaded into the user address space 103. Of course, various
`other techniques may be used to intercept the System calls
`115, which are well known in the art.
`Pointers 114 to the system calls 115 are located in an
`operating system call vector table 113. Those skilled in the
`art will recognize that the term "system call vector table,” as
`used herein, denotes an area in the operating System address
`space 105 in which addresses of system calls are stored. In
`the UNIXOR operating System, this part of the operating
`system is called the “system call vector table,” and that term
`is used throughout this description. Other operating Systems
`employ different terminology to denote the same or similar
`System components. The pointers 114, themselves, are
`Sometimes referred to as "system call