Добрый день, это «Без слайдов». В гостях у меня побывал Роман Елизаров, Java Champion, эксперт по Java и многопоточности (а с недавнего времени — еще и по финансовой математике), спикер многочисленных конференций, председатель жюри Северо-Восточного Европейского региона ACM-ICPC, престижнейшей в мире олимпиады по программированию, лектор в ИТМО и, наконец, VP по технологиям в компании Devexperts. В общем, «человек и пароход».
В разговоре мы затронули следующие темы:
- что такое финансовая математика и как ее учить;
- как устроен софт для финансовой индустрии;
- как в компании Devexperts появилась исследовательская лаборатория по многопоточности;
- куда развивается Concurrency, и что будет в моде в ближайшее время;
- как всемирная олимпиада по программированию пришла в Россию.
Текстовая версия — под катом.
Что такое финансовая математика, и как её учить
— Перед началом интервью ты рассказал, что начал заниматься финансовой математикой. Как и почему эта тема заинтересовала тебя?
— Столкнулся с этой темой по работе — мы много пишем всякого софта для финансовой индустрии. И порой приходят клиенты, которые начинают спрашивать: «Есть у вас это? Или есть у вас вот то?». И при этом разные умные слова говорят, половину которых мы не знаем. Вот так я и заинтересовался.
Сначала пытался учиться сам по учебникам — ничего не получалось. Потом решил процесс систематизировать, пошёл системно учиться. И из-за этого в прошлом году не появлялся ни на каких конференциях. Вместо этого сидел под большой горой учебников. Да и до сих пор у меня книжная полка забита книжками по финансовой математике, а не по теме concurrency, которая на время отошла на задний план. Конечно, я продолжаю ей заниматься и учить, но изучение все нового по concurrency отошло на второй план.
— Насколько много в современной финансовой индустрии именно математики?
— Действительно много. В основном, всё это завязано на сложные финансовые инструменты. Крупные организации, банки постоянно торгуют чем-то сложным. И чтобы оценить риски сложного финансового инструмента, нужна весьма нетривиальная математика.
Вот, например, такая простая вещь, как моделирование Монте-Карло. Она любому программисту понятна: накидал случайных чисел, сложил, получил. Вроде бы, с точки зрения программирования это выглядит очень просто. Но с точки зрения математики понять, как правильно сделать, где именно надо правильно помножить или поделить, чтобы результат имел отношение к действительности, — это нетривиальная порой задача.
— Расскажи, что такое вообще финансовая математика? С какими областями той математики, которую все мы учили в ВУЗах, она соприкасается?
— В основном, это математический анализ, теория вероятностей и такая ее область, которую мало кто изучает, — стохастические процессы, типа интеграла Ито. Их вроде как даже преподают всем понемножку, но дают только базу. Недавно я разговаривал со студентом матмеха СПбГУ, он рассказал, что прослушал курс продвинутой теории вероятностей. Но даже там очень поверхностно об этом рассказывают. Если этому где и учат, то либо в специализированных учебных заведениях, типа ВШЭ, либо на очень специализированных кафедрах. И очень немногие выпускники это знают. А если заниматься сложными финансовыми инструментами – то без этого знания никуда.
— Я помню, что ты рассказывал, что учишься в Лондоне?
— Да, это дистанционное обучение — я туда в итоге ни разу так и не съездил. Там основная фишка в том, что, во-первых, тебе учебники подобраны очень хорошие. Кстати, найти хороший учебник по любому предмету — это чудо. Когда я начинал студентов учить тому же concurrency, у меня было несколько учебников, на которые я случайным образом наткнулся и они так мне понравились, что у меня родилась мысль учить студентов.
А с финансовой математикой мне так не везло, пока я пытался сам учиться. Я гуглил про Ито-исчисление, находил какие-то книжки, попытался их читать — туфта полная. Непонятно — зачем, что к чему, структуры нет. А на курсе, во-первых, нормальные учебники подобраны, и их же авторы читают лекции. И всё это подано логично, с упором на практическое применение. Становится понятно, зачем тебе все это. Тебе показывают реальные примеры, дают кучу домашки, заставляют реально решать задачки, писать код. И это всё с одной стороны математика, а с другой стороны — прикладная математика с расчётом на то, что всё это надо программировать.
Сейчас в современной финансовой математике практически ничего не делается «для красоты» в замкнутом виде, все модели, которые реально используют, они в замкнутом виде не считаются. Это всё численные методы. И либо ты на сетках диффур решаешь методом конечных разностей, либо методом Монте-Карло что-то моделируешь. И математика нужна только для того, чтобы вывести либо конечно-разностную схему, либо понять, что надо моделировать. А дальше надо писать код, потому что без кода никакого ответа ты не получишь.
— Многие обвиняют современную математику в том, что она очень далека от реальности. А тут — наука сугубо практическая?
— Математика — она разная. Я так же сам критикую concurrency. Я читаю по этой теме кучу научных работ, и половина из них — полная чушь. Народ придумывает какие-то алгоритмы, делает какие-то сравнения, но никому на практике эти алгоритмы не нужны.
То же самое и здесь, естественно. Математика — она двигается сама. Есть отдельная область, отдельные люди, которые всё это применяют. И именно поэтому важно иметь правильный учебник. Одно дело – взять учебник, где просто абстрактная математика. Пока через него продерёшься, потратишь кучу времени, а полезного там будет мало, две-три теоремы или факта. И совершенно другое дело, когда материал структурирован, когда из всей огромной базы научного знания отобраны и выстроены в цепочку те факты, которые тебе нужны для решения практических задач.
Собственный курс по многопоточному программированию
— Давай немного поговорим о преподавании. Ты уже больше десяти лет преподаёшь, так? Когда ты начинал — был учебник Херлихи и Шавита?
— Почти десять, с 2007-го года. Учебника этого тогда еще не было, и в этом-то и была вся и сложность. Я когда начинал преподавать, мне было очень тяжело, потому что было несколько учебников, из которых я материал смешивал, добавлял туда разные научные работы, материал статей того же Херлихи. То есть, структуру этого курса мне пришлось создавать самому.
— Как ты это делал?
— Началось всё с одной книги. Я случайно наткнулся на учебник, который мне понравился. На самом деле, учебник очень странный. Автор Гарг, называется Concurrent and Distributed Computing in Java.
Мне он понравился тем, что, во-первых, в нем всё было достаточно поверхностно описано — и Concurrency, и Distributed в прикладном небольшом учебнике; во-вторых, там были практические примеры, как это можно спрограммировать; и в-третьих, были ссылки на реальные научные работы. То есть, ты главу закончил, в ней многие теоремы были пропущены и многие факты опущены, но в конце были ссылочки на дополнительное чтение.
— Чем этот учебник отличался от Java Concurrency in Practice?
— Многим. Это всё-таки теоретическая книга, но с подачей для практиков. С попыткой отобрать то, что может понадобиться на практике. И этим она меня очень зацепила. Поскольку эта книжка показалась мне слишком поверхностной, я пошёл по ссылкам, которые нашел в ней, изучил соответствующую литературу научную, отобрал что-то для студентов и выстроил из этого свой курс. Последовательность подачи материала у меня сначала была примерно такая же, как у Гарга. Но его материал я разбавлял теорией, которую брал из научных работ того же Лампорта, Херлихи и так далее.
А потом вышел уже учебник по Сoncurrency Херлихи и Шавита. Я тогда на много блогов был подписан, и как только увидел анонс и отзывы, то сразу же купил и прочитал. И испытал шок: «Вот оно! Вот то, что на самом деле надо, чтобы читать такой курс. Ни больше, ни меньше». Нужная глубина, нужная последовательность, нужная широта. Я после этого курс немножко скорректировал.
— А вот я эту книжку так всю целиком и не осилил. Знаешь, что меня в ней раздражает больше всего? Она довольно кривым языком написана, в ней сам английский какой-то странный и примеры тоже. Помнишь, там в самом начале примеры с собаками, жестяными банками. Я сидел часа два, пытаясь понять, что авторы хотя мне сказать… А потом вдруг понял, что это классический пример про то, как на атомарных регистрах что-то сделать. Как ты через это всё продирался?
— Мне было проще, потому что я уже был подготовлен. У меня уже была профессиональная деформация, я все эти примеры с собаками 100500 раз читал в статьях Лампорта и остальных авторов. Я знал, откуда это. Что это не Херлихи и Шавит придумали, а это классика, которой уже двадцать лет. И поэтому для меня всё это было знакомое и родное. И студентам я эту книгу рекомендую как дополнительное чтение, не заставляю всех её читать. Из курса моего я часть теории, которая мне кажется малополезной, выкинул и студентам ее не читаю.
—Как ты выбираешь, что рассказать студентам, а что не рассказать?
— Я даю студентам то, что мне самому показалось очень красивым и нетривиальным. Например, я доказываю студентам теорему консенсуса Херлихи, потому что мне кажется, что она очень красива и позволяет понять суть вещей. Позволяет понять, зачем тебе нужен CAS, что без него никуда, что даже два потока не могут прийти к консенсусу, если нет какой-то более высокой конструкции. Показываю универсальную конструкцию. Хотя ее на практике в том виде, как у Херлихи, ты никогда не будешь применять. Это очень искусственная вещь, но в ней используются приёмы, которые нужны дальше в реальных алгоритмах. И вообще я рассказываю про те чисто теоретические алгоритмы, в которых есть какие-то приёмчики, являющиеся строительными блоками в других, уже практических, алгоритмах.
— Кстати, если читать работы Лампорта, например, то его построения выглядят немного искусственными. Для доказательства это хорошо, но когда открываешь какой-нибудь исходный код в попытке понять применение, то видишь, что в нем вообще всё другое. Получается, что на практике эти решения не эффективны?
— Да, именно так. Основной вопрос, который волновал исследователей 20–30 лет назад, когда вся эта теория появлялась, — «Можно ли что-то сделать или нельзя?» Об эффективности вообще никто не задумывался, только о том, можно или нельзя. И появилось очень много красивых теорем, что можно, а что нельзя. И я все эти теоретические построения на регистрах студентам рассказываю за одну лекцию, очень быстро и по верхам. Я не заставляю их наизусть знать. Потому что, с одной стороны, хочется показать, что все это возможно, а с другой стороны, все эти алгоритмы практической ценности не имеют. И вторую часть курса я концентрируюсь именно на практических алгоритмах. Например, на Сoncurrent-списках — рассказываю совершенно классический алгоритм, который много где используется.
— Который с полуинвариантом?
— Да. И соответственно, я его подробно разбираю. Потому что не только сам алгоритм практически ценен. Несмотря на то, что после него появилось вагон улучшений, каких-то научных работ, всё равно по балансу между сложностью и производительностью он всех рвёт.
А вот, например, в HashMap-ах такой победы пока нет. До сих пор это активная тема исследования, которой в числе прочих и занимаемся у себя в исследовательской лаборатории и мы. Потому что HashMap – это вообще структура данных всех структур. Используется постоянно.
Есть байка известная, кажется, про СЕО Амазона. Когда он выступал перед студенческой аудиторией, то студенты, которые изучают алгоритмы, его спросили: «Скажите, какие структуры данных нам понадобятся? Какие алгоритмы? Что вы используете?». Он ответил, что для них самое важное – «хеш-таблицы, хеш-таблицы и хеш-таблицы». И это всё правда.
У нас тоже самое. И в больших бизнес-задачах всегда так: хеш-таблицы – самая важная структура данных. И с ними, конечно, с точки зрения Concurrency очень много открытых вопросов. То есть, там даже посмотреть, как активно всё это меняется в реализации. Хоть внутренности Java посмотри, как там обычный HashMap переписывается.
— По следам ConcurrentHashMap?.
— Ну, его переписали не по следам. Долгая там была история. Фурор произвели чуваки, которые лет восемь назад изучили, как в PHP устроен стандартный словарик, и даже не вникая в суть веб-сайта, сделали запрос, где ключи имеют одинаковый хеш. И стали его на разные сайты посылать.
95% сайтов, которые они попробовали, легли. И об этом они выпустили замечательную статью. После этой статьи началась борьба за хеши, в том числе, за них начал Sun бороться. У Sun первая итерация была — рандомизировать хеш-коды для строк. Потом они поняли, что дело не только в строках. И в общем, всё это закончилось текущей реализацией: если bucket хеш-таблицы переполняется, это всё заменяется на сбалансированное дерево. Цель этого — стабильная борьба с хакерами. Чтобы у тебя в худшем случае хеш-таблица не вырождалась в O(N^2)-алгоритм, а чтобы она хотя бы за O(N logN) работала. Потому что в реальном веб-сайте ты с какими масштабами N сталкиваешься? Может быть, десять тысяч, сто тысяч… И если у тебя где-то есть N^2, то твоя система легла. Потому что 100 000 в квадрате — это уже слишком много. А если у тебя небольшой N – то ещё ничего, нормально, жить будет.
Многопоточность: наука или бизнес?
— Насколько я понимаю, решения вашей компании связаны с высокими нагрузками, с многопоточностью. Расскажи, это твой интерес к Сoncurrency привёл к тому, что вы стали этим заниматься? Или, может, наоборот — работа заставила погрузиться в эту тему?
— Это скорее стечение обстоятельств. Тут сложно проследить причинно-следственную связь. Когда мы начинали (а это было в стародавние времена, в 2000ый год или даже чуть раньше), мы, как маленькая компания, брались за всё подряд. В те времена дотком-бума программисты были на вес золота, народ готов был заказывать кому угодно что угодно… И нам как-то случайно попалась пара проектов в финансовой области. Мы стали их делать, и нам понравилось. И уже года через два мы поняли, что ничем другим заниматься не хотим, перестали брать какие-либо другие проекты. Решили, что больше никакого создания веб-сайтов, никакого аутсортинга, будем заниматься только приложениями для трейдинга, брокеров и бирж.
Все остальное — следствие этого решения. Ты начинаешь заниматься этими приложениями, и у тебя начинаются проблемы с передачей котировок. Потому что их огромное количество, а основная торговля сосредоточена на американском рынке. Опять же, так исторически получилось, что мы занимались более сложными финансовыми продуктами, всякими опционами. А там миллионы инструментов, десятки миллионов котировок в секунду. Всё это надо как-то обрабатывать, досылать клиентам. Клиентов тоже много, десятки тысяч.
И нам пришлось в этом разбираться. Сначала ты переписываешь, переписываешь, изучаешь, профилируешь код, находишь узкие места, придумываешь, как пофиксить… Первые несколько лет вообще всё было исключительно своим потом и кровью достигнуто, сами изобретали решения, без всякой науки. А потом наука как-то уже подошла случайно. Мы все были самоучками в этой области, каждую книгу исчитывали от корки до корки.
И когда появилась Java Concurrency in Practice в 2006 году, ты ее брал и видел, что это сокровище! Но всё это ты уже знаешь, до всего этого уже дошёл сам, потому что у тебя были практические задачи. Но ты понимаешь, как круто, что кто-то это всё систематизировал. И ты знаешь, что если к тебе придёт новый программист, то ты можешь ему сказать: «Вот, бери и читай Java Concurrency in Practice. Там сводка знаний». И ты эту книгу начинаешь ценить за эти знания. И ты готов под каждой страницей кровью своей подписаться! Там автор пишет, а ты уже знаешь: «Да-да, чёрт побери! Я был там! Действительно так! Так не делай — а то «снег башка попадёт — совсем мёртвый будешь».
— Вообще это очень интересно, потому что книжка действительно довольно старая. И результаты тех Performance-тестов, которые там есть, сегодня выглядят довольно дико. Сейчас реальность совсем другая. Интересно наблюдать, как это всё развивается.
— Ценность её не в Performance-результатах, конечно. Ценность её в дизайн-шаблонах. Она и структурирует знания, и заставляет тебя правильно мыслить. Потому что основная проблема Concurrency в том, что его очень сложно протестировать и очень легко допустить баги. Тест можно хоть 10 раз запустить, но всё равно он потом на подвешенной системе упадёт из-за переключения. Поэтому надо писать код так, чтобы и тебе, и соседу, и тому, кто будет через несколько лет читать этот код, было понятно, что он корректный. Потому что написать код как-нибудь запутано, то как потом себя убедить, что он корректный? И вот этому учит Java Сoncurrency in Practice. Она учит шаблонам. Если ты ими пишешь, то дальше другому человеку легко их узнать, понять, что там всё правильно.
Про подход к созданию API
Я недавно разговаривал с Питером Лори, который делает OpenHFT. Он считает, что сейчас вся борьба между фреймворками идёт уже не за Performance, а за то, чтобы предоставляемое решение было некой закрытой коробкой, решающей все задачи Concurrency. Потому что, когда мы даём какие-то Concurrency-ручки наружу людям, всё нафиг вообще рушится. Как вы боретесь с тем, что ваш код потом попадает кому-то, кто не разбирается в многопоточности?
— Мы не боремся. У нас другой бизнес. Мы делаем решение за конечных клиентов, поэтому у нас такой проблемы нет. Мы даём инструмент конкретным людям больше, чем программистам.
— То есть, вы не даете API?
— Даём, но стараемся его упрощать. Мы решаем это многослойной архитектурой. У нас есть низкоуровневый API, где все кишки наружу, и где шаг влево, шаг вправо — подорвался на мине. Но этим низким уровнем пользуемся только мы сами, причем в нашей компании есть очень маленькое количество людей, которые знают, как по этим минам ходить.
А есть еще высокоуровневое API, где все удобно и понятно. И мы клиентам даже и не говорим, что есть внутри. Он документирован, он понятный. Там тоже периодически баги попадаются, но мы их находим и фиксим.
Чем занимается компания Devexperts
— Очень интересно, расскажи еще. У вас какие-то распределённые системы, которые передают котировки клиентам и назад бирже, или что?
— У нас очень много чего. Мы вообще пишем вертикально интегрированное решение. Работа с котировками установочных данных – это всего лишь маленькая часть нашего бизнеса. У нас отдельный есть продукт dxFeed — это фактически отдельная компания в Америке, которая занимается тем, что собирает данные со всех бирж (где какие курсы, котировки), распространяет и клиентам продаёт в упакованном виде через единый API в едином формате. И это только одно маленькое направление. Очень маленькое — там работает от силы десяток человек.
А вся остальная компания — мы чего только не пишем… Возьми брокера какого-нибудь, ему нужно кучу информационных систем, ему нужно учитывать клиентов, ему нужно вести свой бэк-офис, ему надо сделки учитывать… У нас огромное количество команд, которые эти системы создают.
— А биржи тоже самые разные, да?
— Биржи мы не автоматизируем. Биржи предпочитают всё делать сами in-house. Но мы интегрируемся с ними в большом количестве. В основном это американские, но есть и Азия, и ММВБ был долгое время нашим клиентом. И сейчас хорошие отношения с ними, и РТС был нашим клиентом хорошим. Потом, когда РТС и ММВБ объединились, интеграция в основную информационную систему пошла не в нашу пользу. Но на российском рынке у нас вообще клиентов очень мало. Просто потому, что масштаб не тот.
— А насколько больше американская биржа, чем наша?
— Да дело даже не в бирже. Возьмем создание какого-нибудь профессионального торгового терминала с нуля. Каждый брокер хочет, чтобы у него была не такая же фигня, как у соседа, а хочет отличаться. И если раньше гнались за меньшей комиссией, то сейчас это уже давно не главная фишка. Комиссионные у всех брокеров достаточно низкие. А борьба идет за более удобный клиентский интерфейс. Каждый брокер хочет что-то своё, уникальное. Чтобы можно было торговать чем угодно, чтобы были графики, красиво, быстро, не тормозило.
— У вас это веб?
— У нас всё. Мы делаем как веб-фронты, так и декстоп. Профессионалы ставят себе специальные стойки железные, навешивают туда пять – девять мониторов. И все эти мониторы заполнены информацией. Дальше это всё вот так начинает расти вширь и в рост. Есть специальные компании, которые делают для этого машины, специальные стойки для мониторов.
— Это винда, да?
— Так как мы пишем на Java, то у нас работа под Windows и под Mac OS X. Но конкретно такие штуки под виндой обычно делают.
— Так видеокарточек-то даже нету, которые столько мониторов могут поддерживать.
— Втыкаешь сразу несколько видеокарт, и всё. Не проблема.
— А комп мощный нужен для этого? Я так понимаю, что на сам комп нагрузки особой не идёт, его задача просто данные гонять и показывать.
— Зависит, от того, чем ты занимаешься. Конечно, в основном это гонение данных, но поскольку у тебя большой screen space, то данных надо гонять много просто потому, что у тебя экранов много. Ну и еще зависит от того, как эффективно написан весь код. Многие, наоборот, занимаются тех. анализом, и все базы данных котировок держат у себя на локальном компе. Если ты что-то строишь, это анализируется у тебя тут часто. Хотя сейчас это всё постепенно…
— А они это зачем? Это для low latency сделано?
— Нет, low latency — это вообще отдельная тема, это совершенно другой бизнес. Там тебе не нужны все эти мониторы, ты пишешь код, который работает реально быстро, и основная проблема в том, что чтобы победить других, ты должен свои железки ставить прямо на бирже, в специальном colocation, платить немаленькие за это деньги. И тут уже мониторы тебя не спасут. HFT — это очень нишевой бизнес. У нас было пара проектов low latency, но дело не пошло по разным причинам. Одна из них в том, что все, кто занимается low latency, всё стараются делать in-house. А мы сами не торгуем, мы пишем софт.
И ты спрашивал, в чём разница масштаба. Понимаешь, какая-нибудь большая торговая система – это проект от миллиона долларов минимум. Если ты посмотришь даже крупнейшего нашего брокера, то он не может себе по объективным причинам позволить эти деньги потратить, потому что у них нету способа столько заработать. У нас на всю Россию этих трейдеров несколько десятков тысяч.
Все брокеры зарабатывают на комиссионных, которых у нас генерируется с гулькин нос. А у наших брокеров просто нет денег, чтобы инвестировать в разработку какого-то навороченного софта.
В Америке — совершенно другие масштабы. Там у брокеров миллионы клиентов, которые держат миллиардные вклады, и брокер зарабатывает как на процентах с этих вкладов, так и с комиссионных от сделок. И это позволяет крупнейшим американским брокерам вкладываться в создание действительно крутейших систем.
Лаборатория по многопоточности
— В начале 2000-х ты занимался всем. А чем ты занимаешься сейчас, когда компания уже так выросла? Сколько, кстати, у вас человек?
— Четыреста человек или даже больше. Я до сих пор продолжаю заниматься всем, в том числе, пишу код, потому что кодить люблю. И поэтому не откажу себе никогда в удовольствии написать что-нибудь интересное. Но и не только. Например недавно, около года назад, мы сделали такое подразделение обособленное в компании под названием dxLab. Это исследовательская лаборатория, и я теперь активно курирую это направление.
Идея лаборатории — очень простая. К нам много лет подряд приходили на стажировку студенты. И мы поняли, что если в компанию себе берёшь стажёра, то им надо заниматься, его надо вести, помогать ему. И пока это всё остается чьей-то побочной задачей, то оно не работает. И мы поняли в какой-то момент, что из этого надо делать Fulltime-работу, надо делать отдельное подразделение, которое будет этим заниматься. Будет курировать стажёров, давать им задачи, контролировать.
— Какого типа задачи?
— Когда мы создавали dxLab год назад, у нас планировалось несколько основных направлений исследований. Одно из них — это многопоточные структуры данных и алгоритмы. Второе, связанное с этим, направление, — это тестирование и анализ производительности. То есть, мы пишем инструменты для себя, несмотря на обилие на рынке коммерческих профайлеров — в силу специфики того, что наши решения — high concurrent, и у нас есть очень много узких задач. И мы продолжаем в этих направлениях работать, потому что существует очень много вещей, которых нам нужно посмотреть.
Наши системы очень сильно отличаются от классических веб-систем, мы даже метрики другие собираем. Вот как, например, оценить, насколько загружен классический веб-сервер? Ты смотришь, сколько запросов в секунду к нему приходит.
А у нас всё совершенно другое, другие метрики. Для нас важно количество онлайн-активных пользователей. Потому что каждый пользователь получает охрененный поток котировок. Если посмотеть нашу крупнейшую систему, то там на выходе труба больше шести гигабит в секунду, к которой 50 тысяч клиентов подсоединено. Запросов они практически не делают, но, тем не менее, система дико нагружена, потому что она посылает им данные гигабайтами.
Таким образом, у нас вообще подход к дизайну систем и к Performance-мониторингу совершенно другой. И поэтому приходится многие инструменты разрабатывать с нуля. И из-за того, что нам нужны специализированные структуры данных и алгоритмы, которые никому больше не нужны.
— Какие алгоритмы? Приведи пример.
—Пример простой — котировки. В обычных реализациях HashMap пара «ключ и значение» заворачивается в объект. Если ты попытаешься при нашем объеме котировок так делать, у тебя будет дикий Garbage Collection, и всё умрёт. Поэтому нам нужны другие HashMap-ы. Нам нужно, чтобы пару «ключ — много значений» прямо в памяти раскладывать. Попробуй поищи среди научных работ алгоритмы HashMap-ов, которые к одному ключу могут атомарно много значений хронить. Да их просто нет! Ноль таких статей! То есть, надо самому эти алгоритмы придумывать.
— Все вещи, которые связаны с CAS-ами и атомарностью, как раз ругают именно за высокую аллокацию.
— Мы придумываем алгоритмы, которые без этого. Это отдельная тема исследования – как этого избежать. Просто всё приходится делать своими руками. Я давно делал доклад про, например, почему GC жрёт ваш CPU. Мы когда с этой проблемой стали сталкиваться, поняли, что никакой штатный профилировщик ее не решит. У нас все серьезные проблемы возникают всегда на продакшене. И ещё особенность в том, что системы такого рода, как наши, сложно тестировать, поэтому что надо писать свои собственные инструменты.
Если ты поищешь инструменты тестирования приложения под нагрузкой, то найдёшь сто штук. Но что все они умеют? Умеют на веб-сайт посылать HTTP-запрос. Отлично. Только у нас не веб-сайт и нет HTTP-запроса. У нас вообще другая система.
Поэтому, профилировщики приходится писать самим. Но одно дело — писать, а другое дело — пытаться двигать в этом науку. И мы поняли, что без науки нам никуда. Потому что не хочется писать чего-то, что науке неизвестно. Намного приятнее, когда ты прочитал статью, там описан алгоритм, ты взял его и релизовал. А что, если такой статьи нету? Очевидно, тебе эту статью надо самому написать, чтобы потом ты мог по ней написать свой алгоритм.
— А как вы решаете дихотомию между теорией и практикой? В теории-то алгоритм может быть какой угодно хороший, а потом на железо просто не ляжет.
— А мы пока занимаемся только прикладной наукой, фундаментальными исследованиями мы не занимаемся. У нас маленькая лаборатория.
Как развивается Concurrency, и что будет в моде в ближайшее время
—У меня такое ощущение, что есть пять книг в мире Concurrency, и все были опубликованы еще в середине двухтысячных, а новее вообще ничего нет. Дальше только статьи в журналах. Насколько это так?
— Наука всегда так развивается. Учебник Херлихи и Шавита, по научным меркам, —весьма свежая книга. У него переиздание вышло не так давно, несколько лет назад. С тех пор наука прямо семимильными шагами никуда не ушла. Для науки всё-таки лет десять должно пройти.
— Она развивается вообще?
— Развивается. Проблема в том, что когда ты открываешь работы серьёзной научной конференции, то задачи в них, как правило, далеки от практики. И это понятно. Потому что кто на эти конференции ездит? В основном, это всё-таки ВУЗы. Да, у них есть какие-нибудь сотрудничества с компаниями, они пытаются брать практические задачи оттуда, но всё равно чаще всего есть профессор, у которого есть своя тема, он её продолжает двигать вне зависимости от того, связана эта тема с практикой или нет. У профессора есть студенты, они что-то делают ему.
— Есть такой профессор Даг Ли. Какую он роль играет в современной Java и в современном Сoncurrency, я думаю все более-менее знают. И есть мужик такой, Джереми Мэнсон, который, если мне не изменяет память, был аспирантом Дага Ли и в начале двухтысячных сделал диссертацию на тему Memory Model. И потом это все просто взяли и фактически зашили в Java 5 (JSR 133). Это довольно удивительный случай, когда наука соприкасается с практикой. Ты вообще насколько активно следишь за рассылками типа concurrency-interest и hotspot-dev?
— Я подписан на всё и слежу за всем, что там происходит. И естественно, я на все блоги всех этих великих людей подписан. Соответственно, если что-то появляется, я в курсе.
— То есть, ты активно следишь не только за наукой, но и за индустрией?
— Я подписан на тысячу разных фидов. В любое свободное время я что-нибудь читаю. Я слежу за тем, что происходит в мире науки, а сейчас прибавились финансы — теперь я ещё и на это подписан. Это позволяет чувствовать тренды, и если что-то новое и интересное происходит, то мимо меня оно точно не пролетит. Потому что заранее ты не знаешь, когда и кто придумает что-то революционное. Когда читаешь старую Wait-free synchronization авторства Херлихи, вот тогда понимаешь, что по тем временам это была революция, потому что эта работа всё структурировала и сказала: «Да, вот нужны универсальные объекты, все эти CAS и так далее. Без них никак.» Понимаешь? И чётко показала, что, почему, зачем.
Сейчас похожая, горячая тема, которая должна в какой-то момент выстрелить — это Software Transactional Memory (STM). Software при поддержке Hardware, естественно. Чисто железной моделью, к сожалению, не обойдёшься, потому что железо лимитировано по объёму. Поэтому основная тема – как это всё поженить.
Фишка в том, что Hardware Transaction Memory (HTM), которая должна была быть в Haswell, оказалась бажной, и Intel выключил ее. Но рано или поздно эту фичу отладят, и у нас будет HTM-процессор. Как его использовать — понятно. Но проблема в том, как из этого дать инструмент программисту высокого уровня, который сможет любой код писать.
— Умная JVM должна всё делать за него.
— Да, но не совсем понятно, как. Это большая тема для исследования, потому что если умная JVM просто скомпилирует в HTM, то будет проблема, потому что HTM в кэше всё держит. А когда кэш кончился, система говорит: «Всё, транзакция слишком большая, я не могу её хардварно обработать». А ты хочешь хардварно! Ты не хочешь твоего high level программиста этими low level деталями напрягать. Если он написал Atomic, оно просто должно работать. Медленно или быстро — но работать должно! Поэтому тема действительно сложная, ей куча народу занимается, много свежих публикаций выходит.
Идея HTM — довольно простая. Предположим, ты пишешь хеш-таблицу. Чтобы она стала многопоточной, ты пишешь «synchronized». У тебя synchronized хеш-таблица появляется. Дальше, если тебе нужно, что-то более масштабируемое, ты начинаешь париться, придумывать CAS-ы и так далее.
А с транзакционным менеджером тебе париться вообще не надо. Ты пишешь вместо «synchronized» другое магическое слово – «atomic», мол, хочу, чтобы это всё атомарно работало. Не ситуационно, а атомарно. Суть-то вроде для программиста та же самая, но деталь совсем другая. Потому что, если у тебя есть HTM, то процессору просто идёт инструкция xbegin — «начать транзакцию». Данный CPU общается с другими CPU, и знает, какую память он меняет. Он просто начинает отслеживать: вот я сейчас читаю ячейку памяти, а не поменяли ли случайно, пока у меня транзакция, эту ячейку памяти? Потому что придёт сигнал по шине о том, что кто-то поменял.
Крутость в том, что overhead на такие действия — нулевой. Если всё хорошо и конфликта нет, то overhead даже меньше, чем у твоих всех CAS-ов и блокировок. Потому что ничего не надо реально менять. Ты берёшь xbegin, xcommit, и всё: транзакция началась, транзакция закончилась. Если тебе повезло, и никакой другой поток в этот момент с этой ячейкой памяти ничего не делал, то у тебя всё отработало без конфликта и с огромной скоростью.
Более того, у тебя получается тонкая блокировка бесплатно. У тебя огромная хеш-таблица, все операции в которой защищены транзакцией. Если один поток меняет первую половину хеш-таблицы, второй – вторую, они друг другу вообще никак не мешают и работают на полной скорости.
И только когда у тебя возникает конфликт, и два потока лезут в одну ячейку, начинаются проблемы. В классическом варианте, без хардварной транзакции, тебе пришлось бы lock для каждой ячейки держать. Это дорого. Понятно, что JVM — очень умная и умеет эти lock-и выделять объектам по необходимости, но всё равно overhead большой.
А с хардварной транзакцией у тебя появляется суперсила практически бесплатно, без потери производительности. Проблема, что эти хардварные транзакции будут только в Skylake. В Haswell первый блин вышел комом.
— А вот интересно, в hotspot-dev ничего не мелькало на эту тему? То есть, в Java уже начинали уже это всё делать?
— В hotspot-dev — не факт, но Джон Роуз, архитектор JVM, и его коллеги из Oracle на эту тему активно публикуют научные статьи.
—Я не знал, что Джон занимается наукой.
— Занимается: есть его статьи на тему, из которых я сделал вывод, что они с коллегами занимаются исследованиями в области транзакций.
В чем основной challenge работы Devexperts
— Я услышал, что у вас сложная система, что мало исследований в вашей области, поэтому приходится придумывать самим. Это основные челленджи?
— Главный челлендж — это scale. Системы становятся большими, приходится их резать на модули, потому что одним куском всё это уже не задизайнить. И у нас получается несколько проектов в компании, каждый занимается своим куском. Дальше начинаются интеграционные проблемы и поиски баланса: в какой момент надо либо писать всё в одну кучу, одним монолитом, как это сейчас принято называть, либо всё это надо резать на микросервисы и думать, как быть с перформансом тогда. Вот это всё – тоже большая головная боль. В том числе, в плане дизайна. Потому что scale растёт, много всего делаем. Куча организационных проблем из-за этого.
Мы же не делаем коробочные продукты, у нас совершенно другой бизнес. Мы не выпускаем новые версии, у нас код — это такая заготовочка для демонстрации, чтобы на выставке можно было показать. Клиенты смотрят и говорят: «Хорошо. Но мне нужно ещё вот здесь, здесь и здесь перекрасить, там вот такой функционал добавить». В итоге мы делаем custom-копию под одного клиента, custom-копию – под другого…
— А этим отдельные люди занимаются?
— Есть отдельные команды, которые под клиента уже работают. Команды внедрения.
— И они берут некий конструктор ваш?
— Да. А потом уже то, что они наконструировали надо поделить: что-то является интеллектуальной собственностью клиента, потому что это была его мега-придумка, а что-то – это просто наша кодовая база, которую надо замёржить назад в основной продукт.
— И этим отдельные люди занимаются?
— В общем, да. И никто тебе на конференции не расскажет, как такой бизнес вести, чёрт побери! Как клепать сайты – расскажут. Как делать коробочный продукт – расскажут. Как мобильные приложения делать – расскажут. Как вот таким бизнесом заниматься – никто тебе не расскажет. Ни в какой книжке не напишут.
— Это интересно?
— Это интересно. Это бизнес, который не делает больше никто. Это уникальная ниша, она даёт уникальное конкурентное преимущество. С одной стороны, иногда вроде как жалко: вот компании продают коробочные продукты десятками тысяч, а нам каждая продажа даётся с трудом. С одной стороны. С другой стороны – мы понимаем, что есть клиенты, которые просто без нас бы не осилили. Потому что они реально не хотят коробочный продукт, как у всех. Они хотят своё собственное решение, но не готовы платить за его написание с нуля. Потому что это безумно дорого и долго. Поэтому они берут наши готовые кубики, и мы для них собираем подходящее решение.
—И у вас уже есть экспертиза признанная, и фактически они идут к вам.
— Да.
Как всемирная олимпиада по программированию пришла в Россию
— Слушай, уже долго разговариваем, давай еще про одну вещь поговорим. Если я ошибаюсь, то ты еще и директор Европейских олимпиад по программированию, так?
— Не совсем. Я председатель жюри Северо-Восточного Европейского региона ACM-ICPC.
— Это тех самых знаменитых олимпиад по программированию?
— Да, есть самые большие престижные олимпиады для студентов, называются International Collegiate Programming Contest. Их проводит ACM – крупнейшее сообщество профессиональных программистов, которое еще известно тем, что ежегодно вручает всем известную премию Тьюринга. Это как Нобелевская премия, но для программистов. И Лампорт, и другие большие люди — все они лауреаты этой премии. Так вот под эгидой ACM проводится самое большое, самое престижное соревнование по программированию — ICPC.
— Где мы периодически видим наших…
— Да. Там, где периодически наши студенты всех рвут, как Тузик грелку.
— А ты там чем занимаешься?
— ICPC – это глобальная олимпиада, которая проходит в десятках регионов по всему миру. И у нас есть своя зона региональная. Называется «Северо-Восточный Европейский регион» (NEERC). В него входят Россия, Казахстан, Узбекистан, Белоруссия, Прибалтийские государства. Причём система весьма демократичная. Если какая-то команда хочет где-нибудь в другом месте участвовать, она имеет право попроситься в другую зону. Соревнуются ВУЗы, это важный момент. Не конкретные люди, а ВУЗ посылает команду.
— Есть правило, что в финале не может быть больше одной команды от ВУЗа.
— Да. В финале не больше одной команды от вуза. И в финале нельзя участвовать одному человеку больше двух раз. Всё очень жёстко сделано, чтобы не было профессионализма.
Масштаб мероприятия огромный. По всему миру сотни тысяч человек из почти сотни стран участвуют в отборе. Только в нашей Северо-Восточной Европейской зоне мы из тысячи команд отбираем по многоуровневой системе отбираем несколько ребят, которые поедут на финал.
— Как устроен отбор – это стандартизировано? Или на усмотрение региона?
— Есть общее правило, а детали – на усмотрение региона.
— Ты эти детали разрабатывал?
— Да. Я, собственно, был одним из отцов-основателей. Я в первом нашем соревновании ещё участвовал.
— А давно вообще эти соревнования проводятся?
— Сам ICPC проводится с 77-го года. А я там с 96-го года. Когда я первый раз участвовал, у нас ещё не было региона, и мы поехали участвовать в соседний регион. Написали письмо, попросились и нас взяли. Мы поехали в Стокгольм и заняли там первое место, и местных всех лишили путёвки в финал. И они такие: «Ой, как так?». И тут директор стокгольмского финала нашёл оригинальное решение, говорит: «Ребята, сделайте у себя регион». Тогда Антон Суханов, победитель всесоюзных ещё олимпиад по информатике, занимался этим. Он и организовал регион тут, страна-то большая.
— А тебе было лет 20, наверное?
— Во время того первого соревнования я был на втором курсе. И моя команда стала первым чемпионом России, мы заняли первое место в нашем регионе, поехали в финал. В финале выступили не очень: не внизу, но и не на призовые места. А в следующем регионе, так как я уже два раза участвовал в финале, мне уже участвовать было нельзя, и поэтому я стал организатором всего этого дела. Суханов тогда уехал работать в Microsoft, всё оставил на меня. И с тех пор я этим и занимаюсь.
— То есть, 20 лет уже?
— Да. У нас был сейчас юбилейный полуфинал, двадцатый. И 19 лет его организовываю я. Когда я первые года ICPC занимался, это было ужасно. Это происходило в Аничковом дворце, я там ночевал по несколько суток, фактически жил там.
Сейчас у нас отличная большая команда оргкомитета, куча людей. У каждого своё есть направление. Я вот председатель жюри, и моя задача – отобрать задачи. И не все я сам придумываю, у меня есть замечательные коллеги, которые посылают идеи, мы вместе собираемся, решаем, какие задачи – лучшие, работаем над ними. Я потом финальную делаю вычитку, всё.
Последние несколько лет мы проводим соревнования на базе ИТМО в Санкт-Петербурге. Но у нас страна-то большая, поэтому пришлось одновременно проводить соревнования в Санкт-Петербурге и в Барнауле, потому что выяснилось, что из той части России просто денег нет у студентов долететь до Питера. Началось с двух, а сейчас мы проводим в четырёх местах одновременно. Это решение было принято по финансовым соображениям, чтобы люди могли участвовать. Последние соревнования прошли в Санкт-Петербурге, Барнауле, Ташкенте и Тбилиси. Мы стараемся принести олимпиаду к людям, чтобы они всё-таки могли поучаствовать. А потом люди едут на финал.
— А сколько команд едет на финал от нашего региона?
— Обычно немногим больше десяти. В этом году, по-моему, 13 или 14.
— А в финале сколько всего?
— В финале 120–125 команд.
— Получается, что наш регион – это примерно десятая часть от всего, что есть в мире?
— Да. Наш регион большой. И мы исторически хорошо выступаем.
— Вы же принимали финал всей мировой этой олимпиады?
— Да. Два года назад. Я был директором этого финала.
— Это потому, что ваша команда выиграла?
— Потому что мы этим давно занимались и потому что мы выиграли. Было много факторов. Это как олимпийская система: каждый год финал проходит в разном месте. Разные страны, желающие провести финал у себя, шлют заявки. Мы тоже в какой-то момент послали заявку. Не то, что прямо это была наша идея. Скорее это была идея директората соревнований: «Давайте-ка, ребята, в России никогда не было, а вы этим давно занимаетесь, проведите у себя финал». Мы по сусекам поскребли и нашли финансы. И послали заявку. И организовали финал у себя. Это был колоссальный опыт.
— Вы проводили в Юбилейном, по-моему?
— Да. Сам финал проходил в Юбилейном. Фишка в том, что ты должен, организуя финал, всех участников разместить. Участники прилетают за свой счёт к тебе на финал, а дальше ты их должен полностью обеспечить. Поселить, накормить, развлечь. Полный пансион.
— А сколько человек приезжает? 120 команд, каждая команда, наверное, человек по шесть?
— Три человека плюс тренер. Минимум четыре.
— Запасные, наверное, ещё?
— Запасных тут нет. Их отменили, как раз чтобы деньги сэкономить. Решили, что вместо того, чтобы запасных тянуть, лучше больше команд пригласить. Поэтому команда официально — четыре человека. В итоге к нам приехало человек 1200 где-то. Это вереницы автобусов. Всё было летом. Мы всех поселили у Исакиевского.
— Это же белые ночи и прочее. Где гостиниц-то столько взять?
— Астория, Петро Палас — все прямо в центре.
— Это же огромные деньги на самом деле. Кто это финансировал?
— Это был федеральный грант.
— То есть, вы пришли в Правительство или в Минобразования и сказали: «Ребята, вот такая история»?
— По сути да. Это большая заслуга конкретно ИТМО и его ректора Васильева, что он умудрился выиграть большой образовательный грант на развитие вообще образования. Это был не отдельный грант под эту олимпиаду, это был такой огромный грант вообще на создание системы образования и поддержку образования программистов. И маленький кусочек этого гранта – это было проведение финала ICPC.
— То есть было предложено финансирование, вы там с городом особо не взаимодействовали?
— Мы с городом взаимодействовали по вопросам поддержки со стороны, чтобы полиция сопровождала всё это дело, автобусы там делала. Реклама по городу.
— А реклама зачем?
— А ты знаешь, город сам предложил. У города же есть социальные рекламные места. И раз город в этом участвует, помогает, поддерживает, то нам сказали: «Вот мы вам выделяем сколько-то мест». Мы совместно с ними разработали макеты рекламы. И она была там развешена. Приятно, ты приезжаешь на мероприятие – у тебя висит реклама.
А это действительно замечательное мероприятие. Это самое престижное в мире соревнование по программированию. То есть то, что оно приезжало в наш город – это на самом деле супер. Это большое достижение.
Автор: JUG.ru Group
