UncategorizedгаджетыНовостиразработчиктехнология

Прагматический перформанс – Байки из окопов

Стенограмма

Subramonian: Добро пожаловать на трек механической симпатии на QCon. Хочу поделиться нашим опытом по оптимизации производственных систем. Как и в большинстве профессий, но особенно в разработке программного обеспечения, 80% времени – это тяжелая работа, но в 20% случаев мы можем выйти и посмотреть, как мы поступаем по отношению к другим вещам. Это тот опыт, которым я хотел бы поделиться. Меня зовут Рамеш Субрамониан. Я главный инженер Target. Я работаю в группе высокопроизводительных вычислений в Саннивейле. Устав нашей группы заключается в повышении эффективности вычислений во всей компании, как в продуктах, которые мы создаем и поддерживаем, так и в качестве консультантов компании в целом. Причина, по которой я выбрал это название, прагматическая производительность, заключается в том, чтобы подчеркнуть ограничения, с которыми мы часто находимся: редко достаточно времени или ресурсов, ограниченная способность нарушать работу системы в производственной среде и общее нежелание ИТ-отделов внедрять новейшее программное обеспечение или аппаратное обеспечение.

Ключевые выводы

Что я хотел бы оставить тебе в конце? Разве это несмотря на кажущуюся мрачную картину, которую я только что нарисовал, часто надежда зарыта в специфике вашей конкретной проблемы. Общие решения хороши, потому что они общие. Они работают в любых ситуациях. За эту универсальность приходится платить. Я собираюсь побудить вас принять свою внутреннюю снежинку, выяснить, в чем на самом деле ваша проблема, и решить именно ее. Как человек, виновник большего количества ошибок, чем я хотел бы признать, я очень предвзято отношусь к выбору решений с низкой сложностью как с точки зрения реализации, так и с точки зрения обслуживания.

Два простых примера

Я собираюсь проиллюстрировать этот момент двумя простыми примерами, старыми как холмы. Первый – это вычисление логического выражения. Например, A и B или не C и D, где A, B, C, D – это выражения, которые оцениваются как истинные или ложные. Другой – проблема определения того, содержится ли строка s1 в строке s2 и где именно. Решения этой проблемы существуют уже более 50 лет в стандартной библиотеке C, и почти каждый язык предоставляет ту или иную форму решения этой проблемы.

Таламус

Позвольте мне установить бизнес-контекст, который мотивирует оптимизировать производительность вычисления логических выражений. Наша группа отвечает за разработку и поддержку Thalamus, системы мониторинга и оповещения в реальном времени, развернутой в Target. По мере того, как его популярность росла, увеличивались его площадь и использование. Все, что мы можем сделать для его ускорения, оказывает несоразмерное воздействие. Thalamus затрагивает более петабайта трафика данных в неделю. Это действительно огромный поток данных, который нужно обработать, и он требует от нас очень внимательного отношения к максимальной производительности.

Как булевы выражения используются в таламусе

Как булевы выражения используются в таламусе? Допустим, вы являетесь пользователем Thalamus, первое, что вы делаете, это пишете фильтр. Фильтр – это способ определить, представляет ли пакет интерес. Хорошая новость заключается в том, что в большинстве случаев большинство пакетов не представляют интереса. Это потому, что вы ищете отклонения от нормы. Вот почему так важна оптимизация фильтров. Это привратник для последующих вычислений. Как вы подойдете к написанию фильтра? Один из них – написать это на Lua. Lua – это интерпретируемый язык, разработанный как встраиваемый и встроенный язык. Следовательно, он отлично вписывается в нашу структуру C ++. Другой – использовать язык, специфичный для предметной области, в нашем случае мы называем его TQL. На сегодняшний день TQL можно рассматривать как эквивалент написания оператора select в SQL.

Фильтр TQL как двоичное дерево

Детали и синтаксис TQL не важны. Важно то, что у нас есть компилятор, который превращает фильтр TQL в дерево. Конечные выражения A, B и C в этом примере выполняют вычисления на основе значений ключей в пакете JSON и возвращают истину или ложь. Примерами являются совпадения регулярных выражений, совпадения подстрок, членство и наборы, числовые сравнения, проверки диапазона и т. Д. Дерево создается во время компиляции. Ключевое решение во время выполнения – начинать ли мы с левой ветви маршрута или с правой?

Навигация по дереву

Когда дело доходит до принятия подобных решений, мы можем искать вдохновение в самых разных источниках, от Йоги Берры до Матрицы. Что касается художников из нас, мы могли бы взять на себя инициативу Роберта Фроста. Серьезно, нам нужен дисциплинированный процесс принятия решений. Прежде чем мы ответим на вопрос, в каком порядке следует оценивать дерево? Посмотрим, почему порядок вообще имеет значение. Это имеет значение из-за короткого замыкания. Другими словами, если вам нужно было вычислить выражения A и B, и вы оценили B, и оно оказалось ложным, вы знаете, что вам не нужно оценивать A. Что, если бы я сказал вам, что A ложно 99 раз из 100, тогда как B ложно только в 50 раз из 100? У вас может возникнуть соблазн сначала выбрать A. Что, если бы я также сказал вам, что A стоит в 1000 раз больше, чем B? A может быть сложной оценкой регулярного выражения, B может быть простым целочисленным сравнением равенства. Вы все равно выбрали бы первым?

Интуиция за решением

Интуиция, лежащая в основе решения, заключается в следующем. В дереве, которое мы только что видели, мы ведем статистику затрат и результатов, истинных или ложных для каждого узла. Предположим, что корневой узел – это И, у нас есть два варианта: мы можем пойти влево или вправо. Если мы пойдем налево, мы определенно оплачиваем стоимость оценки левого ребенка. Если левый дочерний элемент оценивается как истинный, мы будем платить дополнительную стоимость правого дочернего элемента. Точно так же, если мы сначала пошли направо, мы определенно на крючке из-за того, что заплатим стоимость правого дочернего элемента, и нам может потребоваться оплатить стоимость левого дочернего элемента, если правый дочерний элемент оценивается как истинный. Стратегия заключается в выборе минимальной средней стоимости. Доказательство того, что эта стратегия на самом деле оптимальна, имеет несколько интересных моментов, которые выходят за рамки этого выступления. Вы можете распознать стоимость движения влево по сравнению со стоимостью движения вправо.

Результаты симуляции

Как это работает на практике? Мы провели моделирование, в котором произвольно сгенерировали структуру дерева, результаты и затраты. Ось x показывает ход моделирования. По оси ординат показана общая стоимость оценки дерева. Вначале мы сосредоточились на изучении статистики распределения, не используя ее. После этого мы начали использовать то, что узнали, и относительно скоро алгоритм пришел к оптимальному решению.

Резюме

Таким образом, оптимизация оценки логических выражений важна, потому что фильтры интенсивно используются в нашей системе мониторинга и предупреждений в реальном времени. Контекст, который я просил вас искать, но контекст в этом случае заключался в том, что можно было узнать стоимость и результаты отдельных элементов логического выражения. Внедрение этих знаний в существующую систему не было обременительным. Нам действительно нужно было поддерживать несколько дополнительных счетчиков с каждым узлом и протоколом для устаревания устаревшей информации. Наградой за наши старания стало двукратное улучшение. Это нетривиально по сравнению с минимальным количеством нарушений, которые мы внесли.

Игла в стоге сена: деловой контекст

Давайте посмотрим на другой пример, также мотивированный Thalamus, системой мониторинга и оповещения. Здесь базовое распределение пакетов осуществляется с помощью Kafka. В идеальном мире каждая тема Kafka была бы логической единицей, например журналами из определенного бизнес-приложения. Это позволяет легко масштабировать по горизонтали. Каждое приложение или тема получит свой собственный виртуальный сервер, аппаратные ресурсы которого можно масштабировать независимо от других. Однако наш ИТ-отдел, проявив безграничную мудрость, объединил несколько приложений в одну тему, угрожая перегрузить даже хорошо подготовленный сервер. Я не хочу подвергать сомнению эту мудрость нашего ИТ-отдела, но это отражает тот факт, что на крупных предприятиях часто оптимизируют несколько вещей. В данном случае они просто не оптимизируют для нас.

Схема решения: используйте контекст

В итоге нам пришлось создать дезагрегатор. Нам нужно было отменить то, что сделал ИТ-отдел. Нам нужно было разбить бушующий поток на управляемые ручейки. Это грубая схема того, как все выглядит. Дезагрегатору необходимо маршрутизировать пакеты с минимальной задержкой. Это было бы невыполнимой задачей, если бы не какой-то ценный контекст, который мы могли бы использовать. Каждый пакет содержит ключ-значение, как показано. В этом случае, если бы мы знали, что значением ключевого идентификатора приложения является приложение Джо, мы направляем его в тему Джо, и все готово. Однако у нас просто нет времени на JSON-декодирование пакета. Что, если бы мы могли найти местоположение ключа, если бы точно знали, где он находится в пакете? Мы могли бы получить ценность и начать работу. Здесь на помощь пришла функция strstr. Учитывая размер пакетов, нас беспокоило то, можем ли мы добиться большего, чем наивная реализация strstr.

В этом примере стог сена – это предложение, быстрая коричневая лисица перепрыгнула через ленивую собаку. Иголка – это слово лиса. Обычно мы начинали бы наш поиск с нулевой позиции. Предположим, что у нас было три эксперта, которые дали следующие подсказки. Нулевой эксперт говорит нам начать поиск с 16. Эксперт два говорит нам начать поиск с позиции 10. Эксперт три говорит нам начать поиск с позиции 19. Как это влияет на длину сканирования и стоимость поиска? Ответ следующий. В первом случае, если вы посмотрите на это, у нас вообще не было подсказки, поэтому мы бы начали смещение с нуля, а наша стоимость равна 16. Во втором случае нам говорят, где именно начинается слово лиса, у нас есть поставил практически нулевую стоимость. Если мы послушаем второго эксперта, мы начнем с позиции 10. Не совсем там, где мы хотели бы быть, но определенно лучше, чем начинать с нуля. Тройка – интересный случай, потому что здесь нас, собственно, забивают. Нам говорят начать поиск с позиции 19, что означает, что мы просканируем до конца строки и ничего там не найдем. Затем мы снова начинаем с нулевой позиции, а затем мы находим лису.

Как построить предсказатель

Как построить предсказатель? Это усложняется тем, что у вас нет времени на изучение пакета, все, что вы знаете, – это его длина. С другой стороны, вам не нужно быть настолько хорошим. Вы можете безнадежно ошибаться довольно много раз, вам просто нужно в среднем быть лучше, когда начинаете с нуля. Что мы сделали, так это то, что для каждой возможной длины пакета мы смоделировали смещение, которое является истинным местоположением иглы как нормально распределенной случайной величины. Это не совсем точно, поскольку смещения не могут быть отрицательными, а случайная величина может. Как гласит пословица, все модели неправильные, некоторые полезны. Затем мы оценили среднее значение и стандартное отклонение от исторических данных. Обратите внимание на одно ключевое различие между этим и предыдущим примером. В этом случае обучение происходило онлайн в режиме реального времени. В этом случае это делается в автономном режиме и периодически выгружается на сервер в качестве параметра конфигурации.

Следующее, что мы делаем, это то, что у нас есть mu и sigma, мы начнем поиск немного левее среднего. Вспомните из нашего предыдущего примера, где мы искали лисицу, что при угадывании смещения лучше недооценить, чем промахнуться. Мы называем начальную позицию y, и справа y – это mu минус альфа, умноженное на сигму? У нас есть mu и sigma из данных, вопрос в том, как нам найти альфу? Для этого давайте смоделируем стоимость поиска как фиксированную стоимость C плюс переменную стоимость, которая пропорциональна длине строки, которую необходимо просканировать. Стоимость C плюс бета умноженная на L для некоторой постоянной беты. Мы оцениваем C и бета, выполнив несколько поисков и построив прямую линию для наблюдаемых затрат. Пусть S из x, запятая y будет стоимостью, когда x – истинное смещение, а y – это место, с которого мы начинаем поиск. Формула для S зависит от того, промахнулись мы или перестреляли. Если мы недооцениваем, это C плюс бета, умноженное на x минус y. Если мы промахнемся, мы заплатим дважды. Первая стоимость равна C плюс бета, умноженная на L минус y. Это приводит нас к концу строки, затем мы начинаем снова с начала и платим C плюс бета, умноженное на x. Учитывая, что y – некоторая фиксированная начальная позиция, а x – случайная величина, мы можем вычислить ожидаемую стоимость S, используя интеграл. Наконец, если мы минимизируем S по отношению к y и задействуем какое-нибудь школьное исчисление, нам на самом деле очень повезло, что мы получим хорошее решение в закрытой форме для альфы.

Резюме

Обобщая этот пример, идея заключалась в том, чтобы просто найти контекст. Мы обнаружили это в том, что можно было узнать местонахождение иголки в стоге сена. Обратите внимание, что здесь мы используем обучение в очень слабом смысле. Нам не нужно быть такими точными, нам просто нужно быть лучше, чем начинать с нуля. Обучение можно проводить как онлайн, так и офлайн. В двух рассмотренных нами примерах у нас есть по одному. Стоимость реализации включает периодические автономные вычисления C и beta, а также для каждой длины пакета, mu и sigma. Преимущества оказались неожиданно хорошими, мы получили ускорение в среднем в 5 раз.

Ключевые выводы

Какой главный вывод? Дело в том, что универсальные алгоритмы великолепны. Работают всегда. Вам не нужно слишком много думать об их подключении, и они будут работать нормально. Что я действительно хочу заставить нас признать, так это то, что за универсальность приходится платить. Специализация алгоритмов означает использование преимуществ того, что характерно для вашего продукта, в локальном контексте, в котором этот алгоритм будет работать. Преимущество состоит в том, что мы можем получить значительное ускорение без чрезмерных затрат, по крайней мере, исходя из нашего опыта. Стоимость для нас – это стоимость внедрения, обслуживания. Обратной стороной является то, что это требует от нас поиска контекста, который поднимает вопрос: стоит ли выгода от специализации затрат? К сожалению, ответ, как и на многие из этих вопросов, зависит от всех. Однако мы можем однозначно заявить о том, что стоит некоторое время исследовать и выяснить, есть ли локальная структура, которую можно использовать.

Смотрите больше презентаций с расшифровками стенограмм

Related Articles

Leave a Reply

Your email address will not be published. Required fields are marked *

Back to top button