IN THE FJNITED STATES PATENT AND TRAEMARK OFFICE
`REQUEST FOR FILING
`(RULE 53(b)(1))
`
`~
`
`'
`
`Page 1 of4
`
`_y g
`
`
`
`I-‘OR CIPs)
`
`Group Art Unit:
`
`2776
`
`Examiner:
`
`Homere, J.
`
`“V
`
`‘
`
`’
`
`For Design or Utility Applications
`
`Rule 53(b)i1) PATENT APPLICATION:
`D
`Continuation
`
`))
`
`application under 37 CFR 1.53(b)(1)
`
`E
`
`Divisional
`
`)
`
`of pending prior application of
`
`FARBER et al.
`Inventor(s):
`Parent Appln. No.:
`
`I
`PM 252465
`08
`I
`flflmg
`Series Code 1)
`(Our Deposit Account No. 03-3975
`October 24, 1997
`Parent Filed:
`(Our Order No.
`7018/252465
`April
`, 1999
`This Case Filed:
`Title:
`IDENTIFYING DATA IN A DATA PROCESSING SYSTEM
`C# I @ M#
`
`960,079
`13 Serial No.
`
`Atty. Dkt.
`
`cum; Ref
`
`Asst. Commissioner of Patents
`Washington, DC 20231
`
`Sir:
`
`Date:
`
`'
`
`April 1, 1999
`
`(Parent Matter No.
`
`243063
`
`)
`
`To effect the above-requested filing today:
`
`1.
`
`Attached is a copy (which must be filed) of this application, including:
`
`>14 Abstract
`Q Specification and claims (% pages) (must be attached)
`>14 Drawings (_rr_m_st be attached if originally filed): 2_4 sheet(s)/set: XI 1 set informal;
`E] Formal of size
`D A4
`
`Always X one box, only:
`X} Signed. declaration or oath as originally filed in prior application attached
`@ declaration or fee is enclosed; therefore, this is a filing under Rule 53(f).
`
`1A.
`(1)
`(2)
`
`I: 11"
`
`2.
`
`I:
`
`This application is hereby filed by e§§ than a I of the inyentors named in the prior application. Petition is
`V hereby made requesting deletion as inventor(s) of the following who is/are n_ot inventor(s) of the
`invention being claimed in this application:
`
`S9.“!’~"€v°.-"
`
`—-I-03O1J>|\)
`
`3.
`
`The entire disclosure of the prior application is considered as being part of the disclosure of the accompanying
`application and is hereby incorporated therein» by reference thereto.
`'
`
`PAT<108 1 2198
`
`GOOG-1016-Page 1 of 126
`
`GOOG-1016-Page 1 of 126
`
`

`
`4.
`
`4.
`
`5.
`
`El
`
`(1)
`(2)
`(3)
`
`Priority is claimed under 35 U.S.C. 119/365 based on filing in
`
`Applieetien No.
`
`Filing Date
`
`(4)
`(5)
`(5)
`
`(country)
`Aooiicatbm;
`
`a. E
`b. E)
`
`E
`
`Prior application is assigned to
`
`(No.) Certified copy/copies attached.
`Certified copy/copies previously filed on
`U.S. Application No.
`I
`1} serial no.
`series code 0
`c. E Certified copy/copies filed during international stage of PCTI
`(a) (:1
`Domestic priority is claimed from PCTI
`/
`_
`(b) [:1
`Benefit is claimed of Provisional Application No.
`
`kiNETech inc.
`
`, filed on
`
`/
`
`filed
`
`60/
`
`, filed
`
`Page 2 of4
`
`of
`
`Filing Date
`
`in
`
`by assignment recorded
`
`June 23, 1995
`(Date)
`Attached is the following number of Assignments (including original and all later successive ones by
`different assignors):
`1
`and respective new Cover Sheets. (Do NOT file old cover sheets.)
`
`Reel
`
`7593
`
`Frame
`
`0036.
`
`6.
`
`E
`
`(Assignments in parent mget be refiled with new Cover Sheets in this continuing application if you
`want it/them recorded against thecontinuing application.)
`
`Pleaser turn th re ordedA i nmentt
`
`th
`
`n
`
`r i
`
`
`
`E The power of attorney in the prior application is to Dale S. Lazar, Reg. No. 28 872
`(Name and Reg. No.)
`whose current address is as in item 8 below.
`
`a. E Recognize as associate attorney Brian Siritzky, Reg. No. 37,497
`
`(Name, Reg. No. and Address)
`
`Address all future communications to intellectual Property Group
`of Pillsbury Madison & Sutro LLP, Ninth Floor, East Tower 1100 New York Avenue, N.W.,
`Washington, D.C. 20005-3918
`
`Amend the specification by inserting before the first line the sentence:--This is a
`
`El continuation E division
`of Application No.
`08/960,079,
`filed October 24 1997
`series eode it
`it serial no.
`
`which is a continuation of 08/425,160, filed April 11, 1995, now abandoned.
`
`.--
`
`(a) l: Amend the specification by inserting before the first line: --This application claims the benefit of
`Provisional Application No. 60/
`, filed
`.--
`
`7.
`
`8.
`
`9.
`
`9.
`
`10. E It has been recently determined that this new continuing application is entitled to small entity status.
`Hence:
`(No.) Verified Statement(s) establishing “small entity" status under Rules 9 & 27 were/are:
`E filed in above prior application (and hence applicable hereto)
`E attached.
`
`11.
`(E box)
`mst be)
`(X’d)
`
`Petition to extend the life of the above prior application to at Ieeet the dete hereof
`[I is being concurrently filed in that prior application (Use Form PAT-111).
`[3 was previously filed in that prior application (Check length of prior extension).
`E is not necessary fer_cetEg_degg;v (Double check before X’ing this box).
`
`PAT-108 12/E8
`
`GOOG-1016-Page 2 of 126
`
`GOOG-1016-Page 2 of 126
`
`

`
`O
`
`Page 3 of 4
`
`12. E INFORMATION DISCLOSURE STATEMENT: Attached is Form PTO-1449 listing all of the documents
`cited by Applicant and the PTO in the parent app|ication(s) relied upon under 35 USC 120 and
`referenced in item 9 above. Per Rule 98(d) copies of those documents are not required now. Please
`consider those documents and admse that they have been considered in this new application as by
`returning a copy of the enclosed Form PTO-1449 with the Examiner's initials in the left column per
`MPEP 609. .
`
`13.
`
`14.
`
`[I
`
`K4
`
`Attached is a Rule 103(a) Petition to Suspend Action.
`
`PRELIMINARY AMENDMENT to be entered before fee galculaflgng (Do n_o’t make amendments here
`except for correction of improper multiple dependencies or cancellation of whole claims or multiple
`dependencies for purpose of reducing the filing fee per MPEP §§ 506 and 607; do no_t cancel all claims).
`
`Please cancel claims 1-45 and 50-53 without prejudice. The remaining claims correspond to non-elected
`Groups Ill & IV from the Examiner's Restriction Requirement of June 4, 1996.
`
`FILING FEE
`THE FOLLOWING FILING FEE IS BASED ON
`
`->->->—>CLAIM A FILED AND CHANGED BY IMINARY AMENDMENT IN ITEM 14<-<-<-<-
`
`NOTE:
`
`If box 1A2 is X'd, do not pay fees,
`but leave lines 15-22 and 27-32 blank.
`
`.
`.
`
`.
`.
`
`.
`.
`
`.
`.
`
`.
`.
`
`.
`.
`
`.
`.
`
`.
`.
`
`.
`.
`
`.
`.
`
`.
`.
`
`.
`.
`
`.
`.
`
`.
`.
`
`.
`.
`
`.
`.
`
`.
`.
`
`.
`.
`
`.
`.
`
`.
`.
`
`.
`.
`
`.
`.
`
`.
`.
`
`Fee
`Code
`106/26
`101/201
`
`+380
`
`__
`
`-
`
`m
`
`
`
`
`
`
`
`
`
`Largelsmall
`Entity
`
`
`. .Design Application
`.
`.
`.
`15. Basic Filing Fee .
`$310/$155
`. Not Design Application
`16. Basic Filing Fee .
`$760/$380
`
`
`
`
`
`
`
`
`
`
`
`
`. .$13O_ 122
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`
`
`.
`.
`.
`.
`.
`21. lf“petition" box 13 above is X’d, add petition fee.
`21A. If box 6 above is X’d, add Assignment recording fee .
`
`.
`
`.
`
`.
`
`.
`
`22.
`
`23.
`
`24.
`
`25.
`
`$420
`TOTAL FILING FEE ATTACHED =
`(carry forvvar to Item 31)
`
`[I ATTACHED:
`
`El Preliminary Amendment attached (to be entered after assigning Appln. No.)
`
`I___| The following PRELIMINARY AMENDMENT is to be entered after assigning Appln. No.:
`
`FAT-ID8 12198
`
`GOOG-1016-Page 3 of 126
`
`GOOG-1016-Page 3 of 126
`
`

`
`ADDITIONAL FEE CALCULATION FOR
`PRELIMINARY AMENDMENT
`PER BOXES 24/25
`
`Claims
`remaining
`after
`amendment
`
`Highest
`number
`previously
`paid for
`
`Present
`Extra
`
`Additional
`Fee
`
`Page 4 of4
`
`Total Effective Claims
`
`independent Claims
`
`*
`
`*
`
`minus **
`
`20
`
`minus ***
`
`3
`
`=
`
`=
`
`0
`
`0
`
`x
`
`X
`
`$18/$9
`
`$78/$39
`
`L r
`
`/
`
`'
`
`=
`
`=
`
`$ 0
`
`+ 0
`
`File Code
`
`(103/203)
`
`(102/202)
`
`if amendment enters proper multiple dependent claim(s) into this application for the
`first time, add (per application)
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`. .$260/$130
`
`+ 0
`
`004/204)
`
`ADDITIONAL FEE
`
`$ 0
`
`% FEE from item 22 on page 3
`
`+ 420
`
`TOTAL FEE ATTACHED
`
`$ 420
`
`*If the entry in this space is less than the entry in the next space, the “Present Extra" result is “O”
`
`"if the “Highest number previously paid for’ (see item 17 above) is less than 20, write “Z0” in this space
`
`if the “Highest number previously paid tor‘ (see item 18 above) is less than 3, write "3" in this space
`
`26.
`
`27.
`
`28.
`
`29.
`
`30.
`
`31.
`
`32.
`
`33_
`
`34_
`
`35,
`
`CHARGE STATEMENT: Upon the tiling of a Declaration pursuant to Rule 60(b) or 60(d), the Commissioner is hereby
`authorized to charge any fee specifically authorized hereafter, or any missing or insufficient fee(s) filed, or asserted to be
`filed, or which should have been filed herewith or concerning any paper filed hereafter, and which may be required under
`Rules 16-18 (miseing er insufficient fee gnly) now or hereafter relative to this application and the resulting Official
`document under Rule 20, or credit any overpayment, to our Accountlorder Nos. shown in the heading hereof for which
`purpose a duplicate copy of this sheet is attached.
`This CHARGE STATEMENT flee n_cit authorize charge of the issue Leg untillunless an issue fee transmittal form
`is filed.
`
`//
`Pillsbury Madison & Sutr LLP
`intellectual Property G
`15
`
`By Atty:
`Sig:
`
`
`
`ale S. /’
`/'
`'
`
`‘
`
`‘
`
`
`
`Reg. No.
`
`28872
`
`— ’"
`
`.
`
`/
`
`
`
`
`Fax:
`Tel:
`
`(202) 822-0944
`(202) 861-3527
`
`1100 New York Avenue, N.W.
`Ninth Floor, East Tower
`Washington, D.C. 20005-3918
`Tel: (202) 861-3000
`DSL/Bszkim
`Atty./Sec.
`
`NOTE No. 1: File this Request in duplicate with 2 postcard receipts (PAT—103) & attachments
`NOTE No. 2: Is extension in parent necessary for copendency? DOUBLE CHECK item 11 ebeve.
`
`PAT-108 1 2/33
`
`GOOG-1016-Page 4 of 126
`
`GOOG-1016-Page 4 of 126
`
`

`
`R2“
`
`'=,
`
`1
`
`APPLICATION um-:R UNITED STATES PATENT LAWS
`
`Invention: David A. Farber and Ronald D. Lachman
`Inventor(s):
`IDENTIFYING DATA IN A DATA PQOCESSING SYSTEM
`
`
`
`Cushman Darby & Cushman, L¢.m
`1100 New York Avenue, N.W.
`Ninth Floor, East Tower
`Washington, D.C. 20005-3918
`Attorneys
`Telephone:
`(202) 861-3000
`
`This is a:
`
`[
`
`] Provisional Application
`
`[ X] Regular Utility Application
`
`[
`
`[
`
`[
`
`[
`
`f
`
`] Continuing Application
`
`] PCT National Phase Application
`
`] Design Application
`
`] Reissue Application
`
`1 Plant Application
`
`SPECIFICATION
`
`CDC—I00
`
`3/95
`
`GOOG-1016-Page 5 of 126
`
`GOOG-1016-Page 5 of 126
`
`

`
`:3 :
`iv"
`
`7018/213987
`
`CENE,
`
`;%42?E2EEEEEEEEE:EflEé:EE:fl:£fi$§:EEQ§§§§ifi§:§§§£§§—-
`";%
`BACKGROUND OF THE INVENTION
`
`1.
`
`Field of the invention
`
`This invention relates to data processing
`
`5
`
`systems and, more particularly,
`
`to data processing
`
`systems wherein data items are identified by
`
`substantially unique identifiers which depend on all of
`the data in the data items and only on the data in the
`data items.
`
`
`
`
`10
`
`2.
`
`Background of the Invention
`Data processing (DP) systems, computers,
`
`typically offer users
`networks of computers, or the like,
`and programs various ways to identify the data in the
`
`systems.
`
`N
`Users typically identify data in the data
`processing system by giving the data some form of name.
`For example, a typical operating system (OS) on a
`
`computer provides a file system in which data items are
`
`Programs typically
`named by alphanumeric identifiers.
`identify data in the data processing system using a
`
`15
`
`7
`
`20
`
`For example, a program may identify
`location or address.
`a record in a file or database by using a record number
`which serves to locate that record.
`
`In all but the most primitive operating
`systems, users and programs are able to create and use
`
`.25
`
`collections of named data items,
`
`these collections
`
`themselves being named by identifiers. These named
`
`themselves, be made part of other
`collections can then,
`named collections.
`For example, an 08 may provide
`mechanisms to group files (data items)
`into directories
`
`30
`
`(collections). These directories can then,
`themselves be
`made part of other directories.
`A data item may thus be
`identified relative to these nested directories using a
`
`GOOG-1016-Page 6 of 126
`
`GOOG-1016-Page 6 of 126
`
`

`
`sequence of names, or a so—called pathname, which defines
`a path through the directories to a particular data item
`(file or directory).
`As another example, a database management
`system may group data records (data items)
`into tables
`and then group these tables into database files
`(collections).
`The complete address of any data record
`can then be specified using the database file name,
`the
`table name, and the record number of that data record.
`other examples of identifying data items
`identifying files in a network file system,
`include:
`identifying objects in an object—oriented database,
`identifying images in an image database, and identifying
`articles in a text database.
`In general,
`the terms "data" and “data item" as
`used herein refer to sequences of bits. Thus a data item
`may be the contents of a file, a portion of a file, a
`page in memory, an object in an object—oriented program,
`a digital message, a digital scanned image, a part of a
`video or audio signal, or any other entity which can be
`represented by a sequence of bits.
`The term "data'
`processing" herein refers to the processing of data
`items, and is sometimes dependent on the type of data
`item being processed.
`For example, a data processor for
`a digital image may differ from a data processor for an
`audio signal.
`In all of the prior data processing systems the
`names or identifiers provided to identify data items (the
`data items being files, directories, records in the
`database, objects in object-oriented programming,
`locations in memory or on a physical device, or the like)-
`are always defined relative to a specific context.
`For
`instance,
`the file identified by a particular file name
`can only be determined when the directory containing the
`file (the context)
`is known.
`The file identified by a
`pathname can be determined only when the file system
`(context)
`is known. Similarly,
`the addresses in a
`
`5
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`
`
`
`GOOG-1016-Page 7 of 126
`
`GOOG-1016-Page 7 of 126
`
`

`
`the keys in a database table, or
`process address space,
`domain names on a global computer network such as the
`Internet are meaningful only because they are specified
`relative to a context.
`In prior art systems for identifying data items
`there is no direct relationship between the data names
`and the data item.
`The same data name in two different
`i
`contexts may refer to different data items, and two
`different data names in the same context may refer to the
`same data item.
`In addition, because there is no correlation
`between a data name and the data it refers to,
`there is
`no a priori way to confirm that a given data item is in
`fact the one named by a data name.
`For instance,
`in a DP
`system,
`if one processor requests that another processor
`deliver a data item with a given data name,
`the’
`requesting processor cannot,
`in general, verify that the
`data delivered is the correct data (given only the name).
`Therefore it may require further processing, typically on
`the.part of the requester, to verify that the data item
`it has obtained is,
`in fact,
`the item it requested.
`A common operation in a DP system is adding a
`new data item to the system. When a new data item is
`added to the system, a name can be assigned to it only by
`updating the context in which names are defined. Thus
`such systems require a centralized mechanism for the
`management of names.
`such a mechanism is required even
`in a multi—processing system when data items are created
`and identified at separate processors in distinct
`locations, and in which there is no other need for
`communication when data items are added.
`In many data processing systems or
`environments, data items are transferred between
`different locations in the system. These locations may
`be processors in the data processing system, storage
`devices, memory, or the like.
`For example, one processor
`may obtain a data item from another processor or from an
`
`5
`
`10
`
`15
`
`20
`
`
` 25
`
`30
`
`35
`
`.%M;;M\
`
`GOOG-1016-Page 8 of 126
`
`GOOG-1016-Page 8 of 126
`
`

`
`vdevice, such as a floppy disk, and may
`external storage
`tem (using the
`incorporate that data item into its sys
`ovided with that data item).
`name pr
`However,
`when a processor (0
`ins a data item from another location in the DP
`it is possible that this obtained data item is
`system,
`(either at the location of
`already present in the system
`r location accessible by the
`
`r some location)
`
`obta
`
`sev
`
`product will
`
`processor) and therefore a
`n in a network data
`created.
`This situation is commo
`t where proprietary software
`processing environmen
`floppy disks onto several
`products are installed from
`In these
`processors sharing a common file server.
`it is often the case that the same
`systems,
`so that several copies
`be installed on several systems,
`h file will reside on the common file server.
`of eac
`In some data processing systems in which
`eral processors are connected in a network, one system
`to maintain master copies
`is designated as a cache server
`designated as cache
`and other systems are
`of data items,
`clients to copy local copies of the master data items
`into a local cache on an as-needed basis. Before using a
`a cache client must either reload the cached
`cached item,
`or
`ormed of changes to the cached item,
`item, be inf
`0 the cached
`t the master item corresponding t
`confirm the
`item has not changed.
`In other words, a cache client
`nchronize its data items with those on the cache
`must sy
`lve reloading data
`This synchronization may invo
`server.
`The need to keep the cache
`items onto the cache client.
`s significant overhead to
`synchronized or reload it add
`existing caching mechanisms.
`In View of the above and other problems with
`prior art systems, it is therefore desirable to have a
`mechanism which allows each processor in a multiprocessor
`system to determine a common and substantially unique
`using only the data in the
`identifier for a data item,
`ntext.
`data item and not relying on any sort of co
`
`5
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`
`
`
`
`
`
`
`a
`
`—
`
`GOOG-1016-Page 9 of 125
`
`GOOG-1016-Page 9 of 126
`
`

`
`It is further desirable to have a mechanism for
`reducing multiple copies of data items in a data
`processing system and to have a mechanism which enables
`the identification of identical data items so as to
`reduce multiple copies.
`It is further desirable to
`determine whether two instances of a data item are in
`fact the same data item, and to perform various other
`systems’ functions and applications on data items without
`~relying on any context information or properties of the
`data item.
`‘
`It is also desirable to provide such a
`mechanism in such a way as to make it transparent to
`users of the data processing system, and it is desirable
`that a single mechanism be used to address each of the
`problems described above.
`
`SUMARY OF THE INVENTLON
`This invention provides,
`in a data processing
`system, a method and apparatus for identifying a data
`item in the system, where the identity of the data item
`depends on all of the data in the data item and only on
`the data in the data item. Thus the identity of a data
`item is independent of its name, origin,
`location,
`address, or other information not derivable directly from
`the data, and depends only on the data itself.
`This invention further provides an apparatus
`and a method for determining whether a particular data
`item is present in the system or at a location in the
`system, by examining only the data identities of a
`plurality of data items.
`_
`Using the method or apparatus of the present
`the efficiency and integrity of-a data
`invention,
`processing system can be improved.
`The present invention
`improves the design and operation of a data storage
`system, file system, relational database, object-oriented
`database, or the like that stores a plurality of data
`items, by making possible or improving the design and
`
`5
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`.s
`
`
`
`
`§§“
`
`GOOG-1016-Page 10 of 126
`
`GOOG-1016-Page 10 of 126
`
`

`
`operation of at least some or all of the following
`features:
`
`the system stores at most one copy of any data
`
`5
`
`item at a given location, even when multiple data names
`in the system refer to the same contents;
`the system avoids copying data from source to
`
`destination locations when the destination locations
`already have the data;
`
`the system provides transparent access to any
`
`10
`
`data item by reference only to its identity and
`
`independent of its present location, whether it be local,
`remote, or offline;
`
`the system caches data items from a server, so
`
`,that only the most recently accessed data items need be
`
`15
`
`retained;
`
`7
`when the system is being used to cache data
`
`20
`
`
` 25
`
`ii
`
`30
`
`35
`
`items, problems of maintaining cache consistency are
`
`avoided;
`
`w
`the system maintains a desired level of
`
`to
`redundancy of data items in a network of servers,
`protect against failure by ensuring that multiple copies
`of the data items are present at different locations in
`
`the system;
`
`the system automatically archives data items as
`they are created or modified;
`
`the system provides the size, age, and location
`
`of groups of data items in order to decide whether they
`can be safely removed from a local file system;
`
`the system can efficiently record and preserve
`any collection of data items;
`the systemycan efficiently make a copy of any
`
`collection of data items,
`
`to support a version control
`
`mechanism for groups of the data items;
`
`K
`
`the system can publish data items, allowing
`_
`other, possibly anonymous, systems in a network to gain
`access to the data items and to rely on the availability
`of the data items;
`
`«M?
`
`GOOG-1016-Page 11 of 126
`
`GOOG-1016-Page 11 of 126
`
`

`
`5
`
`10
`
`15
`
`20
`
` 25
`
`'*
`
`the system can maintain a local inventory of
`all the data items located on a given removable medium,
`
`such as a diskette or CD-ROM,
`
`the inventory is
`
`independent of other properties of the data items such as
`
`location, and date of creation;
`their name,
`the system allows closely related sets of data
`items, such as matching or corresponding directories on
`
`disconnected computers, to be periodically resynchronized
`with one another;
`
`the system can verify that data retrieved from
`another location is the desired or requested data, using
`
`only the data identifier used to retrieve the data;
`the system can prove possession of specific
`
`data items by content without disclosing the content of
`
`the data items, for purposes of later legal verification
`and to provide anonymity;
`
`the system tracks possession of specific data
`
`independent of the
`items according to content by owner,
`name, date, or other properties of the data item, and
`
`tracks the uses of specific data items and files by
`content for accounting purposes.
`I
`other objects, features, and characteristics of
`
`the present invention as well as the methods of operation
`and functions of the related elements of structure, and
`
`the combination of parts and economies of manufacture,
`
`will become more apparent upon consideration of the
`
`following description and the appended claims with
`reference to the accompanying drawings, all of which form
`
`a part of this specification.
`
`30
`
`35
`
`BRIEF D ‘CR PTION OF THE DRAWINGS
`
`GURE 1 depicts a typical data processing
`ZIXg:>
`h a preferred embodiment of the present
`system in wh
`invention oper tes;
`
`FIGURE 2 depicts a hierarchy of data items
`stored at any location in such a data processing system;
`
`GOOG-1016-Page 12 of 126
`
`GOOG-1016-Page 12 of 126
`
`

`
`FIGURES 3-9 depict data structures used to
`
`implement an embodiment of the present invention; and
`
`FIGURES 10(a)-28 are flow charts depicting
`
`operation of various aspects of the present invention.
`
`5
`
`DETAIL D DESCRIPTION OF THE PRESENTL
`
`PREFERRED
`
`>>
`
`
`described w th reference to a typical data processing
`
`n embodiment of the present invention is now
`
`EXEMPLARY EMBODIMENTS
`
`
`
`10
`
`includes
`system 100, w ich, with reference to FIGURE 1,
`one or more pr
`essors (or computers) 102 and various
`
`storage devices
`04 connected in some way, for example by
`
`a bus 106.
`
`Each processor 102 includes a CPU 108, a memory
`
`110 and one or more local storage devices 112.
`
`The CPU
`
`15
`
`108, memory 110, and local storage device 112 may be
`
`internally connected, for example by a bus 114.
`Each
`processor 102 may also include other devices (not shown),
`such as a keyboard, a display, a printer, and the like.
`
`In a data processing system 100, wherein more
`than one processor 102 is used, that is,
`in a
`
`20
`
`multiprocessor system,
`
`the processors may be in one of
`
`various relationships.
`
`For example,
`
`two processors 102
`
`may be in a client/server, client/client, or a
`
`server/server relationship. These inter-processor
`
`25
`
`relationships may be dynamic, changing depending on
`
`particular situations and functions. Thus, a particular
`processor 102 may change its relationship to other
`
`processors as needed, essentially setting up a peer-to-
`
`In a peer-to—"
`peer relationship with other processors.
`peer relationship, sometimes a particular processor 102
`acts as a client processor, whereas at other times the
`
`same processor acts as a server processor.
`
`In other
`
`there is no hierarchy imposed on or required of
`words,
`processors 102.
`
`the processors 102
`In a multiprocessor system,
`i
`may be homogeneous or heterogeneous. Further,
`in a
`
`30
`
`35
`
`8
`
`{%
`
`GOOG-1O16-Page 13 of 126
`
`GOOG-1016-Page 13 of 126
`
`

`
`5
`
`10
`
`15
`
`20
`
`multiprocessor data processing system 100, some or all of
`
`the processors 102 may be disconnected from the network
`
`Such disconnection
`of processors for periods of time.
`may be part of the normal operation of the system 100 or
`it may be because a particular processor 102 is in need
`of repair.
`
`Within a data processing system 100,
`the data
`may be organized to form a hierarchy of data storage
`elements, wherein lower level data storage elements are
`combined to form higher level elements. This hierarchy
`can consist of, for example, processors, file systems,
`
`regions, directories, data files, segments, and the like.
`For example, with reference to FIGURE 2,
`the data items
`on a particular processor 102 may be organized or
`structured as a file system 116 which comprises regions
`
`117, each of which comprises directories 118, each of
`which can contain other directories 118 or files 120.
`
`Each file 120 being made up of one or more data segments
`122.
`
`some or
`In a typical data processing system,
`all of these elements can be named by users given certain
`
`implementation specific naming conventions,
`
`the name (or
`
`In
`pathname) of an element being relative to a context.
`the context of a data processing system 100, a pathname
`
`25
`
`is fully specified by a processor name, a filesystem
`
`name, a sequence of zero or more.directory names
`
`identifying nested directories, and a final file name.
`(Usually the lowest level elements,
`in this case segments
`122, cannot be named by users.)
`
`30
`
`In other words, a file system 116 is a
`
`A directory 118 is a
`collection of directories 118.
`collection of named files 120 -- both data files 120 and
`
`other directory files 118.
`
`A file 120 is a named data
`
`item which is either a data file (which may be simple or
`
`35
`
`compound) or a directory file 118.
`
`A simple file 120
`
`consists of a single data segment 122.
`
`A compound file
`
`120 consists ofia sequence of data segments 122.
`
`A data
`
`
`
`GOOG-1016-Page 14 of 126
`
`GOOG-1016-Page 14 of 126
`
`

`
`segment 122 is a fixed sequence of bytes. An important
`
`property of any data segment is its size,
`
`the number of
`
`g
`_
`bytes in the sequence.
`A single processor 102 may access one or more
`
`5
`
`file systems 116, and a single storage device 104 may
`contain one or more file systems 116, or portions of a
`
`file system 116.
`
`For instance, a file system 116 may
`
`span several storage devices 104.
`
`10
`
`system, file system 116 may be divided into distinct
`
`In order to implement controls in a file
`
`regions, where each region is a unit of management and
`control.
`A region consists of a given directory 118 and
`
`is identified by the pathname (user defined) of the
`directory.
`H
`
`In the following,
`
`the term "location", with
`
`respect to a data processing system 100, refers to any of
`
`a particular processor 102 in the system, a memory of a
`particular processor, a storage device, a removable
`
`storage medium (such as a floppy disk or compact disk),
`
`The term
`or any other physical location in the system.
`"local" with respect to a particular processor 102 refers
`
`to the memory and storage devices of that particular
`processor.
`‘
`
`the terms "True Name", "data
`In the following,
`identity" and "data identifier" refer to the
`
`substantially unique data identifier for a particular
`data item.
`The term "True File" refers to the actual
`
`file, segment, or data item identified by a True Name.
`
`15
`
`20
`
`25
`
`
`
`‘*
`
`30
`
`A file system for a data processing system 100
`is now described which is intended to work with an
`
`existing operating system by augmenting some of the
`operating system's file management system codes.
`The
`embodiment provided relies on the standard file
`
`management primitives for actually storing to and
`
`, 35
`
`retrieving data items from disk, but uses the mechanisms
`of the present invention to reference and access these
`data items.
`6
`
`10
`
`GOOG-1016-Page 15 of 126
`
`GOOG-1016-Page 15 of 126
`
`

`
`The processes and mechanisms (services)
`
`provided in this embodiment are grouped into the
`
`following categories: primitive mechanisms, operating
`
`system mechanisms,
`
`remote mechanisms, background
`
`5
`
`mechanisms, and extended mechanisms.
`
`Primitive mechanisms provide fundamental
`capabilities used to support other mechanisms.
`The
`
`following primitive mechanisms are described:
`1.
`Calculate True Name;
`
`10
`
`15
`
`25
`
` 25
`
`*£
`
`30
`
`35
`
`2.
`
`3.
`4.
`
`5.
`
`6.
`
`7.
`
`8.
`9.
`
`Assimilate Data Item;
`
`New True File;
`Get True Name from Path;
`
`Link path to True Name;
`
`Realize True File from Location;
`
`Locate Remote File;
`
`Make True File Local;
`Create Scratch File;
`
`'
`Freeze Directory;
`10.
`Expand Frozen Directory;
`11.
`12. Delete True File;
`13. Process Audit File Entry;
`
`14. Begin Grooming;
`15. Select For Removal; and
`
`16.
`
`End Grooming.
`
`Operating system mechanisms provide typical
`familiar file system mechanisms, while maintaining the
`data structures required to offer the mechanisms of the,
`
`present invention. Operating system mechanisms are
`designed to augment existing operating systems, and in
`this way to make the present invention compatible with,_
`and generally transparent to, existing applications.
`The
`following operating system mechanisms are described:
`1.
`Open File;
`2.
`Close File;
`
`3.
`
`Read File;
`
`4. Write File;
`
`5.
`
`Delete File or Directory;
`
`11
`
`GOOG-1016-Page 16 of 126
`
`GOOG-1016-Page 16 of 126
`
`

`
`Copy File or Directory;
`6.
`Move File or Directory;
`7.
`Get File Status; and
`8.
`Get Files in Directory.
`9.
`Remote mechanisms are used by the operating
`system in responding to requests from other processors.
`These mechanisms enable the capabilities of the present
`invention in a peer—to-peer network mode of operation.
`The following remote mechanisms are described:
`1.
`Locate True File;
`2.
`Reserve True File;
`
`3.
`4.
`
`5.
`
`6.
`7.
`
`8.
`9.
`
`Request True File;
`Retire True File;
`
`Cancel Reservation;
`
`Acquire True File;
`Lock Cache;'
`
`Update Cache; and
`Check Expiration Date.
`
`Background mechanisms are intended to run
`occasionally and at‘a low priority. These provide
`automated management capabilities with respect to the
`present invention.
`The following background mechanisms
`are described:
`1. Mirror True File;
`
`2.
`3.
`
`4.
`S.
`
`Groom Region;
`Check for Expired Links; and
`
`~Verify Region; and
`Groom Source List.
`
`Extended mechanisms run within application
`programs over the operating system. These mechanisms
`provide solutions to.specific problems and applications.;
`The following extended mechanisms are described:
`1.
`Inventory Existing Directory;
`2.
`Inventory Removable, Read-only Files;
`
`3.
`4.
`
`5.
`
`Synchronize directories;
`Publish Region;
`
`Retire Directory;
`
`5
`
`10
`
`15
`
`20
`
` 25
`
`*5
`
`30
`
`35
`
`12
`
`.,.»‘:}‘
`/.,
`
`GOOG-1016-Page 17 of 126
`
`GOOG-1016-Page 17 of 126
`
`

`
`6.
`
`7.
`8.
`
`9.
`
`Realize Directory at location;
`
`Verify True File;
`Track for accounting purposes; and
`
`Track for licensing purposes.
`
`5
`
`The file system herein described maintains
`sufficient information to provide a variety of mechanisms
`
`some of
`not ordinarily offered by an operating system,
`which are listed and described here. Various processing
`
`performed by this embodiment of the present invention
`will now be described in greater detail.
`In some embodiments,
`some files 120 in a data
`
`processing system 100 do not have True Names because they
`have been recently received or created or modified, and
`
`A file
`thus their True Names have not yet been computed.
`that does not yet have a True Name is called a scratch
`
`The process of assigning a True Name to a file is
`file.
`referred to as assimilation, and is described later.
`
`Note that a scratch file may have a user provided name.
`
`Some of the processing performed by the present
`.
`invention can take place in a background mode or on a
`
`delayed or as-needed basis. This background processing
`is used to determine information that is not immediately
`
`10
`
`15
`
`20
`
`required by the system or which may never be required.
`
`As an example,
`
`in some cases a scratch file is being
`
`25
`
`changed at a rate greater than the rate at which it is
`useful to determine its True Name.
`In these cases,
`
`determining the True Name of the file can be postponed or
`
`performed in the background.
`
`Data structures
`
`,
`
`30
`
`The following data structures, stored in memory
`110 of one of more processors 102 are use