Принципы и приёмы обработки очередей

в 7:55, , рубрики: highload, nosql, tarantool, Алгоритмы, Блог компании Конференции Олега Бунина (Онтико), высокая производительность, константин осипов, очереди, очереди с приоритетом, Проектирование и рефакторинг

Принципы и приёмы обработки очередей - 1

Принципы и приёмы обработки очередей

Константин Осипов (Mail.ru)

Как вы считаете, какова стоимость очередей с приоритетами? То есть если кто-то лезет вне очереди, то как посчитать стоимость для всей системы в этой ситуации, чему она пропорциональна? Времени обслуживания клиента — например, 5 минут стоит его обслужить? Она пропорциональна количеству ожидающих, потому что время ожидания для каждого из них увеличится.

Для начала о себе — я занимаюсь разработкой СУБД Tarantool в Mail.ru. Этот доклад будет об обработке очередей. У нас много очередей внутри системы, фактически вся база данных построена как система массового обслуживания.

В основном речь будет идти о проблемах балансировки нагрузки, но перед этим я хотел бы поговорить о том, зачем нужны очереди и как они появились именно в компьютерных системах, чего они позволяют добиться.

Одна из моих любимых мисконцепций по поводу баз данных — это то, что транзакций достаточно для всего. Например, для того, чтобы перевести деньги из одного банка в другой нужно сделать распределенную транзакцию между двумя банками — и все будет хорошо. Т.е. мы берем и лочим аккаунт в одном банке, потом лочим аккаунт в другом банке, делаем списание/начисление, потом разлачиваем. И у нас все консистентно и надежно.

Принципы и приёмы обработки очередей - 2

Или взять проблему с банкоматом: мы пытаемся снять деньги в банкомате — нам нужна распределенная транзакция между банкоматом и автоматизированной банковской системой — бэкендом — и все у нас тоже будет хорошо.

Но есть одна маленькая проблема в этой истории — а что делать с принтером? Тем, что чеки печатает? Он может быть участником распределенной транзакции или нет? Или может диспенсер банкнот стать участником распределенной транзакции? Он поддерживает rollback? Нет.

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

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

Как можно просуммировать то, что я изложил выше? Каковы преимущества, что нам дают очереди?

Принципы и приёмы обработки очередей - 3

Одно из неочевидных преимуществ — это то, что мы можем «развязать» и клиента и сервер, т.е. у нас выполнение задач не зависит от того, доступен ли в данный момент клиент, или доступен в данный момент сервер. Клиент ставит задачу в очередь, после этого его роль, в каком-то смысле, заканчивается, сервер в этот момент не обязан быть доступен. Сервер в какой-то момент, когда у него есть возможность, берет задачи из очереди, выполняет ее, изменяет ее статус и т.д. Клиент всегда может обратиться и проверить статус задачи.

Состояние задачи всегда известно. Мы можем иметь несколько серверов одного клиента, несколько клиентов одного сервера, они все работают через единую очередь, таким образом, можем балансировать нагрузку.

Когда речь идет о балансировке нагрузки, сразу речь заходит о приоритетах, но с ними не все так просто, т.е. если кто-то прыгает в начало очереди, то стоимость такого действия — неочевидна и зависит от загрузки системы.

Каковы минусы данного подхода? То, что у нас появляется дополнительная сущность, фактически у нас на одну и ту же задачу. Если раньше мы обращались напрямую к серверу без предварительного буфера в виде очереди, то мы сразу ее выполняли. Сейчас мы поставили задачу, сервер обращается — изменяет ее статус, у нас больше запросов.

Одна из моих любимых тем — то, что люди склоняются к неперсистентным очередям, потому что им кажется, что в их конкретной задаче неперсистентных очередей достаточно. Например, Rabbit. Хотя Rabbit может быть персистентным, но там персистентность связана с транзакционностью. Речь же идет о надежной персистентности, т.е. как только у вас появляется очередь, ее состояние — это фактически состояние вашей системы. Если вы теряете это состояние, то у вас могут быть всякого рода аномалии, связанные с повторной обработкой задач, т.е. кому-то рассылка пришла 2 раза, у кого-то фотография добавилась 2 раза, у кого-то вообще не добавилась, потому что потерялась задача, т.е. клиент, который поставил задачу в очередь, считает, что все хорошо, а сервер задачу потерял, потому что очередь неперсистентна.

Поэтому очередь — это не какая-то отдельная компонента, а база данных, которая выступает в роли очереди, т.е. она выполняет этот сценарий. Это транзакционная система. В принципе самые правильные очереди. И такого рода очереди стоят дороже.

Когда мы говорим о паттернах, то надо вспомнить ситуацию, когда одна задача может порождать множество задач.

Принципы и приёмы обработки очередей - 4

Допустим, у вас зарегистрировался пользователь, что нужно сделать? Послать уведомление его друзьям, загрузить какие-то его картинки, смс или рассылку ему послать… У вас множество разнородных задач, связанных с одним действием, и очередь может выступать в виде мультиплексора. И помимо load balancing’а, часто используется очередь как паттерн именно для того, чтобы просто выполнить кучу задач. Пользователь пришел, сделал какое-то действие на веб-сайте, ему тут же отдали «ОК», после этого уже система шуршит, разгребает и делает все задачи, связанные с этим действием, за счет этого у нас получается более реактивный интерфейс.

В частности, одна из неочевидных историй, которая запилена исключительно на очередях в Mail.ru — это сборка почты. Вы можете подключать удаленные ящики к Mail.ru, можете подключить Gmail, и в вашем ящике оказывается почта из всех этих ящиков. Или, допустим, вам приходит почта, и вам автоматически высвечивается фотка человека, например, из социальной сети. В какой-то момент, ещё до того, как вы вошли в свой почтовой ящик, mail должен сформировать фронтальную страничку, которую он вам показывает — ваша почта уже прочитана, и аватар того, кто послал почту. Ставится задача получить и сохранить аватар в локальном кэше, чтобы в тот момент, когда вы заходите на фронтальную страничку вам быстро его показать. Чтобы в тот момент, когда вы зайдете, не обращаться по всяким API социальных сетей, gravatar’у для того, чтобы получать эту картинку, и чтобы все это не тормозило. Такой принцип применения.

Если мы говорим о практике применения, то появляется множество специфичных граблей, о которых тоже следует помнить.

Принципы и приёмы обработки очередей - 5

В первую очередь, это связано со всякими «плохими» задачами. Тут все идет рука об руку. Сейчас популярен такой метод DDoS’а, когда он осуществляется после поиска уязвимости в пропускной способности веб-сайта. Т.е. не тупо долбится по сетевой нагрузке в какой-то из веб-сайтов на уровне сетевого стека, а именно выясняются какие-то уязвимости, связанные с тонкими местами в архитектуре. Т.е. предположим, что у нас в момент регистрации нового пользователя есть большой объем работы, связанный с чем-то. Что мы можем сделать? Мы можем загрузить этот веб-сайт количеством пустых регистраций, чтобы его системы завалились от этой работы, и он не смог отвечать по своим типичным сценариям — показы страниц и т.д. В этом смысле очередь может содержать «плохие» задачи.

Если говорить о картинках, у вас есть задача ресайзинга картинок, и какие-то картинки в очереди битые. Есть типичные антипаттерны, когда кто-то загружает битую картинку, воркер ее берет, крэшится, за счет этого очередь считает, что задача не выполнена, отдает ее другому воркеру, он ее снова берет, крэшится, задача постоянно возвращается в очередь, и соответственно результат понятный — воркеры делают пустую работу, а полезную работу никто не делает. Похожая история связана с приоритетами, если вам не удалось выполнить задачу с приоритетами и timeout’ами, у вас может быть желание вернуть задачу в очередь, но выполнить ее немедленно...

Причина, по которой задача не может быть выполнена, может быть разной, она может находиться во внешнем мире. И у вас может возникнуть желание вернуть задачу в очередь с каким-то timeout’ом, чтобы потом ее взять назад с каким-то timeout’ом. По истечении этого timeout’а, возможно, внешний мир изменится и задачу удастся выполнить… И, в конце концов, если задачу не удалось выполнить в течение долгого времени, то вам имеет смысл просто избавиться от этой задачи, пометить ее как невыполнимую и т.д. Все это надо учитывать.

Еще интересна идея применимости очередей в том, как очередь должна работать. Она идет от всяких задач искусственного интеллекта — поиск ближайшего пути и т.д. Когда у нас есть какой-то граф связи, и мы пытаемся найти на этом графе наикратчайший путь из точки А в точку В, один из способов — это полный перебор или какой-то более осмысленный перебор. Мы берем ближайших соседей, ставим для этих соседей в очередь задачу найти кратчайший путь, потом выбираем кратчайший путь из найденных. Но может так получиться, что граф окажется сильно связанным, и вы одни и те же пути будете проходить многократно. За счет того, что у вас поиск в первую очередь идет в глубину, и какие-то пути вам нет смысла проходить, потому что вам уже заранее известно, что они не оптимальны, их нужно отбросить.

Когда очередь используется наивно — типичный пример — это crawler на веб-сайт. Вы заходите на веб-сайт, фечите из него frontpage, выбираете из этого frontpage’а все линки на последующие страницы, ставите задачу в очередь. Дальше происходит все то же самое: на все задачи расфоркиваются воркеры, задачи ставятся в очередь. В итоге сайт может просто за-DDoS’ится, потому что огромное количество воркеров начинают вдруг на него ломиться. Либо одни и те же страницы, если на них идет куча ссылок, вы этого можете не увидеть при таком способе, и вы будете одни и те же ссылки траверсить несколько раз — тоже бессмысленная задача.

Появляются вложенные очереди и зависимые задачи в очередях, т.е. может появиться смысл организовывать подочереди в очередях. Есть общая очередь задач и в контексте каждой из очередей — подочередь, задачи из которой могут быть промультиплексированы.

Я говорю абстрактные вещи, но если на практике вы возьмете любой сервер очередей, то там эти проблемы будут учтены, возможности как-то отражены в интерфейсе и т.д. Сервер очередей должен быть персистентный.

Принципы и приёмы обработки очередей - 6

Вторая часть доклада связана с другим аспектом обработки очередей — максимально эффективными очередями. Строение максимально эффективных очередей и взгляд на проблемы с точки зрения балансировки нагрузки. Что такое балансировка нагрузки? По отпределению из Wikipedia это: “…методология распределения запросов на несколько компьютеров … озволяющая достичь оптимальной утилизации ресурсов, максимизировать пропускную способность системы, минимизировать время ответа на запрос, и избежать перегрузки”

Что здесь важно?

Принципы и приёмы обработки очередей - 7

График — диаграмма насыщения. С одной стороны количество запросов в секунду, а с другой стороны — latency (в данном контексте — время обработки одного запроса).

Задача, когда мы организуем очередь, обработку очереди — это сделать так, чтобы у нас с одной стороны была высокая утилизация ресурсов, с другой стороны мы максимально качественно обслуживали всех клиентов.

Что такое качественно? В первую очередь, качество — это время обработки, время ожидания результата. И если посмотреть на типичную диаграмму системы, которую обслуживает очередь — она выглядит именно вот так. Т.е. можно строить график по latency, график можно строить по RPS. В RPS мы можем либо заметить, либо не заметить снижения RPS. Есть большое количество систем, в которых количество запросов в секунду снижается с увеличением нагрузки.

Что происходит с точки зрения системы массового обслуживания? Она выполняет бесполезную работу, т.е. в момент перегрузки происходит что-то, что не направлено так или иначе на непосредственное обслуживание клиентов, а направлено на борьбу с перегрузками. Например, если взять базу данных, типичным примером в БД является снижение нагрузки, снижение производительности при увеличении количества одновременно присутствующих в БД транзакций. Это происходит за счет того, что появляется ожидание на блокировках и deadlock’и. Ожидание на блокировке — это бесполезное дело, deadlock’и, вообще, приводят к тому, что транзакции рестартуют и их нужно выполнять повторно — пример из компьютерной системы.

В данной ситуации нас интересует построение такой системы, которая будет находиться в оптимальной части кривой, т.е. она будет выполнять максимально возможное количество запросов, при этом сохраняя свои тактико-технические характеристики.

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

Принципы и приёмы обработки очередей - 8

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

Второй критерий, по которому мы можем оптимизировать систему — это максимизация RPS.

Принципы и приёмы обработки очередей - 9

В этом смысле нам полезно дойти до какого-то насыщения системы, при этом сохранив удовлетворительный уровень обслуживания, и не выйти в область перегрузки.

Чтобы понять, почему это взаимосвязанные вещи, я попробую вгрызться в теорию очередей.

Принципы и приёмы обработки очередей - 10

Модель с одним сервером — достаточно показательно.

Есть 2 способа понять, как работает система массового обслуживания:

  • 1-ый способ — построить модель,
  • 2-ой способ — симуляция, т.е. бенчмаркинг, когда вы тестируете, пытаясь дать живую нагрузку.

Если пытаться вгрызться в теорию массового облуживания, то осознаешь, что моделей может быть очень много.

Принципы и приёмы обработки очередей - 11

Есть нотация Кендалла — она классифицирует все системы по шести показателям:

  1. А — распределение времени между прибытиями задач, т.е. мы должны понимать, что живая система — не идеальна, это не метроном, и вам никто раз в секунду задачи ставить не будет, а у живой системы есть какое-то пуассоновское распределение, т.е. количество задач в определенный момент времени следует по пуассоновскому закону, оно случайное — когда-то больше, когда-то меньше.
  2. В — распределение времени обслуживания. В компьютерных системах время облуживания — более-менее фиксировано. Когда мы делаем бенчмарки или симуляцию, мы чаще всего проверяем какие-то типичные проблемы или однотипные задачи, но в целом можно говорить, что это тоже случайная величина.
  3. С — количество серверов, т.е. у вас может быть система с одним сервером или со множеством.
  4. К — ёмкость системы обслуживания. Это вот о чем: у вас может быть очередь фиксированного размера, и все, кто не успел, тот опоздал, т.е. они вообще не получают обслуживания.
  5. Следующая вещь из модели — M — это популяция источника или общий объем, т.е. понятно, что на распределение и на остальные показатели будет влиять то, сколько у вас потенциальных клиентов. Не конкретно в этот момент времени, а потенциальных.
  6. И принцип обслуживания Z — это приоритеты и т.п.

Простейшая модель, которую теория очередей дает — это модель для одного сервера.

Принципы и приёмы обработки очередей - 12

Что здесь дается? Степень утилизации — это соотношение производительности к темпу (скорости) поступления задач. Допустим, у нас 1 сервер может обслуживать 10 задач в секунду, а поступает 9 задач в секунду. Наверное, он справится с нагрузкой, в среднем 9 — это степень утилизации. Здесь хочется сказать — если количество задач в секунду превышает пропускную способность сервера, то пиши пропало, ничего особенного тут не поделаешь, очередь будет неизбежно расти.

πk — это вероятность k задач в очереди.

Что здесь интересно: допустим у вас 10 задач в очереди, скорость поступления задач — 10 в секунду, а сервер может обслужить 12 в секунду. Какова вероятность того, что в тот момент, когда придет следующий потребитель, очередь будет пуста, т.е. он сможет получить обслуживание немедленно? Это вероятность того, что до этого никто не пришел — это 2/12. С большой вероятностью, уже к тому моменту, когда приходит следующая задача, сервер обслуживает какую-то предыдущую с вероятностью 10/12, а с обратной вероятностью он никого не обслуживает — это нам говорит модель из теории массового обслуживания. Т.е. если мы хотим максимизировать утилизацию, то у нас неизбежно будет расти очередь, потому что в тот момент, когда новая задача поступает, сервер уже занят обслуживанием какой-то задачи, и чем выше утилизация, тем выше эта вероятность. Это базовый инсайд теории массового обслуживания.

Принципы и приёмы обработки очередей - 13

Здесь я не привожу модели для нескольких серверов, но базовая идея в том, что если у нас есть единая очередь и множество серверов, то мы дисперсию в распределении участников можем гасить тем, что все сервера получают равномерную нагрузку.

Принципы и приёмы обработки очередей - 14

Результат симуляции, когда у нас есть 80%-ная загрузка на кластер, и синий график — это задача поступает в произвольный сервер по случайному закону, а красный график — это когда у нас есть глобальная очередь, и каждый сервер берет задачу из очереди, когда у него появляется возможность. С увеличением количества серверов latency снижается — это реальная симуляция.

1 — это длина очереди, когда у нас при 80% загрузке каждый сервер работает независимо. В среднем у него есть какая-то очередь. Когда он работает из глобальной очереди вероятность того, что в момент поступления нет доступного для выполнения задачи сервера — в пределах 0,1. Интуитивно понятно: у нас есть 10 воркеров и 8 задач на воркера в каждый момент времени. Вероятность, что у нас пришла задача и нет свободного воркера, маленькая. Если у нас есть 10 воркеров и на каждого своя задача, то вероятность повышается.

Какие ещё инсайды из теории массового обслуживания можно взять?

Принципы и приёмы обработки очередей - 15

Общая идея закона Литтла в том, что количество одновременно обслуживающихся задач пропорционально времени обслуживания и темпу поступления. Что в данном случае важно?

Принципы и приёмы обработки очередей - 16

Если у вас система получает 1000 запросов в секунду, время обслуживания одного запроса — 1 мс. Средняя длина очереди в такой системе будет 10 (количество одновременных задач в системе). В целом, если это разные очереди, т.е. если у вас у каждого воркера своя очередь, то у вас средняя длина очереди может достигать 10-ти.

С точки зрения масштабирования вывод из этого следующий:

Принципы и приёмы обработки очередей - 17

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

Принципы и приёмы обработки очередей - 18

Вывод: у нас есть конфликт требований, и для того, чтобы его удовлетворить, нам нужно так или иначе снижать нагрузку на систему. Это основной вывод, который нам дает теория.

Перейдем к бенчмаркингу и поговорим о практических аспектах бенчмаркинга.

Принципы и приёмы обработки очередей - 19

Постановка задачи: у нас есть 10 серверов, время обслуживания одного клиента, выполнения одной задачи равно 10 мс, и мы хотим, чтоб наш средний latency при такой-то нагрузке был равен 20 мс. Мы хотим, чтоб 99% задач обрабатывались в пределах 20 мс. Такую задачу мы в данный момент решаем.

Я рассказываю про практический уровень, который может понадобиться разработчику интернет-проекта.

Для масштабирования необходимо пропорционально увеличивать число задач “в обработке” — это имеет последствия для качества обслуживания, потому что если у вас, допустим, отключили питание, то вы навредили большому количеству людей. Или наивное предположение, которое делают разработчики о том, что очередь у них в среднем пуста, если у них сервера справляются с нагрузкой — оно не верное, и нельзя говорить о latency.

Большая часть доклада посвящена тому, какие представления у людей появляются о latency. Большинство людей имеют смутное представление о том, какое время обработки одной задачи у их системы. Есть практики измерения и мониторинга этого, но даже эти практики часто не верны — просто не правильная реализация. Что мы можем исследовать, мерять и как мы можем мерять?

Обычно мы пишем бенчмарк, в котором наш скрипт создает случайную задачу, посылает ее на сервер, получает результат, измеряет время, пишет в лог. Если мы ходим увеличить производительность этой системы или проверить как-то лог насыщения, мы увеличиваем количество клиентов, хотя даже это часто люди не осиливают и пытаются нагрузить один сервер с той же машины, на которой стоит тестируемая система.

Принципы и приёмы обработки очередей - 20

Чаще всего в этой ситуации нас интересует RPS — количество запросов в секунду — чем больше, тем лучше. Почему это неправильно? В первую очередь, нас должно интересовать качество обслуживания и в заданном качестве обслуживания нужно добиваться максимального RPS. А качество обслуживания определяется временем, которое тратится на какой-то процент клиентов.

Принципы и приёмы обработки очередей - 21

Предположим, что ваш RPS — 10000 запросов в секунду. Может быть такое, что какая-то часть клиентов, допустим, 5 % клиентов, получает сервис за 2 секунды. Это допустимо или нет? Тем не менее, можно иметь высокий RPS, но часть клиентов будет иметь очень плохое обслуживание. С чем это связано особенно в базах данных? С какой-то периодической работой, которая большую часть бенчмарок просто не меряет. Т.е. если у вас база данных раз в секунду засыпает и что-то делает, то вы можете на своем бенчмарке этого даже не увидеть.

Как обычно у людей выглядит график нагрузки?

Принципы и приёмы обработки очередей - 22

Идея такая — по горизонтальной оси у нас количество запросов (количество клиентов), по вертикальной оси — производительность — 10 тыс., 20 тыс., 30 тыс. запросов в секунду. Что это нам говорит о качестве обслуживания? Ничего. В первую очередь для того, чтобы получить нормальное представление о качестве нужно построить гистограмму распределения времени обслуживания по персентилям (percentile). Т.е. у нас 90% запросов обслуживаются с такой-то производительностью, 10% — в пределах такой (здесь у меня нарисованы такие отбивочные линии), и какой-то маленький процент запросов — вообще уходит в потолок и для него время обслуживания очень высокое.

Принципы и приёмы обработки очередей - 23

В первую очередь, когда мы строим такую систему, нам нужно определить SLA, т.е. нам необходимо, чтобы 90% запросов обслуживались за 1мс, 9,9% — в пределах 5 мс, а для остальных у нас допустимо 10 мс. После определения SLA нам нужно этого SLA добиться.

Принципы и приёмы обработки очередей - 24

Сoordinated omission — скоординированная ошибка измерения. Как мы обычно меряем производительность нашей системы? Меряем latency. Типичный пример кода. Мы говорим «startTime» — это запоминаем время, выполняем запрос и запоминаем время в конце. Потом усредняем и суммируем результат.

Давайте рассмотрим проблему такого подхода. В случае одного клиента она станет более-менее очевидной. Предположим, производительность нашей системы — 10000 запросов в секунду. Мы написали вот такой бенчмарк и меряем эту производительность. А теперь я зашел на серверную консоль и послал сигнал stop серверу, и он остановился на 20 секунд, после этого я послал сигнал continue, который продолжает работу. В общей сложности бенчмарк работал одну минуту. Сколько запросов в результирующей гистограмме будет иметь время исполнения 15 с? Один. А в реальности сколько должно быть? 150 тыс. Т.е. то количество запросов, которое сервер не обслужил. И это проблема большинства бенчмарков.

Допустим, у вас бенчмарк гоняется в 40 потоков, вы все равно имеете эту системную ошибку измерения. И чаще всего эту системную ошибку не видит, минимум и максимум людей не смущает. То, что минимум и максимум не укладывается в 3Σ (сигма) от среднего их тоже не смущает, просто система меряет не то. И это важная проблема, которую нужно решать.

Каким способом ее можно решить? Можно экстраполировать, можно добавлять нагрузку, если мы видим, что у нас количество запросов в данный момент снизилось, т.е. нам нужно было выполнить ещё эти-эти-эти и увеличивать количество запросов. Есть какие-то способы, которыми можем это решать. И часто, если строить гистограмму распределения, то на нескорректированных данных у нас выглядит как-то так — у нас есть малое количество запросов, которое имеет очень большое latency.

Принципы и приёмы обработки очередей - 25

А в реальной жизни у нас latency более равномерно распределено по всему множеству запросов.

Таким образом, мы можем увидеть какую-то периодическую работу, которую выполняет система. Т.е. допустим LSM дерево lavel DB, оно может очень быстро обрабатывать запросы, потом в какой-то момент произойдет процесс мержинга деревьев, и на какой-то момент время выполнения запросов снизится. Вас, естественно, в конечной системе интересует худшее время.

Последняя тема — это борьба с перегрузкой.

Принципы и приёмы обработки очередей - 26

Почему перегрузка возникает, мы обсудили. Какие способы борьбы?

Принципы и приёмы обработки очередей - 27

Простой способ — это просто ограничить размер очереди, т.е. все кто не успел, не получают сервис. Но не всегда это допустимо, на практике есть симуляции, если у нас размер очереди ограничен 20-тью, то у нас всего лишь какой-то процент задач не получает обслуживания на какой-то конкретной системе. Т.е. в конкретных случаях это возможно.

Принципы и приёмы обработки очередей - 28

Второй способ, которым вы можете воспользоваться — это типичная история в баре — вас не факт, что пустят в бар, если он переполнен. Для того, чтобы люди, которые присутствуют в баре, получали нормальный сервис, кто-то должен подождать снаружи.

Это второй паттерн, который вы можете использовать, — система билетов, любых тикетов, раздачи билетов. Люди, которые требуют ресурсов, они ждут снаружи, они ждут не с ресурсами, т.е. люди в баре уже какие-то ресурсы используют (стулья, время бармена и т.д.), поэтому давайте ограничим их ожидание снаружи.

Принципы и приёмы обработки очередей - 29

Более общая идея, которую необходимо реализовать для борьбы с нагрузкой, — это способ обратной связи, обратного давления в гидравлике.

Здесь я привожу пример клапана ограничения давления. Посмотрите, как он устроен — есть какая-то пружина, которая, за счет механической энергии не дает превысить определенный размер, т.е. обратное давление на среду, и так или иначе вы в свою нагруженную систему должны такой механизм встроить, если вы хотите бороться с перегрузками. Давление пружины оно пропорционально увеличивается, оно же не равномерно распределено, т.е. чем больше давление воды, тем выше давление пружины.

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

Этот доклад — расшифровка одного из лучших выступлений на конференции разработчиков высоконагруженных систем HighLoad++. Сейчас мы активно готовим конференцию 2016 года — в этом году HighLoad++ пройдёт в Сколково, 7 и 8 ноября.

Также некоторые из этих материалов используются нами в обучающем онлайн-курсе по разработке высоконагруженных систем HighLoad.Guide — это цепочка специально подобранных писем, статей, материалов, видео. Уже сейчас в нашем учебнике более 30 уникальных материалов. Подключайтесь!

Автор:

Источник


* - обязательные к заполнению поля


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js