Диспетчер транзакций в памяти
Номер патента: 6038
Опубликовано: 25.08.2005
Авторы: Хауорт Уилльям Фредерик Мл., Бэлоу Аристотель Николас
Формула / Реферат
1. Многопоточная сетевая система баз данных, содержащая
по меньшей мере один процессор, связанный с сетью; и
память, связанную с процессором, причем память включает в себя базу данных и команды, адаптированные для выполнения процессором следующих операций:
создание потока обновления и множества поисковых потоков;
назначение каждого из множества поисковых запросов, принятых по сети, одному из множества поисковых потоков;
для каждого поискового потока:
проведение поиска по базе данных в соответствии с назначенными поисковыми запросами;
создание множества поисковых ответов, соответствующих назначенным поисковым запросам, и
отправку множества поисковых ответов по сети; и
для потока обновления:
создание множества новых элементов в соответствии с новой информацией, принятой по сети,
установку бита модификации в каждом из множества новых элементов,
без ограничения доступа к базе данных для множества поисковых потоков, внесение указателя в каждый из множества новых элементов в базе данных с использованием единой непрерываемой операции, и
очистку бита модификации в каждом из множества новых элементов.
2. Система по п.1, в которой команды далее включают в себя следующие операции:
для потока обновления:
установку бита модификации по меньшей мере в одном существующем элементе, подлежащем удалению из базы данных, и
без ограничения доступа к базе данных для множества поисковых потоков, удаление ссылки на существующий элемент, подлежащий удалению с использованием единой непрерываемой операции.
3. Система по п.1, в которой команды далее включают в себя следующие операции:
для потока обновления:
установку бита модификации по меньшей мере в одном существующем элементе, подлежащем изменению в базе данных до того, как указатель будет внесен в соответствующий новый элемент, и
очистку бита модификации в существующем элементе после того, как указатель внесен в соответствующий новый элемент.
4. Система по п.1, в которой единой непрерываемой операцией является команда запоминания.
5. Система по п.4, в которой команда запоминания записывает 4 байта в адрес памяти, расположенный на 4-байтной границе.
6. Система по п.4, в которой команда запоминания записывает 8 байт в адрес памяти, расположенный на 8-байтной границе.
7. Система по п.4, в которой процессор имеет размер слова, равный по меньшей мере n байт, память имеет ширину по меньшей мере n байт, а команда хранения записывает n байт в адрес памяти, расположенный на n-байтной границе.
8. Система по п.1, в которой множество поисковых запросов принимаются в виде единого сетевого пакета.
9. Система по п.1, в которой множество поисковых ответов отправляются в виде единого сетевого пакета.
10. Система по п.1, в которой упомянутое ограничение доступа включает в себя блокировку базы данных.
11. Система по п.1, в которой упомянутое ограничение доступа включает в себя циклическую блокировку.
12. Система по п.11, в которой упомянутая циклическая блокировка включает в себя использование по меньшей мере одного семафора.
13. Система по п.12, в котором упомянутым семафором является мьютекс-семафор.
14. Система по п.1, далее содержащая множество процессоров и симметричную многопроцессорную операционную систему.
15. Система по п.14, в которой множество поисковых потоков выполняют по меньшей мере 100000 поисков в секунду.
16. Система по п.15, в которой поток обновления выполняет по меньшей мере 10000 обновлений в секунду.
17. Система по п.16, в которой поток обновления выполняет от 50000 до 130000 обновлений в секунду.
18. Система по п.1, в которой указатель на новый элемент вносится в поисковый индекс.
19. Система по п.18, в которой поисковым индексом является дерево троичного поиска.
20. Система по п.1, в которой указатель на новый элемент вносится в запись данных в базе данных.
21. Способ поиска по базе данных с одновременным обновлением базы данных, содержащий следующие операции:
создание потока обновления и множества поисковых потоков;
назначение каждого из множества поисковых запросов, принятых по сети, одному из множества поисковых потоков;
для каждого поискового потока:
проведение поиска по базе данных в соответствии с назначенными поисковыми запросами;
создание множества поисковых ответов, соответствующих назначенным поисковым запросам, и
отправку множества поисковых ответов по сети; и
для потока обновления:
создание множества новых элементов в соответствии с новой информацией, принятой по сети,
установку бита модификации в каждом из множества новых элементов,
без ограничения доступа к базе данных для множества поисковых потоков, внесение указателя в каждый из множества новых элементов в базе данных с использованием единой непрерываемой операции, и
очистку бита модификации в каждом из множества новых элементов.
22. Способ по п.21, в котором команды далее включают в себя следующие операции:
для потока обновления:
установку бита модификации по меньшей мере в одном существующем элементе, подлежащем удалению из базы данных, и
без ограничения доступа к базе данных для множества поисковых потоков, удаление ссылки на существующий элемент, подлежащий удалению с использованием единой непрерываемой операции.
23. Способ по п.21, далее содержащий следующие операции: для потока обновления:
установку бита модификации по меньшей мере в одном существующем элементе, подлежащем изменению в базе данных до того, как указатель будет внесен в соответствующий новый элемент, и
очистку бита модификации в существующем элементе после того, как указатель внесен в соответствующий новый элемент.
24. Способ по п.21, в котором единой непрерываемой операцией является команда запоминания.
25. Способ по п.23, в котором команда запоминания записывает 4 байта в адрес памяти, расположенный на 4-байтной границе.
26. Способ по п.23, в котором команда запоминания записывает 8 байт в адрес памяти, расположенный на 8-байтной границе.
27. Способ по п.21, в котором множество поисковых запросов принимаются в виде единого сетевого пакета.
28. Способ по п.21, в котором множество поисковых ответов отправляются в виде единого сетевого пакета.
29. Способ по п.21, в котором упомянутое ограничение доступа включает в себя блокировку базы данных.
30. Способ по п.21, в котором упомянутое ограничение доступа включает в себя циклическую блокировку.
31. Способ по п.30, в котором упомянутая циклическая блокировка включает в себя использование по меньшей мере одного семафора.
32. Способ по п.31, в котором упомянутым семафором является мьютекс-семафор.
33. Способ по п.21, в котором множество поисковых потоков выполняют по меньшей мере 100000 поисков в секунду.
34. Способ по п.21, в котором поток обновления выполняет по меньшей мере 10000 обновлений в секунду.
35. Способ по п.34, в котором поток обновления выполняет от 50000 до 130000 обновлений в секунду.
36. Способ по п.21, в котором указатель на новый элемент вносится в поисковый индекс.
37. Способ по п.21, в котором указатель на новый элемент вносится в запись данных в базе данных.
38. Компьютерно-считываемый носитель, включающий в себя команды, адаптированные для выполнения по меньшей мере одним процессором, чтобы воплотить способ поиска по базе данных с одновременным обновлением базы данных, способ содержит следующие операции:
создание потока обновления и множества поисковых потоков;
назначение каждого из множества поисковых запросов, принятых по сети, одному из множества поисковых потоков;
для каждого поискового потока:
проведение поиска по базе данных в соответствии с назначенными поисковыми запросами;
создание множества поисковых ответов, соответствующих назначенным поисковым запросам, и
отправку множества поисковых ответов по сети; и
для потока обновления:
создаэшх множества новых элементов в соответствии с новой информацией, принятой по сети,
установку бита модификации в каждом из множества новых элементов,
без ограничения доступа к базе данных для множества поисковых потоков, внесение указателя в каждый из множества новых элементов в базе данных с использованием единой непрерываемой операции, и
очистку бита модификации в каждом из множества новых элементов.
39. Компьютерно-считываемый носитель по п.38, в котором способ далее включает в себя следующие операции:
для потока обновления:
установку бита модификации по меньшей мере в одном существующем элементе, подлежащем удалению из базы данных, и
без ограничения доступа к базе данных для множества поисковых потоков, удаление ссылки на существующий элемент, подлежащий удалению с использованием единой непрерываемой операции.
40. Компьютерно-считываемый носитель по п.38, в котором способ далее включает в себя следующие операции:
для потока обновления:
установку бита модификации по меньшей мере в одном существующем элементе, подлежащем изменению в базе данных до того, как указатель будет внесен в соответствующий новый элемент, и
очистку бита модификации в существующем элементе после того, как указатель внесен в соответствующий новый элемент.
41. Компьютерно-считываемый носитель по п.38, в котором единой непрерываемой операцией является команда запоминания.
42. Компьютерно-считываемый носитель по п.41, в котором команда запоминания записывает 4 байта в адрес памяти, расположенный на 4-байтной границе.
43. Компьютерно-считываемый носитель по п.41, в котором команда запоминания записывает 8 байт в адрес памяти, расположенный на 8-байтной границе.
44. Компьютерно-считываемый носитель по п.38, в котором множество поисковых запросов принимаются в виде единого сетевого пакета.
45. Компьютерно-считываемый носитель по п.38, в котором множество поисковых ответов отправляются в виде единого сетевого пакета.
46. Компьютерно-считываемый носитель по п.38, в котором упомянутое ограничение доступа включает в себя блокировку базы данных.
47. Компьютерно-считываемый носитель по п.38, в котором упомянутое ограничение доступа включает в себя циклическую блокировку.
48. Компьютерно-считываемый носитель по п.47, в котором упомянутая циклическая блокировка включает в себя использование по меньшей мере одного семафора.
49. Компьютерно-считываемый носитель по п.48, в котором упомянутым семафором является мьютекс-семафор.
50. Компьютерно-считываемый носитель по п.38, в котором указатель на новый элемент вносится в поисковый индекс.
51. Компьютерно-считываемый носитель по п.38, в котором указатель на новый элемент вносится в запись данных в базе данных.
52. Система по п.8, в которой новая информация принимается в виде единого сетевого пакета.
53. Способ по п.27, в котором новая информация принимается в виде единого сетевого пакета.
54. Компьютерно-считываемый носитель по п.44, в котором новая информация принимается в виде единого сетевого пакета.
Текст
006038 Эта не предварительная заявка заявляет приоритет предварительной патентной заявки США 60/330842, поданной 1 ноября 2001 г., полностью включенной в настоящее описание посредством ссылки и предварительной патентной заявки США 60/365169, поданной 19 марта 2002 г., полностью включенной в настоящее описание посредством ссылки. Область техники Данная заявка относится к компьютерным системам, в частности к способу и системе обеспечения высокоскоростного поиска по базе данных с одновременным обновлением для больших систем баз данных. Существующий уровень техники Поскольку Интернет продолжает стремительно расти, все более сложным становится масштабировать преобразования, проводимые службой имен доменов (Domain Name Service, DNS) для серверов корневых зон и серверов общих доменов верхнего уровня (generic Top Level Domain, gTLD), за приемлемую цену. Сервер корневой зоны А (то есть, a.root-server.net) поддерживает и распределяет файл корневой зоны пространства имен Интернета на 12 вторичных серверов корневых зон, географически распределенных по всему миру (то есть b.root-server.net, с.root-server.net и т.д.), тогда как соответствующие серверы gTLD (то есть, a.gtld-servers.net, b.gtld-servers.net и т.д.) аналогично распределены и поддерживают домены верхнего уровня (например, .com, .net, .org и т.п.). Постоянное увеличивающееся количество данных, связанных с неумолимым ростом количества запросов, заставляет постоянно пересматривать аппаратную и программную инфраструктуру, необходимую для DNS услуг в корневых зонах и gTLD на несколько лет вперед. Типичная односерверная конфигурация стандартного программного обеспеченияBind (для создания DNS-сервера под управлением Linux) уже недостаточна для требований корневой зоны А и скоро даже перестанет удовлетворять нуждам gTLD. При сближении телефонной коммутируемой сети общего пользования (ТСОП) и Интернета имеются возможности для универсального высокопроизводительного поискового механизма, чтобы обеспечивать свойства, обычно связанные с узлами управления услугами (УУУ - Service Control Point, SCP) в сети сигнализации по протоколу SS7 в ТСОП,как новые продвинутые услуги, охватывающие ТСОП и Интернет, включая услуги усовершенствованной интеллектуальной сети (УИС - Advanced Intelligent Network, AIN), передачи речи по Интернет-протоколу(Voice over Internet Protocol, VoIP) , услуги ориентирования на местности и т.п. Краткое описание чертежей Фиг. 1 - блок-схема системы в соответствии с вариантом выполнения настоящего изобретения. Фиг. 2 - подробная блок-схема, иллюстрирующая структуру данных сообщения в соответствии с вариантом выполнения настоящего изобретения. Фиг. 3 - подробная блок-схема, иллюстрирующая архитектуру структуры данных о задержке сообщений в соответствии с вариантом выполнения настоящего изобретения. Фиг. 4 - подробная блок-схема, иллюстрирующая общую архитектуру баз данных в соответствии с вариантом выполнения настоящего изобретения. Фиг. 5 - подробная блок-схема, иллюстрирующая общую архитектуру баз данных в соответствии с вариантом выполнения настоящего изобретения. Фиг. 6 - подробная блок-схема, иллюстрирующая общую архитектуру баз данных в соответствии с вариантом выполнения настоящего изобретения. Фиг. 7 - подробная блок-схема, иллюстрирующая общую архитектуру баз данных в соответствии с вариантом выполнения настоящего изобретения. Фиг. 8 - подробная блок-схема, иллюстрирующая общую архитектуру баз данных в соответствии с вариантом выполнения настоящего изобретения. Фиг. 9 - блок-схема алгоритма верхнего уровня, иллюстрирующая способ поиска и одновременного обновления базы данных в соответствии с вариантом выполнения настоящего изобретения. Фиг. 10 - блок-схема алгоритма верхнего уровня, иллюстрирующая способ поиска и одновременного обновления базы данных в соответствии с вариантом выполнения настоящего изобретения. Подробное описание изобретения Варианты выполнения настоящего изобретения обеспечивают способ и систему высокоскоростного поиска по базе данных с одновременным обновлением для систем с большими базами данных. Конкретнее, по сети может приниматься множество поисковых запросов, по базе данных может проводиться поиск, и множество поисковых ответов может отправляться по сети. При поиске по базе данных, по сети может приниматься новая информация, на основе этой новой информации может создаваться множество новых элементов базы данных, и в каждом новом элементе базы данных может быть установлен бит модификации. Указатель на каждый новый элемент базы данных может быть записан в базу данных с использованием единой непрерываемой операции, а бит модификации внутри каждого нового элемента базы данных может быть очищен. На фиг. 1 представлена блок-схема системы в соответствии с вариантом выполнения настоящего изобретения. В общем случае система 100 может содержать большую базу данных, находящуюся в памяти, принимать поисковые запросы и обеспечивать поисковые ответы по сети. Например, системой 100 может быть симметричный многопроцессорный компьютер, такой как, например, компьютер IBMRS/6000 M80 или S80, изготовленный International Business Machine Corporation (город Армонк, штат Нью-Йорк), компьютер Sun Enterprise 10000, изготовленный Sun Microsystems (город Санта-Клара,штат Калифорния), и т.п.Система 100 также может быть многопроцессорным персональным компьютером, таким как, например, компьютер Compaq ProLiant ML530 (с двумя процессорами Intel PentiumIII 866 МГц), изготовленный Hewlett-Packard Company (город Пало-Альто, штат Калифорния). Система 100 также может включать в себя многопроцессорную операционную систему, такую как, например,IBM AIX 4, операционную среду Sun Solaris 8, Red Hat Linux 6.2 и т.п.Система 100 может получать периодические обновления по сети 124, которые могут одновременно включаться в состав базы данных. В варианте выполнения система 100 может включать в себя по меньшей мере один процессор 102-1,подключенный к шине 101. Процессор 102-1 может включать в себя внешнюю кэш-память (например,кэш первого уровня (L1), не показанный для ясности). Вспомогательная кэш-память 103-1 (например,кэш второго уровня (L2), кэш второго уровня/третьего уровня (L2/L3) и т.п.) могут находиться между процессором 102-1 и шиной 101. В предпочтительном варианте выполнения система 100 может включать в себя множество процессоров 102-1102-Р, подключенных к шине 101. Множество вспомогательных кэш-памятей 103-1103-Р также могут находиться между множеством процессоров 102-1102-Р и шиной 101 (например, архитектура просмотрового типа), либо альтернативно по меньшей мере одна вспомогательная кэш-память 103-1 может быть подключена к шине 101 (например архитектура сохраняющего типа. Система 100 может включать в себя память 104, такую как, например, оперативная память (ОЗУ) и т.д., подключенную к шине 101, для хранения информации и команд, подлежащих выполнению множеством процессоров 102-1102-Р. Память 104 может хранить большую базу данных, например, для преобразования доменных имен Интернета в IP-адреса, для преобразования имен или телефонных номеров в сетевые адреса, для обеспечения и обновления данных профилей абонентов, для обеспечения и обновления данных о присутствии пользователя и т.п.Преимущественно, и размер базы данных, и количество преобразований в секунду могут быть очень большими. Например, память 104 может включать в себя по меньшей мере 64 Гбайт ОЗУ и может хранить базу доменных имен размером 500 М (то есть 500 х 106) , базу данных записей абонентов размером 500 М, базу данных записей о переносимости телефонных номеров размером 450 М и т.д. В приводимой в качестве примера архитектуре 64-битной системы, такой как, например, система,включающая в себя по меньшей мере один 64-битный процессор 102-1 с прямым порядком следования битов (начиная со старшего), подключенный по меньшей мере к 64-битной шине 101 и 64-битной памяти 104, 8-байтное значение указателя может быть записано в адрес памяти на 8-байтной границе (то есть в адрес памяти, поделенный на 8, или, например, 8N) с использованием единой непрерываемой операции. В общем случае, наличие вспомогательной кэш-памяти 103-1 может просто задержать запись 8-байтного указателя в память 104. Например, в одном варианте выполнения вспомогательная кэш-память 103-1 может быть просмотровым кэшем, работающим в режиме прямой записи, так что единая 8-байтная команда запоминания может переместить 8 байт данных из процессора 102-1 в память 104 без прерывания,всего за два тактовых цикла системы. В другом варианте выполнения вспомогательная кэш-память 103-1 может быть просмотровым кэшем, работающим в режиме обратной записи, так что 8-байтный указатель может быть сначала записан во вспомогательную кэш-память 103-1, которая затем вносит 8-байтный указатель в память 104 в более поздний момент времени, например, когда строка данных кэша, в которой хранится 8-байтный указатель, вносится в память 104 (то есть, например, когда конкретная строка данных кэша или вся целиком вспомогательная кэш-память очищается (сбрасывается в постоянную память. Наконец, для процессора 102-1, когда данные фиксируются на выводах процессора 102-1, все 8 байт данных вносятся в память 104 за один последовательный непрерываемый переход, который может быть задержан под воздействием вспомогательной кэш-памяти 103-1, если она имеется. Для процессоров 1022102-Р все 8 байт данных вносятся в память 104 за один последовательный непрерываемый переход,который обеспечивается протоколом когерентности содержимого кэшей по вспомогательным кэшпамятям 103-1103-Р, что может задержать запись в память 104, если она есть. Однако, если 8-байтное значение указателя, такое как адрес памяти, который пересекает 8-байтную границу, записано в невыровненную ячейку в памяти 104, все 8 байт данных не могут быть переданы из процессора 102-1 с использованием единой команды запоминания 8 байтов. Вместо этого процессор 1021 может выдать две отдельных, отличающихся команды запоминания. Например, если адрес памяти начинается за 4 байта до 8-байтной границы (например, 8N-4), то первая команда запоминания передает 4 наиболее значимых байта в память 104 (например, 8N-4), тогда как вторая команда запоминания передает 4 менее значимых байта в память 104 (например, 8N). Важно, что между этими двумя отдельными командами запоминания процессор 102-1 может быть прерван, либо процессор 102-1 может потерять управление шиной 101 в пользу другого компонента системы (например, процессора 102-Р и т.д.). Следовательно, значение указателя, остающееся в памяти 104, будет недействительным до тех пор, пока процессор 102-1 не выполнит вторую команду запоминания. Если другой компонент начинает единое непрерываемое считывание из памяти в этой ячейке памяти, недействительное значение возвратится как-2 006038 предположительно действительное. Аналогично, новое 4-байтное значение указателя может быть записано в адрес памяти, кратный 4(например, 4N) с использованием единой непрерываемой операции. Отметим, что в примере, обсужденном выше, 4-байтное значение указателя может быть записано в ячейку памяти 8N-4 с использованием единой команды запоминания. Разумеется, если 4-байтное значение указателя записано в ячейку, которая пересекает 4-байтную границу, например 4N-2, все 4 байта данных не могут быть переданы из процессора 102-1 с использованием единой команды запоминания, и значение указателя, остающееся в памяти 104, может быть недействительным в течение некоторого периода времени. Система 100 также может включать в себя постоянную память (ПЗУ) 106, или другое устройство постоянного хранения, подключенное к шине 101, для хранения постоянной информации и команд для процессора 102-1. Запоминающее устройство 108, такое как магнитный или оптический диск, могут быть подключены к шине 101 для хранения информации и команд. Система 100 также может включать в себя дисплей 110 (например, ЖК монитор), и устройство 112 ввода (например, клавиатуру, мышь, трекбол и т.п.), подключенное к шине 101. Система 100 может включать в себя множество сетевых интерфейсов 114-1114-0, которые могут посылать и принимать электрические, электромагнитные или оптические сигналы, которые несут потоки цифровых данных, представляющие различные типы информации. В варианте выполнения сетевой интерфейс 114-1 может быть подключен к шине 101 и локальной вычислительной сети (ЛВС) 122, тогда как сетевой интерфейс 114-0 может быть подключен к шине 101 и региональной вычислительной сети (РВС) 124. Множество сетевых интерфейсов 114-1114-0 может поддерживать различные сетевые протоколы, включая, например, Gigabit Ethernet (например, стандарт IEEE 802.3-2002, опубликованный в 2002 г.), стандарт на волоконно-оптические каналы (например, стандартANSI X.3230-1994, опубликованный в 1994 г.) и т.п.Множество сетевых компьютеров 120-1120-N могут быть подключены к ЛВС 122 и РВС 124. В одном варианте выполнения ЛВС 122 и РВС 124 могут быть физически раздельными сетями, тогда как в другом варианте выполнения ЛВС 122 и РВС 124 могут сообщаться через сетевой шлюз или маршрутизатор (не показан для ясности). Альтернативно, ЛВС 122 и РВС 124 могут быть одной и той же сетью. Как указано выше, система 100 может обеспечивать услуги по преобразованию DNS. В варианте выполнения с преобразованием DNS услуги по преобразованию DNS могут быть в общем случае разделены между функциями сетевого транспорта и просмотра данных. Например, система 100 может быть серверным механизмом поиска (МП), оптимизированным для поиска данных в больших массивах данных, тогда как множеством сетевых компьютеров 120-1120-N может быть множество клиентских протокольных механизмов (ПМ) , оптимизированных для сетевой обработки и транспорта. МП может быть реализован на мощном многопроцессорном сервере, который хранит все множество DNS записей в памяти 104, чтобы облегчить высокоскоростные высокопроизводительные поиск и обновление. В альтернативном варианте выполнения услуги по преобразованию DNS могут обеспечиваться рядом мощных многопроцессорных серверов, или МП, каждый из которых хранит подмножество целого множестваDNS записей в памяти, чтобы облегчить высокоскоростные высокопроизводительные поиск и обновление. Напротив, множество ПМ может быть общими маломощными основанными на ПК машинами, выполняющими многозадачную операционную систему (например, Red Hat Linux 6.2), что минимизирует нагрузку на сетевую обработку и транспорт МП, чтобы максимизировать доступные источники для DNS преобразования. ПМ могут учитывать при обработке нюансы проводного DNS протокола, реагировать на недействительные DNS запросы и мультиплексировать действительные DNS запросы на МП по ЛВС 122. Количество ПМ для одного МП может быть определено, например, количеством DNS запросов,подлежащих обработке, в секунду, и характеристиками производительности конкретной системы. Для определения соответствующих соотношений отображения и поведения также могут использоваться другие меры. В общем случае могут поддерживаться другие крупномасштабные, основанные на запросах варианты выполнения, включая, например, преобразование телефонных номеров, обработку сигнализации SS7,определение местоположения, соотнесение телефонных номеров с абонентами, определение местоположения и наличия абонента и т.д. В варианте выполнения центральный сервер 140-1 оперативной обработки транзакций (00 Т - OnLine Transaction Processing, OLTP) может быть подключен к РВС 124 и принимать добавления, изменения и удаления (то есть, трафик обновления) в базе 142-1 данных от различных источников. Сервер 140-1 ООТ может посылать обновления в систему 100, которые включают в себя локальную копию базы 142-1 данных, по РВС 124. Сервер 140-1 ООТ может быть оптимизирован для обработки трафика обновления в различных форматах и протоколах, включая, например, протокол HTTP (протокол передачи гипертекста- HyperText Transmission Protocol), протокол RRP (протокол регистратора реестра Registry Registrar Protocol), протокол ЕРР (протокол расширяемого обеспечения - Extensible Provisioning Protocol), автоматизированный общий интерфейс (Mechanized Generic Interface) системы управления услугами/800 и другие протоколы оперативной обработки. Множество неизменяемых МП может быть объединено в архитектуру типа звезда для обеспечения высокоскоростной поисковой способности, объединенной с объемны-3 006038 ми пошаговыми обновлениями от сервера 140-1 ООТ. В альтернативном варианте выполнения данные могут быть распределены по множеству серверов 140-1140-S ООТ, каждый из которых может быть подключен к РВС 124. Серверы 140-1140-S ООТ могут принимать добавления, изменения и удаления (то есть трафик обновления) своих соответствующих баз 142-1142-S данных (не показаны для ясности) из различных источников. Серверы 140-1140-S ООТ могут посылать обновления в систему 100, которая может включать в себя копии баз 142-1142-S данных, другие динамически создаваемые данные и т.п.по РВС 124. Например, в варианте выполнения определения местоположения серверы 140-1140-S ООТ могут принимать трафик обновления от групп удаленных датчиков. В другом альтернативном варианте выполнения множество сетевых компьютеров 120-1120-N также могут принимать добавления, изменения и удаления (то есть трафик обновления) от различных источников по РВС 124 или ЛВС 122. В этом варианте выполнения множество сетевых компьютеров 120-1120-N могут отправлять обновления, а также запросы, в систему 100. В варианте выполнения преобразования DNS каждый ПМ (например, каждый из множества сетевых компьютеров 120-1120-N) может объединять или уплотнять несколько сообщений с DNS запросами, принятыми по региональной вычислительной сети (например, РВС 124), в единый Суперпакет запросов, и посылать этот Суперпакет запросов на МП (например, в систему 100), по локальной вычислительной сети (например, ЛВС 122) . МП может объединять или уплотнять несколько ответов на сообщения с DNS запросами в единый Суперпакет ответов и посылать этот Суперпакет ответов в соответствующий ПМ по локальной вычислительной сети. В общем случае, максимальный размер Суперпакета запросов или ответов может быть ограничен максимальным размером передаваемого блока данных(Maximum Transmission Unit - MTU) физического сетевого уровня (например, Gigabit Ethernet). Например, размеры сообщений типичных DNS запросов и ответов менее 100 байт и 200 байт соответственно позволяют мультиплексировать более чем 30 запросов в единый Суперпакет запросов, а также позволяют мультиплексировать 15 ответов в единый Суперпакет ответов. Однако в единый Суперпакет запросов может быть включено меньшее количество запросов (например, 20 запросов), чтобы избежать переполнения MTU в ответ (например, 10 ответов). Для больших размеров MTU количество мультиплексированных запросов и ответов может соответственно увеличиться. Каждый многозадачный ПМ может включать в себя входящий поток и исходящий поток, чтобы управлять DNS запросами и ответами соответственно. Например, входящий поток может распаковывать составляющие DNS запроса из входящих пакетов DNS запросов, принятых по региональной вычислительной сети, и мультиплексировать несколько миллисекунд запросов в единый Суперпакет запросов. Входной поток может затем отправлять Суперпакет запросов на МП по локальной вычислительной сети. Напротив, выходной поток может принимать Суперпакет ответов от МП, демультиплексировать ответы,содержащиеся в нем, и упаковывать различные поля в действительные DNS ответы, которые могут затем передаваться по региональной вычислительной сети. В общем случае, как упомянуто выше, могут поддерживаться другие объемные основанные на запросах варианты выполнения. В варианте выполнения Суперпакет запросов также может включать в себя информацию о состоянии, связанную с каждым DNS запросом, таким как, например, адрес источника, тип протокола и т.п.МП может включать в себя информацию о состоянии и связанные DNS ответы в Суперпакете ответов. Каждый ПМ может затем конструировать и возвращать сообщения действительных DNS ответов, используя информацию, переданную от МП. Следовательно, каждый ПМ может преимущественно работать как машина, функционирующая без учета предыдущего состояния, то есть действительные DNS ответы могут формироваться из информации, содержащейся в Суперпакете ответов. В общем случае, МП может возвращать Суперпакет ответов на ПМ, из которого исходит входящий Суперпакет; однако, возможны также и другие варианты. В альтернативном варианте выполнения каждый ПМ может поддерживать информацию о состоянии, связанную с каждым DNS запросом, и включать в себя ссылку или указатель на информацию о состоянии в Суперпакете запросов. МП может включать в себя ссылки на информацию о состоянии и связанные DNS ответы в Суперпакете ответов. Каждый ПМ может затем конструировать и возвращать сообщения с действительным DNS ответом с использованием переданных от МП ссылок на информацию о состоянии, а также самой информации о состоянии, хранящейся в нем. В этом варианте выполнения МП может возвращать Суперпакет ответов на ПМ, из которого исходит входящий Суперпакет. На фиг. 2 представлена подробная блок-схема, иллюстрирующая структуру данных сообщения в соответствии с вариантом выполнения настоящего изобретения. В общем случае сообщение 200 может включать в себя заголовок 210 со множеством номеров 211-1 211-S последовательностей и множеством счетчиков 212-1 212-S сообщений, а также с полезной нагрузкой 215 данных. В варианте выполнения преобразования DNS сообщение 200 может быть использовано для Суперпакетов запросов и Суперпакетов ответов. Например, Суперпакет 220 запросов может включать в себя заголовок 230, имеющий множество номеров 231-1231-S последовательностей и множество счетчиков 232-1232-S сообщений, а также полезную нагрузку 235 данных, имеющую множество DNS запросов 236-1236-Q, собранных ПМ за заранее заданный период времени, такой как, например, несколько миллисекунд. В одном варианте выполнения каждый DNS запрос 236-1236-Q может включать в себя-4 006038 информацию о состоянии, тогда как в альтернативном варианте выполнения каждый DNS запрос 236-1236-Q может включать в себя указатель на информацию о состоянии. Аналогично, Суперпакет 24 0 ответов может включать в себя заголовок 250, имеющий множество номеров 251-1251-S последовательностей и множество счетчиков 252-1252-S сообщений, а также полезную нагрузку 255 данных, имеющую множество DNS ответов 256-1256-R, приблизительно соответствующих множеству DNS запросов, содержащихся в Суперпакете 220. В одном варианте выполнения каждый DNS ответ 256-1256-R может включать в себя информацию о состоянии, связанную с соответствующим DNS запросом, тогда как в альтернативном варианте выполнения каждый DNS ответ 256-1256-R может включать в себя указатель на информацию о состоянии, связанную с соответствующим DNS запросом. Иногда общий размер соответствующих DNS ответов может превышать размер полезной нагрузки 255 данных Суперпакета 240 ответов. Это переполнение может быть ограничено, например, единственным ответом, то есть ответом, связанным с последним запросом, содержащимся в Суперпакете 220 запросов. Вместо отправления дополнительного Суперпакета 240 ответов, содержащего только один ответ, ответ о переполнении может быть предпочтительно включен в следующий Суперпакет 240 ответов, соответствующий следующему Суперпакету запросов. Преимущественно, заголовок 250 может включать в себя соответствующую информацию для определения продолжительности состояния переполнения. При пиковых условиях обработки из-за переполнения в следующий Суперпакет ответов может попасть более чем один ответ. Например, в Суперпакете 240 заголовок 250 может включать в себя по меньшей мере два номера 251-1 и 251-2 последовательностей и по меньшей мере два счетчика 252-1 и 252-2 сообщений, сгруппированных в две пары комплементарных полей. Хотя может иметься количество S пар номеров последовательностей и счетчиков сообщений, обычно S является небольшим числом, таким как 2, 3, 4 и т.д. Таким образом, заголовок 250 может включать в себя номер 251-1 последовательности в паре со счетчиком 252-1 сообщений, номер 251-2 последовательности в паре со счетчиком 252-2 сообщений и т.д. В общем случае, счетчик 252-1 сообщений может отражать количество ответов, содержащихся в полезной нагрузке 25 данных, которая связана с номером 251-1 последовательности. В варианте выполнения номер 251-1 последовательности может быть 2-байтным полем, тогда как счетчик 252-1 сообщений может быть 1-байтным полем. В более конкретном примере полезная нагрузка 235 Суперпакета 220 запросов может включать в себя семь DNS запросов (как показано на фиг. 2). В одном варианте выполнения номер 231-1 последовательности может быть установлен на уникальное значение (например, 1024), счетчик 232-1 сообщений может быть установлен на 7, а номер 231-2 последовательности и счетчик 232-2 сообщений могут быть установлены на нуль. В другом варианте выполнения заголовок 230 может содержать только один номер последовательности и один счетчик сообщений, например, номер 231-1 последовательности и счетчик 232-1 сообщений установлены на 1024 и 7 соответственно. В общем случае Суперпакет 220 запросов может содержать все запросы, связанные с конкретным номером последовательности. Полезная нагрузка 255 данных Суперпакета 240 ответов может включать в себя семь DNS ответов(как показано на фиг. 2). В этом примере заголовок 250 может включать в себя информацию, аналогичную Суперпакету 220, то есть номер 251-1 последовательности может быть установлен на уникальное значение (например, 1024), счетчик 252-1 сообщений установлен на 7, а совместно номер 252-2 последовательности и счетчик 252-2 сообщений могут быть установлены на нуль. Однако в другом примере полезная нагрузка 255 данных Суперпакета 240 ответов может включать в себя лишь пять соответствующих DNS ответов, а счетчик 252-1 сообщений может быть вместо предыдущего установлен на 5. Оставшиеся два ответа, связанные с номером 1024 последовательности, могут быть включены в новый Суперпакет 240 ответов. Следующий Суперпакет 240 запросов может включать в себя отличающийся номер последовательности (например, 1025) и по меньшей мере один DNS запрос, так что следующий Суперпакет 240 ответов может включать в себя два предыдущих ответа, связанных с номером последовательности 1024, а также по меньшей мере один ответ, связанный с номером последовательности 1025. В этом примере заголовок 250 следующего Суперпакета 240 ответов может включать в себя номер 251-1 последовательности, установленный на 1024, счетчик 252-1, установленный на 2, номер 251-2 последовательности, установленный на 1025, и счетчик 252-2, установленный на 1. Таким образом, Суперпакет 240 ответов всего может включать в себя три ответа, связанных с тремя запросами, содержащимися в разных Суперпакетах запросов. На фиг. 3 показана подробная блок-схема, иллюстрирующая архитектуру структуры данных задержки сообщений в соответствии с вариантом выполнения настоящего изобретения. Структура 300 данных задержки сообщений может включать в себя информацию, связанную с передачей и приемом сообщения 200. В варианте выполнения с разрешением преобразования DNS структура 300 данных задержки сообщений может включать в себя информацию задержки в Суперпакетах запросов и Суперпакетах ответов; эта информация задержки может быть организована в табличном формате, проиндексированном в соответствии со значением номера последовательности (например, индекс 301) . Например,структура 300 данных задержки сообщений может включать в себя количество рядов N, равное общему-5 006038 количеству уникальных номеров последовательностей, как показано в общем случае элементами 310, 320 и 330 таблицы. В варианте выполнения номера последовательности в заголовке Суперпакета могут иметь 2 байта в длину и определять диапазон уникальных номеров последовательностей от нуля до 216 - 1 (то есть 65535). В этом случае N может быть равно 65536. Информация задержки может включать в себя отметку 302 времени запросов, счетчик 303 запросов, отметку 304 времени ответов, счетчик 305 ответов и счетчик 306 ответных сообщений. В альтернативном варианте выполнения информация задержки также может включать в себя отметку времени начального ответа (не показана). В примере элемент 320 таблицы иллюстрирует информацию задержки для Суперпакета 220, имеющего номер 231-1 единственной последовательности, равный 1024. Отметка 302 времени запросов может показывать, когда этот конкретный Суперпакет запросов был отослан на МП. Счетчик 303 запросов может показывать, сколько запросов содержатся в конкретном Суперпакете запросов. Отметка 304 времени ответов может показывать, когда Суперпакет ответов, имеющий номер последовательности, равный 1024, был получен ПМ (например, сетевым компьютером 120-N) и может быть обновлен, если на ПМ был принят более чем один Суперпакет ответов. Счетчик 305 ответов может показывать общее количество ответов, содержащихся внутри всех принятых Суперпакетов запросов, связанных с этим номером последовательности (то есть 1024). Счетчик 306 ответных сообщений может показывать, сколько Суперпакетов ответов, имеющих этот номер последовательности (то есть 1024), поступило на ПМ. Ответы на запросы, содержащиеся в конкретном Суперпакете запросов, могут быть разбиты между несколькими Суперпакетами ответов, и в этом случае отметка 304 времен ответов, счетчик 305 ответов и счетчик 306 ответных сообщений могут быть обновлены, когда принимается каждый из дополнительных Суперпакетов ответов. В альтернативном варианте выполнения отметка времени начального ответа может показывать, когда первый Суперпакет ответов, содержащий ответы на этот номер последовательности (то есть 1024), был получен ПМ. В этом варианте выполнения отметка 304 времени ответов может быть обновлена, когда принимаются дополнительные (то есть второй и последующие) Суперпакеты ответов. Из информации задержки, содержащейся в структуре 300 данных задержки сообщений, можно определить различные важные метрики задержки. Например, простая перекрестная проверка между счетчиком 303 запросов и счетчиком 305 ответов для заданного индекса 301 (то есть для номера последовательности), может показать количество пропущенных ответов. Эта разница может показывать количество запросов, необъяснимо отброшенных МП. Сравнение отметки 302 времени запросов и отметки 304 времени ответов может показать, насколько хорошо конкретное сочетание ПМ/МП может работать при текущей нагрузке сообщений. Разница между текущим номером последовательности Суперпакета запросов и текущим номером последовательности Суперпакета ответов может быть связана с эффективностью ответа для МП; например, чем больше разница, тем меньше производительность. Счетчик 306 ответных сообщений может показывать, сколько Суперпакетов ответов используются для каждого Суперпакета запросов, и может быть важен при анализе трафика преобразования DNS. Когда задержка запросов и ответов, проходящих между ПМ и МП, увеличивается, ПМ могут уменьшить количество пакетов DNS запросов, обрабатываемых системой. В общем случае МП может выполнять многопоточный просмотр входящих уплотненных Суперпакетов запросов и может объединять ответы в исходящие уплотненные Суперпакеты ответов. Например,МП может выделить один поисковый поток или процесс для каждого активного ПМ и перенаправлять все входящие Суперпакеты запросов от этого ПМ в поисковый поток. МП может выделить управляющий поток, чтобы управлять связью ПМ с поисковыми потоками, а также поток или процесс обновления,чтобы обновлять базу данных, расположенную в памяти 104. Каждый поисковый поток может извлекать поисковые запросы из входящего Суперпакета запросов, исполнять различные поиски, создавать исходящий Суперпакет ответов, содержащий поисковые ответы, и посылать Суперпакет на соответствующий ПМ. Поток обновления может получать обновления базы данных от сервера 140-1 ООТ и внедрять новые данные в базу данных. В альтернативном варианте выполнения множество сетевых компьютеров 120-1120-N могут отправлять обновления в систему 100. Эти обновления могут включаться, например, внутрь потока сообщений входящего Суперпакета запросов. Соответственно, на основании протокола Суперпакетов МП может тратить менее 15% пропускной способности процессора на сетевую обработку, тем самым существенно увеличивая пропускную способность поисковых запросов. В варианте выполнения компьютер IBM 8-way M80 может поддерживать скорости поиска в 180-220 тыс. запросов в секунду (з/с), тогда как компьютер IBM 24-way S80 может поддерживать скорость 400-500 тыс. з/с. Удвоение скоростей поиска, то есть до 500 тыс. и до 1 млн. з/с соответственно, просто требует вдвое больше аппаратного обеспечения, то есть, например, двух МП с их сопутствующими ПМ. В другом варианте выполнения двухпроцессорный персональный компьютерPentium III 8 66 МГц, работающий под управлением Red Hat Linux 6.2, может выдерживать скорости обновления порядка 100 КБайт/с. Конечно, увеличение аппаратной производительности также увеличит скорости поиска и обновления, связанные с вариантами выполнения настоящего изобретения, и по мере того, как производители заменяют эти многопроцессорные компьютеры более быстрыми машинами, например, выдерживаемые скорости поиска и обновления могут соизмеримо вырасти. В общем случае,система 100 не ограничена клиентской или серверной архитектурой, и варианты выполнения настоящего-6 006038 изобретения не ограничены никаким специальным сочетанием программного и/или аппаратного обеспечения. На фиг. 4 показана блок-схема, иллюстрирующая общую архитектуру баз данных в соответствии с вариантом выполнения настоящего изобретения. В этом варианте выполнения база данных 400 может включать в себя по меньшей мере одну таблицу или группу записей 401 в базе данных, и по меньшей мере один соответствующий поисковый индекс 402 с указателями (индексами, прямыми сдвигами байтов и т.п.) на конкретные записи в группе записей 401 в базе данных. Например, указатель 405 может ссылаться на запись 410 базы данных. В одном варианте выполнения база данных 400 может включать в себя по меньшей мере одну хэштаблицу 403 как поисковый индекс с указателями (индексами, прямыми сдвигами байтов и т.п.) в таблице или группе записей 401 в базе данных. Хэш-функция может отображать ключ поиска на целочисленное значение, которое затем может быть использовано как индекс в хэш-таблице 403. Поскольку более одного ключа поиска могут отображаться на единственное целочисленное значение, хэш-группы могут создаваться с помощью однонаправленного списка указателей хэш-цепочек. Например, каждая запись в хэш-таблице 403 может содержать указатель на первый элемент хэш-группы, а каждый элемент хэшгруппы может содержать указатель хэш-цепочки на следующий элемент или запись в базе данных в связанном списке. Преимущественно, указатель хэш-цепочки может требоваться только для тех элементов или записей в базе данных, которые ссылаются на последующий элемент в хэш-группе. Хэш-таблица 403 может включать в себя матрицу 8-байтных указателей на отдельные записи 401 в базе данных. Например, хэш-указатель 404 в хэш-таблице 403 может ссылаться на запись 420 в базе данных как на первый элемент в хэш-группе. Элемент 420 в базе данных может содержать указатель 424 хэш-цепочки, который может ссылаться на следующий элемент или запись в базе данных, в хэш-группе. Запись 420 в базе данных также может включать в себя длину 421 данных, и связанные с ней данные 422 постоянной или меняющейся длины. В вариант выполнения может быть также включен нулевой символ 423, указывающий на окончание данных 422. Дополнительно, запись 420 в базе данных может включать в себя указатель 425 данных, который может ссылаться на запись в другой базе данных, либо в группе записей 4 01 в базе данных, либо в другой группе записей в базе данных (не показана) , в которой могут быть расположены дополнительные данные. Система 100 может использовать различные известные алгоритмы для поиска заданного поискового термина или ключа по этой архитектуре структуры данных. В общем случае по базе 400 данных поиск может вестись множеством поисковых процессов или потоков, выполняемых по меньшей мере на одном из множества процессоров 102-1102-Р. Однако изменения в базе 400 данных могут не выполняться полностью потоком (-ами) обновления, если только поисковому(-ым) потоку(-ам) не запрещено получать доступ к базе 400 данных на период времени, необходимый для добавления, изменения или удаления информации в базе 400 данных. Например, для того, чтобы изменить запись 430 в базе 400 данных, группа записей 401 в базе данных может быть блокирована потоком обновления, чтобы запретить поисковым запросам получать доступ к базе 400 данных, пока поток обновления модифицирует информацию в записи 430 в базе данных. Существует множество известных механизмов блокирования базы данных, чтобы запретить доступ для поиска, включая использование циклических блокировок, семафоров и мьютексов(взаимных исключений) и т.п. Кроме того, различные коммерческие базы данных обеспечивают специальные команды для блокирования всей базы 400 данных или ее частей, например, команда блокирования таблицы в базе данных Oracle 8, выпускаемой Oracle Corporation (город Редвуд Шорс, штат Калифорния). На фиг. 5 показана подробная блок-схема, иллюстрирующая общую архитектуру базы данных в соответствии с другим вариантом выполнения настоящего изобретения. В этом варианте выполнения база 500 данных может включать в себя высокооптимизированный главный файл 510 (копия состояния в заданный момент времени), доступный только для чтения и растущий файл 520 предыстории. Главный файл 510 может включать в себя по меньшей мере одну таблицу или группу 511 записей в базе данных, и по меньшей мере один соответствующий поисковый индекс 512 с указателями (индексами, прямыми сдвигами байтов и т.п.) на конкретные записи внутри группы 511 записей в базе данных. Альтернативно главный файл 510 может включать в себя по меньшей мере одну хэш-таблицу 513 в качестве поискового индекса с указателями (индексами, прямыми сдвигами байтов и т.п.) в таблице или группе 511 записей в базе данных. Аналогично файл 520 предыстории может включать в себя по меньшей мере две таблицы или группы записей в базе данных, в том числе записи 521 добавления в базу данных и записи 532 удаления из базы данных. Могут быть предусмотрены соответствующие поисковые индексы 522 и 532 с указателями (индексами, прямыми сдвигами байтов и т.п.) на конкретные записи внутри записей 521 добавления в базу данных и записей 531 удаления из базы банных. Альтернативно файл 520 предыстории может включать в себя хэш-таблицы 523 и 533 в качестве поисковых индексов с указателями (индексами, прямыми сдвигами байтов и т.п.) среди записей 521 добавления в базу данных и записей 531 удаления из базы данных соответственно. Система 100 может использовать различные общеизвестные алгоритмы для поиска заданного поискового термина или ключа по этой архитектуре структуры данных. В типичном примере файл 520 пре-7 006038 дыстории может включать в себя все последние изменения данных, и по нему может проводиться поиск до главного файла 510, доступного только для чтения. Если ключ поиска обнаруживается в файле 520 предыстории, ответ возвращается без получения доступа к главному файлу (файлу копии) 510, но если ключ не обнаружен, то затем поиск может быть проведен по файлу 510 копии. Однако, когда файл 520 предыстории более не совпадает в памяти 104 с главным файлом 510, частота поисковых запросов заметно падает, например, в 10-50 раз или даже более. Следовательно, чтобы избежать какого-либо падения в частоте поисковых запросов или минимизировать его, главный файл 510 может периодически подвергаться обновлению, или повторному созданию путем включения всех добавлений, удалений и изменений, содержащихся в файле 520 предыстории. Данные внутри главного файла 510 физически не изменяются, но логически добавляются, изменяются или удаляются. Например, данные внутри главного файла 510 могут быть удалены или логически забыты путем создания соответствующей записи удаления среди записей 531 удаления из базы данных, и внесения указателя на запись удаления в соответствующую ячейку в хэш-таблице 533. Данные в главном файле 510 могут быть логически изменены путем копирования записи данных из главного файла 510 в новую запись данных среди записей 521 добавления в базе данных, изменения данных в новом элементе, а затем внесения указателя на новый элемент в соответствующую хэш-таблицу (например,хэш-таблицу 522), или хэш-цепочки в записи 521 добавления в базе данных. Аналогично, данные внутри главного файла 510 могут быть логически добавлены к главному файлу 510 путем создания новой записи данных среди записей 521 добавления в базе данных, и затем внесения указателя на новый элемент в соответствующую хэш-таблицу (например, хэш-таблицу 522) или хэш-цепочки в записи 521 добавления в базе данных. В варианте выполнения преобразования DNS, например, главный файл 510 может включать в себя данные доменных имен и данные сервера имен, организованные как отдельные таблицы или блоки данных, с раздельными поисковыми индексами (например, 511-1, 511-2, 512-1, 512-2, 513-1, 513-2 и т.п., не показаны для ясности). Аналогично, файл 520 предыстории может включать в себя добавления и изменения как для данных доменных имен, так и для данных сервера имен, равно как и удаления для данных доменных имен и для данных сервера имен (например, 521-1, 521-2, 522-1, 522-2, 523-1, 523-2, 532-1,532-2, 533-1, 533-2 и т.п., не показаны для ясности). На фиг. 6 показана подробная блок-схема, иллюстрирующая общую архитектуру базы данных в соответствии с вариантом выполнения настоящего изобретения. В общем случае, база 600 данных может быть организована в единое пригодное для поиска представление данных. Обновления набора данных могут непрерывно включаться в базу 600 данных, а удаления и изменения могут физически выполняться на соответствующих записях в базе данных, чтобы освободить место в памяти 104, например, для последующих добавлений или изменений. Единое пригодное для поиска представление хорошо масштабируется до больших размеров наборов данных и высоких частот поиска и обновлений и устраняет необходимость в периодическом повторном создании, распространении и перезагрузке файлов мгновенного состояния среди множества компьютеров поискового механизма. В варианте выполнения преобразования DNS, например, база 600 данных может включать в себя данные 610 доменных имен и данные 620 сервера имен. Данные 610 доменных имен и данные 620 сервера имен могут включать в себя поисковые индексы с указателями (индексами, прямыми сдвигами байтов и т.п.) в блоках записей различной длины. Как описано выше, хэш-функция может преобразовывать ключ поиска в целочисленное значение, которое затем может быть использовано как индекс в хэштаблице. Аналогично, хэш-группы могут быть созданы для каждой хэш-таблицы с помощью однонаправленного списка указателей хэш-цепочек. Данные 610 доменных имен могут включать в себя, например, хэш-таблицу 612 в качестве поискового индекса и блок записей 611 переменной длины доменных имен. Хэш-таблица 612 может включать в себя матрицу 8-байтных указателей на отдельные записи 611 доменных имен, такие как, например, указатель 613, ссылающийся на запись 620 доменного имени. Запись 620 переменной длины доменного имени может включать в себя, например, сдвиг 621 следующей записи, длину 622 имени, нормированное имя 623, указатель 624 цепочки (то есть, например, указывающий на следующую запись в хэш-цепочке), количество серверов 625 имен и указатель 626 серверов имен. Размеры как указателя 624 цепочки, так и указателя 626 сервера имен могут быть оптимизированы,чтобы отражать требуемый размер блока для каждого конкретного типа данных, например, 8 байтов для указателя 624 цепочки и 4 байта для указателя 626 сервера имен. Данные 630 сервера имен могут включать в себя, например, хэш-таблицу 632 в качестве поискового индекса и блок записей 631 переменной длины серверов имен. Хэш-таблица 632 может включать в себя матрицу 4-байтных указателей на отдельные записи 631 серверов имен, такие как, например, указатель 633, ссылающийся на запись 640 сервера имен. Запись 640 переменной длины сервера имен может включать в себя, например, смещение 641 следующей записи, длину 642 имени, нормированное имя 643, указатель 644 цепочки (то есть, например, указывающий на следующую запись в хэш-цепочке), количество сетевых адресов 645 серверов имен, длина 646 адреса сервера имен и сетевой адрес 647 сервера имен,которым, например, может быть IP (Протокол Интернета - Internet Protocol) сетевой адрес. В общем случае сетевые адреса серверов имен могут храниться в формате ASCII (American Standard Code for Informa-8 006038tion Interchange Американский стандартный код для обмена информацией) (например, ISO-14962-1997,ANSI-X3.4-1997 и т.д.), либо в двоичном формате; в этом примере длина 646 сетевого адреса сервера имен указывает, что сетевой адрес 647 сервера имен хранится в двоичном формате (то есть 4 байта). Размер указателя 644 цепочки также может быть оптимизирован, чтобы отражать требуемый размер блока данных о сервере имен, например, 4 байта. В общем случае, как поисковые индексы, такие как хэш-таблицы, так и записи данных переменной дины могут быть структурированы так, что 8-байтные указатели располагаются на 8-байтных границах в памяти. Например, хэш-таблица 612 может содержать непрерывную матрицу 8-байтных указателей на записи 611 доменных имен, и может храниться в адресе памяти, кратном 8 (то есть на 8-байтной границе,8N). Аналогично, как поисковые индексы, такие как хэш-таблицы, так и записи данных переменной длины могут быть структурированы так, что 4-байтные указатели располагаются на 4-байтных границах в памяти. Например, хэш-таблица 632 может содержать непрерывную матрицу 4-байтных указателей на записи 631 о серверах имен и может храниться в адресе памяти, кратном 4 (то есть на 4-байтной границе,4N) . Следовательно, изменения в базе 600 данных могут завершаться обновлением указателя на выровненный адрес в памяти с использованием единой непрерываемой операции, включая, например, внесение нового указателя в поисковый индекс, такой как хэш-таблицу, или внесение нового указателя хэшцепочки на запись данных переменной длины. На фиг. 7 показана подробная блок-схема, иллюстрирующая общую архитектуру базы данных в соответствии с вариантом выполнения настоящего изобретения. В общем случае, база 700 данных также может быть организована в единое пригодное для поиска представление данных. Обновления набора данных могут непрерывно включаться в базу 700 данных, а удаления и изменения могут физически выполняться на соответствующих записях в базе данных, чтобы освободить место в памяти 104, например,для последующих добавлений или изменений. Единое пригодное для поиска представление хорошо масштабируется до больших размеров наборов данных и высоких частот поиска и обновлений и устраняет необходимость в периодическом повторном создании, распространении и перезагрузке главных файлов мгновенного состояния среди множества компьютеров поискового механизма. Возможно множество типов организации физической структуры данных. Организация в данном примере может использовать альтернативный поисковый индекс хэш-таблиц для упорядоченного последовательного доступа к записям данных, таких как дерево TST (ternary search tree) троичного поиска(trie), которое объединяет свойства деревьев двоичного поиска и trie-структуры цифрового поиска. В приложениях с текстовым интерфейсом, таких как, например, услуга whois (кто есть кто), разрешение доменных имен с использованием защищенных расширений DNS (IETF RFC:2535 - Internet EngineeringTask Force Request for Comments - Целевая группа инженерной поддержки интернета, Запрос на комментарий:2535) и т.п.Преимущественно, TST минимизирует количество операций сравнения, подлежащих выполнению, особенно в случае неудачи поиска, и может обусловить метрики производительности поиска, превосходящие воплощения поискового механизма с хэшированием. Дополнительно TST также могут обеспечить продвинутые свойства поиска по тексту, такие как, например, поиски с групповым символом, которые могут быть полезны в применениях поиска по тексту, таких как, например, сервис whois,разрешение доменных имен, контекстный поиск по Интернету и т.д. В варианте выполнения TST может содержать последовательность узлов, связанных вместе в иерархическое отношение. Корневой узел может быть расположен на вершине дерева, связанные с ним дочерние узлы и линии родства могут образовать ветви, и каждая ветвь может оканчиваться узламилистьями. Каждый узел-лист может быть ассоциирован с конкретным ключом поиска, и каждый узел на пути к узлу-листу может содержать единый последовательный элемент ключа. Каждый узел в дереве содержит символ сравнения, или значение-разделитель, и три указателя на другие последовательные узлы в дереве, или на дочерние узлы. Эти указатели ссылаются на дочерние узлы, значения-разделители которых меньше, равны или больше значения-разделителя узла. Поиск конкретного ключа по TST, следовательно, включает в себя прохождение по дереву от корневого узла до конечного узла-листа, с последовательным сравнением каждого элемента, или положения символа, для ключа со значениямиразделителями узлов на пути. Дополнительно узел-лист может также содержать указатель на запись ключа, которая, в свою очередь, содержит по меньшей мере один указатель на запись конечных данных,содержащую данные записи, связанные с ключом (например, IP-адрес). Альтернативно, запись ключа может содержать данные записи во всей их полноте. Данные записи могут храниться в двоичном формате, текстовом формате ASCII и т.п. В варианте выполнения база 700 данных может быть организована как TST, включая в себя множество узлов 701 поиска фиксированной длины, множество записей 702 данных ключей переменной длины и множество записей 703 конечных данных переменной длины. Узлы 701 поиска могут включать в себя различные типы информации, как описано выше, включая, например, символ (или значение) и положение сравнения, указатели узлов ветвей и указатель ключа. Размер указателей узлов в общем случае может быть определен количеством узлов, тогда как размер указателей ключей может быть в общем случае определен размером набора данных ключа переменной длины. Записи 702 данных ключей могут содержать информацию ключа и информацию конечных данных, включая, например, указатели на записи ко-9 006038 нечных данных или встроенные данные записи, тогда как записи 703 конечных данных могут содержать данные записи. В варианте выполнения каждый узел поиска фиксированной длины может иметь длину 24 байта. Узел 710 поиска, например, может содержать 8-битный символ 711 сравнения (или значение байта), 12 битное положение 712 символа (или байта) и 12-битный тип/статус узла (не показаны для ясности); эти данные могут быть закодированы в первых четырех байтах узла. Символ 711 сравнения может быть закодирован в первом байте узла, как показано на фиг. 7, или, альтернативно, положение 712 символа может быть закодировано в первых 12 битах узла, чтобы оптимизировать доступ к положению 712 символа с помощью простой операции сдвига. Следующие 12 байтов каждого узла поиска могут содержать три 32-битных указателя, то есть указатель 713, указатель 714 и указатель 715, представляющие собой указатели узлов ветвей, соответственно, меньше чем, равно и больше чем. Эти указатели могут содержать счетчик, или индекс узла, вместо сдвига байтов или адреса памяти. Для узлов поиска с фиксированной длиной сдвиг байтов может быть вычислен из счетчика, или значения индекса, и фиксированной длины, например, длины счетчика. Конечные 4 байта могут содержать 40-битный указатель 716 ключа,который может быть нулевым значением, показывающим, что соответствующая запись данных ключа не существует (показан), либо указатель на существующую соответствующую запись данных ключа (не показан), а также могут содержать другие данные, включая, например, 12-битную длину ключа и поле типа/статуса 12-битного указателя. Указатель 716 ключа может содержать сдвиг байтов на соответствующую запись данных ключа, тогда как длина ключа может использоваться для оптимизации поиска и ввода при устранении однонаправленного ветвления в TST. Поле типа/статуса указателя может содержать информацию, используемую для проверки действительности, и данные о распределении, используемых в управлении памятью. В варианте выполнения запись 750 данных ключа может включать в себя, например, ключ 753 переменной длины и по меньшей мере один указатель конечных данных. Как показано на фиг. 7, запись 750 данных ключа включает в себя два указателя конечных данных: указатель 757 конечных данных и указатель 758 конечных данных. Записи 750 данных ключа может предшествовать длина 751 12-битного ключа и счетчик/статус 752 12-битного конечного указателя, и она может включать в себя заполнение (не показано для ясности) , чтобы выровнять указатель 757 конечных данных и указатель 758 конечных данных на 8-байтной границе в памяти 104. Каждый из указателя 757 конечных данных и указателя 758 конечных данных может содержать различные данные, такие как, например, тип, длина, статус или другие данные конечных данных, полезные для двоичного поиска по записям. Указатель 757 конечных данных и указатель 758 конечных данных могут быть отсортированы по типу конечных данных для более быстрого отыскания записей конкретных ресурсов (например, записи 760 конечных ресурсов и записи 770 конечных ресурсов). В другом варианте выполнения запись 740 данных ключа может включать в себя внедренные конечные данные 746 вместо указателей записей конечных данных или вместе с ними. Например, запись 740 данных ключа может включать в себя длину 741 ключа, счетчик 742 конечного указателя, ключ 743 переменной длины, некоторое количество внедренных элементов 744 записей, за которыми следует длина 745 элемента записи (в байтах, например) и внедренные данные 746 записей (например, строку, последовательность байтов и т.п.) для каждого из внедренных элементов 744 записей. В варианте выполнения запись 760 конечных данных, например, может включать в себя 12-битную длину 761, 4-битный статус и строку 762 переменной длины (например, IP-адрес). Альтернативно, строка 762 переменной длины может быть последовательностью байтов. Запись 760 конечных данных может включать в себя заполнение, чтобы выровнять каждую запись конечных данных на 8-байтной границе в памяти 104. Альтернативно, запись 760 конечных данных может включать в себя заполнение до 4 байтной границы, либо запись 760 конечных данных может не включать никакого заполнения. Алгоритмы управления памятью могут определять, в общем случае, дополнены ли записи 760 конечных данных до 8-байтной, 4-байтной или 0-байтной границ. Аналогично, запись 770 конечных данных может включать в себя 12-битную длину 771, 4-битный статус и строку 772 переменной длины (например IP-адрес). В общем случае как поисковые индексы, такие как TST, так и записи данных могут быть структурированы так, что 8-байтные указатели расположены на 8-байтных границах в памяти. Например, указатель 726 ключа может содержать 8-байтный (или меньше) указатель на запись 740 данных ключа и может храниться в адресе памяти, кратном 8 (то есть, на 8-байтной границе, или 8N). Аналогично, как поисковые индексы, такие как TST, так и записи данных могут быть структурированы так, что 4-байтные указатели расположены на 4-байтных границах в памяти. Например, указатель 724 ключа может содержать 4-байтный (или меньше) указатель на узел 730 и может храниться в адресе памяти, кратном 4 (то есть, на 4-байтной границе, или 4N). Следовательно, изменения в базе 700 данных могут завершаться обновлением указателя на выровненный адрес в памяти с помощью единой непрерываемой операции,включая, например, внесение нового указателя в поисковый индекс, такой как узел TST, или внесение нового указателя на запись данных. На фиг. 8 показана подробная блок-схема, иллюстрирующая общую архитектуру базы данных в соответствии с вариантом выполнения настоящего изобретения. Как и выше, база 800 данных также может быть организована в единое пригодное для поиска представление данных. Обновления набора данных- 10006038 могут непрерывно включаться в базу 800 данных, а удаления и изменения могут физически выполняться на соответствующих записях в базе данных, чтобы освободить место в памяти 104, например, для последующих добавлений или изменений. Единое пригодное для поиска представление хорошо масштабируется до больших размеров наборов данных и высоких частот поиска и обновлений и устраняет необходимость в периодическом повторном создании, распространении и перезагрузке главных файлов мгновенного состояния среди множества компьютеров поискового механизма. Для получения доступа к данным записей возможно использовать другие структуры индекса поиска. В варианте выполнения база 800 данных может быть использована как альтернативно упорядоченный поисковый индекс, организованный в виде дерева с ключом упорядоченного доступа (то есть, дерево КУД - ordered access key, OAK). База 800 данных может включать в себя, например, множество узлов 801 поиска переменной длины, множество записей 802 ключей переменной длины и множество записей 803 конечных данных переменной длины. Узлы 801 поиска могут включать в себя различные типы информации, как описано выше, такие как, например, ключи поиска, указатели на другие узлы поиска, указатели на записи ключей и т.п. В варианте выполнения множество узлов 801 поиска могут включать в себя вертикальные и горизонтальные узлы, содержащие фрагменты ключей поиска (например, строки), а также указатели на другие узлы поиска или записи ключей. Вертикальные узлы могут включать в себя,например, по меньшей мере, один ключ поиска, или символ, указатели на горизонтальные узлы во множестве узлов 801 поиска, указатели на записи ключей во множестве записей 802 ключей и т.п. Горизонтальные узлы могут включать в себя, например, по меньшей мере два ключа поиска или символа, указатели на вертикальные узлы во множестве узлов 801 поиска, указатели на записи ключей во множестве записей 8 02 ключей и т.п.В общем случае вертикальные узлы могут включать в себя последовательность ключей (например, символов), представляющих фрагмент ключа поиска (например, строку), тогда как горизонтальные узлы могут включать в себя различные ключи (например, символы), которые могут существовать в конкретном положении во фрагменте ключа поиска, например, в строке). В варианте выполнения множество узлов 801 поиска может включать в себя вертикальный узел 810,вертикальный узел 820 и горизонтальный узел 830. Вертикальный узел 810 может включать в себя, например, 2-битный тип 811 узла (например, "10"), 38-битный адрес 812, 8-битную длину 813 (например,"8"), 8-битный первый символ 814 (например, "1") и 8-битный второй символ 815 (например, "нуль"). В этом примере адрес 812 может указывать на следующий узел в дереве поиска, то есть вертикальный узел 820. В варианте выполнения 38-битный адрес 812 может включать в себя 1-битный указатель окончания/узла и 37-битный адрес сдвига в качестве ссылки на одно из 8-байтных слов в адресном пространстве из 1 Тбайта (1012 байт) памяти 104. Соответственно, вертикальный узел 810 может быть 8 байтов (64 бита) в длину, и преимущественно располагаться на 8-байтной границе слов в памяти 104. В общем случае каждый вертикальный узел в множестве узлов 801 поиска может располагаться на 8-байтной границе слов в памяти 104. Вертикальный узел может включать в себя многосимвольный фрагмент ключа поиска (например,строку). В общем случае ключи поиска без связанных с ними записей данных ключа могут быть помещены в один вертикальный узел, чтобы эффективно сократить количество вертикальных узлов, требуемых в множестве узлов 801 поиска. В варианте выполнения вертикальный узел может включать в себя 8 битов для каждого дополнительного символа поверх двух символов в пределах фрагмента ключа поиска,таких как, например, 8-битные символы 816-1, 816-2816-N (показаны внутри пунктирной линии). Преимущественно, вертикальный узел 610 может быть заполнен до 64-битной границы внутри памяти 104 в соответствии с количеством дополнительных символов, расположенных в пределах фрагмента строки. Например, если в вертикальный узел 810 должны быть включены 9 символов, то затем первым и вторым символами могут стать первый символ 814 и второй символ 815, соответственно, и 56 битов информации о дополнительных символах, соответствующей символам от третьего до девятого, могут быть введены в вертикальный узел 810. Дополнительные 8 битов заполнения могут быть включены, чтобы выровнять информацию о дополнительных символах на 8-байтной границе слов. Аналогично, вертикальный узел 820 может включать в себя, например, 2-битный тип 821 узла (например, "10"), 38-битный адрес 822, 8-битную длину 823 (например, "8"), 8-битный первый символ 824(например, "а") и 8-битный второй символ 825 (например, "нуль"). В этом примере адрес 822 может указывать на следующий узел в дереве поиска, то есть горизонтальный узел 830. Соответственно, вертикальный узел 820 может быть 8 байтов в длину, и преимущественно располагаться на 8-байтной границе слов в памяти 104. Конечно, внутрь вертикального узла 820 также может быть включена дополнительная информация, если требуется, как описано выше со ссылкой на вертикальный узел 810. Горизонтальный узел 830 может включать в себя, например, 2-битный тип 831 узла (например,"01"), 38-битный первый адрес 832, 8-битную длину 833 (например, "2"), 8-битный первый символ 834(например, ) и 8-битный второй символ 835 (например, "w"), битовый массив 836 переменной длины и 38-битный второй адрес 837. В этом примере первый символ 834 может включать в себя один символ,, представляющий фрагмент "1 а" ключа поиска, определенный вертикальными узлами 810 и 820, а последний символ 831 может включать в себя единственный символ "w", представляющий фрагмент"law" (закон) ключа поиска, определенного вертикальными узлами 810 и 820. Первый адрес 832 может- 11006038 указывать на запись 840 данных ключа, связанную с фрагментом "1 а" ключа данных, тогда как второй адрес 837 может указывать на запись 850 данных ключа, связанную с фрагментом "law" ключа поиска. Битовый массив 836 может преимущественно показывать, на какие ключи (например, символы) ссылается горизонтальный узел 830. "1" в положении бита в битовом массиве 836 указывает, что на ключ, или символ, ссылается горизонтальный узел 830, а "0" в положении бита в битовом массиве 836 может означать, что на ключ, или символ, горизонтальный узел 830 не ссылается. В общем случае длина битового массиве 836 может зависеть от количества последовательных ключей, или символов, между первым символом 834 и последним символом 835, включая символы их границ. Например, если первым символом 834 является "а", а последним символом 835 является "z", то затем битовый массив 836 может быть длиной 26 бит, где каждый бит соответствует одному из символов между "а" и "z" и включает их. В этом примере дополнительные 38-битные адреса будут присоединяться к концу горизонтального узла 830, соответствующего каждому из символов, представленных в битовом массиве 836. Каждый из этих 38-битных адресов, так же как и битовый массив 836, может быть дополнен, чтобы выровнять каждое количество на 8-байтной границе слов в памяти 104. В варианте выполнения 8-битный набор символовASCII может быть использован как пространство ключей поиска, так что битовый массив 836 может быть 256 битов длиной (то есть, 28 битов или 32 байта). В примере, показанном на фиг. 8, благодаря специальному ссылочному символу и счетчику 833 адреса "2", битовый массив 836 может быть длиной в два бита и может включать в себя "1" в каждом положении бита, соответствующего последнему символу 835. В варианте выполнения, как описано выше со ссылкой на запись 750 данных ключа (фиг. 7), запись 850 данных ключа может включать в себя, например, ключ 853 переменной длины и по меньшей мере один указатель конечных данных. Как показано на фиг. 8, запись 850 данных ключа включает в себя два указателя конечных данных, указатель 857 конечных данных и указатель 858 конечных данных. Записи 850 данных ключа может предшествовать 12-битная длина 851 ключа и 12-битный счетчик/статус 852 конечных указателей, и может включать в себя заполнение (не показано для ясности), чтобы выровнять указатель 857 конечных данных и указатель 858 конечных данных на 8-байтной границе в памяти 104. Каждый из указателя 857 конечных данных и указателя 858 конечных данных может содержать 10 битный тип конечных данных и другие данные, такие как, например, длина, статус или данные, пригодные для двоичных поисков по записям. Указатель 857 конечных данных и указатель 858 конечных данных могут быть рассортированы по типу конечных данных для более быстрого отыскания записей конкретных ресурсов (например, запись 860 конечных данных и запись 870 конечных данных). В другом варианте выполнения, как описано со ссылкой на запись 740 данных ключа (фиг. 7), запись 840 данных ключа может включать в себя внедренные конечные данные 84 6 вместо указателя записи конечных данных. Например, запись 840 данных ключа может включать в себя длину 841 ключа,счетчик 842 конечного указателя, ключ 843 переменной длины, некоторое количество внедренных элементов 844 записей, за которыми следует длина 845 элемента записи (в байтах, например), и внедренные данные 84 6 записей (например, строка, последовательность байтов и т.п.) для каждого из внедренных элементов 844 записей. В другом варианте выполнения, как описано со ссылкой на запись 760 данных ключа (фиг. 7), запись 860 конечных данных, например, может включать 12-битную длину 861, 4-битный статус и строку 862 переменной длины (например, IP-адрес). Альтернативно, строка 862 переменной длины может быть последовательностью байтов. Запись 860 конечных данных может включать в себя заполнение (не показано для ясности), чтобы выровнять каждую запись конечных данных на 8-байтной границе в памяти 104. Альтернативно, запись 860 конечных данных может включать в себя заполнение (не показано для ясности) до 4-байтной границы, либо запись 860 конечных данных может не включать никакого заполнения. Алгоритмы управления памятью могут определять, в общем случае, дополнены ли записи 860 конечных данных до 8-байтной, 4-байтной или 0-байтной границ. Аналогично, запись 870 конечных данных может включать в себя 12-битную длину 871, 4-битный статус и строку 872 переменной длины (например IP-адрес). В общем случае, как поисковые индексы, такие как деревья КУД, так и записи данных могут быть структурированы так, что 8-байтные указатели расположены на 8-байтных границах в памяти. Например,вертикальный узел 810 может содержать 8-байтный (или менее) указатель на вертикальный узел 820, и может храниться в адресе памяти, кратном 8 (например, на 8-байтной границе или 8N). Аналогично, как поисковые индексы, таких как деревья КУД, так и записи данных могут быть структурированы так, что 4-байтные указатели располагаются на 4-байтных границах в памяти. Следовательно, изменения в базе данных 800 могут завершаться обновлением указателя на выровненный адрес в памяти с использованием единой непрерываемой операции, включая, например, внесения нового указателя на поисковый индекс,такой как узел дерева КУД, или внесения нового указателя на запись данных. Различные варианты выполнения, описанные выше со ссылкой на фиг. 8, предоставляют множество преимуществ. Например, структура данных дерева КУД крайне нетребовательна по пространству и полностью 8-битна. Поиски по регулярным выражениям могут быть использованы для поиска вертикальных узлов, содержащих фрагменты многосимвольных строк, поскольку 8-битный первый символ (например,- 12006038 первый символ 814), 8-битный второй символ (например, второй символ 815) и любые другие дополнительные 8-битные символы (например, дополнительные символы 816-1816-N) могут располагаться по соседству с вертикальным узлом (например, вертикальным узлом 810). Поисковые неудачи могут быть быстро обнаружены, и не более N узлов может потребоваться до того, чтобы переместить их в поиск строки поиска длиной в N символов. На фиг. 9 показана блок-схема алгоритма верхнего уровня, иллюстрирующая способ поиска и одновременного обновления базы данных в соответствии с вариантом выполнения настоящего изобретения. Могут быть созданы поток обновления и множество поисковых потоков (операция 900). В варианте выполнения система 100 может запускать единственный поток обновления, чтобы внедрять обновления в полученную локальную базу данных, например, от сервера 140-1 ООТ по РВС 124. В других вариантах выполнения система 100 может принимать обновления от серверов 140-1140-S ООТ по РВС 124, и от множества сетевых компьютеров 120-1120-N по РВС 124 или ЛВС 122. Система 100 также может запускать поисковый поток в ответ на каждый запрос сеанса, принятый от множества сетевых компьютеров 120-1120-N. Например, поток управления может опрашивать один или более портов управления,связанных с одним или более сетевых интерфейсов 114-1114-0, на предмет запросов сеанса, переданных от множества сетевых компьютеров 120-1120-N. Когда принят запрос сеанса от конкретного сетевого компьютера 120-1120-N, поток управления может создать поисковый поток и связать поисковый поток с конкретным сетевым компьютером (например, ПМ). В альтернативном варианте выполнения система 100 может запускать несколько поисковых потоков без опрашивания на предмет запросов сеанса от множества сетевых компьютеров 120-1120-N. В этом выполнении поисковые потоки могут не быть связаны с конкретными сетевыми компьютерами и могут быть равномерно распределены среди множества процессоров 102-1102-Р. Альтернативно, поисковые потоки могут выполняться на подмножестве из множества процессоров 102-1102-Р. Количество поисковых потоков не обязательно может соответствовать количеству сетевых компьютеров (например, N). По сети может быть принято множество поисковых запросов (операция 910). В варианте выполнения множество сетевых компьютеров 120-1120-N может посылать множество поисковых запросов в систему 100 по ЛВС 122 или, альтернативно, по РВС 124. Множество поисковых запросов может содержать, например, поисковый термин или ключ, а также информацию о состоянии, которая может быть связана с каждым запросом (например, адрес источника запроса, тип протокола и т.п.). Информация о состоянии может поддерживаться системой 100 в явном виде, или, альтернативно, может быть предусмотрена обработка информации о состоянии. В предпочтительном варианте выполнения каждый из множества сетевых компьютеров 120-1120-N может мультиплексировать заранее заданное количество поисковых запросов в единый сетевой пакет для передачи в систему 100 (например, Суперпакет 220 запросов, показанный на фиг. 2). В альтернативном варианте выполнения множество поисковых запросов и новая информация могут приниматься по сети одновременно (операции 910, 960). Например, множество сетевых компьютеров 120-1120-N могут посылать множество поисковых запросов и новую информацию в систему 100 по ЛВС 122 или альтернативно по РВС 124. Множество поисковых запросов могут содержать, например,поисковый термин или ключ, а также информацию о состоянии, которая может быть связана с каждым запросом (например, адрес источника запроса, тип протокола и т.д.). Новая информация может включать в себя, например, добавления, изменения или удаления в базе данных, и может группироваться как транзакция со связанным с ней идентификатором. Например, в варианте выполнения каждый из множества сетевых компьютеров 120-1120-N может мультиплексировать заранее заданное количество поисковых запросов и новую информацию в единый сетевой пакет для передачи в систему 100, такой как, например,единый Суперпакет 220 запросов (новая информация не показан для ясности). Для тех запросов, которые зависят от новой информации внутри транзакции, информация о состоянии, связанная с этим запросами,может включать в себя идентификатор транзакции, и, как правило, может поддерживаться системой 100. Когда поток обновления подает транзакцию в базу данных (то есть, например, текущую транзакцию),поисковые запросы, зависящие от этой транзакции, будут задержаны, пока поток обновления не будет успешно завершен и не зафиксирует транзакцию. Каждый поисковый запрос может быть назначен одному из поисковых потоков для обработки (операция 920). В варианте выполнения каждый поисковый поток может быть связан с одним из множества сетевых компьютеров 120-1120-N, а все поисковые запросы, принятые от конкретного сетевого компьютера, могут быть назначены поисковому потоку (операция 920). Другими словами, один поисковый поток может обрабатывать все поисковые запросы, приходящие от единственного сетевого компьютера(например, единственного ПМ) . В варианте выполнения каждый поисковый поток может выделять отдельные поисковые запросы из единого уплотненного сетевого пакета (например, Суперпакета 220 запросов, который показан на фиг. 2) или, альтернативно, выделение может выполняться другим процессом или потоком. В другом варианте выполнения поисковые запросы, принятые от каждого из множества сетевых компьютеров 120-1120-N, могут назначаться различным поисковых потокам (операция 920). В этом- 13006038 варианте выполнения многопоточное назначение может быть основано на функции оптимального распределения, которая может включать в себя различные параметры системы, в том числе, например, загрузку процессора. Конечно, назначение поисковых запросов поисковым потокам может меняться во времени, основываясь на различных параметрах системы, включая доступность процессора, производительность составляющих системы и т.п. Различные механизмы могут быть использованы для передачи поисковых запросов в назначенные поисковые потоки внутри системы 100, такие как, например, совместно используемая память, сообщения взаимодействия процессов, маркеры, семафоры и т.д. Каждый поисковый поток может производить поиск по базе данных, основываясь на назначенных поисковых запросах (операция 930). В варианте выполнения каждый поисковый поток может выделять отдельные поисковые запросы из единого мультиплексированного сетевого пакета (например, Суперпакета 220 запросов, показанного на фиг. 2) или, альтернативно, выделение может выполняться другим процессом или потоком. Очевидно, что поиск по базе данных может зависеть от структуры базы данных. В варианте выполнения поиск по базе данных может зависеть от изменений, содержащихся внутри конкретной транзакции, для которой поисковые запросы зависят от транзакции. Как показано в варианте выполнения базы данных на фиг. 4, по базе 400 данных может проводиться поиск ключа поиска (операция 930). Затем может быть определена запись данных (например, запись 420 базы данных) , соответствующая ключу поиска. Как показано в варианте выполнения на фиг. 5, по сохраняющему файлу 520 сначала может быть проведен поиск ключа поиска (операция 930), а затем, если совпадение не определено, поиск может быть проведен по главному файлу 510 мгновенного состояния(операция 930) . Затем может быть определена запись данных, соответствующая ключу поиска. Как показано в варианте выполнения базы данных на фиг. 6, сначала может быть проведен поиск ключа поиска по данным 610 доменных имен (операция 930), а затем могут быть определены данные ресурса в данных 630 серверов имен, соответствующих ключу поиска. Например, для ключа поиска"la.com", совпадение может быть определено с записью 620 доменного имени в данных 610 доменных имен. Может выделяться соответствующая информация, включая, например, указатель 626 сервера имен. Затем соответствующая запись 640 сервера доменных имен может быть проиндексирована с использованием указателя 626 сервера имен, и может быть выделен сетевой адрес 647 сервера имен. Как показано в варианте выполнения базы данных на фиг. 7, может проводиться поиск ключа поиска по TST (операция 930), из которого могут определяться данные ресурса. Например, для ключа поиска"law.com" может быть проведен поиск по поисковым узлам 701 (операция 930) и определено совпадение с узлом 730. Может быть выделен указатель 736 ключа, из которого может быть определена запись 750 данных ключа. Затем может быть идентифицировано количество указателей 752 конечных данных, и может быть выделен каждый указатель конечных данных. Например, указатель 757 конечных данных может ссылаться на запись 760 конечных данных, и указатель 758 конечных данных может ссылаться на запись 770 конечных данных. Данные ресурса переменной длины, например, сетевой адрес 762 сервера имен и сетевой адрес 772 сервера имен могут затем выделяться из каждой записи конечных данных с использованием длины 761 и 771 соответственно. Как показано в варианте выполнения базы данных на фиг. 8, может быть проведен поиск ключа поиска по дереву КУД (операция 930) , из которого могут определяться данные ресурса. Например, для ключа поиска "law.com" может быть проведен поиск по поисковым узлам 801 (операция 930) и определено совпадение с узлом 830. Может быть выделен второй адрес 737, из которого может быть определена запись 850 данных ключа. Затем может быть идентифицировано количество указателей 852 конечных данных, и может быть выделен каждый указатель конечных данных. Например, указатель 857 конечных данных может ссылаться на запись 8 60 конечных данных, а указатель 858 конечных данных может ссылаться на запись 870 конечных данных. Данные ресурса переменной длины, например, сетевой адрес 862 сервера имен и сетевой адрес 872 сервера имен затем могут выделяться из каждой записи конечных данных с помощью длины 861 и 871 соответственно. Каждый поисковый поток может создавать множество поисковых ответов, соответствующих назначенным поисковым запросам (операция 940). Если не обнаружено совпадения для конкретного ключа поиска, ответ может включать в себя соответствующее указание, такое как, например, нулевой символ. На фиг. 6-8, например, ключ поиска может быть "law.com", а соответствующие данные ресурса могут быть "180.1.1.1". С ключом поиска может быть связано более одного сетевого адреса серверов имен, в этом случае может быть определено более одного сетевого адреса серверов имен. Ответы могут посылаться по сети (операция 950). В варианте выполнения каждый поисковый поток может уплотнять соответствующие ответы в единый сетевой пакет (например, Суперпакет 240 ответов),соответствующий единому сетевому пакету, содержащему исходные запросы (например, Суперпакету 220 запросов). Альтернативно другой процесс или поток может мультиплексировать соответствующие ответы в единый сетевой пакет. Сетевой пакет ответов затем может быть отправлен (операция 950) на соответствующий сетевой компьютер среди множества сетевых компьютеров 120-1120-N по ЛВС 122 или, альтернативно, РВС 124. В одном варианте выполнения пакеты ответов могут быть отправлены на тот же сетевой компьютер, с которого исходят пакеты запросов, тогда как в другом варианте выполнения пакеты ответов могут быть отосланы на другой сетевой компьютер.- 14006038 Поток поиска может принимать по сети новую информацию (операция 960). В варианте выполнения новая информация может отправляться, например, от сервера 140-1 ООТ в систему 100 по РВС 124. В других вариантах выполнения система 100 может принимать обновления от серверов 140-1140-S ООТ по РВС 124, и от множества сетевых компьютеров 120-1120-N по РВС 124 или ЛВС 122. Как обсуждено выше, в варианте выполнения множество сетевых компьютеров 120-1120-N могут отправлять множество поисковых запросов и новую информацию в систему 100 по ЛВС 122 или, альтернативно, РВС 124. Следовательно, в этом варианте выполнения множество поисковых запросов и новая информация могут приниматься по сети одновременно (операции 910, 960). В варианте выполнения преобразования DNS, например, новая информация может включать в себя данные нового доменного имени, данные нового сервера имен, новый сервер имен для существующего доменного имени и т.п. Альтернативно новая информация может показывать, что запись доменного имени, запись сервера имен и т.п.могут быть удалены из базы данных. В общем случае, любая информация,содержащаяся в базе данных, может быть дополнена, изменена или удалена соответственно. В варианте выполнения несколько изменений в базе данных могут быть сгруппированы в транзакцию и применены к базе данных как набор последовательных изменений. Например, транзакция может включать в себя различные сочетания дополнений, изменений и удалений записей в базе данных. Поскольку доступ к поиску в базе данных не ограничен, внутри каждой записи базы данных может быть предусмотрено поле индикатора (например, бит модификации), чтобы уведомлять поисковые запросы о том, что, когда для конкретной записи в базе данных установлен бит модификации, происходят изменения базы данных, связанные с транзакцией, и требуется последующее повторение запроса этой конкретной записи в базе данных. Когда транзакция применена и изменения завершены, бит модификации может быть очищен для всех новых элементов базы данных, созданных транзакцией. В некотором смысле новая информация может рассматриваться как зафиксированная. Таким образом, база данных может быть преобразована из одного действительного состояния в другое действительное состояние без ограничения доступа к поиску по базе данных. Преимущественно, чтобы не допустить поисковые запросы к доступу к базе данных во время периодов ее обновления, не требуется блокировок операционной системы или таблиц базы данных. Имеет место незначительное замедление производительности, так как может потребоваться повторение поискового запроса, если определено, что для какой-либо конкретной записи в базе данных установлен бит модификации. Бит модификации находиться в пределах наиболее значимого слова в записи в базе данных,так что этот бит может быть обнаружен сразу же, как только это слово передано из памяти 104 в процессор 102-1, например. Дополнительные переносы данных в памяти, связанные с оставшейся частью записи в базе данных, таким образом устраняются, если обнаружено, что установлен бит модификации. Период повторения запроса может быть порядка наносекунд для примерных вариантов выполнения системы, обсужденных со ссылкой на фиг. 1. В общем случае бит модификации может быть очищен до того,как повторный запрос снова получает доступ к конкретной базе данных. Альтернативно, либо когда бит модификации установлен в течение текущей транзакции, непротиворечивый на некий момент времени результат запроса может быть восстановлен из содержания журнала отката, или диспетчера журнала, например, что является обычной практикой в транзакционных системах баз данных. Для поисковых запросов, которые могут обнаружить бит модификации вследствие одного осуществляемого обновления, которое не является частью текущей транзакции, повторение запроса обычно вызывает меньшее снижение производительности, чем восстановление результата запроса из диспетчера журнала. Когда бит модификации обусловлен текущей транзакцией с расширенным набором изменений, принятых за расширенный период времени, восстановление результата поиска из диспетчера журнала может быть предпочтительным, так как результат запроса не может быть чрезмерно задержан. Хотя количество изменений записей в базе данных за одну транзакцию в общем случае не ограничено, транзакция включает в себя достаточно информации, чтобы поддерживать элементарность, непротиворечивость, изоляцию и продолжительность базы данных. Множество различных транзакций могут предусматриваться для каждого варианта выполнения базы данных, показанного на фиг. 4 и 6-8. На фиг. 4 транзакция может включать в себя изменение записей 410 и 420 в базе данных, изменение записи 420 в базе данных и добавление новой записи в базу данных (например, записи 430 в базе данных), изменение записи 420 в базе данных и удаление записи из базы данных (например, записи 410 в базе данных) и т.д. На фиг. 6, например, транзакция может включать в себя изменение записи 620 доменного имени и записи 640 сервера имен, удаление записи 620 доменного имени и добавление записи 615 доменного имени и т.д. На фиг. 7, например, транзакция может включать в себя изменение записи 750 данных ключа и записи 760 конечных данных и удаление записи 770 конечных данных, добавление записи 780 данных ключа и удаление записи 740 ключа и т.д. Аналогично, на фиг. 8, например, транзакция может включать в себя изменение записи 850 данных ключа и записи 860 конечных данных и удаление записи 870 конечных данных, добавление записи 880 данных ключа и удаление записи 840 ключа и т.д. Поток обновления может создавать множество новых элементов, основываясь на новой информации (операция 970). Обычно изменения в информации, содержащейся в существующем элементе, могут быть внедрены путем создания нового элемента, основанного на существующем элементе, а затем изме- 15006038 нения нового элемента, чтобы включить в него новую информацию. В течение этого процесса новый элемент может не быть видимым для поисковых потоков или процессов, выполняемых в текущий момент в системе 100, до тех пор, пока в базу данных не будет записан указатель на новый элемент. В общем случае добавления в базу данных могут быть завершены одинаковым образом, без необходимости использования информации, содержащейся в существующем элементе. В одном варианте выполнения удаление существующего элемента из базы данных может быть произведено путем добавления нового явного элемента удалить в базу данных. В другом варианте выполнения удаление существующего элемента из базы данных может быть произведено путем перезаписи указателя на существующий элемент соответствующим индикатором (например, нулевым указателем и т.п.). В этом варианте выполнения поток обновления не создает в базе данных нового элемента, содержащего новую информацию. На фиг. 4, например, пространство памяти для новой записи данных (например, записи 430 данных) может быть назначено из пула памяти, связанного с записями 401 в базе данных. Новая информация может быть скопирована в данные 432 записи 430 данных, а другая информация может быть вычислена и добавлена в запись 430 данных, такая как, например, указатель 434 цепочки, указатель 435 данных и т.п.Бит 408 модификации также может быть включен в новую запись 430 данных. Как показано в вариантах выполнения базы данных на фиг. 6-8, например, новая информация может включать в себя новые доменные имена и/или сервера доменных имен, подлежащие добавлению в базу данных. На фиг. 6, например, пространство памяти для новой записи 615 доменного имени может быть назначено из пула памяти, связанного с записями 611 в базе данных, или альтернативно, из общего пула памяти, связанного с данными 610 доменных имен. Новая информация о доменном имени может быть нормализована и скопирована в новую запись 615 доменного имени, указатель на существующий сервер имен (например, запись 655 серверов имен) может быть определен и скопирован в новую запись 615 доменного имени. Бит 618 модификации может быть включен в новую запись 615 доменного имени. Другая информация может быть вычислена и добавлена в запись 615 доменного имени, такая как, например,количество серверов имен, указатель цепочки и т.п.В более сложных примерах новая информация может включать в себя новый ключ поиска с соответствующими данными ресурсов. Как показано на фиг. 7 в более сложном примере могут быть созданы новый узел 705 поиска, а также новая запись 780 данных ключа. В этом примере новый узел 705 поиска может включать в себя символ сравнения ("m") в первом положении, который больше символа сравнения ("1") в первом положении существующего узла 710 поиска. Следовательно, узел 705 поиска может быть введен в TST на том же уровне (то есть в первом положении символа) , как и узел 710 поиска. До введения узла 705 поиска в базу данных 4-байтный указатель 715 больше чем узла 710 поиска может содержать нулевой указатель. Узел 705 поиска также может включать в себя 4-байтный указатель 706 ключа, который может содержать 40-битный указатель на новую запись 780 данных ключа. Запись 780 данных ключа может включать в себя длину 781 ключа (например, "5") и тип 782 (например, указывающий на данные внедренного ресурса) , ключ 783 переменной длины (например, "m.com"), количество внедренных ресурсов 784 (например, "1"), длину 785 ресурса (например, "9"), строку 786 ресурса переменной длины или последовательность бит (например, "180.1.1.1") и бит 707 модификации. Пространство памяти для узла 705 поиска может быть назначено из пула памяти, связанного с узлами 701 TST, тогда как пространство памяти для записи 770 данных ключа может быть назначено из пула памяти, связанного со множеством записей 702 данных ключа. Согласно фиг. 8, например, могут быть созданы новый узел 890 поиска, а также новая запись 880 данных ключа. В этом примере новый узел 890 поиска может быть горизонтальным узлом, включающим в себя, например, 2-битный тип 891 узла (например, "01"), 38-битный первый адрес 892, 8-битный счетчик 893 адреса (например, 2), 8-битный первый символ 894 (например, "1") и 8-битный последний символ 895 (например, m), битовый массив 896 переменной длины и 38-битный второй адрес 897. Первый адрес 892 может указывать на вертикальный узел 820, следующий вертикальный узел в пути строки поиска "1", тогда как второй адрес 897 может указывать на запись 880 данных ключа, связанную с фрагментом "m" ключа поиска. Запись 880 данных ключа может включать в себя длину 881 ключа (например, "5") и тип 882 (например, указывающий на данные внедренного ресурса), ключ 883 переменной длины (например, "m.com"), количество внедренных ресурсов 884 (например, "1"), длину 885 ресурса(например, "9"), строку 886 ресурса переменной длины или последовательность бит (например,"180.1.1.1") и бит 807 модификации. Пространство памяти для узла 890 поиска может быть назначено из пула памяти, связанного с узлами 801 поиска, тогда как пространство памяти для записи 880 данных ключа может быть назначено из пула памяти, связанного со множеством записей 802 данных ключа. Новая информация также может включать в себя несколько изменений в существующих записях в базе данных. На фиг. 4 новая информация может включать в себя изменения в записи 410 данных. В этом примере может быть создана новая запись 420 данных, и информация из записи 410 данных может быть скопирована в нее. Как и ранее, пространство памяти для записи 420 данных может быть назначено из пула памяти, связанного с записями 401 в базе данных. Изменения затем могут быть применены к данным 422. Записи 410 и 420 данных также могут включать биты 406 и 407 модификации соответственно. На фиг. 6 новая информация может включать в себя изменения в записи 640 сервера имен, такие- 16006038 как, например, новый IP-адрес (например, "180.2.1.2"). В этом примере может быть создана новая запись 660 сервера имен, и информация из старой записи 640 сервера имен может быть скопирована в нее. Как и ранее, пространство памяти для записи 660 сервера имен может быть назначено из пула памяти, связанного с записями 631 серверов имен или, альтернативно, из общего пула памяти, связанного с данными 630 серверов имен. Новый IP-адрес сервера имен может быть скопирован в соответствующее поле в записи 660 сервера имен, то есть, например, в IP-адрес 667 сервера имен. Бит 668 модификации может включаться в новую запись 660 сервера имен. Также предполагаются аналогичные изменения в различные элементы в вариантах выполнения баз данных со ссылками на фиг. 7 и 8. Новая информация также может включать в себя удаление по меньшей мере одного существующего элемента в базе данных. В одном варианте выполнения может не быть создано никакого нового элемента, но поток обновления может установить бит модификации элемента, подлежащего удалению. В другом варианте выполнения может быть создан новый явный элемент удаления с установленным битом модификации, указывающим, что предыдущий элемент был удален из базы данных. На фиг. 4, например, новая информация может включать в себя удаление записи 410 данных, которая может включать в себя бит 407 модификации. На фиг. 6, например, новая информация может включать в себя удаление записи 670 доменного имени, которая может содержать бит 678 модификации. Также предполагаются аналогичные удаления различных элементов в вариантах выполнения базы данных, описанных со ссылками на фиг. 7 и 8. Поток обновления может установить бит модификации в каждом элементе из множества новых элементов (операция 975). Как указано выше, бит модификации может уведомлять поисковые потоки,что конкретная запись в базе данных связана с текущей транзакцией и что должен быть проведен последующий повторный запрос к базе данных. Таким образом, может быть идентифицирована каждая из записей в базе данных, на которую в данный момент воздействует транзакция. На фиг. 4 и 6-8, например,поток обновления может установить бит модификации в каждой из записей в базе данных, на которую в данный момент воздействует транзакция. Бит 408 модификации может быть установлен на "1" для новой записи 430 данных, а биты 407 и 406 модификации могут быть установлены на "1" для измененных записей 410 и 420 данных соответственно. Бит 618 модификации может быть установлен на "1" для новой записи 615 доменного имени, а биты 606 и 668 модификации могут быть установлены на "1" для измененных записей 640 и 660 имен серверов соответственно. Биты 707 и 807 модификации могут быть установлены на "1" для новых записей 780 и 880 данных ключа соответственно. Для ясности, блок-схема алгоритма верхнего уровня, изображенная на фиг. 9, продолжена на фиг. 10 посредством символа "А" соединения блок-схем. На фиг. 10 для записей в базе данных, подлежащих удалению, поток обновления также может установить бит модификации (операция 1075) в соответствующих записях в базе данных. Например, бит 407 модификации может быть установлен на "1" для удаленной записи 410 данных, а бит 678 модификации может быть установлен на "1" для удаленной записи 670 доменного имени. Записи 420 и 430 данных, запись 615 доменного имени, запись 660 сервера имен и записи 780 и 880 данных ключа могут рассматриваться как новые элементы в базе данных, тогда как измененная запись 410 данных, измененная запись 640 сервера имен, удаленная запись 410 и удаленная запись 670 доменного имени могут рассматриваться как старые элементы в базе данных. В этих примерах запись 410 данных используется одновременно как измененная запись данных и как удаленная запись данных. Поток обновления может записать в базу данных указатель (операция 980) с помощью единой непрерываемой операции. В общем случае новый элемент может быть зафиксирован в базе данных (то есть стать постоянно видимым для поисковых потоков или процессов) путем записи указателя в новый элемент в соответствующем положении в базе данных. Как обсуждено выше, это соответствующее положение может быть выровнено в памяти, так что единая операция включает в себя единственную команду запоминания соответствующей длины. Даже несмотря на то, что новые элементы могут быть видимыми для поисковых потоков после записи указателя, установленный бит модификации уведомляет поисковые потоки, что каждый новый элемент базы данных может быть частью текущей транзакции и что могут быть необходимыми последующий повторный запрос или восстановление из журнала отката. Для вариантов выполнения баз данных, содержащих множественные индексы, может быть возможно, чтобы один индекс содержал указатели на старые элементы, тогда как другой индекс будет содержать указатели на новые элементы. Следовательно, в варианте выполнения с разрешением DNS, например, две записи доменных имен с одним и тем же доменным именем, или первичным ключом, могут одновременно существовать в поисковом пространстве, но только в течение транзакции, включающей эту запись в уникальный индекс. На фиг. 4 8-байтный указатель, соответствующий новой записи 430 данных, может быть записан в хэш-таблицу 403. На фиг. 6 8-байтный указатель, соответствующий новой записи 615 доменного имени,может быть записан в хэш-таблицу 612. Важно, что эти ячейки хэш-таблицы могут быть выровнены на 8 байтных границах в памяти 104, чтобы гарантировать, что для обновления этого значения используется единственная 8-байтная команда запоминания. На фиг. 7 4-байтный указатель, соответствующий новому узлу 705 поиска, может быть записан в 4-байтный указатель 715 узла больше чем внутрь узла 710 по- 17006038 иска. Важно, что указатель 715 узла может быть выровнен на 4-байтной границе в памяти 104, чтобы гарантировать, что для обновления этого значения может использоваться единственная 4-байтная команда запоминания. На фиг. 8 множество поисковых узлов 801 также могут включать в себя адрес 899 наверху дерева, который может быть выровнен на 8-байтной границе слов в памяти 104, и может ссылаться на первый узел во множестве узлов 801 поиска (то есть, например, вертикальный узел 810). 8-байтный указатель, соответствующий новому узлу 890 поиска, может быть записан в адрес 899 наверху дерева с помощью единственной команды запоминания. В каждом из этих вариантов выполнения непосредственно перед командой запоминания новые данные невидимы для поисковых потоков, тогда как непосредственно после команды запоминания новые данные уже видимы для поисковых потоков. Таким образом, с помощью единой непрерываемой операции новые данные могут быть зафиксированы в базе данных без использования операционной системы или блокирований таблиц базы данных. На фиг. 10 для записей в базе данных, подлежащих удалению из базы данных, указатель или указатели на существующую запись могут быть записаны нулевым указателем (операция 1080) с использованием единой непрерываемой операции. Нулевой указатель может снять ссылку с существующей записи и указать, что существующая запись была удалена из базы данных. На фиг. 4, например, запись 410 данных может быть удалена из базы 400 данных путем перезаписи соответствующей ячейки в хэш-таблице 403 8-байтным нулевым указателем. На фиг. 6, например, запись 670 доменного имени может быть удалена из базы данных путем перезаписи соответствующей ячейки в хэш-таблице 612 8-байтным нулевым указателем. В альтернативном варианте выполнения 8-байтный указатель на новую явную удаленную запись, соответствующую удаленной записи 670 доменного имени, может быть записан в хэш-таблицу 613. В этом варианте выполнения изменения, добавления и удаления в базе данных могут выполняться аналогичным образом. Поток обновления может очистить бит модификации (операция 985) внутри каждого из множества элементов. В варианте выполнения бит модификации может быть очищен в каждом новом элементе путем установления бита модификации на "0". Например, как обсуждено выше со ссылками на фиг. 4 и 6-8,биты 406 и 408 модификации могут быть установлены на "0" для записей 420 и 430 данных соответственно. Бит 618 модификации может быть установлен на "0" для записи 615 доменного имени, биты 606 и 668 могут быть установлены на "0" для записей 640 и 660 серверов имен соответственно. Биты 707 и 807 модификации могут быть установлены на "0" для записей 780 и 880 данных ключа соответственно. В варианте выполнения бит модификации может быть установлен на "0" для каждого из новых элементов в любом порядке. После того, как биты модификации в каждом из новых элементов очищены (операция 985), старые или существующие элементы базы данных более не активны, то есть на них внутри базы данных больше нет ссылок. В варианте выполнения биты модификации внутри этих элементов могут быть очищены путем установления битов модификации на "0", тогда как в альтернативном варианте выполнения биты модификации вообще могут не очищаться. В варианте выполнения поток обновления может физически удалить существующие элементы в базе данных (операция 990), которые были изменены после того, как биты модификации были очищены из каждого из новых элементов (операция 985) . Преимущественно, физическое удалениеэтих измененных элементов из памяти 104 может быть задержано, чтобы сохранить непротиворечивость в текущих поисках. Например, после того, как существующий элемент изменен и соответствующий новый элемент зафиксирован в базе данных, физическое удаление существующего элемента из памяти 104 может быть задержано так, что существующие поисковые потоки, имеющие результат, полученный непосредственно перед тем, как новый элемент был зафиксирован в базе данных, могут продолжить использовать предыдущее состояние данных. Поток обновления может физически удалить существующий элемент (операция 990) после того, как завершатся все поисковые потоки, начавшиеся до того, как был изменен существующий элемент. Аналогично, после того, как существующий элемент был удален из базы данных, физическое удаление существующего элемента из памяти 104 может быть задержано так, что существующие поисковые потоки, имеющие результат, полученный непосредственно перед тем, как новый элемент был удален из базы данных, могут продолжить использовать предыдущее состояние данных. На фиг. 10 поток обновления может физически удалить существующий элемент (операция 990) после того, как завершатся все поисковые потоки, начавшиеся до того, как был изменен существующий элемент. При взаимодействии способов, связанных с вариантами выполнения настоящего изобретения и различными характеристиками архитектуры системы 100, могут появиться потенциальные сложности. Например, процессор, на котором выполняется поток обновления (например, процессор 102-1, 102-2 и т.д.),может включать в себя аппаратное обеспечение для поддержки выполнения команд вне очереди. В другом примере система 100 может включать в себя оптимизирующий компилятор, который может вырабатывать последовательность команд, связанных с вариантами выполнения настоящего изобретения, которые были оптимально переупорядочены, чтобы использовать параллелизм внутренней архитектуры процессора (например, процессора 102-1, 102-2 и т.д.). Специалист может легко допустить и множество других сложностей. Опасности для данных, обусловленные исполнением команд вне очереди, могут быть устранены, например, путем создания зависимостей между созданием нового элемента (операция 970) и- 18006038 внесением указателя в базу данных (операция 980). В одном варианте выполнения эти зависимости могут быть установлены путем введения дополнительных арифметических операций, таких как, например, команда исключающее ИЛИ, в последовательность команд, выполняемых процессором 102-1, чтобы вызвать исполнение команд, связанных с созданием нового элемента (операция 970), или их завершение до выполнения внесения указателя в базу данных (операция 980). Например, содержание ячейки в памяти 104, соответствующее новому элементу и содержащее бит модификации, может быть подвергнуто действию исключающего ИЛИ по отношению к содержанию ячейки в памяти 104, соответствующей указателю на новый элемент. Следовательно,адрес нового элемента может быть записан в память 104 (операция 980), чтобы зафиксировать новый элемент в базе данных. Различные способы для преодоления этих сложностей могут быть очевидны для специалиста. Выше конкретно проиллюстрировано и описано несколько вариантов выполнения настоящего изобретения. Однако должно быть понятно, что модификации и изменения настоящего изобретения охватываются приведенным выше раскрытием и объемом формулы изобретения без отклонения от сущности и предполагаемого объема изобретения. ФОРМУЛА ИЗОБРЕТЕНИЯ 1. Многопоточная сетевая система баз данных, содержащая по меньшей мере один процессор, связанный с сетью; и память, связанную с процессором, причем память включает в себя базу данных и команды, адаптированные для выполнения процессором следующих операций: создание потока обновления и множества поисковых потоков; назначение каждого из множества поисковых запросов, принятых по сети, одному из множества поисковых потоков; для каждого поискового потока: проведение поиска по базе данных в соответствии с назначенными поисковыми запросами; создание множества поисковых ответов, соответствующих назначенным поисковым запросам, и отправку множества поисковых ответов по сети; и для потока обновления: создание множества новых элементов в соответствии с новой информацией, принятой по сети,установку бита модификации в каждом из множества новых элементов,без ограничения доступа к базе данных для множества поисковых потоков, внесение указателя в каждый из множества новых элементов в базе данных с использованием единой непрерываемой операции, и очистку бита модификации в каждом из множества новых элементов. 2. Система по п.1, в которой команды далее включают в себя следующие операции: для потока обновления: установку бита модификации по меньшей мере в одном существующем элементе, подлежащем удалению из базы данных, и без ограничения доступа к базе данных для множества поисковых потоков, удаление ссылки на существующий элемент, подлежащий удалению с использованием единой непрерываемой операции. 3. Система по п.1, в которой команды далее включают в себя следующие операции: для потока обновления: установку бита модификации по меньшей мере в одном существующем элементе, подлежащем изменению в базе данных до того, как указатель будет внесен в соответствующий новый элемент, и очистку бита модификации в существующем элементе после того, как указатель внесен в соответствующий новый элемент. 4. Система по п.1, в которой единой непрерываемой операцией является команда запоминания. 5. Система по п.4, в которой команда запоминания записывает 4 байта в адрес памяти, расположенный на 4-байтной границе. 6. Система по п.4, в которой команда запоминания записывает 8 байт в адрес памяти, расположенный на 8-байтной границе. 7. Система по п.4, в которой процессор имеет размер слова, равный по меньшей мере n байт, память имеет ширину по меньшей мере n байт, а команда хранения записывает n байт в адрес памяти, расположенный на n-байтной границе. 8. Система по п.1, в которой множество поисковых запросов принимаются в виде единого сетевого пакета. 9. Система по п.1, в которой множество поисковых ответов отправляются в виде единого сетевого пакета. 10. Система по п.1, в которой упомянутое ограничение доступа включает в себя блокировку базы данных.- 19006038 11. Система по п.1, в которой упомянутое ограничение доступа включает в себя циклическую блокировку. 12. Система по п.11, в которой упомянутая циклическая блокировка включает в себя использование по меньшей мере одного семафора. 13. Система по п.12, в котором упомянутым семафором является мьютекс-семафор. 14. Система по п.1, далее содержащая множество процессоров и симметричную многопроцессорную операционную систему. 15. Система по п.14, в которой множество поисковых потоков выполняют по меньшей мере 100000 поисков в секунду. 16. Система по п.15, в которой поток обновления выполняет по меньшей мере 10000 обновлений в секунду. 17. Система по п.16, в которой поток обновления выполняет от 50000 до 130000 обновлений в секунду. 18. Система по п.1, в которой указатель на новый элемент вносится в поисковый индекс. 19. Система по п.18, в которой поисковым индексом является дерево троичного поиска. 20. Система по п.1, в которой указатель на новый элемент вносится в запись данных в базе данных. 21. Способ поиска по базе данных с одновременным обновлением базы данных, содержащий следующие операции: создание потока обновления и множества поисковых потоков; назначение каждого из множества поисковых запросов, принятых по сети, одному из множества поисковых потоков; для каждого поискового потока: проведение поиска по базе данных в соответствии с назначенными поисковыми запросами; создание множества поисковых ответов, соответствующих назначенным поисковым запросам, и отправку множества поисковых ответов по сети; и для потока обновления: создание множества новых элементов в соответствии с новой информацией, принятой по сети,установку бита модификации в каждом из множества новых элементов,без ограничения доступа к базе данных для множества поисковых потоков, внесение указателя в каждый из множества новых элементов в базе данных с использованием единой непрерываемой операции, и очистку бита модификации в каждом из множества новых элементов. 22. Способ по п.21, в котором команды далее включают в себя следующие операции: для потока обновления: установку бита модификации по меньшей мере в одном существующем элементе, подлежащем удалению из базы данных, и без ограничения доступа к базе данных для множества поисковых потоков, удаление ссылки на существующий элемент, подлежащий удалению с использованием единой непрерываемой операции. 23. Способ по п.21, далее содержащий следующие операции: для потока обновления: установку бита модификации по меньшей мере в одном существующем элементе, подлежащем изменению в базе данных до того, как указатель будет внесен в соответствующий новый элемент, и очистку бита модификации в существующем элементе после того, как указатель внесен в соответствующий новый элемент. 24. Способ по п.21, в котором единой непрерываемой операцией является команда запоминания. 25. Способ по п.23, в котором команда запоминания записывает 4 байта в адрес памяти, расположенный на 4-байтной границе. 26. Способ по п.23, в котором команда запоминания записывает 8 байт в адрес памяти, расположенный на 8-байтной границе. 27. Способ по п.21, в котором множество поисковых запросов принимаются в виде единого сетевого пакета. 28. Способ по п.21, в котором множество поисковых ответов отправляются в виде единого сетевого пакета. 29. Способ по п.21, в котором упомянутое ограничение доступа включает в себя блокировку базы данных. 30. Способ по п.21, в котором упомянутое ограничение доступа включает в себя циклическую блокировку. 31. Способ по п.30, в котором упомянутая циклическая блокировка включает в себя использование по меньшей мере одного семафора. 32. Способ по п.31, в котором упомянутым семафором является мьютекс-семафор. 33. Способ по п.21, в котором множество поисковых потоков выполняют по меньшей мере 100000 поисков в секунду. 34. Способ по п.21, в котором поток обновления выполняет по меньшей мере 10000 обновлений в- 20006038 секунду. 35. Способ по п.34, в котором поток обновления выполняет от 50000 до 130000 обновлений в секунду. 36. Способ по п.21, в котором указатель на новый элемент вносится в поисковый индекс. 37. Способ по п.21, в котором указатель на новый элемент вносится в запись данных в базе данных. 38. Компьютерно-считываемый носитель, включающий в себя команды, адаптированные для выполнения по меньшей мере одним процессором, чтобы воплотить способ поиска по базе данных с одновременным обновлением базы данных, способ содержит следующие операции: создание потока обновления и множества поисковых потоков; назначение каждого из множества поисковых запросов, принятых по сети, одному из множества поисковых потоков; для каждого поискового потока: проведение поиска по базе данных в соответствии с назначенными поисковыми запросами; создание множества поисковых ответов, соответствующих назначенным поисковым запросам, и отправку множества поисковых ответов по сети; и для потока обновления: создание множества новых элементов в соответствии с новой информацией, принятой по сети,установку бита модификации в каждом из множества новых элементов,без ограничения доступа к базе данных для множества поисковых потоков, внесение указателя в каждый из множества новых элементов в базе данных с использованием единой непрерываемой операции, и очистку бита модификации в каждом из множества новых элементов. 39. Компьютерно-считываемый носитель по п.38, в котором способ далее включает в себя следующие операции: для потока обновления: установку бита модификации по меньшей мере в одном существующем элементе, подлежащем удалению из базы данных, и без ограничения доступа к базе данных для множества поисковых потоков, удаление ссылки на существующий элемент, подлежащий удалению с использованием единой непрерываемой операции. 40. Компьютерно-считываемый носитель по п.38, в котором способ далее включает в себя следующие операции: для потока обновления: установку бита модификации по меньшей мере в одном существующем элементе, подлежащем изменению в базе данных до того, как указатель будет внесен в соответствующий новый элемент, и очистку бита модификации в существующем элементе после того, как указатель внесен в соответствующий новый элемент. 41. Компьютерно-считываемый носитель по п.38, в котором единой непрерываемой операцией является команда запоминания. 42. Компьютерно-считываемый носитель по п.41, в котором команда запоминания записывает 4 байта в адрес памяти, расположенный на 4-байтной границе. 43. Компьютерно-считываемый носитель по п.41, в котором команда запоминания записывает 8 байт в адрес памяти, расположенный на 8-байтной границе. 44. Компьютерно-считываемый носитель по п.38, в котором множество поисковых запросов принимаются в виде единого сетевого пакета. 45. Компьютерно-считываемый носитель по п.38, в котором множество поисковых ответов отправляются в виде единого сетевого пакета. 46. Компьютерно-считываемый носитель по п.38, в котором упомянутое ограничение доступа включает в себя блокировку базы данных. 47. Компьютерно-считываемый носитель по п.38, в котором упомянутое ограничение доступа включает в себя циклическую блокировку. 48. Компьютерно-считываемый носитель по п.47, в котором упомянутая циклическая блокировка включает в себя использование по меньшей мере одного семафора. 49. Компьютерно-считываемый носитель по п.48, в котором упомянутым семафором является мьютекс-семафор. 50. Компьютерно-считываемый носитель по п.38, в котором указатель на новый элемент вносится в поисковый индекс. 51. Компьютерно-считываемый носитель по п.38, в котором указатель на новый элемент вносится в запись данных в базе данных. 52. Система по п.8, в которой новая информация принимается в виде единого сетевого пакета. 53. Способ по п.27, в котором новая информация принимается в виде единого сетевого пакета. 54. Компьютерно-считываемый носитель по п.44, в котором новая информация принимается в виде единого сетевого пакета.
МПК / Метки
МПК: G06F 17/30
Метки: диспетчер, транзакций, памяти
Код ссылки
<a href="https://eas.patents.su/27-6038-dispetcher-tranzakcijj-v-pamyati.html" rel="bookmark" title="База патентов Евразийского Союза">Диспетчер транзакций в памяти</a>
Система выполнения транзакций
Номер патента: 3957
Опубликовано: 30.10.2003
Автор: Райандо Максвелл Эрл
Метки: транзакций, выполнения, система
Формула / Реферат:
1. Система выполнения транзакций, содержащая, по меньшей мере, один терминал и, по меньшей мере, один сервер объектов типа карт, образующие коммуникационную сеть для регистрации неперсонифицированного идентификатора карты на указанном сервере и выпуска неперсонифицированной карты на указанном терминале, причем указанная система, обеспечивающая регистрацию объекта типа карты, содержит (а) средства приема невыпущенного объекта типа карты в...
Способ сокращения объема памяти, требуемого базой данных для хранения данных, и создания базы данных
Номер патента: 1826
Опубликовано: 27.08.2001
Автор: Эль-Газзар Амин
МПК: G06F 17/30
Метки: сокращения, способ, хранения, требуемого, базой, памяти, данных, объема, базы, создания
Формула / Реферат:
1. Способ сокращения объема памяти, требуемого базой данных для хранения информации, отличающийся тем, что - сохраняемые единицы информации распределяют по точкам пересечения строк и столбцов, по меньшей мере, двумерной растровой матрицы, - размещенным в растровой матрице единицам информации присваивают индивидуальные координаты цвета и - сформированную таким путем матрицу изображения сохраняют в качестве базы данных или части базы данных. 2....
Переносимая защищенная система осуществления транзакций для программируемых устройств с микропроцессорами
Номер патента: 1598
Опубликовано: 25.06.2001
Авторы: Йоханнес Петер, Хейнс Гидо
МПК: G06K 19/07, G07F 7/10
Метки: защищенная, программируемых, устройств, микропроцессорами, переносимая, транзакций, осуществления, система
Формула / Реферат:
1. Система управления транзакциями, предназначенная для осуществления транзакций между первым устройством и вторым устройством, причем указанные первое и второе устройства выполнены с возможностью обмена информацией друг с другом и, по меньшей мере, одно из указанных первого и второго устройств представляет собой карточку с интегральной схемой, при этом упомянутая система содержит по меньшей мере, одно устройство ввода/вывода, переносимую...
Способ изменения неделимым образом множества ячеек энергонезависимой памяти в карточке с микросхемой, в частности в бесконтактной карточке
Номер патента: 2994
Опубликовано: 26.12.2002
Авторы: Дидье Стефан, Грие Франсуа
МПК: G07F 7/10
Метки: памяти, множества, карточке, бесконтактной, ячеек, частности, энергонезависимой, способ, неделимым, микросхемой, изменения, образом
Формула / Реферат:
1. Способ изменения содержимого энергонезависимой памяти карточки с микросхемой, в частности бесконтактной карточки, согласно которому карточку временно подключают к терминалу во время выполнения транзакции, в частности транзакции дистанционного заказа билетов, причем транзакция включает в себя подачу из терминала в карточку множества команд изменения, каждая из которых содержит, по меньшей мере, одну операцию записи в память карточки...
Способ и система защиты обработки активных транзакций
Номер патента: 1825
Опубликовано: 27.08.2001
Автор: Сикстас Тимоти
МПК: H04K 1/00, H04L 9/00, G06F 13/00...
Метки: способ, система, активных, транзакций, обработки, защиты
Формула / Реферат:
1. Способ осуществления безопасной активной транзакции между компьютером продавца и компьютером пользователя, когда компьютеры пользователя и продавца подключены к компьютерной сети для обмена информацией, включающий в себя следующие стадии: (a) компьютер пользователя передает запрос о проведении транзакции компьютеру продавца посредством компьютерной сети, запрос о проведении финансовой транзакции включает в себя идентификационные данные...
Предыдущий патент: Комбинация молочно-кислых бактерий и ее применение для профилактики и/или лечения инфекций и воспалительных состояний
Следующий патент: Способ стабилизации многофазного потока, контроллер и способ стабилизации производительности установки для добычи нефти и газа
Случайный патент: Гетариламинонафтиридины в качестве ингибиторов атф-связывающих белков