High speed non-concurrency controlled database

• US 20070100808A1
• Filed: 12/19/2006
• Published: 05/03/2007
• Est. Priority Date: 11/01/2001
• Status: Abandoned Application

• Current Assignee: VeriSign, Inc.
• Original Assignee: VeriSign, Inc.
• Inventors: Balogh, Aristotle
• Application Number:
  US11/641,054
• Publication Number:
  US 20070100808A1
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2315 Optimistic concurrency control
• CPC Class Codes: G06F 16/2358 Change logging, detection, and notification replication G06F16/27
• CPC Class Codes: G06F 16/2365 Ensuring data consistency and integrity
• CPC Class Codes: G06F 16/245 Query processing
• CPC Class Codes: G06F 16/2471 Distributed queries
• CPC Class Codes: G06F 2209/5018 Thread allocation
• CPC Class Codes: G06F 9/505 considering the load
• CPC Class Codes: G06F 9/546 Message passing systems or structures, e.g. queues
• CPC Class Codes: Y10S 707/959 Network
• CPC Class Codes: Y10S 707/966 Distributed
• CPC Class Codes: Y10S 707/99938 Concurrency, e.g. lock management in shared database
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface
• CPC Class Codes: Y10S 707/99952 Coherency, e.g. same view to multiple users
• CPC Class Codes: Y10S 707/99953 Recoverability

Abstract

Embodiments of the present invention provide a method and system for high-speed database searching with concurrent updating, without the use of database locks or access controls, for large database systems. Specifically, a plurality of search queries may be received over a network, the database may be searched, and a plurality of search replies may be sent over the network. While searching the database, new information received over the network may be incorporated into the database by creating a new element based on the new information and writing a pointer to the new element to the database using a single uninterruptible operation.

Claims

1. A multi-threaded network database system, comprising:

at least one processor coupled to a network; and

a memory coupled to the processor, the memory including a database and instructions adapted to be executed by the processor to;

create an update thread and a plurality of search threads;

assign each of a plurality of search queries, received over the network, to one of the plurality of search threads;

for each search thread;

search the database according to the assigned search queries,

create a plurality of search replies corresponding to the assigned search queries, and

send the plurality of search replies over the network; and

for the update thread;

create a plurality of new elements according to new information received over the network,

set a dirty bit within each of the plurality of new elements, without restricting access to the database for the plurality of search threads,

write a pointer to each of the plurality of new elements to the database using a single uninterruptible operation for each pointer,

clear the dirty bit within each of the plurality of new elements, and

delete an existing element from the memory after the pointers are written to the database.

2. The system of claim 1, wherein the instructions further include:

for the update thread;

set a dirty bit within at least one existing element to be deleted from the database, and

without restricting access to the database for the plurality of search threads, de-reference the existing element to be deleted using a single uninterruptible operation.

3. The system of claim 1, wherein the instructions further include:

for the update thread;

set a dirty bit within at least one existing element to be modified in the database before the pointer is written to corresponding new element, and

clear the dirty bit within the existing element after the pointer is written to the corresponding new element.

4. The system of claim 1, wherein the single uninterruptible operation is a store instruction.

5. The system of claim 4, wherein the store instruction writes four bytes to a memory address located on a four byte boundary.

6. The system of claim 4, wherein the store instruction writes eight bytes to a memory address located on an eight byte boundary.

7. The system of claim 4, wherein the processor has a word size of at least n-bytes, the memory has a width of at least n-bytes and the store instruction writes n-bytes to a memory address located on an n-byte boundary.

8. The system of claim 1, wherein the plurality of search queries are received within a single network packet.

9. The system of claim 1, wherein the plurality of search replies are sent within a single network packet.

10. The system of claim 1, wherein said restricting access includes database locking.

11. The system of claim 1, wherein said restricting access includes spin locking.

12. The system of claim 11, wherein said spin locking includes the use of at least one semaphore.

13. The system of claim 12, wherein said semaphore is a mutex semaphore.

14. The system of claim 1, further comprising a plurality of processors and a symmetric multi-processing operating system.

15. The system of claim 14, wherein the plurality of search threads perform at least 100,000 searches per second.

16. The system of claim 15, wherein the update thread performs at least 10,000 updates per second.

17. The system of claim 16, wherein the update thread performs between 50,000 and 130,000 updates per second.

18. The system of claim 1, wherein the pointer to the new element is written to a search index.

19. The system of claim 18, wherein the search index is a ternary search tree.

20. The system of claim 1, wherein the pointer to the new element is written to a data record within the database.

52. The system of claim 8, wherein the new information is received within the single network packet.

21. A method for searching and concurrently updating a database, comprising:

creating an update thread and a plurality of search threads;

assigning each of a plurality of search queries, received over the network, to one of the plurality of search threads;

for each search thread;

searching the database according to the assigned search queries,

creating a plurality of search replies corresponding to the assigned search queries, and

sending the plurality of search replies over the network; and

for the update thread;

creating a plurality of new elements according to new information received over the network,

setting a dirty bit within each of the plurality of new elements,

without restricting access to the database for the plurality of search threads, writing a pointer to each of the plurality of new elements to the database using a single uninterruptible operation for each pointer,

clearing the dirty bit within each of the plurality of new elements, and

deleting an existing element from the memory after the pointers are written to the database.

22. The method of claim 21, wherein the instructions further include:

for the update thread;

setting a dirty bit within at least one existing element to be deleted from the database, and

without restricting access to the database for the plurality of search threads, de-referencing the existing element to be deleted using a single uninterruptible operation.

23. The method of claim 21, further comprising:

for the update thread;

setting a dirty bit within at least one existing element to be modified in the database before the pointer is written to corresponding new element, and

clearing the dirty bit within the existing element after the pointer is written to the corresponding new element.

24. The method of claim 21, wherein the single uninterruptible operation is a store instruction.

25. The method of claim 23, wherein the store instruction writes four bytes to a memory address located on a four byte boundary.

26. The method of claim 23, wherein the store instruction writes eight bytes to a memory address located on an eight byte boundary.

27. The method of claim 21, wherein the plurality of search queries are received within a single network packet.

28. The method of claim 21, wherein the plurality of search replies are sent within a single network packet.

29. The method of claim 21, wherein said restricting access includes database locking.

30. The method of claim 21, wherein said restricting access includes spin locking.

31. The method of claim 30, wherein said spin locking includes the use of at least one semaphore.

32. The method of claim 31, wherein said semaphore is a mutex semaphore.

33. The method of claim 21, wherein the plurality of search threads perform at least 100,000 searches per second.

34. The method of claim 21, wherein the update thread performs at least 10,000 updates per second.

35. The method of claim 34, wherein the update thread performs between 50,000 and 130,000 updates per second.

36. The method of claim 21, wherein the pointer to the new element is written to a search index.

37. The method of claim 21, wherein the pointer to the new element is written to a data record within the database.

53. The method of claim 27, wherein the new information is received within the single network packet.

38. A computer readable medium including instructions adapted to be executed by at least one processor to implement a method for searching and concurrently updating a database, the method comprising:

creating an update thread and a plurality of search threads;

assigning each of a plurality of search queries, received over the network, to one of the plurality of search threads;

for each search thread;

searching a database according to the assigned search queries,

creating a plurality of search replies corresponding to the assigned search queries, and

sending the plurality of search replies over the network; and

for the update thread;

creating a plurality of new elements according to new information received over the network,

setting a dirty bit within each of the plurality of new elements,

without restricting access to the database for the plurality of search threads, writing a pointer to each of the plurality of new elements to the database using a single uninterruptible operation for each pointer, and

clearing the dirty bit within each of the plurality of new elements, and

deleting an existing element from the memory after the pointers are written to the database.

39. The computer readable medium of claim 38, wherein the method further includes:

for the update thread;

setting a dirty bit within at least one element to be deleted from the database, and

without restricting access to the database for the plurality of search threads, de-referencing the element to be deleted using a single uninterruptible operation.

40. The computer readable medium of claim 38, wherein the method further includes:

for the update thread;

setting a dirty bit within at least one existing element to be modified in the database before the pointer is written to corresponding new element, and clearing the dirty bit within the existing element after the pointer is written to the corresponding new element.

41. The computer readable medium of claim 38, wherein the single uninterruptible operation is a store instruction.

42. The computer readable medium of claim 41, wherein the store instruction writes four bytes to a memory address located on a four byte boundary.

43. The computer readable medium of claim 41, wherein the store instruction writes eight bytes to a memory address located on an eight byte boundary.

44. The computer readable medium of claim 38, wherein the plurality of search queries are received within a single network packet.

45. The computer readable medium of claim 38, wherein the plurality of search replies are sent within a single network packet.

46. The computer readable medium of claim 38, wherein said restricting access includes database locking.

47. The computer readable medium of claim 38, wherein said restricting access includes spin locking.

48. The computer readable medium of claim 47, wherein said spin locking includes the use of at least one semaphore.

49. The computer readable medium of claim 48, wherein said semaphore is a mutex semaphore.

50. The computer readable medium of claim 38, wherein the pointer to the new element is written to a search index.

51. The computer readable medium of claim 38, wherein the pointer to the new element is written to a data record within the database.

54. The computer readable medium of claim 44, wherein the new information is received within the single network packet