Делай как вGoogle
 Скачать 5.77 Mb.
|
|
Ранжирование Для небольшой кодовой базы ранжирование не приносит особой пользы, потому что результатов поиска не много. Но чем больше размер кодовой базы, тем больше 358 Глава 17. Code Search результатов будет получено в ходе поиска и тем важнее становится ранжирование. В кодовой базе в Google любая короткая подстрока встречается тысячи, а то и мил- лионы раз. Без ранжирования пользователю придется проверить все полученные результаты, чтобы найти правильный, или уточнять запрос 1 до тех пор, пока в на- боре результатов не останется несколько файлов. Оба варианта ведут к пустой трате времени разработчика. Ранжирование обычно начинается с оценки, которая отражает набор характеристик каждого файла (сигналы) в некоторое число: чем выше оценка, тем выше результат. Цель поиска — как можно эффективнее найти первые N результатов. Обычно раз- личают два типа сигналов: зависящие только от документа («не зависящие от запро- са») и зависящие от поискового запроса и его соответствия документу («зависящие от запроса»). Примерами сигналов, не зависящих от запроса, могут служить длина имени файла или язык программирования, на котором написан код в файле, а при- мерами сигналов, зависящих от запроса, могут служить совпадения с определением функции или строковым литералом. Сигналы, не зависящие от запроса К числу наиболее важных сигналов, не зависящих от запроса, можно отнести ко- личество просмотров файла и количество ссылок на файл. Количество просмотров файла показывает, какие файлы разработчики с большей вероятностью захотят найти. Например, служебные функции в базовых библиотеках просматриваются часто. Не- важно, является ли библиотека стабильной или продолжает активно развиваться. Самый большой недостаток этого сигнала — создаваемая им петля обратной связи. Увеличение оценки для часто просматриваемых документов увеличивает вероят- ность, что разработчики увидят их, и уменьшает шансы других документов попасть в первые N строк. Эта проблема известна как компромисс между эксплуатацией и исследованием (exploitation versus exploration). Существуют разные решения этой проблемы (например, расширенные поисковые A/B-эксперименты или курирование обучающих данных). На практике можно завышать рейтинг результатов: они будут игнорироваться, если не имеют отношения к делу, и приниматься во внимание, если требуется обобщенный пример. Однако эта проблема актуальна для новых файлов, еще не имеющих достаточно информации для хорошего сигнала 2 Мы также учитываем количество ссылок на файл, как в оригинальном алгоритме ранжирования страниц ( https://oreil.ly/k3CJx ), заменив веб-ссылки операторами include и import , присутствующими в большинстве языков. Эту идею можно распространить вверх, до поиска зависимостей (ссылки на уровне библиотеки или модуля), и вниз, 1 В отличие от веб-поиска, добавление большего количества знаков в запрос Code Search всегда уменьшает набор результатов (за исключением редких случаев, связанных с особен- ностями регулярных выражений). 2 Этот недостаток можно исправить, если использовать степень новизны как сигнал, как это реализовано, например, в веб-поиске в отношении новых страниц. Но мы пока отложили это исправление. Реализация в Google 359 до определений функций и классов. Эту глобальную релевантность часто называют «приоритетом» документа. При ранжировании на основе количества ссылок следует учитывать две проблемы. Во-первых, нужно уметь надежно извлекать ссылочную информацию. Раньше Code Search извлекал операторы include и import с помощью простых регулярных выра- жений, а затем применял эвристику для преобразования их в полные пути к файлам. Но с ростом сложности кодовой базы эта эвристика стала все чаще допускать ошибки, и ее было сложно поддерживать. Поэтому мы заменили эти процедуры извлечением информации из графа Kythe. Вторая проблема — крупномасштабный рефакторинг, такой как в базовых библио- теках с открытым исходным кодом ( http://abseil.io ), не применяется автоматически в одном обновлении кода — его нужно развертывать в несколько этапов. Для этого обычно вводятся косвенные ссылки, скрывающие, например, перемещение файлов. Подобные косвенные ссылки снижают рейтинг перемещаемых файлов и затрудня- ют определение нового их местоположения. Кроме того, при перемещении обычно сбрасываются счетчики просмотров файлов, что еще больше усугубляет ситуацию. Поскольку такая глобальная реорганизация кодовой базы происходит сравнительно редко (большинство интерфейсов редко перемещается), самым простым решением является увеличение рейтинга файлов вручную на время переходных процессов (либо ожидание завершения миграции и увеличения рейтинга файла на новом месте). Сигналы, зависящие от запроса Сигналы, не зависящие от запросов, можно вычислить в автономном режиме, по- этому вычислительные затраты не являются серьезной проблемой, хотя и могут быть высокими. Например, «рейтинг страницы» зависит от всего корпуса поиска и требует пакетной обработки в стиле MapReduce. Сигналы, зависящие от запроса, вычисляются для каждого запроса отдельно и должны быть дешевыми с вычисли- тельной точки зрения. Это означает, что они ограничены информацией, доступной в запросе и индексе. В отличие от веб-поиска, Code Search ищет не только лексемы. Однако если есть точные совпадения с лексемами (то есть поисковый запрос совпадает с содержимым, обрамленным разрывами некоторого вида, например пробелами), то релевантность документа дополнительно увеличивается и учитывается регистр. Это означает, на- пример, что поиск по запросу «Point» даст более высокую оценку релевантности файлу со строкой «Point *p», чем файлу с текстом «appointed to the council». Для удобства при поиске кроме фактического содержимого сопоставляются также имена файлов и полные квалифицированные символы 1 . Пользователь может задать 1 В языках программирования символы, такие как имена функций, например Alert , часто определяются в некоторой области видимости, такой как класс ( Monitor ) или простран- ство имен ( absl ). Полное квалифицированное имя такой функции может иметь вид absl::Monitor::Alert , и его можно найти, даже если оно отсутствует в фактическом тексте. 360 Глава 17. Code Search конкретный тип сопоставления, но это необязательно. За совпадения с символами и именами файлов дается более высокая оценка релевантности, чем за совпадения в обычном содержимом, что точнее соответствует предполагаемым намерениям разработчиков. Так же как в случае с веб-поиском, разработчики могут добавлять дополнительные термины, чтобы сделать запросы более конкретными. Очень ча- сто в запрос добавляются «подсказки» с именами файлов (например, «base» или «myproject»), а механизм ранжирования автоматически учитывает их, увеличивая рейтинг результатов за наличие совпадений с этими терминами и ставя такие ре- зультаты выше тех, которые содержат такие же отдельные слова в случайных местах. Извлечение Прежде чем оценить документ, выполняется писк кандидатов, которые могут со- ответствовать поисковому запросу. Этот этап называется извлечением. Поскольку нецелесообразно извлекать все документы, а оценивать можно только извлеченные, для поиска наиболее релевантных документов их извлечение и оценка должны про- изводиться вместе. Например, в зависимости от популярности искомый класс может иметь тысячи применений, но только одно определение. Если поиск не был явно огра- ничен определениями классов, извлечение фиксированного числа результатов поиска имени класса может остановиться еще до достижения файла с единственным опре- делением. Очевидно, что с ростом кодовой базы эта проблема только усложняется. Основная задача на этапе извлечения — найти несколько наиболее релевантных файлов. Одно из решений, которое работает достаточно хорошо, называется до- бавочным извлечением. Оно преобразует исходный запрос в более специализиро- ванный. В нашем примере это означает, что добавочный запрос ограничит поиск только определениями и именами файлов и добавит вновь извлеченные документы в выходные данные этапа извлечения. При наивной реализации добавочного из- влечения придется оценить больше документов, зато полученную дополнительную информацию можно будет использовать для более точной оценки только наиболее релевантных документов. Разнообразие результатов Другой важный аспект поиска — разнообразие результатов, то есть выбор лучших результатов из нескольких категорий. Простым примером может служить пред- ставление совпадений с именем функции в Java и Python вместо заполнения первой страницы поиска результатами для какого-то одного языка. Это особенно важно, когда намерения пользователя неясны. Одна из проблем, связанных с разнообразием, заключается в существовании множества разных кате- горий, таких как функции, классы, файлы, локальные переменные, тесты, способы использования, примеры и т. д., в которые можно сгруппировать результаты. В поль- зовательском интерфейсе Code Search не так много свободного пространства, чтобы отобразить результаты из всех этих категорий или хотя бы их комбинаций, и это не всегда желательно. Code Search ищет не так хорошо, как веб-поиск, но его раскрыва- ющийся список результатов (действующий подобно автодополнению в веб-поиске) Некоторые компромиссы 361 настроен для предоставления разнообразного множества имен файлов, определений и совпадений в текущем рабочем пространстве пользователя. Некоторые компромиссы Необходимость поддержки огромной кодовой базы и высокой скорости работы заставила разработчиков Code Search пойти на компромиссы, которые описаны в следующем разделе. Полнота: главная ветвь репозитория Мы уже видели, что увеличение кодовой базы отрицательно влияет на поиск: замед- ляет индексирование и увеличивает его стоимость, замедляет обработку запросов и искажает результаты. Можно ли уменьшить негативное влияние роста кодовой базы, если пожертвовать полнотой, то есть оставить часть содержимого кода вне индекса? Да, если действовать осторожно. Нетекстовые файлы (двоичные артефакты, изображения, видео, аудио и т. д.) обычно не предназначены для чтения, поэтому их содержимое отделяется от имени файла. А поскольку они часто имеют огромные размеры, такое решение экономит много ресурсов. Также из-за обфускации и потери структуры сгенерированные файлы JavaScript почти нечитаемы, поэтому исключение их из индексирования помогает сэкономить ресурсы и уменьшить шум. Исключение многомегабайтных файлов, которые редко содержат релевантную информацию, тоже бывает полезно. Однако исключение файлов из индекса имеет один большой недостаток. Чтобы разработчики использовали Code Search, они должны доверять ему. К сожалению, невозможно сообщить о неполных результатах поиска по конкретному запросу, если файлы не были проиндексированы. Возникающая путаница и потеря продуктив- ности разработчиков — слишком высокая цена за экономию ресурсов. Даже если разработчики знают об ограничениях, но им все равно нужно что-то найти, они будут выполнять поиск необычным способом, подверженным ошибкам. Учитывая эти редкие, но потенциально высокие затраты, мы считаем, что лучше ошибиться, определив более высокие пределы для индекса, которые в основном выбираются для предотвращения злоупотреблений и обеспечения стабильности системы, чем сэкономить ресурсы. С другой стороны, сгенерированные файлы не входят в кодовую базу, но их часто полезно индексировать. В настоящее время этого не делается, потому что для ин- дексации потребовалась бы интеграция инструментов и конфигурации, что стало бы огромным источником сложностей, путаницы и задержек. Полнота: все результаты, а не только наиболее релевантные Обычный поиск жертвует полнотой ради скорости, делая ставку на то, что после ран- жирования на первой странице окажутся все желаемые результаты. И действительно, 362 Глава 17. Code Search ранжированный поиск в Code Search является самым распространенным способом выявить среди миллионов совпадений что-то конкретное, например определение функции. Но иногда разработчикам нужны все результаты, например все вхождения определенного символа для рефакторинга. Требование всех результатов является обычным явлением для анализа, инструментов или рефакторинга, например с целью глобального поиска и замены. Необходимость предоставлять все результаты — фун- даментальное отличие Code Search от веб-поиска, в котором допустимыми считаются многие сокращения, например по рейтингу. Возможность возвращать очень большие наборы со всеми результатами обходится дорого, но мы понимаем, что это помогает инструментам и разработчикам доверять поиску. Однако поскольку для большинства запросов релевантны лишь некоторые результаты (когда имеется мало совпадений 1 или мало интересных результатов), мы не хотели жертвовать средней скоростью ради потенциальной полноты. Для достижения обеих целей с помощью одной архитектуры мы разбили кодовую базу на сегменты с файлами, упорядоченными по их приоритету. Благодаря такой организации инженеру достаточно рассмотреть только совпадения с высокопри- оритетными файлами из каждого фрагмента. Примерно так же работает веб-поиск. Но если это явно указано в запросе, Code Search может извлечь все результаты из каждого фрагмента, чтобы гарантировать поиск всех результатов 2 . Это позволяет нам достигать обеих целей без замедления типичного поиска из-за реже использу- емой возможности возврата больших и полных наборов. Результаты также могут доставляться в алфавитном порядке, а не в порядке ранжирования, что удобно для некоторых инструментов. В данном случае компромисс заключается в усложнении реализации и API за счет сужения возможностей, а не в уменьшении задержки за счет сужения полноты. Полнота: главная ветвь, побочные ветви, вся история и рабочие пространства С увеличением размера корпуса поиска встает вопрос: какие версии кода индек- сировать? В частности, следует ли индексировать что-то еще кроме текущего со- стояния главной ветви? Сложность системы, ресурсоемкость и общая стоимость резко возрастают при индексировании нескольких версий файла. Насколько нам известно, ни одна IDE не индексирует что-то еще кроме текущей версии кода. Мно- гие DVCS, такие как Git или Mercurial, обеспечивают высочайшую эффективность в основном за счет сжатия хронологических данных. Но при построении обратных индексов компактность этих представлений теряется. Другая проблема заключается в сложности эффективного индексирования графовых структур, которые являются основой DVCS. 1 Как показал анализ, около трети поисковых запросов дают менее 20 результатов. 2 Мы делаем все возможное, чтобы ответы не стали слишком большими, а разработчики не нарушили работу всей системы, выполняя поисковые запросы с бесконечным количеством ответов (представьте поиск буквы «i» или пробела). Некоторые компромиссы 363 Индексировать несколько версий репозитория сложно, но такая индексация по- зволяет видеть, как менялся код, и находить удаленный код. Code Search индек- сирует (линейно) хронологию Piper. Благодаря этому можно производить поиск в кодовой базе в любом ее состоянии, находить удаленный код и авторов изменений. Одним из самых больших преимуществ такого подхода является возможность просто удалить устаревший код. Раньше такой код перемещался в каталоги, отмеченные как устаревшие, чтобы потом его можно было найти. Индексирование всей хронологии также заложило основу для эффективного поиска в рабочих пространствах (с неот- правленными изменениями), которые синхронизируются с конкретным состоянием кодовой базы. Хронологический индекс открывает возможность использования в будущем интересных сигналов для ранжирования, таких как авторство, актив- ность кода и т. д. Рабочие пространства имеют существенные отличия от глобального репозитория: y каждый разработчик может иметь свои рабочие пространства; y в рабочем пространстве обычно находится ограниченное количество измененных файлов; y файлы в рабочем пространстве часто изменяются; y рабочее пространство существует на протяжении относительно короткого вре- мени. Наиболее полезен индекс рабочего пространства, который точно отражает текущее состояние этого пространства. Выразительность: лексемы, подстроки и регулярные выражения Эффект масштаба в значительной степени зависит от поддерживаемого набора функ- ций поиска. Code Search поддерживает поиск по регулярным выражениям, которые расширяют возможности языка запросов и позволяют указывать или исключать целые группы терминов. Их с успехом можно использовать для поиска в любом тексте, что особенно полезно для документов и языков, для которых отсутствуют инструменты с более глубокой семантикой. Кроме того, всем известно, что в других инструментах (например, grep ) и контек- стах регулярные выражения повышают эффективность поиска без увеличения когнитивной нагрузки на разработчиков. Однако создание индекса для обработки запросов — сложная задача. Есть ли варианты проще? Индекс на основе лексем (слов) хорошо масштабируется, потому что хранит только часть фактического исходного кода, и хорошо поддерживается стандартными поис- ковыми системами. С другой стороны, многие варианты использования сложно или даже невозможно эффективно реализовать с помощью индекса на основе лексем, потому что многие символы, которые обычно игнорируются при формировании лек- сем, в исходном коде имеют определенное значение. Например, поиск по function() 364 Глава 17. Code Search вместо function(x) , (x ^ y) или === myClass сложно или невозможно реализовать на основе лексем. Еще одна проблема, связанная с лексемами, состоит в неопределенности процедуры формирования лексем из идентификаторов в коде. Идентификаторы могут записы- ваться разными способами, например в ВерблюжьемРегистре, змеином_регистре или даже как простаясмесьслов без разделителя. Поиск идентификатора по некоторым словам — сложная задача для индекса на основе лексем. При формировании лексем также обычно не учитывается регистр букв (например, r и R считаются одинаковыми буквами) и значение слов оказывается размытым из-за сокращения до основы слова, например searching и searched сокращаются до основы search . Такая потеря точности — серьезная проблема при поиске кода. На- конец, использование лексем делает невозможным поиск по пробелам или другим разделителям слов (запятым, круглым скобкам), то есть по символам, имеющим значение в коде. Следующий шаг 1 в развитии возможностей поиска — полный поиск подстроки, который позволяет отыскать любую последовательность символов. Одно из эффек- тивных решений, обеспечивающих такую возможность, основано на использовании индекса триграмм 2 . В простейшей форме получающийся индекс имеет размер на- много меньше размера исходного кода и точность ниже, чем у индексов, полученных другими способами индексирования подстрок. Он замедляет обработку запросов, потому что несоответствия необходимо отфильтровать из набора результатов. Здесь важно найти хороший компромисс между размером индекса, задержкой поиска и потреблением ресурсов с учетом размера кодовой базы, доступности ресурсов и количества запросов в секунду. Кстати, индекс подстрок легко расширить до поддержки поиска по регулярным вы- ражениям. Для этого нужно преобразовать автомат регулярных выражений в набор поисков по подстрокам. Это преобразование несложно реализовать для индекса триграмм и обобщить для других индексов на основе подстрок. Поскольку нет идеального индекса для регулярных выражений, можно конструировать запросы, которые приводят к поиску методом полного перебора. Однако поскольку лишь небольшая часть запросов содержит сложные регулярные выражения, аппроксима- ция с использованием индексов на основе подстрок на практике должна работать очень хорошо. 1 Есть и другие промежуточные варианты, такие как построение индекса префиксов и суф- фиксов, но обычно они имеют меньшую выразительность запросов и высокую сложность и стоимость индексации. 2 Cox R. Regular Expression Matching with a Trigram Index or How Google Code Search Worked ( https://oreil.ly/VSZe7 ). |