초록 ▼

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. O

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. A method of managing a plurality of counters stored in a computer memory, comprising the steps of:computing a sum by summing values actually stored in each of the plurality of counters; determining the maximum value that can be stored in each of the plurality of counters; determining a maximum su

1. A method of managing a plurality of counters stored in a computer memory, comprising the steps of:computing a sum by summing values actually stored in each of the plurality of counters; determining the maximum value that can be stored in each of the plurality of counters; determining a maximum sum value by summing the maximum values that can be stored in each of the plurality of counters; determining a threshold value based on the maximum sum value; and decrementing each of the counters when the sum is greater than the threshold value that is based on a maximum sum value.