as United States
`a2) Patent Application Publication co) Pub. No.: US 2002/0169818 A1
`(43) Pub. Date: Nov. 14, 2002
`
`Stewartet al.
`
`US 20020169818A1
`
`(54) METHOD AND APPARATUS FOR
`EFFICIENT STORAGE AND RETRIEVAL OF
`OBJECTS IN AND FROM AN OBJECT
`STORAGE DEVICE
`
`(75)
`
`Inventors: Christoher H. Stewart, Tomball, TX
`(US); Svilen B. Pronev, Cypress, TX
`(US); Darrell J. Starnes, Tomball, TX
`(US)
`
`Correspondence Address:
`AKIN, GUMP, STRAUSS, HAUER & FELD,
`L.L.P.
`300 WEST 6TH STREET
`SUITE 2100
`AUSTIN, TX 78701 (US)
`
`(73) Assignee: Compaq Computer Corporation
`
`(21) Appl. No.:
`
`10/128,778
`
`(22)
`
`Filed:
`
`Apr. 24, 2002
`
`Related U.S. Application Data
`
`(63) Continuation of application No. 09/133,497,filed on
`Aug. 12, 1998, now Pat. No. 6,389,460.
`
`(60) Provisional application No. 60/085,309, filed on May
`13, 1998.
`
`Publication Classification
`
`Tint, C0 ieeeeeeeeccscceeeennnteemeeeeceeceeenne GO6F 15/16
`(BV)
`(52) US. Cd.cece css tesseeesetenncsesessnesaneeeneess 709/202
`
`(57)
`
`ABSTRACT
`
`Techniques for storing objects (¢.g., images) in and retriev-
`ing objects from a storage device (e.g., image store) in a
`rapid and efficient mannerare disclosed. More particularly,
`the techniques include: storage of an object in and retrieval
`of an object from the storage device with reference to an
`object locator together with state and permission informa-
`tion, use of a directory structure of a file system to efficiently
`provide database structure for storage of the objects, storage
`and retrieval of object states as attributes of associatedfiles
`in the file system, storage andretrieval of multiple versions
`of objects, and multi-threaded management of the storage
`device.
`
`106
`
`CONTENT|
`SERVER
`
`
` 104
`
`
`
`
`
`
`
`BROWSER
`
`
`
`402
`
`PROXY
`
`SERVER
`
`104
`
`BROWSER
`
`
`ACCELERATION
` SERVER
`
`BROWSER
`
`104
`
`110
`
`Data Co Exhibit 1035
`Data Co Exhibit 1035
`Data Co v. Bright Data
`Data Co v. Bright Data
`
`

`

`Patent Application Publication Nov. 14, 2002 Sheet 1 of 10
`
`US 2002/0169818 Al
`
`00hOb}
`
`NOILVYSATA90V
`
`YsAdss
`
`|Old
`
`901
`
`801
`
`ZOL
`
`
`
`YaANRSWaAWASwasmoug|70b
`_
`
`LNALNOODAXOUd
`
`wuasmoud|7Ol
`wasmoug|70!
`
`
`
`

`

`Patent Application Publication Nov. 14, 2002 Sheet 2 of 10
`
`US 2002/0169818 Al
`
`
`
`200
`
`
`
`PROXY FILTER
`
`
`
`202
`
`
`
`OBSERVER
`
`RESOURCE
`MANAGER
`
`204
`
`aAmMmZ2zmUmMAz—
`
`MANAGER
`
`Cc’)
`
`AMZ2IMASZ~OVMYHWSOTVWA
`
`a
` PROXY CACHE
`PROXY SERVER
`
` ACCELERATOR
`
`
`
`IMAGE
`
`STORE
`
`MANAGER
`
`214
`
`
`
`ACCELERATION SERVER
`
`FIG. 2
`
`

`

`Patent Application Publication Nov. 14, 2002 Sheet 3 of 10
`
`US 2002/0169818 Al
`
`a 300
`
`PAGE
`REQUESTED
`
`
`NO
`Q ?
`
`
`302
`
`YES
`
`SEND HTTP REQUEST FOR WEB PAGE
`TO PROXY SERVER
`
`304
`
`CE306
`
`SsYE
`
`DISPLAY HTML FILE ON A DISPLAY DEVICE
`
`308
`
`SEND GET IMAGE REQUESTS FORIMAGES |__
`WITHIN HTML FILE TO PROXY SERVER
`
` RECIEVED
`
`/NO
`
`312
`
`VES
`
`314
`
`DISPLAY IMAGE FILE TOGETHER WITH
`HTML FILE ON THE DISPLAY DEVICE
`
`/
`
`FIG. 3
`
`

`

`Patent Application Publication Nov. 14, 2002 Sheet 4 of 10
`
`US 2002/0169818 Al
`
`“>.
`
`=
`
`RETRIEVING HTML FILE FROM CONTENT SERVER
`
`FORWARD RETRIEVED
`HTML FILE TO
`BROWSER
`
`SCAN RETRIEVED
`HTML FILE TO
`
`408
`
`404
`IDENTIFY IMAGES
`
`410
`
`STORE IMAGE
`FILE TO SLOT
`IN IMAGE STORE
`
`
`
`REDUCESIZE OF
`
`
`IMAGE FILE
`
`
`
`
`
` STORE REDUCED IMAGE
`
`
`FILE INAPPROPRIATE
`SLOTIN IMAGE STORE
`
`
`
`RETRIEVE IMAGE
`FILE FROM CONTENT
`SERVER
`
`
`
`FIG. 4
`
`

`

`Patent Application Publication Nov. 14, 2002 Sheet 5 of 10
`
`US 2002/0169818 Al
`
`eran)
`
`RECEIVE URL AND ASSOCIATED HTTP
`REQUEST AND HTTP RESPONSE INFORMATION
`
`
`
`PARSE HTTP REQUEST AND HTTP RESPONSE
`INFORMATION TO OBTAIN COOKIES AND
`AUTHORIZATIONS
`
`=
`
`504
`
`MERGE COOKIES AS NEEDED
`
`906
`
`
`
`FORM ANIMAGEIDENTIFICATION STRING BY
`CONCENRATING THE URL, MERGED COOKIES,
`AND AUTHORIZATIONS
`
`508
`
`HASH THE IMAGE IDENTIFICATION STRING
`TO PRODUCEA HASH DIRECTORY
`
`510
`
`ENCODE THE IMAGEIDENTIFICATION STRING
`FOR COMPLIANCE WITH FILE SYSTEM
`
`DIVIDE THE ENCODEDIMAGEIDENTIFICATION
`
`
`STRING TO FORM A DIRECTORY PATH
`STORE FOR THE DIRECTORYPATH
`
`512
`
`514
`
`FORM THE DIRECTORIESIN THE IMAGE
`
`516
`
`FORM SETOF FILES IN THE RESULTING
`
`DIRECTORY AND SET THEIR INITIAL STATE
`
`518
`
`FIG. 5
`
`

`

`Patent Application Publication Nov. 14, 2002 Sheet 6 of 10
`
`US 2002/0169818 Al
`
`600
`
`J
`
`SLOT-1 SLOT-2 SLOT-3
`
`«++
`
`SLOT-n
`
`- —
`
`=
`
`~!
`
`$09 741399
`go WW Ww
`a OW
`7606081] #8
`oct ¢€
`Oo <
`
`FIG. 6
`
`g6i
`
`vO
`
`

`

`Patent Application Publication Nov. 14, 2002 Sheet 7 of 10
`
`US 2002/0169818 Al
`
` RECEIVE
`
` 702
`
`IMAGE
`
`REQUEST
`
`PARSE IMAGE REQUEST FROM BROWSER TO
`OBTAIN URL, COOKIES, AND AUTHORIZATIONS
`
`FORM AN IMAGEIDENTIFICATION SRING BY
`CONCATENING THE URL, COOKIES AND
`
`708
`
`HASH THE IMAGE IDENTIFICATION STRING
`TO PRODUCE A HASH DIRECTORY
`
`ENCODE THE IMAGEIDENTIFICATION STRING
`FOR COMPLIANCE WITH FILE SYSTEM
`
`0
`
`a
`
`AUTHORIZATIONS
`DIRECTORY PATH
`
`FORM A DIRECTORYPATHBY DIVIDING THE
`ENCODEDIMAGEIDENTIFICATION STRING
`
`m2
`
`REQUESTFILE SYSTEM TO OPENIMAGEFILE
`IN THE RESULTING DIRECTORY OF THE
`
`714
`
`FIG. 7A
`
`

`

`Patent Application Publication Nov. 14, 2002 Sheet 8 of 10
`
`US 2002/0169818 Al
`
`7
`
`REQUESTED
`FILE
`
`|D.
`7
`
`716
`726 EXIST
`
`VES
`
`REQUESTIMAGE
`FROM REMOTE
`CONTENT SERVER
`
`718
`
`IS
`STATE
`OF FILE
`“DONE” YES
`?
`
`724
`
`NO
`
`FILE WAIT
`
`720
`
`RETRIEVE IMAGE
`FROM IMAGE STORE
`
`PROCESSING
`FORWARD REQUESTED
`=
`IMAGE TO REQUESTOR|~~/22
`
`ZS
`
`(DONE)
`
`
`
`FIG. 7B
`
`

`

`Patent Application Publication Nov. 14, 2002 Sheet 9 of 10
`
`US 2002/0169818 Al
`
`£-0H
`
`OH
`
`AdvWlad
`
`“HIG
`
`
`playclayclad=/+t-de0l-de
` \/\ZeLre-dscLre-dsbLe-asNYLe-ds
`
`
`SdY2dyY9CYHNsay\/\Z\ZONbho-dsZeb--as
`
`Le-as
`
`8‘Sls
`
`f--ds
`
`\7ZL-IH
`
`beb-ds
`
`rayfcdycayt-dy/.
`
`
`
`b’L-as
`
`

`

`Patent Application Publication Nov. 14, 2002 Sheet 10 0f 10
`
`US 2002/0169818 Al
`
`2”
`rare)
`CRITERION THREADS TO RUN IN PARALLEL
`
`DISPATCH A PLURALITY OF SPECIFIC
`
`CLEAN CACHE
`BASED ON HTTP
`
`CLEAN CACHE
`BASED ON
`FILE DATE
`
`EXPIRATION DATE IS
`
`MAX.
`CACHE
`SIZE
`EXCEEDED/“NO
`?
`
`lYES
`
`
`
`DISPATCH N THREADS TO
`CLEAN PARTS OF CACHE
`
`910
`
`WAIT FOR N THREADS
`TO COMPLETE
`
`912
`
`914
`
`WATT FOR SPECIFIC
`
`CRITERION THREADS
`TO COMPLETE
`
`FIG. 9
`
`

`

`US 2002/0169818 Al
`
`Nov. 14, 2002
`
`METHOD AND APPARATUSFOR EFFICIENT
`STORAGE AND RETRIEVAL OF OBJECTS IN AND
`FROM AN OBJECT STORAGE DEVICE
`
`CROSS-REFERENCE TO RELATED
`APPLICATIONS
`
`[0001] The present application is a continuation of US.
`patent application Ser. No. 09/133,497, which claims the
`benefit of U.S. Provisional Application No. 60/085,309,
`entitled “METHOD AND APPARATUS FOR STORAGE
`
`AND DELIVERY OF CONTENT”, and filed on May
`13,1998, each of the disclosures are incorporated herein by
`reference in their entireties for all purposes.
`
`BACKGROUND OF THE INVENTION
`
`[0002]
`
`1. Field of the Invention
`
`[0003] The present invention relates to information stor-
`age and retrieval and more particularly,
`to storage and
`accelerated retrieval of objects from an object storage
`device.
`
`[0004]
`
`2. Description of the Related Art
`
`[0005] The Internet is a resource for tremendous amounts
`of content information. As examples, the content informa-
`tion can include text, images or other types of data. A user
`normally accesses the Internet using a connection provided
`by a modem and a regular telephone line or ISDNline, or by
`a T1 line orleased line. The connection to the Internet may
`be indirectly through an Internet Service Provider (ISP) or
`more directly to the Internet (or World Wide Web). The
`higher the bandwidth supported by the connection, the better
`the responsiveness of the Internet to the user’s requests. For
`example, since a T7 line offers substantially greater band-
`width than does a 28.8 kbps modem andregular telephone
`line, the connection to the Internet provided by the T1 line
`will provide substantially faster responsiveness to a user’s
`requests than would the 28.8 kbps modem.
`
`[0006] A uniform resource locator (URL) is a unique
`identifier for a particular content location in the Internet.
`Every object located on the Internet has an associated URL.
`Each URLis divided up into four pieces, protocol, host
`nameandport, uniform resourceidentifier (URD),and query.
`Furthermore, the content actually served from a particular
`URL location can depend on associated factors, such as
`cookics and authorizations which are scnt between the
`
`requesting client and the content server using the Hypertext
`Transfer Protocol (HTTP). HTTPis one of several Internet
`protocols for transporting data between client and servers.
`Other transport protocols include file transport protocols,
`gopher,file and WYSIWIG.An Internet host (e.g., content
`server) is an entity on the Internet which has either a domain
`name, an IP address or both, and whichis capable of serving
`content to requesting clients. A URIis a particular location
`of data on the Internet host. A query is a text string passed
`from the client to the host which requests a particular piece
`of data from a particular URI location within the host. A
`valid URL request sent by a client must contain a protocol,
`a host and a URI. The query is optional.
`
`Internet proxy servers have been used to allow
`[0007]
`multiple users to share Internet access through a common
`high speed connection. Examples of such Internet proxy
`servers are (1) WinGate available from Deerfield Commu-
`
`nications Company and (2) Microsoft Proxy Server avail-
`able from Microsoft Corporation. Shared connectionsfacili-
`tate providing firewalls to prevent unauthorized access into
`the user’s (e.g., corporate) internal computers. These shared
`connections can also provide the Hypertext Transfer Proto-
`col (HTTP) caching to allow improved responsiveness.
`These Internet proxy servers can also providesite filtering to
`prevent user (behind the Internet proxy server) access to
`certain Internet sites.
`
`[0008] HTTP caching operates to locally store frequently
`accessed Internet material so that it is quickly available
`when subsequently requested. HTTP cachingis described in
`detail in the Hypertext Transfer Protocol (HTTP) document,
`version 1.1, which is hereby incorporated by reference. Such
`caching enables an organization to moreefficiently share the
`bandwidth of the Internet connection.
`
`the delivery over the Internet of
`[0009] Conventionally,
`similar data in different formats was achieved in several
`
`different ways. One way is to present the user with a low
`resolution version of an image but then allowthe user to
`click on the image to request a higher resolution version. A
`second wayis to allow for initially load-up a low resolution
`version of an image to the user while a higher resolution
`version loads in the background. A third approach is by
`content negotiation between content server and user so that
`a client can request a high or low resolution version from the
`contentserver at the same URL.The content negotiation can
`be achieved by communicating cookies and authorizations
`between the user and the content server or by a POST
`request to a dynamic URLlocated on the content server. A
`POSTrequest is an HTTP mechanism that allows a browser
`to send data to a content server.
`
`[0010] Content negotiation is known and described in the
`HTTP document, version 1.1. Content negotiation is the
`process in which a HTTP response to a HTTP request is
`chosen to be that which is most suitable, assuming of course
`that
`there is a choice. The content negotiation can be
`client-driven or server-driven. The content differences being
`negotiated can vary widely but are nevertheless stored on a
`content server on the Internet. As an example, the content
`differences could be different
`languages or different size
`images. In such a case, a client may negotiate on behalf of
`a user with a content server to receive smaller (¢.g., less
`robust, lower quality, or smaller image area) images instead
`of commonly provided larger images from the server. If the
`content server can provide the smaller images, then the user
`is able to receive and display the information (e.g., images)
`faster than had their been no choice or no negotiation. Thus,
`in some cases, the negotiation facilitates improved band-
`width utilization and responsiveness of the Internet. One
`problem with the conventional approaches to negotiated
`content delivery over the Internet
`is that most content
`servers do not offer multiple versions of information content.
`As a result, content negotiation, even if available, is not
`supported by most content servers. There arc also no stan-
`dards on whattypes of versionsorvariations of information
`content a content server should make available. Conse-
`quently, content negotiation is difficult to obtain over the
`Internet.
`
`conventional
`these
`all of
`(0011] One problem of
`approachesis that the content server is required to support
`and maintain both a high resolution and a low resolution
`
`

`

`US 2002/0169818 Al
`
`Nov. 14, 2002
`
`version of an image or object. While both versions occupy
`the same logical location on the Internet (e.g., URL) the
`content server must allocate separate physical space for each
`version. Also, content providers must expend and utilize
`scarce resources to provide multiple versions of the same
`content.
`
`{0012] Other problemsare concerned with efficiently stor-
`ing, using and managing the cache. Conventionally, a proxy
`server generally reserves or provides a single location in a
`cache for a single URL.In other words, imagesstored in the
`cache are identified only by URLs. However, such an
`approach ignores the fact that URLsare often modified by
`cookies or authorizations. See HTTP,version 1.1. This is a
`deficiency of the conventional approaches because cookies
`and authorizations impact the availability of images. Fur-
`ther, the storage of images within a cache for a proxy server
`has been conventionally done using a standard database
`(with either a relational database model or a hierarchical
`database model). The relational database model typically
`does not offer high-performance and developing a database
`system tends to require a lot of time and associated cost. In
`a hierarchical database modeldata is stored as nodesin a tree
`
`structure, and the edges ofthe tree are identified by particu-
`lar keys which identify the location of the data within the
`database. The tree nodes store the data, and the tree edges
`which point to successive nodes facilitate retrieval of the
`data. While the hierarchical modelis a faster model than the
`relational model, there is still sufficient overhead associated
`with the database engine being utilized. These problems
`associated with the conventional approaches are typically
`associated with the cost of the system and its performance.
`[0013] Thus, there is a need for improved techniques for
`caching information content from a remote contentserverin
`a temporary storage device as well as for delivering infor-
`mation content from the temporary storage device to a user.
`SUMMARY OF THE INVENTION
`
`‘The invention pertains to techniques for storing
`[0014]
`objects (e.g.,
`images)
`in and retrieving objects from a
`storage device (€.g.,
`image store) in a rapid and efficient
`manner. The various aspects of the invention include: stor-
`age of an object in andretrieval of an object from the storage
`device with reference to an object locator together with state
`and permission information, use of a directorystructure of
`a file system to efficiently provide database structure for
`storage of the objects, storage and retrieval of object states
`as. attributes of associated files in the file system, storage
`and retrieval of multiple versions of objects, and multi-
`threaded managementof the storage device.
`{0015] The invention can be utilized in a variety of sys-
`temsor apparatuses,but is particularly well suited for use in
`a proxysystem for a network(e.g., the Internet) wherein the
`database storage stores an object identifier, state information
`and permission information. A proxy system operates to
`store (e.g., caching) object files in a storage device (e.g.,
`image store) so that these object files are able to more
`quickly and efficiently be supplied to requestors coupled to
`the proxy system. A directory structure points to resulting
`directories in the storage device where one or more different
`versions of an object can be stored. Whenthe storage device
`is used as a cache device that provides temporary storage,
`the managementof the storage device operates to clean out
`the storage device to remove expired data as well as to
`prevent overflow.
`
`[0016] The proxy system can also include an acceleration
`apparatus (e.g., an acceleration server). Such a proxy system
`is able to produce an accelerated version of content infor-
`mation from the network, cache the accelerated version (and
`possibly original versions) for subsequent requests for the
`same information content, and supply the accelerated ver-
`sion of the information content to a requesting user.
`
`[0017] The invention can be implemented in numerous
`ways, including as a method, an apparatus, a system, or
`computer readable medium. Several embodiments of the
`invention are summarized below.
`
`[0018] Asa methodfor storing objects in an object storage
`device, one embodimentof the invention includes the opera-
`tions of: receiving a uniform resource locator, state infor-
`mation and authorization information associated with a
`particular object to be stored in the object storage device;
`combining the uniform resource locator, the state informa-
`tion and the authorization information to obtain an object
`identification string; dividing the object identification string
`into a plurality of individual directories,
`the individual
`directories form a directory path to a resulting directory
`where the particular object is to be stored; and storing at
`least one version of the particular object in the resulting
`directory in the object storage device. Optionally, the inven-
`tion can also include the operations of producing a second
`version on the particular object by reducing the size of the
`first version of the particular object; and subsequentlystor-
`ing the second version of the particular object in the result-
`ing directory in the object storage device. As another option,
`the object storage device is a database, and at least a part of
`the database has a directory structure of a file system used
`with the object storage device.
`
`[0019] As a method for storing an image in an image
`storage device, one embodimentof the invention includes
`the operations of:
`receiving URL and associated HTTP
`Request and HTTP Response information; parsing the HTTP
`Request information and the HTTP Response information to
`obtain cookies and authorizations contained therein; merg-
`ing the cookiesif related cookies are contained in the HTTP
`Request and the HTTP Response; forming an image iden-
`tification string by combining the URL, the merged cookies
`and the authorizations; hashing the image identification
`String to produce a hash directory; replacing unpermitted
`characters in the image identification string with predeter-
`mined replacements; dividing the image identification string
`to form a directory path having a series of individual
`directories; forming the individual directories of the direc-
`tory path in the image storage device to the extent not
`already present; and storing at least one file in a resulting
`directory identified by the directory path.
`
`[0020] As a proxy system for accelerated delivery of
`objects to a requester, one embodiment of the invention
`includes: an object storage device for storing objects, and a
`proxy server coupled between the requester’s computer and
`a network of computers. The object storage device usesa file
`system that supports directories to store the objects in files
`at directory locations within said object storage device. The
`directory location where each object
`is to be stored is
`identified by an object locator associated with the network
`together with state and authorization information. The proxy
`server intercepts a request for an object from the requester’s
`computer to the network of computers, and thensatisfies the
`
`

`

`US 2002/0169818 Al
`
`Nov. 14, 2002
`
`request by delivering the object requested from said object
`storage device to the requestor’s computer. The object
`requested from said object storage device is retrieved from
`said object storage device using a combination of an object
`locator obtained from the request together with state and
`authorization information associated with the request.
`Optionally, the proxy system can also include an accelera-
`tion unit to produce an accelerated version of certain of the
`objects stored in said object storage device. As another
`option,
`the directory structure within said object storage
`device can be used to implementa database. As still another
`option, the combination of the object locator together with
`state and authorization information identify a unique slot in
`said object storage device, and each of the slots can store
`files pertaining to a different version of an associated object.
`
`[0021] As a proxy system for accelerated delivery of
`objects to a requestor, another embodimentof the invention
`includes: an object storage device for storing objects, and a
`proxy server coupled between the requester’s computer and
`a network of computers. The object storage device uses a file
`system that supports directories to store the objects in files
`at directory locations within said object storage device. The
`directory location where each object
`is to be stored is
`identified by at least an object locator. The proxy server
`intercepts a
`request for an object from the requester’s
`computer to the nctwork of computers, and thensatisfics the
`request by delivering the object requested from said object
`storage device to the requestor’s computer. The object
`requested from said object storage device is retrieved from
`said object storage device using an object locator obtained
`from the request. Optionally, the object storage device also
`stores a current state for each of the files. As another option,
`the directory structure within said object storage device
`implements a database. As still another option, the proxy
`system can include an acceleration unit that produces an
`accelerated version of certain of the objects stored in said
`object storage device.
`
`[0022] As a proxy system for temporarily storing objects
`previously requested by a requestor, another embodiment of
`the invention includes: an object storage device for storing
`objects, a proxy server coupled between the requester’s
`computer and a network of computers, and an object storage
`device cleaner. The proxy server intercepts a request for an
`object from the requester’s computer to the network of
`computers, and then satisfies the request by delivering the
`object requested from the object storage device to the
`requestor’s computer. The object requested from the object
`storage device is retrieved from the object storage device
`using an object locator obtained fromthe request. The object
`storage device cleaner operates to clean out from the object
`storage device those objects that are aged using a plurality
`of concurrent processes or threads that operate on different
`criterion in cleaning out the object storage device.
`
`[0023] Other aspects and advantagesof the invention will
`become apparent from the following detailed description,
`taken in conjunction with the accompanying drawings,
`illustrating by way of example the principles of the inven-
`tion.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`[0024] The present inventionwill be readily understood by
`the following detailed description in conjunction with the
`
`accompanying drawings, wherein like reference numerals
`designate like structural elements, and in which:
`
`[0025] FIG. 1 is a proxy system that provides improved
`data delivery over a network according to an embodiment of
`the invention;
`
`[0026] FIG. 2 is a block diagram of a proxy system
`according to an embodimentof the invention;
`
`(0027] FIG. 3 is a flow diagram of browser processing
`whichinteracts with a proxy system according to an embodi-
`ment of the invention;
`
`[0028] FIG. 4 is a flow diagram of HTTP request pro-
`cessing according to an embodiment of the invention;
`
`[0029] FIG. 5 illustrates a flow diagram of slot creation
`processing according to an embodiment of the invention;
`
`[0030] FIG. 6 is a schematic diagram of a representative
`slot organization within an image store according to an
`embodimentof the invention;
`
`([0031] FIGS. 7A and 7B illustrate flow diagrams of
`image retrieval processing according to an embodiment of
`the invention;
`
`FIG.8 is a detailed example of a directory struc-
`[0032]
`ture for a file system in to storing image files in the image
`store according to an embodimentof the invention; and
`
`[0033] FIG. 9 is a block diagram of image store cleaner
`processing according to an embodiment of the invention.
`
`DETAILED DESCRIPTION OF THE
`INVENTION
`
`‘The invention pertains to techniques for storing
`[0034]
`objects (e.g.,
`images) in and retrieving objects from a
`storage device (e.g., image store) in a rapid and efficient
`manner. The various aspects of the invention include: stor-
`age of an object in andretrieval of an object from the storage
`device with reference to an object locator together with state
`and permission information, use of a directory structure of
`a file system to efficiently provide database structure for
`storage of the objects, storage and retrieval of object states
`as attributes of associated files in the file system, storage and
`retrieval of multiple versions of objects, and multi-threaded
`managementof the storage device.
`
`[0035] The improved techniques according to the inven-
`tion can be utilized in a variety of systems or apparatuses,
`including a proxy system having an acceleration apparatus
`(e.g., an acceleration server). Such a proxy system is able to
`produce an accelerated version of content information from
`the network, cache the accelerated version (and possibly
`original versions) for subsequent requests for the same
`information content, and supply the accelerated version of
`the information content to a requesting user. Some tech-
`niques accordingto the invention are well suited for use with
`a multi-threaded operating systemso that high performance
`operation can be obtained.
`
`[0036] The inventionis particularly well suited for use in
`a proxy system for a network(e.g., the Internet) wherein the
`database storage stores an object identifier, state information
`and permission information. The directory structure points
`to resulting directories in the storage device where one or
`more different versions of an object can be stored. The
`
`

`

`US 2002/0169818 Al
`
`Nov. 14, 2002
`
`objects are stored as files by a file system, and object states
`for the stored objects can be storedasattributes for thefiles.
`When the storage device is used as a cache device that
`provides temporary storage, the managementof the storage
`device operates to clean out the storage device to remove
`expired data as well as to prevent overflow. Although the
`storage device can generally store objects, for ease of
`understanding, much of the discussion below assumesthat
`the objects being stored are image files. However,it should
`be recognized that the objects could also pertain to a variely
`of other things such as video, audio,etc.
`
`[0037] A proxy system operates to store (e.g., caching)
`image files in a storage device (e.g., image store) so that
`these imagefiles are able to more quickly and efficiently be
`supplied to requesters coupled to the proxy system. The
`proxy system also allows requesters to view data in several
`different versions, namely, an original version and various
`possible accelerated or compressed versions. Hence, only a
`single version of the data needs to be provided on a content
`server, and the content server need not worry about provid-
`ing different versions. The construction, arrangement and
`usage of the storage device (e.g., image store) facilitates the
`rapid storage of images to andretrieval of images from the
`storage device.
`
`[0038] Embodiments of the invention are discussed below
`with reference to FIGS. 1-8. However, those skilled in the art
`will readily appreciate that the detailed description given
`herein with respect
`to these figures is for explanatory
`purposes as the invention extends beyond these limited
`embodiments.
`
`[0039] FIG. 1 is a proxy system 100 that provides
`improved data delivery over a network. The proxy system
`100 includes the proxy server 102 that couples to network
`browsers 104. The proxy server 102 is also coupled to the
`Internet 106. The Internet 106 is a collection of intercon-
`
`nected computer systems, some of which act as content
`servers. Accordingly, FIG. 1 illustrates the Internet 106
`coupled to a content server 108 as a representative onc of the
`content servers associated with the Internet 106. Addition-
`ally, the proxy system 100 includes an acceleration server
`110. The acceleration server 110 couples to the proxy server
`102 as well as the Internet 106.
`
`[0040] The proxy system 100 is able to provide improved
`content (data) delivery over the Internet 106. Namely, the
`proxy system 100 operates to speed up the response timethat
`a user of one of the browsers 104 undergoesafter requesting
`some content from the content server 108 until the requested
`contentis supplied to the user at the one of the browsers 104.
`
`[0041] The general operation of the proxy system 100 is as
`follows. Normally, as a user of one of the browsers 104
`makes a request for data from a content server on the
`Internet 106. The proxy server 102 initially intercepts the
`request
`for data from the browser 104 and determines
`whether the request for data can be satisfied locally by the
`proxy server 102 or the acceleration server 110. When the
`proxy server 102 determines that the request for data cannot
`be satisfied locally,
`the proxy server 102 forwards the
`request for data to the content server 108 through the
`Internet 106. In this case, the previously intercepted request
`for data is passed through the proxy server 102 to the content
`server 108 via the Internet 106 so that the request for data
`can be satisfied in a conventional, unaccelerated manner.
`
`[0042] On the other hand, when the proxy server 102
`determines that the request for data can be satisfied locally
`with an improved response time(i.e., accelerated delivery)
`to the user, then the proxy server 102 and the acceleration
`server 110 operate to satisfy the request for data using
`information locally stored, thereby avoiding the need to
`traverse the sluggish Internet 106 andretrieve the requested
`data from the content server 108. Also, if the acceleration
`server 110 believesit can satisfy the request for data locally
`but the necessary information is not yel locally available,
`then the acceleration server 110 operates to retrieve the
`requested data from the content server 108 with a pre-fetch
`operation and then locally store the necessary information.
`‘Thereafter,
`the acceleration server 110 can satisfy the
`request for data from local storage. In either of these cases,
`the data returned to the browser 104 in response to the
`request for data will not only be locally available but also be
`reducedin size (e.g. reducedfile size). Both of these features
`contribute to the ability of the proxy system 100 to signifi-
`cantly improve the response time in which the requested
`data can be delivered to the browser 104. Accordingly, the
`proxy server 102 acting together with the acceleration server
`110 is able to accelerate the delivery of the requested data to
`the user of the browser 104 that has made the request.
`
`[0043] During normal operation of the proxy system 100,
`the addition of the acceleration server 110 to the proxy
`system 100 causes the delivery of requested data to be
`delivered to a user in an accelerated manner. However, if the
`numberof users (i-e., clients) being serviced by the proxy
`system 100 becomessignificant and the number of acceler-
`ated versions needed at any point in time becomestoo large
`for the acceleration server 110 to handle, this concentrated
`processing burden can cause the performance of the accel-
`eration server 110, and thus the proxy system, to degrade.
`The invention resolves this potential problem by managing
`the load on the acceleration server 110 such that even in the
`
`worst case condition the performance of the proxy server
`100 is, for example, no worse than it would be had the proxy
`system been a conventional proxy scrver (i.c., without
`acceleration capabilities).
`
`[0044] FIG. 2 is a block diagram of a proxy system 200
`according to an embodiment of the invention. The proxy
`system 200 includes a proxy server 202 and an acceleration
`server 204. As an example,
`the proxy server 202 can
`correspond to the proxy server 102 illustrated in FIG. 1, and
`the acceleration server 204 can correspond to the accelera-
`tion server 110 in FIG.1.
`
`[0045] The proxy server 202 includes a proxy filter 206
`and a proxy cache 208. The proxy filter 206 monitors
`requests for data received from