John B Plevyak

US Patent:

6453319, Sep 17, 2002

Filed:

Apr 5, 2000

Appl. No.:

09/543238

Inventors:

Peter Mattis - Belmont CA
John Plevyak - San Francisco CA
Matthew Haines - Lararie NY
Adam Beguelin - San Mateo CA
Brian Totty - Foster City CA
David Gourley - Palo Alto CA

Assignee:

Inktomi Corporation - Foster City CA

International Classification:

G06F 1730

US Classification:

707100, 707103, 711118, 711119, 711120, 370236, 370252, 370429

Abstract:

A high-performance cache is disclosed. The cache is designed for time- and space-efficiency for a diverse range of information objects. Information objects are stored in portions of a non-volatile storage device called arenas, which are contiguous regions from which space is allocated in parallel. Objects are substantially contiguously allocated within an arena and are mapped by name keys and content-based object keys to a tag table, an open directory, and a directory table. The tag table is indexed by the name keys, and stores references to sets in the directory table. The tag table is compact and therefore can be stored in fast main memory, facilitating rapid lookups. The directory table is organized so that at least a frequently-accessed portion of it also usually resides in fast main memory, which further speeds lookups. The tag and directory tables are organized to quickly determine non-presence of objects. Large objects are chunked into fragments, which are chained using a forward functional-iteration mechanism, to prevent the need for mutating existing on-disk data structures.

US Patent:

6848005, Jan 25, 2005

Filed:

Apr 9, 2001

Appl. No.:

09/829873

Inventors:

John Plevyak - San Francisco CA, US
Vikas Jha - San Leandro CA, US
Ivry Semel - San Francisco CA, US
Peter Mattis - Belmont CA, US
Brian Totty - Foster City CA, US
Eric Brewer - Berkeley CA, US

Assignee:

Inktomi Corporation - San Mateo CA

International Classification:

G06F 1516

US Classification:

709233, 709235

Abstract:

A mechanism for managing data communications is provided. A circularly arranged set of buckets is disposed between input buffers and output buffers in a networked computer system. Connections among the system and clients are stored in the buckets. Each bucket in the set is successively examined, and each connection in the bucket is polled. During polling, the amount of information that has accumulated in a buffer associated with the connection since the last poll is determined. Based on the amount, a period value associated with the connection is adjusted. The connection is then stored in a different bucket that is generally identified by the sum of the current bucket number and the period value. Polling continues with the next connection and the next bucket. In this way, the elapsed time between successive polls of a connection automatically adjusts to the actual operating bandwidth or data communication speed of the connection.

US Patent:

6915307, Jul 5, 2005

Filed:

May 6, 2002

Appl. No.:

10/140497

Inventors:

Peter Mattis - Belmont CA, US
John Plevyak - San Francisco CA, US
Matthew Haines - Laramie WY, US
Adam Beguelin - San Mateo CA, US
Brian Totty - Foster City CA, US
David Gourley - Palo Alto CA, US

Assignee:

Inktomi Corporation - Foster City CA

International Classification:

G06F017/30

US Classification:

707103R, 707100, 707102, 7071041, 717121, 717170, 717216, 719310

Abstract:

The foregoing needs and other needs are addressed by the present invention, which provides, in one aspect, a mechanism for locating a data object. According to an aspect of the present invention, key values for data objects are generated, each key value may contain a first subkey value and a second subkey value. A mapping associates the first subkey values with storage locations. A particular first subkey value is mapped to storage location that contains second subkeys of a set of key values that correspond to the first subkey value. The storage location also includes additional information that may be used to locate objects associated with the set of key values.

US Patent:

62928805, Sep 18, 2001

Filed:

Apr 15, 1998

Appl. No.:

9/060886

Inventors:

Peter Mattis - Belmont CA
John Plevyak - San Francisco CA
Matthew Haines - Laramie WY
Adam Beguelin - San Mateo CA
Brian Totty - Foster City CA
David Gourley - Palo Alto CA

Assignee:

Inktomi Corporation - Foster City CA

International Classification:

G06F 1200

US Classification:

711216

Abstract:

A method for caching information objects is provided. Information objects are stored in portions of a non-volatile storage device called arenas, which are contiguous regions from which space is allocated in parallel. Objects are contiguously allocated within an arena and are mapped to directory tables that provide an efficient search mechanism. Each object is identified by a name key and a content key. The name key is constructed by applying a hash function to the composition of the name or URL of the object along with implicit or explicit context about the request. The content key is constructed by applying a hash function to the entire contents of the object data. Buckets and blocks in the directory tables store tags and subkeys derived from the keys. Since duplicate objects that have different names will hash to the same content key, the cache can detect duplicate objects even though they have different names, and store only one copy of the object. As a result, cache storage usage is dramatically reduced, and tracking object aliases is not required.

US Patent:

63082144, Oct 23, 2001

Filed:

Sep 23, 1998

Appl. No.:

9/159468

Inventors:

John Plevyak - San Francisco CA
Vikas Jha - San Leandro CA
Ivry Semel - San Francisco CA
Peter Mattis - Belmont CA
Brian Totty - Foster City CA
Eric Brewer - Berkeley CA

Assignee:

Inktomi Corporation - Foster City CA

International Classification:

G06F 1516
G06F 15173

US Classification:

709233

Abstract:

A method and apparatus for managing data communications is provided. A circularly arranged set of buckets is disposed between input buffers and output buffers in a networked computer system. Connections among the system and clients are stored in the buckets. Each bucket in the set is successively examined, and each connection in the bucket is polled. During polling, the amount of information that has accumulated in a buffer associated with the connection since the last poll is determined. Based the amount, a period value associated with the connection is adjusted. The connection is then stored in a different bucket that is generally identified by the sum of the current bucket number and the period value. Polling continues with the next connection and the next bucket. In this way, the elapsed time between successive polls of a connection automatically adjusts to the actual operating bandwidth or data communication speed of the connection.

US Patent:

62893580, Sep 11, 2001

Filed:

Apr 15, 1998

Appl. No.:

9/060887

Inventors:

Peter Mattis - Belmont CA
John Plevyak - San Francisco CA
Matthew Haines - Laramie WY
Adam Beguelin - San Mateo CA
Brian Totty - Foster City CA
David Gourley - Palo Alto CA

Assignee:

Inktomi Corporation - Foster City CA

International Classification:

G06F 1780

US Classification:

707203

Abstract:

A method is provided for caching and delivering an alternate version from among a plurality of alternate versions of information objects. One or more alternate versions of an information object, for example, versions of the information object that are prepared in different languages or compatible with different systems, are stored in an object cache database. In the cache, a vector of alternates is associated with a key value that identifies the information object. The vector of alternates stores information that describes the alternate, the context and constraints of the object's use, and a reference to the location of the alternate's object content. When a subsequent client request for the information object is received, the cache extracts information from the client request, and attempts to select an acceptable and optimal alternate from the vector by matching the request information to the cached contextual information in the vector of alternates. This selection is performed in a time- and space-efficient manner. Accordingly, the cache can deliver different versions of an information object based on the metadata and criteria specified in a request to the cache.

US Patent:

62090038, Mar 27, 2001

Filed:

Jul 17, 1998

Appl. No.:

9/061136

Inventors:

Peter Mattis - Belmont CA
John Plevyak - San Francisco CA
Matthew Haines - Laramie WY
Adam Beguelin - San Mateo CA
Brian Totty - Foster City CA
David Gourley - Palo Alto CA

Assignee:

Inktomi Corporation - Foster City CA

International Classification:

G06F12/00

US Classification:

707206

Abstract:

A method for garbage collection in a cache of information objects is provided. A non-volatile storage device is segmented into storage areas called pools. Each pool has a pool header and a plurality of arenas. Each arena stores one or more fragments of an object. Header information for each arena is stored in the pool header in which that arena is stored. Each fragment comprises a fragment header and fragment data. The garbage collection periodically selects a pool that is storing an amount of data greater than a minimum storage value or high water mark. Each arena in the pool is examined and selected for garbage collection according to selection criteria. Each fragment within a selected arena is examined based upon a second set of selection criteria that determine whether the fragment is retained or deleted. If the fragment is deleted, all other fragments in the storage device that relate to that fragment's object are also deleted. When a fragment arena is retained, it is moved into contiguous storage in another available arena.

US Patent:

61286230, Oct 3, 2000

Filed:

Apr 15, 1998

Appl. No.:

9/060866

Inventors:

Peter Mattis - Belmont CA
John Plevyak - San Francisco CA
Matthew Haines - Laramie WY
Adam Beguelin - San Mateo CA
Brian Totty - Foster City CA
David Gourley - Palo Alto CA

Assignee:

Inktomi Corporation - San Mateo CA

International Classification:

G06F 1730

US Classification:

707103

Abstract:

A high-performance cache is disclosed. The cache is designed for time- and space-efficiency for a diverse range of information objects. Information objects are stored in portions of a non-volatile storage device called arenas, which are contiguous regions from which space is allocated in parallel. Objects are substantially contiguously allocated within an arena and are mapped by name keys and content-based object keys to a tag table, an open directory, and a directory table. The tag table is indexed by the name keys, and stores references to sets in the directory table. The tag table is compact and therefore can be stored in fast main memory, facilitating rapid lookups. The directory table is organized so that at least a frequently-accessed portion of it also usually resides in fast main memory, which further speeds lookups. The tag and directory tables are organized to quickly determine non-presence of objects. Large objects may be chunked into fragments, which are chained using a forward functional-iteration mechanism, to prevent the need for mutating existing on-disk data structures.