Без базы данных, даже без нескольких кардинально разных, такой проект невозможен. Поэтому немного посвящу времени этому вопросу.
Итак как минимум будет нужна БД обслуживающая обычные «плоские» («2D») данные – т.е. некоторому идентификатору ID ставится в соответствие поле данных.
Почему поле данных я рассматриваю одно? Потому что:
Если не задаваться задачей минимизации кол-ва строк кода работы с данными и немного удобством, то почти любую задачу можно свести к той, где эти пункты будут достаточны. И в случае таких высоких требований к оптимальности и скорости, по моему мнению это вполне оправдано.
Основными операциями для таких таблиц БД являются:
Оптимальным я счел использование таблиц «страничного типа», где данные хранятся, пишутся, читаются с диска страницами. В каждой странице – фиксированное количество записей. Совсем просто если я заранее знаю фиксированный размер записи – тогда таблица будет работать еще быстрее, однако и в случае когда размер записи изменяется – существенно в обработке ничего не меняется. Обновление, добавление в конец делаются в рамках страницы в памяти, потом страница пишется на диск. В файле таблицы страницы хранятся последовательно.
Возникает вопрос как обновлять записи в середине таблицы когда их размер меняется – ведь если вся таблица больше 10-20-200 Гб, то скопировать половину таблицы во временный файл, а потом обратно будет занимать часы? Я переложил этот вопрос на файловую систему разбив все страницы на блоки. Один блок – один файл на диске, количество файлов одной таблицы не ограничено. В каждом файле хранятся последовательно ограниченное фиксированное количество страниц. Тогда если надо обновить запись в середине таблицы, то мне надо изменить только 1 файл гораздо меньшего и, зачастую, ограниченного объема. Ответственность за то чтобы не просить файловую систему делать глупости типа сначала пишем в начало, потом в конец, потом опять в начало — я взял на себя. Просто чтобы не напрягать сервер пишу всегда пакетно, соответствующий функционал максимально оптимизирован, все происходит в памяти. Ну и понятное дело, вся система модулей поисковой машины построена исходя из того что записать 1000 записей в конец быстрее чем 1 в начало — поэтому при записи в начало иногда проще сделать копию таблицы.
Хорошо, с обычными таблицами решили. Сейчас описанная БД очень неплохо, в частности, обрабатывает в процессе поиска 35 Гб кусков текстов, с произвольной выборкой.
Но есть и ограничения – в такой таблице хранить соответствие: для каждого слова список документов в которых слово встретилось (вместе с дополнительной информацией) — практически невозможно – по каждому слову будет ну очень много документов, а соответственно и объем будет огромный.
Итак какие операции надо делать с такой БД:
Как обновлять такой индекс? Очевидно что если индекс пустой и мы начнем в него вставлять списки документов начиная с первого слова и заканчивая последним – писать мы будем только в конец файла. Более того, писать или не писать физически отдельные блоки для каждого слова – отдельно на диск, дело разработчика – и в том и другом случае можно просто запомнить: где закончился очередной блок и его длину, сохранить это в простейший список. Тогда процедура последовательного чтения будет такая: перемещаемся в файле на начало списка для нужного слова, и читаем последовательно пока не начнется список для следующего слова: 1 seek, и минимально необходимое кол-во read — победа (здесь я специально не считаю операции самой файловой системы — можно отдельно заняться их оптимизацией)
Теперь, очевидно, когда мы хотим добавить в индекс информацию о ново проиндексированных страницах, можем скопить новую информацию отдельно, открыть текущий индекс для чтения, а новый создаваемый на запись, и читать-писать последовательно сливая с информацией которую надо добавить, начиная с первого слова и заканчивая последним. Вопрос о том, в каком порядке складывать в список документы я рассмотрю чуть позже, когда буду рассказывать про построение индекса.
Полное содержание и список моих статей по поисковой машине будет обновлятся вот здесь: http://habrahabr.ru/blogs/search_engines/123671/
Итак как минимум будет нужна БД обслуживающая обычные «плоские» («2D») данные – т.е. некоторому идентификатору ID ставится в соответствие поле данных.
Почему поле данных я рассматриваю одно? Потому что:
- выборка производится только по полю ID – поиск по данным не производится. Для этого есть специализированные индексы – иначе с такими количествами информации толку будет мало
- любое количество полей можно упаковать в одно, для этого я «на коленке» создал набор небольших прикладных библиотек, в частности при упаковке сохраняется CRC данных, чтобы не использовать не дай бог битые
Если не задаваться задачей минимизации кол-ва строк кода работы с данными и немного удобством, то почти любую задачу можно свести к той, где эти пункты будут достаточны. И в случае таких высоких требований к оптимальности и скорости, по моему мнению это вполне оправдано.
Основными операциями для таких таблиц БД являются:
- выборка по ID
- прочитать последовательно всю базу (в память или хэш)
- обновить запись по ID
- вставить новую в конец, получить ID
Оптимальным я счел использование таблиц «страничного типа», где данные хранятся, пишутся, читаются с диска страницами. В каждой странице – фиксированное количество записей. Совсем просто если я заранее знаю фиксированный размер записи – тогда таблица будет работать еще быстрее, однако и в случае когда размер записи изменяется – существенно в обработке ничего не меняется. Обновление, добавление в конец делаются в рамках страницы в памяти, потом страница пишется на диск. В файле таблицы страницы хранятся последовательно.
Возникает вопрос как обновлять записи в середине таблицы когда их размер меняется – ведь если вся таблица больше 10-20-200 Гб, то скопировать половину таблицы во временный файл, а потом обратно будет занимать часы? Я переложил этот вопрос на файловую систему разбив все страницы на блоки. Один блок – один файл на диске, количество файлов одной таблицы не ограничено. В каждом файле хранятся последовательно ограниченное фиксированное количество страниц. Тогда если надо обновить запись в середине таблицы, то мне надо изменить только 1 файл гораздо меньшего и, зачастую, ограниченного объема. Ответственность за то чтобы не просить файловую систему делать глупости типа сначала пишем в начало, потом в конец, потом опять в начало — я взял на себя. Просто чтобы не напрягать сервер пишу всегда пакетно, соответствующий функционал максимально оптимизирован, все происходит в памяти. Ну и понятное дело, вся система модулей поисковой машины построена исходя из того что записать 1000 записей в конец быстрее чем 1 в начало — поэтому при записи в начало иногда проще сделать копию таблицы.
Хорошо, с обычными таблицами решили. Сейчас описанная БД очень неплохо, в частности, обрабатывает в процессе поиска 35 Гб кусков текстов, с произвольной выборкой.
Но есть и ограничения – в такой таблице хранить соответствие: для каждого слова список документов в которых слово встретилось (вместе с дополнительной информацией) — практически невозможно – по каждому слову будет ну очень много документов, а соответственно и объем будет огромный.
Итак какие операции надо делать с такой БД:
- последовательную выборку с начала списка по нужному произвольному слову и пока не надоест
- по хорошему надо бы изменять список документов для слова, но тут можно сделать финт – обойтись только вставкой в конец БД
Как обновлять такой индекс? Очевидно что если индекс пустой и мы начнем в него вставлять списки документов начиная с первого слова и заканчивая последним – писать мы будем только в конец файла. Более того, писать или не писать физически отдельные блоки для каждого слова – отдельно на диск, дело разработчика – и в том и другом случае можно просто запомнить: где закончился очередной блок и его длину, сохранить это в простейший список. Тогда процедура последовательного чтения будет такая: перемещаемся в файле на начало списка для нужного слова, и читаем последовательно пока не начнется список для следующего слова: 1 seek, и минимально необходимое кол-во read — победа (здесь я специально не считаю операции самой файловой системы — можно отдельно заняться их оптимизацией)
Теперь, очевидно, когда мы хотим добавить в индекс информацию о ново проиндексированных страницах, можем скопить новую информацию отдельно, открыть текущий индекс для чтения, а новый создаваемый на запись, и читать-писать последовательно сливая с информацией которую надо добавить, начиная с первого слова и заканчивая последним. Вопрос о том, в каком порядке складывать в список документы я рассмотрю чуть позже, когда буду рассказывать про построение индекса.
Полное содержание и список моих статей по поисковой машине будет обновлятся вот здесь: http://habrahabr.ru/blogs/search_engines/123671/
