High speed non-concurrency controlled database

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.

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.  
     
     
         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.  
     
     
         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.  
     
     
         52 . The system of  claim 8 , wherein the new information is received within the single network packet.  
     
     
         53 . The method of  claim 27 , wherein the new information is received within the single network packet.  
     
     
         54 . The computer readable medium of  claim 44 , wherein the new information is received within the single network packet