公开(公告)号：US06687732B1

公开(公告)日：2004-02-03

申请号：US09369659

申请日：1999-08-05

申请人： Rajeev Bector ,  David Gourley ,  Paul Andre Gauthier ,  Brian Totty

发明人： Rajeev Bector ,  David Gourley ,  Paul Andre Gauthier ,  Brian Totty

IPC分类号： G06F1516

CPC分类号： H04L29/12009 ,  H04L29/12481 ,  H04L61/2557 ,  H04L67/28 ,  H04L67/2814 ,  H04L67/327

摘要： An Internet Protocol driver executed by a network interface card, or a network address translation module, includes a mechanism that enables a server to bypass packets associated with certain destinations, sources, or a combination of the two based upon their IP address. When a packet arrives at the network interface card, the driver extracts a source IP address and a destination IP address from the packet. The driver searches a table to locate a rule matching one of the addresses. If a match is found, the packet is bypassed. If no match is found, the packet is sent on to an indexing and caching server for further processing. The bypass rules may be adaptively and dynamically generated when a message causes a remote server to respond with an error code. The dynamically generated bypass rules prevent the first server from sending subsequent requests to the remote server, thereby insulating the indexing and caching server from unnecessary network traffic.

摘要翻译： 由网络接口​​卡或网络地址转换模块执行的因特网协议驱动器包括使得服务器能够基于其IP地址绕过与某些目的地，源或两者的组合相关联的分组的机制。 当数据包到达网络接口卡时，驱动程序从数据包中提取源IP地址和目的IP地址。 驱动程序搜索表以查找匹配其中一个地址的规则。 如果找到匹配，则会绕过该数据包。 如果没有找到匹配，则将数据包发送到索引和缓存服务器进行进一步处理。 当消息导致远程服务器使用错误代码进行响应时，旁路规则可以自适应地和动态地生成。 动态生成的旁路规则阻止第一个服务器向远程服务器发送后续请求，从而使索引和缓存服务器与不必要的网络流量隔离。

公开(公告)号：US06209003B1

公开(公告)日：2001-03-27

申请号：US09061136

申请日：1998-07-17

申请人： Peter Mattis ,  John Plevyak ,  Matthew Haines ,  Adam Beguelin ,  Brian Totty ,  David Gourley

发明人： Peter Mattis ,  John Plevyak ,  Matthew Haines ,  Adam Beguelin ,  Brian Totty ,  David Gourley

IPC分类号： G06F1200

CPC分类号： G06F12/0253 ,  G06F12/023 ,  Y10S707/99957

摘要： 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. A computer program product, computer apparatus, and data signal embodied in a carrier wave, configured to carry out the steps of the method, are also disclosed.

摘要翻译： 提供了一种在信息对象缓存中进行垃圾收集的方法。 非易失性存储设备被分割成称为池的存储区域。 每个游泳池都有一个游泳池首标和多个场地。 每个竞技场存储一个或多个对象的片段。 每个竞技场的标题信息存储在存储该竞技场的池标题中。 每个片段包含片段标题和片段数据。 垃圾收集周期性地选择存储大于最小存储值或高水位标记的数据量的池。 根据选择标准，对泳池中的每个竞技场进行检查和选择进行垃圾收集。 基于确定片段是否被保留或删除的第二组选择标准来检查所选竞技场内的每个片段。 如果片段被删除，存储设备中与该片段对象相关的所有其他片段也将被删除。 当片段竞技场被保留时，它被移动到另一个可用竞技场中的连续存储中。 还公开了一种体现在载波中的计算机程序产品，计算机装置和数据信号，被配置为执行该方法的步骤。

公开(公告)号：US6128623A

公开(公告)日：2000-10-03

申请号：US60866

申请日：1998-04-15

申请人： Peter Mattis ,  John Plevyak ,  Matthew Haines ,  Adam Beguelin ,  Brian Totty ,  David Gourley

发明人： Peter Mattis ,  John Plevyak ,  Matthew Haines ,  Adam Beguelin ,  Brian Totty ,  David Gourley

IPC分类号： G06F12/00 ,  G06F13/00 ,  G06F17/30 ,  H04L29/08

CPC分类号： G06F17/30902 ,  H04L67/2842 ,  Y10S707/955 ,  Y10S707/99944

摘要： 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. Garbage collection periodically moves objects within an arena or to other arenas so that inactive objects are deleted and free space becomes contiguous. Because the objects are substantially contiguously allocated, reading and writing an typical object requires only one or two disk head actuator movements; thus, the cache can efficiently and smoothly stream data off of the storage device, providing optimal delivery of multimedia objects. The disclosure also encompasses a computer apparatus, computer program product, and computer data signal embodied in a carrier wave that are similarly configured.

摘要翻译： 公开了一种高性能缓存。 高速缓存旨在为各种信息对象提供时间和空间效率。 信息对象存储在称为区域的非易失性存储设备的部分中，这些区域是并行分配空间的连续区域。 对象在竞技场内基本连续分配，并通过名称键和基于内容的对象键映射到标签表，打开目录和目录表。 标签表由名称键索引，并存储对目录表中的集合的引用。 标签表是紧凑的，因此可以存储在快速主存储器中，便于快速查找。 目录表被组织，使得至少其频繁访问的部分通常也驻留在快速主存储器中，这进一步加快了查找速度。 标签和目录表被组织以快速确定不存在对象。 可以使用前向功能迭代机制将大对象分块成片段，以阻止对现有磁盘数据结构进行突变的需要。 垃圾收集会周期性地移动竞技场内的对象或其他场所，从而删除非活动对象并使可用空间变得连续。 由于物体基本连续分配，读取和写入典型物体仅需要一个或两个盘头致动器运动; 因此，高速缓存可以有效地平滑地将数据从存储设备流出，从而提供多媒体对象的最佳传送。 本公开还包括计算机设备，计算机程序产品和体现在类似配置的载波中的计算机数据信号。

公开(公告)号：US09235848B1

公开(公告)日：2016-01-12

申请号：US12169599

申请日：2008-07-08

申请人： David Gourley ,  Brian Totty ,  Ed Haslam ,  Paul Gauthier ,  Gary Lerhaupt ,  Mike Y. Chen ,  Christopher Colby

发明人： David Gourley ,  Brian Totty ,  Ed Haslam ,  Paul Gauthier ,  Gary Lerhaupt ,  Mike Y. Chen ,  Christopher Colby

IPC分类号： G10L17/00 ,  G06Q30/02

CPC分类号： G06Q30/0255 ,  G06Q30/0201 ,  G06Q30/0209 ,  G06Q30/0254 ,  G06Q50/01

摘要： Social media networking applications, web sites, and services creates implicit relationships between users based on their interest or participation in real-world and optionally virtual or online activities in addition to explicitly defined peer relationships. User profiles, activity entities, and expressions may be associated with metadata to assist in searching and navigation. Metadata is implicitly associated with user profiles, activity entities, expressions, or other data entities based on user behavior using metadata collector. A metadata collector is a poll, survey, list, questionnaire, census, test, game, or other type of presentation adapted to solicit user interaction. A metadata collector is associated with metadata elements. When users interact with a metadata collector, their user profiles and the data entities included in their interactions become associated with the metadata elements of the metadata collector. These metadata element associations may then be used for any purpose.

摘要翻译： 社交媒体网络应用程序，网站和服务，除了明确定义的对等关系之外，还基于他们对现实世界以及可选的虚拟或在线活动的兴趣或参与，创建了用户之间的隐含关系。 用户配置文件，活动实体和表达式可以与元数据相关联，以帮助搜索和导航。 基于使用元数据收集器的用户行为，元数据隐含地与用户简档，活动实体，表达式或其他数据实体相关联。 元数据收集器是调查，调查，列表，问卷调查，人口普查，测试，游戏或适用于征求用户交互的其他类型的演示。 元数据收集器与元数据元素相关联。 当用户与元数据收集器进行交互时，其用户简档和其交互中包含的数据实体将与元数据收集器的元数据元素相关联。 然后可以将这些元数据元素关联用于任何目的。

公开(公告)号：US06453319B1

公开(公告)日：2002-09-17

申请号：US09543238

申请日：2000-04-05

申请人： Peter Mattis ,  John Plevyak ,  Matthew Haines ,  Adam Beguelin ,  Brian Totty ,  David Gourley

发明人： Peter Mattis ,  John Plevyak ,  Matthew Haines ,  Adam Beguelin ,  Brian Totty ,  David Gourley

IPC分类号： G06F1730

CPC分类号： G06F17/30902 ,  H04L67/2842 ,  Y10S707/955 ,  Y10S707/99944

摘要： 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. Garbage collection periodically moves objects within an arena or to other arenas. Additionally, for a plurality of counters, the following is computed: (1) the sum of values stored in the counters, and (2) the maximum value that can be represented by the coimters. Each of the counters are decremented when the sum is greater than half of the maximum value. Each of the counters is associated with an information object, which is deleted when a counter is decremented to zero.

摘要翻译： 公开了一种高性能缓存。 高速缓存旨在为各种信息对象提供时间和空间效率。 信息对象存储在称为区域的非易失性存储设备的部分中，这些区域是并行分配空间的连续区域。 对象在竞技场内基本连续分配，并通过名称键和基于内容的对象键映射到标签表，打开目录和目录表。 标签表由名称键索引，并存储对目录表中的集合的引用。 标签表是紧凑的，因此可以存储在快速主存储器中，便于快速查找。 目录表被组织，使得至少其频繁访问的部分通常也驻留在快速主存储器中，这进一步加快了查找速度。 标签和目录表被组织以快速确定不存在对象。 大型对象被分块，使用前向功能迭代机制链接，以防止对现有磁盘数据结构进行突变的需要。 垃圾收集周期性地将场内的物体移动到其他场地。 另外，对于多个计数器，计算以下内容：（1）存储在计数器中的值的总和，以及（2）可由coimter表示的最大值。 当和大于最大值的一半时，每个计数器递减。 每个计数器都与一个信息对象相关联，当一个计数器递减到零时被删除。

公开(公告)号：US06289358B1

公开(公告)日：2001-09-11

申请号：US09060887

申请日：1998-04-15

申请人： Peter Mattis ,  John Plevyak ,  Matthew Haines ,  Adam Beguelin ,  Brian Totty ,  David Gourley

发明人： Peter Mattis ,  John Plevyak ,  Matthew Haines ,  Adam Beguelin ,  Brian Totty ,  David Gourley

IPC分类号： G06F1780

CPC分类号： G06F17/30902 ,  H04L67/2842 ,  H04L69/329 ,  Y10S707/918 ,  Y10S707/99954

摘要： 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. As a result, the information delivered by the cache is customized for the requesting client, without requiring access to the original object server.

摘要翻译： 提供了一种用于从多个替代版本的信息对象中缓存并递送备用版本的方法。 信息对象的一个​​或多个替代版本，例如，以不同语言准备或与不同系统兼容的信息对象的版本被存储在对象缓存数据库中。 在缓存中，交替的向量与标识信息对象的键值相关联。 交替的向量存储描述对象使用的备用，上下文和约束的信息，以及对替代对象内容的位置的引用。 当接收到对信息对象的后续客户端请求时，高速缓存从客户端请求中提取信息，并尝试通过将请求信息与交替的向量中的缓存的上下文信息相匹配来从向量中选择可接受和最佳的替代。 该选择以时间和空间有效的方式执行。 因此，缓存可以基于在向高速缓存的请求中指定的元数据和标准来传送信息对象的不同版本。 因此，由缓存提供的信息是针对请求的客户端而定制的，而不需要访问原始对象服务器。

公开(公告)号：US06292880B1

公开(公告)日：2001-09-18

申请号：US09060886

申请日：1998-04-15

申请人： Peter Mattis ,  John Plevyak ,  Matthew Haines ,  Adam Beguelin ,  Brian Totty ,  David Gourley

发明人： Peter Mattis ,  John Plevyak ,  Matthew Haines ,  Adam Beguelin ,  Brian Totty ,  David Gourley

IPC分类号： G06F1200

CPC分类号： G06F17/30902 ,  Y10S707/99937

摘要： 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. The disclosure also encompasses a computer apparatus, computer program product, and computer data signal embodied in a carrier wave that are configured similarly.

摘要翻译： 提供了一种用于缓存信息对象的方法。 信息对象存储在称为区域的非易失性存储设备的部分中，这些区域是并行分配空间的连续区域。 对象在场景中被连续分配，并被映射到提供有效的搜索机制的目录表。 每个对象由一个名称键和一个内容密钥来标识。 通过将哈希函数应用于对象的名称或URL以及关于请求的隐式或显式上下文的构成来构造名称键。 通过将哈希函数应用于对象数据的全部内容来构造内容密钥。 目录表中的桶和块存储从键派生的标签和子项。 由于具有不同名称的重复对象将散列到相同的内容密钥，所以缓存可以检测重复的对象，即使它们具有不同的名称，并且仅存储对象的一个​​副本。 因此，缓存存储使用率大大降低，并且不需要跟踪对象别名。 本公开还包括类似地配置在载波中体现的计算机装置，计算机程序产品和计算机数据信号。

公开(公告)号：US6128627A

公开(公告)日：2000-10-03

申请号：US60974

申请日：1998-04-15

申请人： Peter Mattis ,  John Plevyak ,  Matthew Haines ,  Adam Beguelin ,  Brian Totty ,  David Gourley

发明人： Peter Mattis ,  John Plevyak ,  Matthew Haines ,  Adam Beguelin ,  Brian Totty ,  David Gourley

IPC分类号： G06F17/30

CPC分类号： G06F17/30315 ,  Y10S707/99953

摘要： A method for consistently storing cached objects in the presence of failures is provided. This method ensures atomic object consistency--in the event of failure and restart, an object will either be completely present or completely absent from the cache, never truncated or corrupted. Furthermore, this consistency comes without any time-consuming data structure reconstruction on restart. In this scheme, objects are indexed by a directory table that is stored in main memory and mapped to non-volatile storage, and changes to the directory table are buffered into an open directory that is stored in main memory. Cache objects are either stored in volatile aggregation buffers or in segments of non-volatile disk storage called arenas. Objects are first coalesced into memory-based aggregation buffers, and later committed to disk. Locking is used to control parallel storage to aggregation buffers. Directory entries pointing to objects are only permitted to be written to persistent disk storage after the target objects are themselves committed to disk, preventing dangling pointers. Periodically, when the contents of open directory entries point to objects that are stably stored on disk, the open directory entries are copied into the directory table and committed to non-volatile storage. The disclosure also encompasses a computer program product, computer apparatus, and computer data signal configured similarly.

摘要翻译： 提供了一种在出现故障时一直存储缓存对象的方法。 此方法可确保原子对象一致性 - 在发生故障和重新启动的情况下，对象将完全存在或完全不存在于缓存中，不会被截断或损坏。 此外，这种一致性在重新启动时没有任何耗时的数据结构重建。 在该方案中，对象被存储在主存储器中并映射到非易失性存储器的目录表进行索引，并将目录表的更改缓存到存储在主存储器中的打开目录中。 缓存对象或者存储在易失性聚合缓冲区中，或存储在称为区域的非易失性磁盘存储器的段中。 对象首先合并到基于内存的聚合缓冲区中，然后将其提交到磁盘。 锁定用于控制并行存储到汇聚缓冲区。 指向对象的目录条目只允许在目标对象自身提交到磁盘后写入持久磁盘存储器，从而防止悬挂指针。 定期地，当打开的目录条目的内容指向稳定存储在磁盘上的对象时，打开的目录条目被复制到目录表中并提交到非易失性存储。 本公开还包括类似地配置的计算机程序产品，计算机设备和计算机数据信号。

公开(公告)号：US06915307B1

公开(公告)日：2005-07-05

申请号：US10140497

申请日：2002-05-06

申请人： Peter Mattis ,  John Plevyak ,  Matthew Haines ,  Adam Beguelin ,  Brian Totty ,  David Gourley

发明人： Peter Mattis ,  John Plevyak ,  Matthew Haines ,  Adam Beguelin ,  Brian Totty ,  David Gourley

IPC分类号： G06F17/30

CPC分类号： G06F17/30067 ,  Y10S707/99943 ,  Y10S707/99944 ,  Y10S707/99945

摘要： 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.

摘要翻译： 上述需求和其他需要由本发明来解决，本发明在一个方面提供了一种用于定位数据对象的机制。 根据本发明的一个方面，生成数据对象的键值，每个键值可以包含第一子键值和第二子键值。 映射将第一个子项值与存储位置相关联。 特定的第一子密钥值被映射到包含与第一子密钥值对应的一组密钥值的第二子密钥的存储位置。 存储位置还包括可用于定位与该组键值相关联的对象的附加信息。

公开(公告)号：US07035864B1

公开(公告)日：2006-04-25

申请号：US09573305

申请日：2000-05-18

申请人： Adam J. Ferrari ,  David Gourley ,  Keith Johnson ,  Frederick C. Knabe ,  Daniel Tunkelang ,  John S. Walter

发明人： Adam J. Ferrari ,  David Gourley ,  Keith Johnson ,  Frederick C. Knabe ,  Daniel Tunkelang ,  John S. Walter

IPC分类号： G06F7/00

CPC分类号： G06F17/30398 ,  G06F3/0482 ,  G06F17/30 ,  G06F17/30873 ,  Y10S707/962 ,  Y10S707/99932 ,  Y10S707/99933 ,  Y10S707/99935 ,  Y10S707/99943

摘要： A data-driven, hierarchical information navigation system and method enable search of sets of documents or other materials by certain common attributes that characterize the materials. The invention includes several aspects of a data-driven, hierarchical navigation system that employs this navigation mode. The navigation system of the present invention includes features of an interface, a knowledge base and a taxonomy definition process and a classification process for generating the knowledge base, a graph-based navigable data structure and method for generating the data structure, World Wide Web-based applications of the system, and methods of implementing the system. Users are able to search or browse a particular collection of documents by selecting desired values for the attributes. A data-driven, hierarchical information navigation system and method enable this navigation mode by associating terms with the materials, defining a set of hierarchical relationships among the terms, and providing a guided search mechanism based on the relationship between the terms.

摘要翻译： 数据驱动的分级信息导航系统和方法可以通过表征材料的某些共同属性来搜索文档或其他材料集合。 本发明包括采用该导航模式的数据驱动的分级导航系统的若干方面。 本发明的导航系统包括接口的特征，知识库和分类定义过程以及用于生成知识库的分类过程，用于生成数据结构的基于图形的可导航数据结构和方法，万维网 - 系统的基于应用的系统和实现系统的方法。 用户可以通过选择属性的所需值来搜索或浏览特定的文档集合。 数据驱动的层级信息导航系统和方法通过将术语与材料相关联，在术语之间定义一组分层关系，并且基于术语之间的关系提供引导搜索机制来实现该导航模式。