На этой неделе была тьма анонсов про поиски. Вышел новый Bing, в Google анонсировали Bard.
Они интересны и холиварны, поэтому о них я рассказывать не буду, потому что техническая часть там не в моей компетенции :)
А зато мне хочется сильно похвалить команду GitHub за то, что теперь cs.github.com индексирует 45 миллионов репозиториев с 115 млрд файлов.
У обратных индексов по всему, что связано с кодом история достаточно давняя и не сильно заисследованная: Russ Cox рассказывал про то, что обратная индексация по триграмам и токенизация запроса по им работает достаточно хорошо, но на масштабах GitHub они признались, что такой подход работает только до поры до времени. Почему? Потому что мы любим писать всякие циклы через последовательности
Если вы будете использовать 4, 5 граммы, то есть индексировать 4-5 подряд символов в document_id и позицию, то индекс сильно вырастет, поэтому это как-то непрактично, а 2-граммы не сильно хорошо фильтруют. Но хочется добавить и подстроки побольше, чтобы быстрее фильтровать. Чтобы запрос хорошо фильтровал, надо чтобы разбивка n-grams у подстроки запроса была подмножеством разбивки документа (то есть если есть подстрока s в запросе, то любая надстрока S в документе должна иметь n-grams от s), иначе будет некорректный поиск. В итоге придумали схему, которая в среднем увеличивает индекс в пару раз и добавляет приличное количество подстрок бОльшей длины:
На каждую биграму посчитать хэш, поставить на позиции значения хешей. Взять только те подстроки, в которых все значения хешей внутри строго меньше, чем на краях. Так как хеши не зависят от подстрок, свойство о разбивки подстрок выполняется. С другой стороны количество строк увеличится в среднем в константу раз, так как количество подстрок попавших в индекс при переходе с длины n на n+1 уменьшается в среднем в экспоненциальное количество раз. Если аккуратно выписать все выражения, количество строк в индексе будет примерно в 2 раза больше, а по размеру в большую, но удобную константу, когда индексация происходит построчная. Инженерно можно ещё запретить слишком большие n-grams, хорошо пожать с алгоритмом и положить на SSD. В итоге будет индекс GitHub, который хорошо расширяется. Интересные задачи у них скорее всего связаны с метаданными, метаданные на 115млрд растут всё таки линейно, но об этом они ничего не написали :(
В итоге если вы ищете какое-нибудь выражения с очень частой подстрокой типа
В добавочку:
Пригласили на LLVM Code Generation and Optimization Symposium, буду рассказывать с коллегами про то как мы меняли std::sort в LLVM и в Google. Спойлер: у истории есть продолжение, а именно хоть огня и не было, а вот ускорений в проде по сравнению с микробенчмарками мы не увидели
https://llvm.org/devmtg/2023-02-25/
Если мне, конечно, одобрят визу в Канаду к концу февраля :)
Они интересны и холиварны, поэтому о них я рассказывать не буду, потому что техническая часть там не в моей компетенции :)
А зато мне хочется сильно похвалить команду GitHub за то, что теперь cs.github.com индексирует 45 миллионов репозиториев с 115 млрд файлов.
У обратных индексов по всему, что связано с кодом история достаточно давняя и не сильно заисследованная: Russ Cox рассказывал про то, что обратная индексация по триграмам и токенизация запроса по им работает достаточно хорошо, но на масштабах GitHub они признались, что такой подход работает только до поры до времени. Почему? Потому что мы любим писать всякие циклы через последовательности
for ( и поэтому они плохо фильтруют документ, если в запросе есть триграма for. В Google мы рассказывали, что долго использовали суффиксные структуры, но в итоге решили использовать решение о sparse n-grams, которое хорошо заработало, и в статье GitHub упоминается. Немного истории:Если вы будете использовать 4, 5 граммы, то есть индексировать 4-5 подряд символов в document_id и позицию, то индекс сильно вырастет, поэтому это как-то непрактично, а 2-граммы не сильно хорошо фильтруют. Но хочется добавить и подстроки побольше, чтобы быстрее фильтровать. Чтобы запрос хорошо фильтровал, надо чтобы разбивка n-grams у подстроки запроса была подмножеством разбивки документа (то есть если есть подстрока s в запросе, то любая надстрока S в документе должна иметь n-grams от s), иначе будет некорректный поиск. В итоге придумали схему, которая в среднем увеличивает индекс в пару раз и добавляет приличное количество подстрок бОльшей длины:
На каждую биграму посчитать хэш, поставить на позиции значения хешей. Взять только те подстроки, в которых все значения хешей внутри строго меньше, чем на краях. Так как хеши не зависят от подстрок, свойство о разбивки подстрок выполняется. С другой стороны количество строк увеличится в среднем в константу раз, так как количество подстрок попавших в индекс при переходе с длины n на n+1 уменьшается в среднем в экспоненциальное количество раз. Если аккуратно выписать все выражения, количество строк в индексе будет примерно в 2 раза больше, а по размеру в большую, но удобную константу, когда индексация происходит построчная. Инженерно можно ещё запретить слишком большие n-grams, хорошо пожать с алгоритмом и положить на SSD. В итоге будет индекс GitHub, который хорошо расширяется. Интересные задачи у них скорее всего связаны с метаданными, метаданные на 115млрд растут всё таки линейно, но об этом они ничего не написали :(
В итоге если вы ищете какое-нибудь выражения с очень частой подстрокой типа
for (int i = 42, то вы не будете искать пересечения триграм с for, которая находится в каждом файле, а будете искать в том числе какую-нибудь большую подстроку вида i = 42, что встречается реже. В итоге меньше проверок на вхождение, лучше фильтрация. А если вы ищете то, что находится в миллионах документов, скажем, вы просто ввели запрос for, то там не так важно что вернуть, непонятно что вы и хотите, если спрашиваете такое, и документов скорее всего будет много.В добавочку:
Пригласили на LLVM Code Generation and Optimization Symposium, буду рассказывать с коллегами про то как мы меняли std::sort в LLVM и в Google. Спойлер: у истории есть продолжение, а именно хоть огня и не было, а вот ускорений в проде по сравнению с микробенчмарками мы не увидели
https://llvm.org/devmtg/2023-02-25/
Если мне, конечно, одобрят визу в Канаду к концу февраля :)