Diablo 1 — это классический roguelike 1996 года в жанре hack and slash. Это была одна из первых успешных попыток познакомить широкие массы с roguelike, которые до этого имели нишевую графику в виде ASCII-арта. Игра породила несколько сиквелов и множество имитаций. Она известна своей тёмной, мрачной атмосферой, сгущающейся по мере спуска игрока в подземелья, располагающиеся под городом Тристрам. Это была одна из первых для меня игр с процедурной генерацией карт, и возможность генерации столь правдоподобных уровней просто потрясла меня.

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

Благодарю Дэвида Бревика и команду Blizard North за создание такой потрясающей игры, а также galaxyhaxz и команду Devilution за их удивительную работу по восстановлению читаемого исходного кода проекта.

Несколько дней назад случилась конференция Hydra. Ребята из JUG.ru Group пригласили спикеров мечты (Лесли Лэмпорт! Клифф Клик! Мартин Клеппманн!) и посвятили два дня распределённым системам и вычислениям. Контур был одним из трёх партнёров конференции. Мы общались на стенде, рассказывали про наши распределённые хранилки, играли в бинго, решали задачки.

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

Были даже участники, которые разобрали флипчарт на слайды, чтобы записать своё решение. Я не шучу — они сдали на проверку вот такую пачку бумаги:

Всего было три задачи:

• о выборе реплик по весам для балансировки нагрузки
• о сортировке результатов запроса к in-memory базе данных
• о передаче состояния в распределённой системе с кольцевой топологией

Понадобилась мне как-то для будущих самоделок водяная помпа. Да не простая — с ограничениями по габаритам — толщина до 25мм, ширина до 50мм (длина — уже можно варьировать). Из желаемых характеристик — напор 1м и расход 100л/ч. Не найдя в продажах желаемого (в основном — по габаритам), по своей упоротойупорной натуре приступил к реализации своего решения данного вопроса!

Внимание — много фото!

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

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

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

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

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

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


— CatBoost у нас живет на GitHub под лицензией Apache 2.0, то есть открыт и бесплатен для всех. Проект активно развивается, сейчас у нашего репозитория больше четырех тысяч звездочек. CatBoost написан на C++, это библиотека для градиентного бустинга на деревьях решений. В ней поддержано несколько видов деревьев, в том числе так называемые «симметричные» деревья, которые используются в библиотеке по умолчанию.

Привет! Меня зовут Андрей Степачев. В конце прошлого года я выступил перед коллегами с небольшим рассказом о том, что такое ZooKeeper, и как его можно использовать. Доклад изначально был рассчитан на широкий круг аудитории и может быть полезен и разработчикам, и админам, желающим разобраться, как все это примерно работает.

Начнем, пожалуй, с истории появления ZooKeeper. Сначала, как известно, в Google написали сервис Chubby для управления своими серверами и их конфигурацией. Заодно решили задачу с распределенными блокировками. Но у Chubby была одна особенность: для захвата локов необходимо открывать объект, потом закрывать. От этого страдала производительность. В Yahoo посчитали, что им нужен инструмент, при помощи которого они могли бы строить различные системы для конфигураций своих кластеров. Именно в этом основная цель ZooKeeper — хранение и управление конфигурациями определенных систем, а локи получились как побочный продукт. В итоге вся эта система была создана для построения различных примитивных синхронизаций клиентским кодом. В самом ZooKeeper явных понятий подобных очередям нет, все это реализуется на стороне клиентских библиотек.

Стоит отметить, что протокол, используемый Zookeeper называется ZAB, ссылки на описания протокола приведены в конце статьи.

disclaimer Так получилось, что последний месяц я разбираюсь с ZooKeeper, и у меня возникло желание систематизировать то, что я узнал, собственно пост об этом, а не о сервисе блокировок, как можно было подумать исходя из названия. Поехали!

При переходе от многопоточного программирования к программированию распределенных систем многие стандартные техники перестают работать. Одной из таких техник являются блокировки (synchronized), так как область их действия ограничена одним процессом, следовательно, они не только не работают на разных узлах распределенной системы, но так же не между разными экземплярами приложения на одной машине; получается, что нужен отдельный механизм для блокировок.

От распределенного сервиса блокировок разумно требовать:

1. работоспособность в условиях моргания сети (первое правило распределенных систем — никому не говорить о распределенных системах сеть ненадежна)
2. отсутствие единой точки отказа

Создать подобный сервис нам поможет ZooKeeper

В википедии написано, что ZooKeeper — распределенный сервис конфигурирования и синхронизации, не знаю как вам, но мне данное определение мало что раскрывает. Оглядываясь на свой опыт, могу дать альтернативное определение ZooKeeper, это распределенное key/value хранилище со следующими свойствами:

• пространство ключей образует дерево (иерархию подобную файловой системе)
• значения могут содержаться в любом узле иерархии, а не только в листьях (как если бы файлы одновременно были бы и каталогами), узел иерархии называется znode
• между клиентом и сервером двунаправленная связь, следовательно, клиент может подписываться как изменение конкретного значения или части иерархии
• возможно создать временную пару ключ/значение, которая существует, пока клиент её создавший подключен к кластеру
• все данные должны помещаться в память
• устойчивость к смерти некритического кол-ва узлов кластера

Что делать, если ваш запрос к базе выполняется недостаточно быстро? Как узнать, оптимально ли запрос использует вычислительные ресурсы или его можно ускорить? На последней конференции HighLoad++ в Москве я рассказал об интроспекции производительности запросов — и о том, что даёт СУБД ClickHouse, и о возможностях ОС, которые должны быть известны каждому.



Каждый раз, когда я делаю запрос, меня волнует не только результат, но и то, что этот запрос делает. Например, он работает одну секунду. Много это или мало? Я всегда думаю: а почему не полсекунды? Потом что-нибудь оптимизирую, ускоряю, и он работает 10 мс. Обычно я доволен. Но все-таки я стараюсь в этом случае сделать недовольное выражение лица и спросить: «Почему не 5 мс?» Как можно выяснить, на что тратится время при обработке запроса? Можно ли его в принципе ускорить?

Исследователи Positive Technologies активировали аппаратную отладку (JTAG) для Intel Management Engine, которая позволяет получить полный доступ ко всем устройствам PCH (Platform Controller Hub), используя технологию Intel DCI (через интерфейс USB). Мы планируем поделиться подробностями на одной из ближайших конференций. А о том, как активировать этот интерфейс, но для основного процессора, расскажем ниже.

Я планировал написать статью о том, как LLVM оптимизирует функцию, но сначала необходимо написать, как Clang транслирует C или C++ в LLVM.

Вместо предисловия

Пожалуй с этой картинки должно начинаться любое повествование о boost, Loki, самостоятельных, да и так же поставляемых с компиляторами реализациях стандартной библиотеки C++.

Да-да, и если вы думали что разработчики стандартной библиотеки для того же g++, clang, Visual Studio или, прости господи, C++ Builder (бывший Borland, а нынешний Embarcadero) — гуру, что не городят костылей, не ломают стандарт под свой компилятор и не пишут велосипедов, то, скорее всего, вы не так активно используете стандартную библиотеку C++ как вам казалось.

Статья написана как рассказ, и содержит много «воды» и отступлений, но я надеюсь, что мой опыт и получившийся код будет полезен тем, кто столкнулся с похожими проблемами при разработке на C++, особенно на старых компиляторах. Ссылка на GitHub с результатом на сегодня для нетерпеливых и нечитателей:

https://github.com/oktonion/stdex (коммиты и конструктивная критика приветствуются)

А теперь, обо всем по порядку.

Бесфайловое распространение вредоносного ПО набирает популярность. Что не удивительно, ведь работа таких программ практически не оставляет следов. В этой статье мы не будем касаться техник выполнения программ в памяти Windows. Сконцентрируемся на GNU/Linux. Linux по праву доминирует в серверном сегменте, обитает на миллионах встраиваемых устройств и обеспечивает работу подавляющего большинства веб-ресурсов. Далее мы сделаем небольшой обзор возможностей исполнения программ в памяти и продемонстрируем что это возможно даже в затруднительных условиях.

Доброе время суток, читатель. Возможно, вы уже читали мои предыдущие статьи, и знаете, что я занимаюсь написанием собственной ОС. Сегодня мы поговорим, и рассмотрим несложный и достаточно быстрый алгоритм для управления памятью — менеджер памяти — критически важная часть ОС, ведь быстрая, надежная и нерастратная работа с памятью залог хорошей ОС.
Искал я несложные и адекватные идеи для менеджера и в рунете, и на англоязычных сайтах — всё никак не мог найти никаких хороших статей про адекватный, работающий не за O(N) аллокатор. Что же, сегодня мы рассмотрим более хорошую идею для менеджера памяти, продолжение помещаю под кат.

В прошлые выходные, изучая интересные факты об аппаратном переключателе контекста 80386, я вдруг вспомнил, что первые версии ядра Linux полагались именно на него. И я погрузился в код, который не видел уже много лет. Сейчас я решил описать это чудесное путешествие по истории Linux. Я покажу все самородки и забавные артефакты, которые нашёл по пути.

Задача: проследить, как изменялось переключение контекста в ядре Linux от первой (0.01) до последней версии LTS (4.14.67), с особым акцентом на первую и последнюю версии.

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

Яндекс, как и любая другая большая интернет-компания, хранит много, а точнее очень много данных. Это и пользовательские данные из разных сервисов, и намайненные сайты, и промежуточные данные для расчёта погоды, и резервные копии баз данных. Стоимость хранения ($/ГБ) — один из важных показателей системы. В этой статье я хочу рассказать вам про один из методов, который позволил нам серьезно удешевить хранилище.

В 2015 году, как вы все помните, сильно вырос курс доллара. Точнее, расти-то он начал в конце 2014-го, но новые партии железа мы заказывали уже в 2015-м. Яндекс зарабатывает в рублях, и поэтому вместе с курсом выросла и стоимость железа для нас. Это заставило нас в очередной раз подумать о том, как сделать, чтобы в текущий кластер можно было положить больше данных. Мы такое, конечно, делаем регулярно, но в этот раз мотивация была особенно сильной.

Каждый сервер кластера предоставляет для нас следующие ресурсы: процессор, оперативную память, жёсткие диски и сеть. Сеть здесь — более сложное понятие, чем просто сетевая плата. Это ещё и вся инфраструктура внутри дата-центра, и связность между разными дата-центрами и точками обмена трафиком. В кластере для обеспечения надёжности применялась репликация, и суммарный объём кластера определялся исключительно через суммарную ёмкость жёстких дисков. Нужно было придумать, как обменять оставшиеся ресурсы на увеличение места. Кстати, если после поста у вас останутся вопросы, которые бы вы хотели обсудить лично, приходите на нашу встречу.

При выполнении запросов в ClickHouse можно обратить внимание, что в профайлере на одном из первых мест часто видна функция LZ_decompress_fast. Почему так происходит? Этот вопрос стал поводом для целого исследования по выбору лучшего алгоритма разжатия. Здесь я публикую исследование целиком, а короткую версию можно узнать из моего доклада на HighLoad++ Siberia.

Данные в ClickHouse хранятся в сжатом виде. А во время выполнения запросов ClickHouse старается почти ничего не делать — использовать минимум ресурсов CPU. Бывает, что все вычисления, на которые могло тратиться время, уже хорошо оптимизированы, да и запрос хорошо написан пользователем. Тогда остаётся выполнить разжатие.



Вопрос — почему разжатие LZ4 может быть узким местом? Казалось бы, LZ4 — очень лёгкий алгоритм: скорость разжатия, в зависимости от данных, обычно составляет от 1 до 3 ГБ/с на одно процессорное ядро. Это уже существенно больше скорости работы дисковой подсистемы. Более того, мы используем все доступные ядра, а разжатие линейно масштабируется по всем физическим ядрам.

Доброго времени суток.

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

Что такое адаптивная антенная решётка?

Антенная решётка – это набор антенных элементов, некоторым образом размещённых в пространстве. Упрощённо структуру адаптивной антенной решётки, которую мы будем рассматривать, можно представить в следующем виде:

Исключения и связанная с ними раскрутка стека – одна из самых приятных методик в C++. Обработка исключений интуитивно понятно согласуется с блочной структурой программы. Внешне, обработка исключений представляется очень логичной и естественной.

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

Тем не менее, в C++, исключения традиционно рассматриваются буквально как исключительные ситуации, связанные с восстановлением после ошибок. Трудно сказать, является ли это причиной или следствием того, что реализация обработки исключений компиляторами чрезвычайно дорога. Попробуем разобраться почему.