System and method for processing DNS queries

• US 8,630,988 B2
• Filed: 12/10/2008
• Issued: 01/14/2014
• Est. Priority Date: 11/01/2001
• Status: Active Grant

• Current Assignee: VeriSign, Inc.
• Original Assignee: VeriSign, Inc.
• Inventors: Balogh, Aristotle Nicolas
• Primary Examiner(s): Lu, Charles
• Application Number:
  US12/331,498
• Publication Number:
  US 20090106211A1
• Time in Patent Office: 1,861 Days
• Field of Search: 707/705
• US Class Current: 707/705
• 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. In a system comprising a first back-end lookup computer and a plurality of protocol computers, a method comprising:

at a first of the plurality of protocol computers;

receiving a plurality of DNS queries;

multiplexing the plurality of DNS queries and state information associated with each of the plurality of DNS query into a first single communication;

sending the first single communication to the first back-end lookup computer, wherein the first back-end lookup computer is configured to receive multiplexed DNS queries and to search a single database using the first single communication including the plurality of DNS queries that are multiplexed;

receiving a second single communication from the first back-end lookup computer;

retrieving a plurality of DNS responses by de-multiplexing the second single communication, wherein each of the plurality of DNS responses corresponds to one of the plurality of DNS queries; and

transmitting the plurality of DNS responses; and

at the first back-end lookup computer;

de-multiplexing the first single communication received from the first of the plurality of protocol computers into the plurality of DNS queries;

constructing a DNS response to each of the plurality of DNS queries by searching the single database using each of the plurality of DNS queries;

multiplexing the DNS responses into the second single communication;

sending the second single communication to the first of the plurality of protocol computers;

receiving an update to the single database from the first of the plurality of protocol computers; and

updating the single database using the update, wherein the update is packaged in the first single communication.

2. The method of claim 1, further comprising, at the first of the plurality of protocol computers:

selecting the first back-end lookup computer from a plurality of back-end lookup computers, based on an ability of each of the plurality of back-end lookup computers to provide responses to the plurality of DNS queries received by the first of the plurality of protocol computers.

3. The method of claim 1, further comprising, at the first of the plurality of protocol computers:

maintaining the state information associated with each of the plurality of DNS queries that is received; and

for each of the plurality of DNS queries, including a reference to the state information in the first single communication sent to the back-end lookup computer.

4. The method of claim 1, wherein the state information associated with each of the plurality of DNS queries comprises at least one of:

a source address or a protocol type.

5. A system, comprising:

a first back-end lookup computer; and

a plurality of protocol computers comprising a first of the plurality of protocol computers,

wherein the first of the plurality of protocol computers includes a processor and a memory system, wherein the memory system includes one or more non-transitory computer readable media storing instructions that, when executed by the processor, are configured to cause the first of the plurality of protocol computers to perform first operations, the first operations comprising;

receiving a plurality of DNS queries;

multiplexing the plurality of DNS queries and state information associated with each of the plurality of DNS query into a first single communication;

sending the first single communication to the first back-end lookup computer, wherein the first back-end lookup computer is configured to receive multiplexed DNS queries and to search a single database using the first single communication including the plurality of DNS queries that are multiplexed;

receiving a second single communication from the first back-end lookup computer;

retrieving a plurality of DNS responses by de-multiplexing the second single communication, wherein each of the plurality of DNS responses corresponds to one of the plurality of DNS queries; and

transmitting the plurality of DNS responses, and

wherein the first back-end lookup computer comprises a processor and a memory system, wherein the memory system of the first back-end lookup computer comprises one or more non-transitory computer readable media storing instructions that, when executed by the processor of the first back-end lookup computer, cause the first back-end lookup computer to perform second operations, the second operations comprising;

de-multiplexing the first single communication received from the first of the plurality of protocol computers into the plurality of DNS queries;

constructing a DNS response to each of the plurality of DNS queries by searching the single database using each of the plurality of DNS queries;

multiplexing the DNS responses into the second single communication;

sending the second single communication to the first of the plurality of protocol computers;

receiving an update to the single database from the first of the plurality of protocol computers; and

updating the single database using the update, wherein the update is packaged in the first single communication.

6. The system of claim 5, wherein the first operations further comprise:

selecting the first back-end lookup computer from a plurality of back-end lookup computers, based on an ability of each of the plurality of back-end lookup computers to provide responses to the plurality of DNS queries received by the first of the plurality of protocol computers.

7. The system of claim 5, wherein the first operations further comprise:

maintaining the state information associated with each of the plurality of DNS queries that is received; and

for each of the plurality of DNS queries, including a reference to the state information in the first single communication sent to the first back-end lookup computer.

8. The system of claim 5, wherein the state information associated with each of the plurality of DNS queries comprises at least one of:

a source address or a protocol type.