Как и обещал в предыдущем посте - разберем каким образом Dan Luu смог сократить Твиттеру расходы на железо на 100 млн долларов в год и переложить часть себе в карман, став Senior Staff Engineer

Вступление

At Twitter, most CPU bound services start falling over at around 50% reserved container CPU utilization and almost all services start falling over at not much more CPU utilization even though CPU bound services should, theoretically, be able to get higher CPU utilizations. Because load isn't, in general, evenly balanced across shards and the shard-level degradation in performance is so severe when we exceed 50% CPU utilization, this makes the practical limit much lower than 50% even during peak load events.

Утверждение первое. Большинство сервисов в Твиттере уходили в отказ при нагрузке около 50% аллоцированных CPU, хотя в теории должно были работать и при большей 50%. А с учетом того, что нагрузка между разными частями системы была неравномерно распределена, а при 50% наступал отказ, реально нагрузка была еще ниже чем 50:, так как приходилось ориентироваться на самую нагруженную часть системы

Almost all services at Twitter run on Linux with the CFS scheduler, using CFS bandwidth control quota for isolation, with default parameters. The intention is to allow different services to be colocated on the same boxes without having one service's runaway CPU usage impact other services and to prevent services on empty boxes from taking all of the CPU on the box, resulting in unpredictable performance, which service owners found difficult to reason about before we enabled quotas. The quota mechanism limits the amortized CPU usage of each container, but it doesn't limit how many cores the job can use at any given moment. Instead, if a job "wants to" use more than that many cores over a quota timeslice, it will use more cores than its quota for a short period of time and then get throttled, i.e., basically get put to sleep, in order to keep its amortized core usage below the quota, which is disastrous for tail latency.

Почти все в твиттере работает на Линуксе через CFS scheduler, используется дефолтный CFS bandwidth control quota для изоляции. Идея в том, чтобы разные сервисы бегали на одной машинке, но не было ситуации, когда один сервис отжирает мощности у других или чтобы сервис, который бегает на пустой машинке, не потреблял все мощности, что приводило бы к труднопредсказуемому перформансу. Квотирование ограничивает амортизированное (то есть растянутое во времени) использование CPU, но не ограничивает как много ядер может быть использованному в отдельный момент времени. Если процесс попытается использоваться больше ядер, чем позволено квотой в определенных временных границах, он это сможет сделать в начале, а потом будет заглушен. То есть если моя квота это в среднем 2 ядра в 10 секунд, я могу использовать четыре ядра 5 секунд, а затем 5 секунд спать. Очевидно это жестко ломает p99/999 latency

Since the vast majority of services at Twitter use thread pools that are much larger than their mesos core reservation, when jobs have heavy load, they end up requesting and then using more cores than their reservation and then throttling. This causes services that are provisioned based on load test numbers or observed latency under load to over provision CPU to avoid violating their SLOs. They either have to ask for more CPUs per shard than they actually need or they have to increase the number of shards they use.

А так как многие сервисы в Твиттере могут требовать ресурсов больше, чем за ними зарезервировано (вспоминаем про амортизационное использование), когда идет высокая нагрузка, сервис запрашивает больше ресурсов, получает их, выходит за квоту и засыпает. Это в свою очередь приводит к тому, что сервисы с автомасштабированием CPU на основе латенси или нагрузки запрашивают больше CPU, чтобы не нарушить SLO. То есть либо больше CPU на шард, чем нужно, либо растет количество шардов
#SystemDesign

На этом вступление заканчивается, но кажется уже становится понятно где больно, напоминает древнюю проблему с JVM Garbage Collector и stop-the-world GC pause
Стоит ли разбирать как это было решено?

#SystemDesign

Сегодня сократили в компании 25% человек. Дата команду на 3%

Прочитал небольшой обзор о том что что ожидает геометрическое и графовое машинное обучение в 2022 году
What does 2022 hold for Geometric & Graph ML?

Делают следующие предсказания/выводы (привел не все)

1. Геометрия начинает игратт все более важную роль в машинном обучении (Хотя я это увидел в применении к Графовым Сетям(GNN) и как-то меня не удивило что в них важна геометрия)
2. Message passing все еще играет главную роль в GNN, вроде как думали что уже все - дальше выжимать нечего, однако нет, - придумали новые трюки. Впрочем и MLP воскрес недавно, так что тоже не удивительно.
3. Дифференциальные уравнения вдохновили новые архитектуры GNN. Вышел ряд работ, в которых было показано как представить GNN в виде дискретизации непрерывных дифференциальных уравнений
4. Старые идеи из обработки сигналов и физики получили новую жизнь. Впрочем весь deep learning - это по факту representational learning
5. Моделирование сложных систем выходит за пределы графов. Верхнеуровнево конечно можно описывать и графом, но системы с динамически меняющимися связями требуют чего то посложнее, новые работы посвящены тому как применять GNN там, где обычно работала алгебраическая топология. В прочем смотри пункт 3
6. Графы набирают популярность в reinforcement learning. В RL полно графов - либо в структуре RL агента, либо в представлении окружения
7. AlphaFold 2 - триумф Геометрического Машинного Обучения - показала биологам что машинное обучение вам не шутки
8. Исследования и разработка новых лекарств - стали впиливать трансформеры есть надежда что здесь может быть прорыв

Для интересующихся - советую ознакомиться

Какие же были варианты решения проблемы некорректной аллокации и тротлинга, описанные здесь?

Задать более продуманную дефолтную квоту для тредпулов
Потенциальный импакт: небольшой прирост в производительности
Преимущества: По сравнению со всеми другими вариантами - не надо делать почти ничего, также может работать в параллель с другими правками
Недостатки: не решает проблему в целом

Корректировать размер тредпула через общий API
Потенциальный импакт: может решить большую часть проблем для большей части машин
Преимущества: понятно что и как делать
Недостатки: необходимо чтобы каждый сервис самостоятельно подписался (использовал новый API для создания тредуплов)

Тюнинг периода CFS

У CFS есть периоды которые делятся на отрезки, например период в 100мс делится на отрезки по 5мс. Если в первые 5 мс квота будет израсходована - следующие 95мс будет тротлинг

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

Тюнинг отрезка CFS
Почти тоже самое что и предыдущее, только с другой стороны

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

Доработка планировщика CFS
Потенциальный импакт: улучшение утилизации CPU и минимизация тротлинга по причине низкой эффективности CFS
Преимущества: улучшения прозрачны и очевидны
Недостатки: CFS сложна штука, можно так “улучшить”, что потом придется еще больше страдать

Фиксация и изоляция CPU
Потенциальный импакт: никакого тротлинга, мапинг 1-1 на физический CPU - все ресурсы в распоряжении сервиса
Преимущества: разработчикам просто жить в такой модели, тротлинг со стороны планировщика отсутствует, повышается эффективность использования кэша, отсутствие пересечений с другими потребителями позволяет точнее оценивать производительность
Недостатки: Усложнение системы, так как теряем один уровень абстракции, гораздо чаще становятся случаи избыточной аллокации ресурсов, радикально отличается от текущей модели

Отключить CFS квоты
Потенциальный импакт: предотвращает тротлинг и позволяет сервисам использовать все доступные ядра, надеясь на эффективный шаринг
Преимущества: в некотором смысле дает позволяет максимально утилизировать CPU
Недостатки: Отдельный сервис-негодяй может съесть все ресурсы и затормозить другие сервисы на той же коробке, полная противоположность предыдущему пункту, что приводит к недетерминированности по времени

В следующем посте разберем финальное решение ребят
#SystemDesign

Когда я прилетел с пересадками из Лондона в офис необанка Тинькоф, чтобы завершить перевод акций из Альфы и снять ограничения с аккаунта, там сидело несколько человек.

Среди них был мужик, который скандалил что он приехал издалека и у него осталось 10 минут чтобы закончить все дела и уехать

Я не стал спрашивать откуда он приехал. Может быть из Аргентины?

Вышло новое интервью
Поговорили про разные вещи, развитие, карьеру, прошлое и будущее

Прочитал заметку от Блумберга, There’s a New Way to See When the Economy Is Going Off the Rails

В ней рассказывается что ребята из UC Berkeley сделали инструмент, который в реальном времени (конечно нет, по месяцам) отображает доходы групп населения в разрезе возраста и перцентиля по США. Эту информацию можно эффективно использовать для оценки того, где сейчас находится экономика, вместо средней цифры по больнице.

Чем-то напоминает статью от Uber Analyzing Experiment Outcomes: Beyond Average Treatment Effects. Мне кажется что это разумно, иначе 0.01% перцентиль мега богатых может выдать среднее, показывающее что все отлично, правда всем остальным очень плохо, но в среднем стало лучше!

Инструмент доступен по ссылке - особенно интересно посмотреть на posttax income, стоит помнить, что почти половина населения в США не платит налоги

57% of U.S. households paid no federal income tax last year as Covid took a toll, study says
61% of Americans paid no federal income taxes in 2020, Tax Policy Center says
Five Myths about the 47 percent

P.S. Заодно узнал что в США есть свой аналог мат капитала, child tax credit - сейчас это 3600$ в год для детей до 6 лет и 3000$ c 6 до 17, на неограниченное количество детей, которые можно вернуть через налоги (или даже их не уплатить), получается - 51 тысяча долларов на ребенка. For 2021, the Child Tax Credit provides a credit of up to $3,600 per child under age 6 and $3,000 per child from ages 6 to 17. If the credit exceeds taxes owed, families may receive the excess amount as a refund.

Порой заголовки новостей все больше начинают напоминать панораму

Мой близкий друг Саша Сахнов - человек который на мой взгляд лучше всех разбирается в а/б тестах

Еще в далеком 2018 году мы с ним и рядом других людей начали писать на Хабр про А/Б.
Сейчас он запустил цикл статей про А/Б, где каждая статья будет сложнее предыдущей - первая довольно базовая статья про Бутстрап (Обратите внимание на центральный доверительный интервал)

Также интересен небольшой разбор стратификации для повышения чувствительности тестов
Еще можно посмотреть это видео

Между тем у нас новая вакансия
Engineering Manager (Financial Data)
Желательно США или ЮК но можно и удаленно

По факту делаем что-то среднее между BlackRock Alladin и вменяемой финансовой инфрой что делать толковый reconciliation с крипто ассетами

Можно аплаиться через сайт или писать мне

Рад сообщить что меня наконец то признали страной/географическим объектом.

Познакомился сегодня с крутым чуваком из финансовой команды

Он Software Engineer из гейм дева, где писал на плюсах
Затем работал behavioural scientist в казино, работал над тем, чтобы сделать игровые автоматы более привлекательными/подсаживающими на себя
Кроме того он сертифицированный бухгалтер

Интересная жизнь у него

В рамках написания книги по Мл систем дизайну и главы про метрики, прочитал статью Evaluating predictive count data distributions in retail sales forecasting

Статья от Академика, но неплохая, более менее понятная, а как вы знаете, любая статья которую я могу понять - хорошая

В статье разбирается следующая проблема. Прогноз спроса - вещь важная, которую решают многие люди и организации. При этом решают они эту проблему зачастую используя неподходящие метрики/функции потерь. Потому как во первых очень часто природа прогнозируемых данных дискретна - если мы прогнозируем продажи товаров (SKU) они кратны единице учета, нельзя продать 1.5 шампуня. Во вторых спрос вещь прерывистая, продажи определенного товара легко могут упасть в ноль

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

В чем проблемы ?
1. Абсолютные ошибки, MAE оптимизирует - медиану, а тот же wMAPE это по факту MAE разделенное на среднее и даже MASE(mean absolute scaled error) почти тоже самое.
Выбор между средним и медианой не самая большая проблема если распределение симметрично, но это не так в случае дискретных распределений с возможностью падением в ноль
Кроме того оптимизация медианы приводит к смещению, что легко доказать
As an example, assume that f = Pois(λ) for λ < log 2 ≈ 0.693. In this case, the median of f is 0, whereas its expectation is λ. The EMAD-optimal point forecast is 0, regardless of whether λ = 0.01, λ = 0.1 or λ = 0.5. Thus, an EMAD-optimal point forecast will be biased downward. Similarly, if log 2 < λ < λ0 , where λ0 ≈ 1.678 satisfies λ0 e−λ0 + e−λ0 = 12 , then the E MAD-optimal point forecast will be 1, which is biased upward for log2 < λ < 1 and downwardfor1<λ<λ0.

2. Ошибки в процентах тоже не подходят. MAPE не определена в нуле, а symmetric MAPE на самом деле не симметричный, кроме того smape ломается если и предикт и факт равны нулю

3. Квадратичные ошибки - чувствительны к выбросам, но хотя бы могут быть несмещенными (плюс пара интересных заметок про GMAE и GRMSE)

4. Относительные ошибки - Prominent variations are the median relative absolute error (MdRAE) and the geometric mean relative absolute error (GMRAE). Часты они сравнивают абсолютные ошибки - смотри п.1, если сравнивать с бенчмарками, то те могут выдавать ноль и снова неопределенность в нуле

5. Ранжирующие ошибки - Mean Squared Rank и Mean Absolute Rank, пытаются оценить насколько хорошо прогноз оценивает средний спрос на возрастающем отрезке времени. Интересный подход, но недостаток в том, что больший вес задается ближайшему будущему. В принципе может быть именно это и нужно, но хотелось бы уметь задавать веса

6. Scaled Errors - признаны в статье самым многообещающим подходом. sMSE - усредненный квадрат ошибки. (MSE где предикт получается регрессией факта на предикт с изначальной модели). Хотя все еще могу быть чувствительны к перепрогнозу

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

Здесь мы подходим к тому, что-же предложили пацаны

Возникает вопрос, стоит ли это разбирать?
#ArticleReview

В жизни каждого человека наступает период, когда хочется заниматься чем-то неконструктивным и отвлекающим. Играть в доту, тусить с пацанами на районе или обвинять кого-то во всех грехах. Я тоже решил позаниматься подобной активностью и поэтому завел твиттер. https://twitter.com/ValerijBabuskin

Продолжаем разбирать статью Evaluating predictive count data distributions in retail sales forecasting из этого поста
Итак, мы пришли к выводу что хотим оценивать распределение, ведь зачастую это гораздо полезнее

Для оценки непрерывных распределений можно использовать подход предложенный Розенблатом через probability integral transform (PIT)

К сожалению PIT напрямую не подходит для дискретных распределений (будет пиковать вместо выдачи равномерного распределения). Но как часто бывает в математике - не беда! Путем доработки напильником - подойдет и он - randomized PIT, где вместо интегрирования идет семплирование ( при желании можно провести связь с MCMC) и получившиеся распределение сэмплов оценивается на предмет наличия i.i.d. на U[0, 1]

Предлагают оценивать через use of a data driven smooth test to assess whether pt ∼ U [0, 1]. Specifically, we propose to apply the data driven version of Neyman’s (1937) smooth test of goodness-of-fit, as introduced by Inglot and Ledwina (2006) and Ledwina (1994). This test, when applied to one time series’ vector of pt s, yields a test statistic WT, for which we can in turn calculate a P value numerically

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

Дальше обсуждают что неплохо чтобы модель была по настоящему вероятностной, то есть была откалибрована

На что я посоветую прочитать прекрасный пост Александра Дьяконова - Проблема калибровки уверенности

В целом статья в той части где идет обзор метрик - очень познавательная, в той части где предлагается решение - вызывает вопросы
#ArticleReview

Когда становится совсем невмоготу читать статьи, на помощь приходят эспандеры. Крепкий хват вещь полезная как в борьбе, так и в качалке. На фото в ряд разминочные и тренировочные экспандеры: 60, 100, 120 и 140 фунтов

В очередной раз наткнулся на упоминание Frances Haugen

As Bloomberg noted, you might recognize his name if you've thumbed through the leaked material that whistleblower Frances Haugen revealed in 2021

Я несколько раз пересекался с Frances по работе, так как отвечал за user data privacy в WhatsApp, а она работала в FB messenger, который в тот момент планировал тоже стать end to end encrypted и им нужна была помощь чтобы понять, как жить после этого

Человек как человек, разумно радеющий за свое дело, но не overzealous.

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

Что наводит на определенные мысли.
Одно можно сказать точно, она превзошла все ожидания

Поучаствовал в записи подкаста вместе с Ruth Pike, Adrian Martins и Jeff Watkins

Будет готов где-то через 10 дней, из сложностей - делал его с еще активной анестезией челюсти, было непросто

Ниже анонс от Ruth

Yesterday marked my 10th podcast and what a podcast it was!!

Joined by three great Tech leaders, it was such a pleasure to host and listen to you all share your knowledge and experience on the topic - Career Development within Tech.

THANK YOU
⭐️Adrian Martins VP of Technology Coyote Software
⭐️Valerii Babushkin Head of Data Science Blockchain.com
⭐️Jeff Watkins Chief Product and Technology Officer xDesign

We spoke about how anyone starting their career can stand out from the crowd plus much more!!!!😎

This will be ready 10 days - in the meantime head over to our Spotify channel for more of my episodes.
https://lnkd.in/ePKJTGtg

I would love to speak with more tech leaders about getting involved in my upcoming episodes - get in touch if you or if you know of someone

На днях прочитал статью Deep Neural Networks and Tabular Data: A Survey

Статья обзорная, пытается описать и понять почему же прекрасный мир глубокого обучения так хорошо себя чувствует в гомогенных данных (картинки, звук, текст) и никак не может победить деревянные методы в гетерогенных

Сначала обсуждают причины

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

После этого ребята делят модели на следующие типы
Encoding/Data Transformations Methods - когда получаем репрезентацию признаком в каком то виде, например VIME, SuperTML( представляет данные в виде картинок для сверток)
Hybrid - когда пытается соединить классический мл и сетки, например DeepFM, TabNN, DeepGBM
Transformer based - используем механизм attention, например TabNet
Regularisation based - со строгой регуляризацией, например RLN

Затем рассматривают методы генерации табличных данных, в первую очередь для аугментации и imputation данных, во вторую - для privacy, сгенерированных данных сохраняют моменты и особенности распределений но не дают конкретной информации

Последняя часть посвящена explainable machine learning
В конце приводят графики где показывается как деревянные модели рвут сетке везде и во всем и обсуждают как жить дальше

В целом рекомендую

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

Вместо вертикального подхода aka - задизайним гугл/фейсбук/инстаграмм, мы решили пойти горизонтальным. Подробно разбираем каждый блок: БД, расчет нагрузки, масштабирование системы, повышение отзывчивости и тп, с кучей примеров и затем, уже в конце, комбинируем в готовый дизайн.

Два потока уже прошло, основные шероховатости обработали и теперь можно объявить здесь о третьем Потоке, стартующем в сентябре

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

●‎ ‎ Выпуск 1

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

●‎ Выпуск 2

Али — аналитик-разработчик из Яндекса получил задачу задизайнить Instagram

●‎ Выпуск 3

Тимлид команды ML в AliExpress Russia Евгений разрабатывал дизайн сервиса такси. Собственно с ним вместе мы и сделали System Design

●‎ Выпуск 4
Бонус, где аналитик Егор дизайнит web crawler.