Bird

Коллеги рассказали задачку

Есть бесконечная река с пристанями, пронумерованными всеми целыми числами (..., -2, -1, 0, 1, 2, ...). По реке плывет корабль-призрак, из неизвестной начальной точки, с фиксированной, но неизвестной целочисленной скоростью - т.е. для каких-то неизвестных a, b в день i корабль останавливается в пристани ai+b.
Корабль-призрак можно засечь только ночью - то есть, чтобы его засечь, нужно остановиться в какой-то пристани на ночь - и если корабль в эту ночь был как раз в этой пристани, то мы его поймали. Нужно придумать стратегию (f(i) - в день i стоим в пристани i; f может быть любой, наша скорость не ограничена), позволяющую гарантированно за конечное (но не ограниченное и не обязательно оптимальное) число шагов поймать корабль.

Короче, нужно придумать целочисленную функцию, пересекающуюся с любой целочисленной арифметической прогрессией.
Bird

Про подкаст DevZen

С большой радостью, благодаря gliv, послушал подкаст http://devzen.ru/episode-0038, где обсуждался в т.ч. и Cloud Dataflow (начало обсуждения в 00:38:30 примерно).

Хотел бы публично прояснить пару обсуждаемых там вещей.

0. Конечно же, это не "общая теория всего" и это даже не не инструмент для разработки приложений. Это просто инструмент, очень хорошо решающий одну конкретную задачу: удобно задавать и эффективно исполнять распределенные вычисления над большим объемом данных. Использовать MapReduce или Hadoop для этого удобнее, чем писать соответствующую систему с нуля для каждой задачи, использовать FlumeJava, Millwheel или Spark еще удобнее; мы надеемся, что использовать Dataflow будет и того удобнее.

1. Почему-то в подкасте про Dataflow говорили как про "программирование мышкой" - однако это совсем не так; возможно, ведущих ввел в заблуждение скриншот (см. http://antilamer.livejournal.com/461918.html), показывающий схему программы. Программа, использующая Dataflow, выглядит примерно так же, как программа, использующая Spark - это просто код, использующий наш API. Например, см. примеры из Google Genomics или примеры из нашего SDK. В коде вы оперируете коллекциями (PCollection) и преобразованиями (PTransform), собирая из них схему (Pipeline). На скриншоте изображена фича системы мониторинга, показывающая структуру вашей схемы, то, сколько по ней где течет данных в секунду, и т.п. Если угодно, "EXPLAIN PLAN".

2. Примерно в 00:44:20 звучит вопрос, как быть с ситуацией, когда нужно подождать одного события, перед тем, как обрабатывать другое. Для этой и схожих ситуаций, как я понимаю, предназначена концепция триггеров. Лучший способ выяснить точно - задать вопрос на StackOverflow с тегом google-cloud-dataflow; мы постоянно их мониторим и обычно отвечаем в течение нескольких часов. Я работаю над другими частями продукта и думаю, что кто-то другой из команды ответит на этот вопрос гораздо лучше меня.

3. В районе 00:46 обсуждается наш scheduler. Под этим можно понимать несколько разных вещей: 1) как Dataflow разбивает задачу на куски 2) как Dataflow решает, сколько ресурсов нужно для этих кусков 3) какой кусок задачи нужно выполнить на каком ресурсе 4) как, собственно, выделяются ресурсы, запрошенные Dataflow. Пункт 4 - это просто Google Compute Engine: он играет наиболее близкую к YARN роль в этой системе, и ему совершенно неважно, Dataflow на нем исполняется или что-то другое. Для пользователя GCE предоставляет абстракцию бесконечного количества ресурсов, ваше дело - попросить и заплатить. Подсистемы, решающие задачи 1, 2, 3 - это уже сам Dataflow, и они скорее являются аналогом Spark master или Hadoop JobTracker.

4. Около 00:47:30 - вопрос о динамическом изменении топологии потокового вычисления. Мы в курсе, что это очень важная проблема; внутри гугла (в Millwheel) она решена; рано или поздно, полагаю, она будет решена и в Dataflow.
Bird

Cloud Dataflow is available

Пару дней назад Cloud Dataflow перешел в стадию "beta", что фактически эквивалентно полному запуску, разве что без SLA и без гарантий backward compatibility. В общем, можно пробовать. Есть free trial.

Напомню немного, что это за продукт.

Это фреймворк для пакетной или потоковой обработки данных с API, похожим на FlumeJava (на который, в свою очередь, похожи Spark, Flink и другие): вы пишете программу, которая конструирует схему обработки, манипулируя логическими "коллекциями" (PCollection) и всячески преобразуя и комбинируя их с помощью "преобразований" (PTransform), а затем программа говорит "схема, запустись!" и наш сервис запускает от вашего лица нужное количество ресурсов, оптимизирует схему, оптимально распределяет ее по ресурсам, мониторит и т.п.

Например:


Продукт создан объединением команд, ранее создавших MapReduce, FlumeJava и FlumeC++, Pregel и Millwheel, на основе всего полученного опыта, и вырос из попытки создать объединяющую эти продукты внутреннюю технологию.

Вот ключевые отличительные особенности:

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

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

  • Новая модель обработки, объединяющая batch и streaming. Это действительно круто - почитайте тут про эту модель, и в частности про Windowing и Triggering. Ключевое отличие от других streaming фреймворков - бескомпромиссное отношение к consistency и явный учет "поздних" данных. Один из моих коллег уже несколько раз выступал на тему того, как эта технология делает Lambda Architecture ненужной.

  • SDK в опенсорсе и позволяет исполнять программу не только на нашем сервисе, а и на других платформах. Существуют движки, исполняющие Dataflow на Spark и на Flink. Можно и локально (на своей машине).

  • Мы хорошо интегрированы с другими продуктами GCP - само собой, с Cloud Storage и Cloud Pub/Sub, но также и с BigQuery, с Cloud Logging (там можно смотреть логи ваших виртуалок) и т.п. - more to come.

  • У нас решена проблема stragglers. В то время, как другие фреймворки пытаются предсказывать, какие шарды будут медленными, и шедулить их в правильном порядке или вовремя бекапить, мы просто разрезаем уже запущенные отстающие шарды на куски, не теряя сделанной работы, и перебалансируем оставшееся. Это очень интересная проблема, на несколько порядков более сложная, чем кажется (я надеюсь, что у нас найдется время написать про это статью в обозримом будущем) - поэтому, вероятно, нигде больше она пока и не решена - но в результате у нас она решена, по сути, окончательно (за исключением некоторых патологических случаев). Интересующиеся могут посмотреть соответствующие куски в Java SDK - например, некоторые вопросы семантики этого дела затронуты в документации к классам BoundedReader и FileBasedReader. Эта техника публично называется "dynamic work rebalancing", но внутри мы ласково именуем ее "liquid sharding".

  • У нас есть auto-scaling. Пока простенький, но мы точно знаем, что нужно сделать, чтобы он был намного точнее - stay tuned. В комбинации с динамический перебалансировкой это означает, что мы можем начать с малого числа машин и очень грубого шардинга, а затем довольно быстро осознать, что нам нужно намного больше машин, и перераспределиться по ним.

Я из этого в основном вложился в: "dynamic work rebalancing", поддержку пользовательских форматов ввода-вывода, комбинацию этих двух вещей, внутренние тулы для отладки производительности, и многие части движка на бэкенде - фичи, производительность, просто code health, итп.

Ну и повторюсь, уже в который раз. Я очень счастлив быть в этой команде. Все больше свидетельств, что она исключительна даже по гугловским стандартам. Тут не только феноменальная концентрация людей уровня Staff+, ресерчеров и бывших профессоров computer science из крутых университетов, но люди крайне дружелюбны, искренне делают the right thing, и полностью отсутствует политика, эгоизм, попытки присвоить себе чужие заслуги и т.п. Классная культура тестирования и code health. Нашего engineering director'а другие директора спрашивают "как получается, что в вашей команде не бывает конфликтов?" (хотя команда-то уже под 80 человек). Это дорогого стоит и совершенно меняет динамику принятия решений и их качество.

В общем - используйте продукт и пишите, если что не так. Основной канал поддержки - StackOverflow (по тегу #google-cloud-dataflow), но можете и мне лично писать.

Ссылки:
Bird

Ulcamp

Закончился Ulcamp, сижу в Домодедово, сидеть еще 6 часов.
Впечатления интересные, in no particular order.

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

Прочитал два доклада - про "архитектуру bigdata processing в Google" (более "популярное" изложение, со сцены) и баркемп про сущность и устройство Millwheel (потоки), Pregel (графы), Dremel (read-only сверхбыстрый SQL по protobuf-ам).

Мой стиль изложения первого доклада был весьма необычным для меня. Обычно-то я заряжаю телегу на час-полтора с витиеватыми слайдами, а тут даже проектора не полагалось - правда, полагался бумажный флипчарт. Кроме того, незадолго до улькампа я прочитал книжку Made To Stick, которая меня очень впечатлила и, надеюсь, навеки изменила мой стиль донесения информации (а по дороге купил и прочитал еще и Talk like TED - тоже довольно полезно). Постараюсь как-нибудь написать про нее пост - но, как бы там ни было, я задался целью сделать доклад более увлекательным и доступным, чем обычно, с помощью использования историй (хоть каких-нибудь), curiosity gaps, больше конкретики, структурирования тройками, и делания очень явных акцентов на самых важных идеях, выраженных в простой форме. Целью было максимизировать не то, насколько доклад впечатлит слушателей, а то, сколько они из него запомнят.
За пару недель до улькампа я написал подробный план доклада (это сырые заметки, по которым я готовился), вроде бы соответствующий этим целям, и я даже впервые в жизни отрепетировал доклад. Нарисовал фломастером на флипчарте слайды со смешными картинками (фоток у меня нет, флипчарт я выкинул). Вроде бы получилось прикольно; во всяком случае, мне самому понравилось. Ответил многим на много вопросов про Гугл.

Узнал, что многие люди занимаются всякими интересными вещами - кто на clojure пишет кровавый энтерпрайз, кто прошивки к раутерам на эрланге и фильтры пакетов на хаскеле, кто видеостриминг с фонтанными кодами, кто так и вовсе суперкомпиляцию встраивает в анализатор IntelliJ IDEA. Это все освежает - а то эдак в гугле-то и зазнаться можно. Из баркемпов, на которых был, понравился доклад про суффиксные массивы от Павла Айткулова, про какую-то security сертификацию платежной системы, про ReactJS. Много других интересных баркемпов я пропустил, т.к. либо готовился к своим докладам, либо спал, либо толковал с кем-нибудь о жизни.

Режим дня у меня сбился совершенно. Это началось еще в полете с пересадками SFO - LHR - MUC - DME - ULV: было совсем непонятно, какое сейчас время дня, и относительно какой временной зоны этот вопрос вообще следует задавать, так что я кушал по принципу "прошло много времени с предыдущей еды", не особо понимая, это у меня завтрак, обед или ужин. Потом на самом улькампе выяснилось, что многие люди любят ночью потолковать и попеть песни - в первый день я проснулся в 2 часа ночи и так и не заснул, т.к. люди продолжали толковать и петь песни (особенно "о любви"). Во второй день я предусмотрительно лег спать в 7 вечера и проснулся в 8 утра - в общем, скомпенсировал.

Искупался в Волге разок.

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

Придумал неожиданно NP-полную задачу

Disclaimer: задача представляет чисто теоретический / развлекательный интерес. Не для интервью.

Вы организуете событие, на котором N мест. Люди могут покупать билеты, в т.ч. билеты на несколько мест сразу (например, я могу купить билет на 4 человека).
Допускается продажа бОльшего числа мест, чем есть. Тогда после окончания продажи билетов проводится лотерея и те, чьи билеты не "выиграли", получают деньги назад.
Нужно провести справедливую лотерею:
1) Билет на несколько мест атомарен - он либо "выигрывает" целиком, либо "проигрывает" целиком.
2) Для каждого человека, который хотел пойти, вероятность пойти должна быть одинаковой.
3) Эта вероятность должна быть максимальна (иначе можно было бы просто вернуть всем деньги).

Пример: 8 мест; хотят пойти 12 человек: куплены билеты на 3, 4, 5.
Одно из оптимальных решений такое: бросить монетку, и либо выбрать {3, 4}, либо {5}.
Тогда у всех 12 человек вероятность пойти 1/2.

Заметьте, что {5} не максимально - можно было бы добавить и {3}, но тогда нарушилось бы условие справедливости - у этих троих вероятность была бы 1, а у четверых и пятерых - 1/2.
Bird

Google Cloud Dataflow

Сегодня на Google IO (живое видео - http://google.com/io) анонсировали проект, над которым наша команда работала последние пару лет (смотря как считать) - Google Cloud Dataflow. Посмотрите - там очень прикольная демка. (перед этим, кстати - анонс cloud debugger и tracing для AppEngine - тоже офигенно крутые вещи).

Это сервис, который за вас оптимизирует и гоняет ваши распределённые вычисления - и batch, и потоковые. Например, такие (фрагменты кода из демки):
Pipeline pipeline = Pipeline.create();

PCollection<Tweet> tweets = pipeline.begin()
    .apply(new InputFromPubSub())
    .apply(new TweetTransformer());

tweets.apply(new CalculateSentiment());
tweets.apply(new CorrelateKeywords());

pipeline.run();

public class CalculateSentiment {
 ...
 return tweets.apply(new ExtractSentiment())
              .apply(Bucket.By(SlidingWindows.of(3, MINUTES)))
              .apply(Mean.perKey())
              .apply(new OutputAverageToBigQuery());
}

(за объяснением и пр. - смотрите анонс и демку; там минут 15-20, насколько я помню)

В общем, это гибрид FlumeJava и Millwheel, доступный in the cloud. Вы пишете программу на Java, которая конструирует и просит запустить pipeline, который, например, читает что-нибудь из Cloud PubSub, всячески мурыжит, а результат складывает в BigQuery - мы его оптимизируем (некоторые из оптимизаций описаны в статье про FlumeJava), запускаем на GCE, выделяем ресурсы, распределяем, балансируем, мониторим, восстанавливаем от крахов и пр.

MapReduce - тривиальный частный случай того, что можно делать с помощью Dataflow, выглядящий примерно как .apply(new MyMapper()).groupByKey().apply(new MyReducer()).

В ближайшие 9 вечера по московскому времени (10 утра по тихоокеанскому) на http://google.com/io можно будет наблюдать ещё одну демку этого продукта - сессия называется "The Dawn of Fast Data".

Моя роль в этом проекте - я один из разработчиков фреймворка, на котором держится этот продукт и другие связанные с ним внутренние инструменты обработки данных Гугла. "Клаудных" частей я не касался, но наблюдал за их разработкой, и они очень круты - удобство мониторинга, например, это чуть ли не главная selling point. Ещё одна главная selling point - auto-everything; нулевая необходимость в настройке (выборе количества машин, шардинге, упаси боже каких-нибудь размеров буферов, и пр.)

Пока что проект в режиме private beta. Через какое-то время будет limited preview, через какое - не могу сказать.