History database structure for Usenet
First Claim
1. 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.
26 Assignments
0 Petitions
Accused Products
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.
-
Citations
28 Claims
-
1. 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11)
-
-
12. 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. - View Dependent Claims (13, 14, 15, 16, 17, 18, 19)
-
-
20. 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.
-
-
21. 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. - View Dependent Claims (22, 23, 24, 25, 26, 27, 28)
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.
-
-
23. 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.
-
24. 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.
-
25. 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.
-
26. 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.
-
27. The system of claim 26 where said cache is implemented in random access memory (RAM).
-
28. 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.
Specification