High speed non-concurrency controlled database
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.
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.