High speed non-concurrency controlled database

• US 20030084057A1
• Filed: 11/01/2002
• Published: 05/01/2003
• Est. Priority Date: 11/01/2001
• Status: Active Grant

• Current Assignee: VeriSign, Inc.
• Original Assignee: VeriSign, Inc.
• Inventors: Balogh, Aristotle Nicholas
• Granted Patent: US 7,203,682 B2
• Time in Patent Office: Days
• US Class Current: 707/100
• 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 according to new information received over the network, and

without restricting access to the database for the plurality of search threads, write a pointer to the new element to the database using a single uninterruptible operation.

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

3. The system of claim 1, further comprising:

for the update thread;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

18. The system of claim 17, wherein the search index is a TST.

19. The system of claim 17, wherein the search index is a hash table.

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

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 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 according to new information received over the network, and

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

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

23. The method of claim 21, further comprising:

for the update thread;

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

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

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

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

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

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

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

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

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

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

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

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

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

36. The method of claim 35, wherein the search index is a TST.

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

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 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 according to new information received over the network, and

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

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

40. The computer readable medium of claim 38, wherein said method further comprising:

for the update thread;

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

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

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

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

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

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

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

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

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

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

50. The computer readable medium of claim 49, wherein the search index is a TST.

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

52. 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 based on the new information, and

without locking the database, writing a pointer to the new element to the database using a single uninterruptible operation.

53. The method of claim 52, wherein the single uninterruptible operation is a store instruction.

54. The method of claim 52, further comprising:

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

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

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

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

58. The method of claim 52, 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.

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

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

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

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

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

64. 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 based on new information received over the network, and

without restricting search access to the database, write a pointer to the new element to the database using a single uninterruptible operation.

65. The system of claim 64, wherein the single uninterruptible operation is a store instruction.

66. The system of claim 64, wherein the instructions are further adapted to:

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

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

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

69. The system of claim 65, 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.

70. The system of claim 64, wherein said restricting search access includes database locking.

71. The system of claim 64, wherein said restricting search access includes spin locking.

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

73. The system of claim 72, wherein said semaphore is a mutex semaphore.

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

75. The system of claim 64, wherein the search index is a TST.

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

77. A method for updating a non-concurrency controlled ternary search tree having a plurality of nodes, comprising:

creating a new node; and

updating a pointer within one of the plurality of nodes to reference the new node using a single store instruction.

78. The method of claim 77, wherein the single uninterruptible operation is a store instruction.

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

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

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

82. The method of claim 77, wherein said updating includes at least 10,000 updates per second.

83. The method of claim 82, wherein said updating includes between 50,000 and 130,000 updates per second.

84. A method for updating a non-concurrency controlled ordered access key search tree having a plurality of vertical and horizontal nodes, comprising:

creating a new node; and

updating a pointer within one of the plurality of nodes to reference the new node using a single store instruction.

85. The method of claim 84, wherein the single uninterruptible operation is a store instruction.

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

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

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

89. The method of claim 84, wherein said updating includes at least 10,000 updates per second.

90. The system of claim 89, wherein said updating includes between 50,000 and 130,000 updates per second.

91. A method for updating a non-locking linked list having a first element, a second element and a third element, the first element having a first pointer to the second element, and the second element having a second pointer to the third element, comprising:

creating a new element having a pointer to the third element; and

updating the first pointer to reference the new element using a single store instruction.

92. The method of claim 91, wherein the single uninterruptible operation is a store instruction.

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

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

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

96. The method of claim 91, wherein said updating includes at least 10,000 updates per second.

97. The method of claim 97, wherein said updating includes between 50,000 and 130,000 updates per second.

98. 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, writing a pointer to an existing element to the database using a single uninterruptible operation.

99. The method of claim 98, wherein the pointer comprises a null pointer.

100. The method of claim 98, further comprising:

for the update thread;

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