High speed non-concurrency controlled database

• US 7,203,682 B2
• Filed: 11/01/2002
• Issued: 04/10/2007
• Est. Priority Date: 11/01/2001
• Status: Active Grant

• Current Assignee: VeriSign, Inc.
• Original Assignee: VeriSign, Inc.
• Inventors: Balogh, Aristotle Nicholas
• Primary Examiner(s): Wu; Yicun
• Application Number:
  US10/285,618
• Publication Number:
  US 20030084057A1
• Time in Patent Office: 1,621 Days
• Field of Search: 707 1- 10, 707100-1041, 707200-206, 715/536, 714/751, 709/245, 370/389
• 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 new element in the database according to new information received over the network,

without restricting access to the database for the plurality of search threads, and not using a different copy of the database than used by the search threads, write a pointer to the new element to the database using a single uninterruptible operation, and

physically delete an existing element from the memory after the pointer is written to the database.

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

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

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

5. The system of claim 2, 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.

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

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

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

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

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

11. The system of claim 10, wherein said semaphore is a mutex semaphore.

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

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

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

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

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

17. The system of claim 16, wherein the search index is a TST (ternary search tree).

18. The system of claim 16, wherein the search index is a hash table.

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

20. 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 a 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 new element in the database according to new information received over the network,

without restricting access to the database for the plurality of search threads, and not using a different copy of the database than used by the search threads, writing a pointer to the new element to the database using a single uninterruptible operation, and

physically deleting an existing element after the pointer is written to the database.

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

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

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

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

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

26. The method of claim 20, wherein said restricting access includes database locking.

27. The method of claim 20, wherein said restricting access includes spin locking.

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

29. The method of claim 28, wherein said semaphore is a mutex semaphore.

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

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

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

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

34. The method of claim 33, wherein the search index is a TST (ternary search tree).

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

36. 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 a 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 new element in the database according to new information received over the network,

without restricting access to the database for the plurality of search threads, and not using a different copy of the database than used by the search threads, writing a pointer to the new element to the database using a single uninterruptible operation, and

physically deleting an existing element after the pointer is written to the database.

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

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

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

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

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

42. The computer readable medium of claim 36, wherein said restricting access includes database locking.

43. The computer readable medium of claim 36, wherein said restricting access includes spin locking.

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

45. The computer readable medium of claim 44, wherein said semaphore is a mutex semaphore.

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

47. The computer readable medium of claim 46, wherein the search index is a TST (ternary search tree).

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

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

receiving a plurality of search queries over a network;

searching the database;

sending a plurality of search replies over the network; and

while searching the database, modifying the database to incorporate new information received over the network, including;

creating a new element in the database based on the new information,

without locking the database, and not using a different copy of the database than used by the search threads, writing a pointer to the new element to the database using a single uninterruptible operation, and

physically deleting an existing element after the pointer is written to the database.

50. The method of claim 49, wherein the single uninterruptible operation is a store instruction.

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

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

53. The method of claim 50, wherein the store instruction writes n-bytes to a memory address located on an n-byte boundary.

54. The method of claim 49, wherein the plurality of search queries are received within a first network packet and the plurality of search replies are sent within a second network packet.

55. The method of claim 49, wherein said searching the database includes at least 100,000 searches per second.

56. The method of claim 49, wherein said modifying the database includes at least 10,000 modifications per second.

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

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

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

60. A system for searching and updating a database, comprising:

at least one processor coupled to a network; and

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

create a new element in the database based on new information received over the network,

without restricting search access to the database, and not using a different copy of the database than used for searching the database, write a pointer to the new element to the database using a single uninterruptible operation, and

physically delete an existing element after the pointer is written to the database.

61. The system of claim 60, wherein the single uninterruptible operation is a store instruction.

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

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

64. The system of claim 61, 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.

65. The system of claim 60, wherein said restricting search access includes database locking.

66. The system of claim 60, wherein said restricting search access includes spin locking.

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

68. The system of claim 67, wherein said semaphore is a mutex semaphore.

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

70. The system of claim 60, wherein the search index is a TST (ternary search tree).

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

72. 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;

without restricting access to the database for the plurality of search threads, and not using a different copy of the database than used for searching the database, writing a pointer to an existing element to the database using a single uninterruptible operation, and

physically deleting the existing element after the pointer is written to the database.

73. The method of claim 72, wherein the pointer comprises a null pointer.