Как структурировать индекс для, вводят с опережением для чрезвычайно большого использования набора данных Lucene или подобный?
У меня есть набор данных 200 миллионов + записи, и надеюсь создавать специализированный бэкенд для включения типа вперед решение. Lucene представляет интерес, учитывая свою популярность и тип лицензии, но я открыт для других предложений с открытым исходным кодом также. Я ищу совет, рассказы от канавок или еще лучшую прямую инструкцию относительно того, в чем я буду нуждаться до суммы аппаратных средств и структуры программного обеспечения. Требования:
Должен иметь:
- Способность сделать запускается с подстроки, соответствующей (я ввожу в 'Св.', и она должна соответствовать 'Stephen'),
- Способность возвратить результаты очень быстро, я сказал бы, что 500 мс являются верхней границей.
Хороший, чтобы иметь:
- Способность подать информацию об уместности в процесс индексации, так, чтобы, например, более популярные условия были бы возвращены перед другими и не только алфавитные, иначе стиль Google.
- Соответствие подстроки в слове, так например ('Св.' соответствовал бы 'бестселлеру'),
Примечание:
- Этот индекс будет просто использоваться для, вводят с опережением и не должен вручать стандартные поисковые запросы.
- Я не волнуюсь по поводу преуспевающего совета, как настроить фронтэнд или Ajax, пока индекс может быть запрошен как услуга или непосредственно с помощью кода Java.
Голоса за любую полезную информацию, которая позволяет мне становиться ближе к уровню предприятия, вводят решение с опережением
2 ответа
Если каждая запись относительно небольшая (меньше нескольких слов), вы можете попробовать структуру данных Trie:
http://en.wikipedia.org/wiki/Trie
Она создана для облегчения быстрого сопоставления префиксов и это относительно компактно. Я использовал эту структуру данных для точной функции автозаполнения, которую вы ищете, и я знаю других, которые делали это для веб-сайтов массового производства. По моему опыту, время ответа на один запрос может составлять десятки миллисекунд.
Вы можете довольно легко реализовать Trie самостоятельно, или есть реализации, которые вы можете скачать. См.
Где я могу найти стандартную реализацию карты на основе Trie в Java?
В зависимости от того, какую реализацию вы используете, должно быть относительно просто пометить каждую проиндексированную запись оценкой релевантности, которую затем можно использовать для сортировки по когда вы получаете список записей из запроса.
Возможно, вам не понадобится ничего особенного. Вашему «обязательному» списку может помочь простой движок базы данных (например, BerkeleyDB или ESENT). Поместите все слова в таблицу, а затем используйте поиск, чтобы найти слова.
В-дерево со страницами 8 Кбайт должно содержать не менее 250 строк на страницу, что приведет к 1 миллиону листовых страниц, давая b-дерево высоты 3. Даже с диском портативного компьютера со скоростью вращения 5400 об / мин задержка ввода-вывода будет меньше. чем 15 мс, поэтому в худшем случае вы сможете получить результат через ~ 50 мс в худшем случае (полностью некэшированные данные и медленный диск).
(Я создал приложение с опережением ввода текста, которое использует класс PersistentDictionary на основе ESENT. С 200 000 записей я получаю ответ ~ 35 мс для первого поиска, когда данные вообще не кэшируются. После выполнения нескольких запросов ответ время падает до ~ 5 мс).
Для поддержки большого количества одновременных пользователей вы можете добавить больше кеша или более быстрые диски. Полное кэширование всех данных, вероятно, возможно (8 ГБ ОЗУ в наши дни вполне доступны), а данные с предварительным вводом, безусловно, будут достаточно малы, чтобы поместиться на SSD, что обеспечит смехотворное количество операций ввода-вывода в секунду. Я мог бы выбрать SSD, потому что он будет обеспечивать отличную производительность, даже когда кеш холодный (например, после перезапуска).
Решение на базе ядра СУБД должно быть построено очень быстро.