US6507847B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
History database structure for Usenet
Assignee: HIGHWINDS SOFTWARE LLC
•
Filing: 1999-12-17
•
Granted: 2003-01-14
•
Expires: 2019-12-17
Abstract
Abstract A database structure is disclosed that is particularly suited to Usenet servers. The database is thread-hot, synchronized, and highly parallel. In addition, the database structure enables high speed read/write activity with low latency search processes. The database is statically sized, self-expiring, and self-reparing. No throttling or down-time is required in the normal course of operations. The database is accompanied by several caches to provide a system capable of high perfomance Usenet operations. The invention comprises a "key-value" database, several pointers, linked lists, locks, and queues. All of these elements are arranged to operate in a synergistic manner to achieve a highly efficient history database. Under normal conditions, most of the queries from newsfeeds can be satisfied from a cache of the latest history database entries because many of the newsfeeds will offer the same articles as the other newsfeeds. The same cache also provides space in which to store and aggregate the latest additions to the database such that both "read" and "write" operations to the disk are optimized.
Inventors
- 👤 Robert M. Fleischman
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-05 08:15
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/20; G06F16/22; G06F16/2228; G06F16/2255; G06F16/23; G06F16/2308; G06F16/2336; G06F16/2358; Y; Y10; Y10S; Y10S707/00; Y10S707/912; Y10S707/943; Y10S707/99931; Y10S707/99938; Y10S707/99941; Y10S707/99942; Y10S707/99943; Y10S707/99944; Y10S707/99945; Y10S707/99951; Y10S707/99952; Y10S707/99953
Claims Analysis
Total Claims: 32
Claim 1
Independent Claim
161 words
A history database for a Usenet server to record the status of news articles, comprising: (a) a hashing algorithm for producing at least a first hash value and a second hash value from a unique identifier that identifies a news article; (b) a key-value database comprising a value section and a record section, wherein said value section has a plurality of storage buckets each containing at least a pointer, and wherein said record section has a plurality of linked records and a record pointer; and wherein said unique identifier is hashed to one of said plurality of storage buckets based upon at least a portion of said first hash value, and wherein said pointer within said one of said plurality of storage buckets points to a head of said plurality of linked records, and wherein said second hash value is compared sequentially against said plurality of linked records to determine whether said news article is already recorded in said history database.
Claim 2
Dependent Claim
161 words
A history database for a Usenet server to record the status of news articles, comprising: (a) a hashing algorithm for producing at least a first hash value and a second hash value from a unique identifier that identifies a news article; (b) a key-value database comprising a value section and a record section, wherein said value section has a plurality of storage buckets each containing at least a pointer, and wherein said record section has a plurality of linked records and a record pointer; and wherein said unique identifier is hashed to one of said plurality of storage buckets based upon at least a portion of said first hash value, and wherein said pointer within said one of said plurality of storage buckets points to a head of said plurality of linked records, and wherein said second hash value is compared sequentially against said plurality of linked records to determine whether said news article is already recorded in said history database.
Claim 3
Dependent Claim
16 words
The system of claim 1 , further comprising a quicklist cache for caching currently active threads.
Claim 4
Dependent Claim
13 words
The system of claim 1 , wherein said key-value database is statically sized.
Claim 5
Dependent Claim
24 words
The system of claim 1 , further comprising a record cache, having a read portion and a write portion separated by a cache pointer.
Claim 6
Dependent Claim
17 words
The system of claim 4 , wherein said record cache is configured to cache recently added records.
Claim 7
Dependent Claim
31 words
The system of claim 5 , wherein said record cache is configured to write recently added records to said key-value database in contiguous areas of storage during each cache flush operation.
Claim 8
Dependent Claim
26 words
The system of claim 1 , wherein said record pointer incrementally points to records in said record section that have persisted longest within said history database.
Claim 9
Dependent Claim
14 words
The system of claim 7 , further comprising a lock on said record pointer.
Claim 10
Dependent Claim
33 words
The system of claim 1 , wherein each of said linked records has a plurality of fields including a first hash field, a second hash field, a payload field, and a linking pointer.
Claim 11
Dependent Claim
32 words
The system of claim 9 , wherein said linking pointer of each record is set to point at the next most recently added record that hashed to the same first hash value.
Claim 12
Dependent Claim
20 words
The system of claim 9 , wherein said payload field contains a reference to a location within an article database.
Claim 13
Independent Claim
112 words
A method for operating a history database for a server, comprising the steps of: (a) receiving a unique identifier at the server; (b) hashing said unique identifier into at least a first hash value and a second hash value; (c) mapping said first hash value into a storage location within a value database, wherein said storage location contains at least a record pointer to a linked list of records, said records comprised of at least the following: (i) a first hash field; (ii) a second hash field; (iii) a payload field; and (iv) a linking pointer; and (d) searching said linked list of records for a match of said second hash value.
Claim 14
Independent Claim
112 words
A method for operating a history database for a server, comprising the steps of: (a) receiving a unique identifier at the server; (b) hashing said unique identifier into at least a first hash value and a second hash value; (c) mapping said first hash value into a storage location within a value database, wherein said storage location contains at least a record pointer to a linked list of records, said records comprised of at least the following: (i) a first hash field; (ii) a second hash field; (iii) a payload field; and (iv) a linking pointer; and (d) searching said linked list of records for a match of said second hash value.
Claim 15
Dependent Claim
19 words
The method of claim 12 , further comprising the step of caching currently active threads in a quicklist cache.
Claim 16
Dependent Claim
15 words
The method of claim 13 , further comprising the step of locking said quicklist cache.
Claim 17
Dependent Claim
24 words
The method of claim 12 , further comprising the step of caching the most current records in a read cache having a cache pointer.
Claim 18
Dependent Claim
24 words
The method of claim 15 , further comprising the step of flushing said read cache in contiguous areas of storage within said key-value database.
Claim 19
Dependent Claim
19 words
The method of claim 15 , further comprising the step of synchronizing said record pointer with said cache pointer.
Claim 20
Dependent Claim
36 words
The method of claim 12 , further comprising the step of incrementally pointing said record pointer along said record section to facilitate overwriting records in said record section that have persisted longest within said history database.
Claim 21
Dependent Claim
15 words
The method of claim 18 , further comprising the step of locking said record pointer.
Claim 22
Dependent Claim
174 words
A history database for a Usenet server to record the status of news articles, comprising: (a) a hashing algorithm for producing at least a first hash value and a second hash value from a unique identifier that identifies a news article; (b) a key-value database comprising a value section and a record section, wherein said value section has a plurality of storage buckets each containing at least a pointer, and wherein said record section has a plurality of linked records; (c) a record cache, having a read portion and a write portion separated by a cache pointer and wherein said unique identifier is hashed to one of said plurality of storage buckets based upon at least a portion of said first hash value, and wherein said pointer within said one of said plurality of storage buckets points to a head of said plurality of linked records, and wherein said second hash value is compared sequentially against said plurality of linked records to determine whether said news article is already recorded in said history database.
Claim 23
Dependent Claim
174 words
A history database for a Usenet server to record the status of news articles, comprising: (a) a hashing algorithm for producing at least a first hash value and a second hash value from a unique identifier that identifies a news article; (b) a key-value database comprising a value section and a record section, wherein said value section has a plurality of storage buckets each containing at least a pointer, and wherein said record section has a plurality of linked records; (c) a record cache, having a read portion and a write portion separated by a cache pointer and wherein said unique identifier is hashed to one of said plurality of storage buckets based upon at least a portion of said first hash value, and wherein said pointer within said one of said plurality of storage buckets points to a head of said plurality of linked records, and wherein said second hash value is compared sequentially against said plurality of linked records to determine whether said news article is already recorded in said history database.
Claim 24
Independent Claim
137 words
A system for communicating Usenet articles, comprising: code for receiving an offer to download a Usenet article, wherein said offer comprises a unique identifier of said Usenet article; code for hashing said unique identifier to a hash memory identifier of a memory location that stores a pointer to a first record of a linked list that maintains a history of selected previously downloaded Usenet articles; code for searching a lock table to determine whether a previous offer to download said Usenet article is being processed; and code for searching said linked list utilizing said pointer to determine whether said Usenet article has been download, wherein said code for searching said linked list is operable only when said code for searching said lock table determines that a previous offer to download said Usenet article is not being processed.
Claim 25
Independent Claim
137 words
A system for communicating Usenet articles, comprising: code for receiving an offer to download a Usenet article, wherein said offer comprises a unique identifier of said Usenet article; code for hashing said unique identifier to a hash memory identifier of a memory location that stores a pointer to a first record of a linked list that maintains a history of selected previously downloaded Usenet articles; code for searching a lock table to determine whether a previous offer to download said Usenet article is being processed; and code for searching said linked list utilizing said pointer to determine whether said Usenet article has been download, wherein said code for searching said linked list is operable only when said code for searching said lock table determines that a previous offer to download said Usenet article is not being processed.
Claim 26
Dependent Claim
38 words
The system of claim 21 further comprising: code for declining said offer to download said Usenet article when said code for searching said lock table determines that a previous offer to download said Usenet article is being processed.
Claim 27
Dependent Claim
33 words
The system of claim 21 further comprising: code for declining said offer to download said Usenet article when said code for searching said linked-list determines that said Usenet article has been previously downloaded.
Claim 28
Dependent Claim
34 words
The system of claim 22 further comprising: code for accepting said offer to download said Usenet article when said code for searching said linked-list determines that said Usenet article has not been previously downloaded.
Claim 29
Dependent Claim
36 words
The system of claim 21 wherein said code for searching said linked-list is operable to stop searching when a last record in said linked-list points to a memory location associated with a different hash memory identifier.
Claim 30
Dependent Claim
56 words
The system of claim 21 further comprising: code for searching a cache that identifies at least Usenet articles that have been recently downloaded, wherein said code for searching a cache is operable after said code for searching a lock table and said code for searching a cache is operable before said code for searching said linked-list.
Claim 31
Dependent Claim
15 words
The system of claim 26 where said cache is implemented in random access memory (RAM).
Claim 32
Dependent Claim
31 words
The system of claim 27 further comprising: code for flushing said cache by writing cached information as a linked list that is stored in block-wise contiguous portions of a storage medium.
References Cited (Backward Citations)
US5778388A
Cited
US5857181A
Cited
US5953732A
Cited
US5963208A
Cited
US5878233A
Cited
US5717919A
Cited
US5974417A
Cited
US5873084A
Cited
US5835718A
Cited
US5893911A
Cited
US5884282A
Cited
US5905863A
Cited
US5915249A
Cited
US5987460A
Cited
US5987480A
Cited
US5995105A
Cited
US6016475A
Cited
US5953528A
Cited
US6141664A
Cited
US5924072A
Cited
US5877759A
Cited
US6023684A
Cited
US6266667B1
Cited
US6012067A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2006-01-13 | 2006-07-15 | 2007-01-14 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2010-01-13 | 2010-07-15 | 2011-01-14 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2014-01-13 | 2014-07-15 | 2015-01-14 | $7700.00 | Window Closed / Lapsed |