В 2016-м я выступил на Highload с докладом про Vinyl, движок для хранения данных на диске в Tarantool. С тех пор мы добавили много новых возможностей, но хранение данных на диске — такая объемная тема, что основы, о которых идет речь в этой статье, совсем не изменились.

Содержание (чтобы удобно было ориентироваться):

• Почему мы написали новый движок?
• Алгоритм
  
  • Наполнение LSM дерева
  • Управление формой LSM-дерева
  • Поиск
  • Поиск по диапазону
  • Удаление
• Преимущества LSM
• Недостатки LSM и их устранение
  
  • Непредсказуемая скорость записи
  • Непредсказуемая скорость чтений
    
    • Компрессия и постраничный индекс
    • Bloom-фильтры
    • Кэширование
  • Управление сборкой мусора
• Расширенные возможности Vinyl
  
  • Upsert
  • Вторичные ключи
  • Транзакции
• Заключение

В 1980 году Intel представила чип 8087 для ускорения обработки чисел с плавающей запятой на 8086-х процессорах, и его использовали в оригинальном IBM PC. Поскольку первые микропроцессоры работали только с целыми числами, арифметика с числами с плавающей запятой была медленной, а с трансцендентными функциями вроде арктангенса или логарифмов дела обстояли ещё хуже. Добавление чипа сопроцессора 8087 к системе было способно ускорить операции с числами с плавающей запятой до ста раз.

Я вскрыл чип 8087 и сделал несколько его фотографий под микроскопом. На фото ниже показан крохотный кремниевый кристалл чипа. По его бокам крохотные проводники соединяют его с 40 внешними ногами. Разметка основных функциональных блоков на картинке сделана мною благодаря реверс-инжинирингу. Если внимательно изучить чип, то можно извлечь из его ПЗУ различные константы – такие числа, как π, используемые чипом в вычислениях.


Кристалл чипа от Intel 8087 для работы с плавающей запятой с отмеченными основными функциональными блоками. ПЗУ с константами отмечен зелёным. Кликабельно.

Я ловлю в далёком отголоске,
Что случится на моём веку.
(«Гамлет», Борис Пастернак)

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

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

Несколько дней назад Ron Pressler разродился статьей State of Loom, которую не полайкал только самый ленивый джавист. Статья действительно хорошая, в ней много интересных метафор, которые я собираюсь бессовестно использовать теперь без ссылки на первоисточник.

Со своей стороны я неосторожно позволил высказать некоторый скептицизм, когда же с этим Project Loom можно будет наконец-то реально поработать. Спустя буквально час прилетела ответочка от самого Ron'а — «а ты попробуй!». Что ж, пришлось пробовать.

Перевод пятой статьи из серии от Fabien Sanglard, в этот раз про порт Another World на Sega Genesis.

Разработка MegaDrive/Genesis началась сразу после того, как Sega выпустила свою Master System ​​в 1987 году. В то время целью Sega было создание чего-то, что превосходит PC Engine от NEC и Famicom от Nintendo.

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



Такие тесты мы начали проводить в 2013 году, задолго до того, как продукт стал доступным в опенсорсе. Как и сейчас, тогда нас больше всего интересовала скорость работы данных сервиса Яндекс.Метрика. Мы уже хранили данные в ClickHouse с января 2009 года. Часть данных записывалась в базу с 2012 года, а часть — была переконвертирована из OLAPServer и Metrage — структур данных, которые использовались в Яндекс.Метрике раньше. Поэтому для тестов мы взяли первое попавшееся подмножество из 1 миллиарда данных о просмотрах страниц. Запросов в Метрике ещё не было, и мы придумали запросы, больше всего интересные нам самим (всевозможные виды фильтрации, агрегации и сортировки).

ClickHouse тестировался в сравнении с похожими системами, например, Vertica и MonetDB. Для честности тестирования его проводил сотрудник, который до этого не был разработчиком ClickHouse, а частные случаи в коде не оптимизировались до получения результатов. Похожим образом мы получили набор данных и для функциональных тестов.

После того, как ClickHouse вышел в опенсорс в 2016 году, к тестам стало больше вопросов.

ClickHouse users already know that its biggest advantage is its high-speed processing of analytical queries. But claims like this need to be confirmed with reliable performance testing. That's what we want to talk about today.



We started running tests in 2013, long before the product was available as open source. Back then, just like now, our main concern was data processing speed in Yandex.Metrica. We had been storing that data in ClickHouse since January of 2009. Part of the data had been written to a database starting in 2012, and part was converted from OLAPServer and Metrage (data structures previously used by Yandex.Metrica). For testing, we took the first subset at random from data for 1 billion pageviews. Yandex.Metrica didn't have any queries at that point, so we came up with queries that interested us, using all the possible ways to filter, aggregate, and sort the data.

ClickHouse performance was compared with similar systems like Vertica and MonetDB. To avoid bias, testing was performed by an employee who hadn't participated in ClickHouse development, and special cases in the code were not optimized until all the results were obtained. We used the same approach to get a data set for functional testing.

After ClickHouse was released as open source in 2016, people began questioning these tests.

Операции ввода-вывода, как известно, принадлежат к числу критических ресурсов с точки зрения производительности в современных linux-системах. Выявление и анализ «узких мест» производительности в Linux-системах — дело достаточно сложное. Обычно для этой цели используются специализированные утилиты. В числе наиболее известных инструментов анализа производительности следует в первую очередь назвать утилиты, входящие в пакет sysstat (iostat, sar и т.п.). Однако в некоторых ситуациях информации получаемой с помощью этих утилит, бывает недостаточно. Например, с помощью iostat нельзя узнать, какой именно процесс совершает ту или иную операцию. Между тем такая информация бывает необходимой при решении некоторых специфических задач: например, для поиска и анализа «узких мест» в системах хранения данных.

Известный разработчик ядра Linux Йенс Аксбо в 2007 году создал blktrace — специальную утилиту, осуществляющую трассировку операций ввода-вывода и предоставляющую пользователю подробную информацию о них. В этой статье мы хотели бы подробно рассказать о возможностях blktrace.

Недавно в топике habrahabr.ru/blogs/spam/74007 было рассказано о новом виде капчи.

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

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

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

Годами эксперты в С++ рассуждают о семантике значений, иммутабельности и разделении ресурсов за счет коммуникации. О новом мире без мьютексов и гонок, без паттернов Command и Observer. На деле все не так просто. Главная проблема по-прежнему в наших структурах данных.



Иммутабельные структуры данных не меняют своих значений. Чтобы что-то с ними сделать, нужно создавать новые значения. Старые же значения остаются на прежнем месте, поэтому их можно без проблем и блокировок читать из разных потоков. В итоге ресурсы можно совместно использовать более рационально и упорядоченно, ведь старые и новые значения могут использовать общие данные. Благодаря этому их куда быстрей сравнить между собой и компактно хранить историю операций с возможностью отмены. Все это отлично ложится на многопоточные и интерактивные системы: такие структуры данных упрощают архитектуру десктопных приложений и позволяют сервисам лучше масштабироваться. Иммутабельные структуры — секрет успеха Clojure и Scala, и даже сообщество JavaScript теперь пользуется их преимуществами, ведь у них есть библиотека Immutable.js, написанная в недрах компании Facebook.

Под катом — видео и перевод доклада Juan Puente с конференции C++ Russia 2019 Moscow. Хуан рассказывает про Immer — библиотеку иммутабельных структур для C++. В посте:

• архитектурные преимущества иммутабельности;
• создание эффективного персистентного векторного типа на основе RRB-деревьев;
• разбор архитектуры на примере простого текстового редактора.

Если Вы используете стандарт C++17 в MS Visual Studio 2017 — будьте осторожны: текущая версия содержит критический баг в реализации std::map::merge и std::set::merge. Подробности — под катом.

В статье рассмотрены причины возникновения и способы избежания неопределённого поведения при обращении к синглтону в современном c++. Приведены примеры однопоточного кода. Ничего compiler-specific, всё в соответствии со стандартом.

В настоящей статье приводится разбор вариантов устранения антипаттерна «Зомби», описанного в первой части: Сказ об опасном std::enable_shared_from_this, или антипаттерн «Зомби».

В статье исследуются возможные проявления неопределённого поведения, возникающего в c++ при завершении не-void функции без вызова return с подходящим значением. Статья носит больше научно-развлекательный характер, чем практический.

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

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



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

Здесь будут рассмотрены следующие часто используемые интерфейсы: IPIP, SIT, ip6tnl, VTI и VTI6, GRE и GRETAP, GRE6 и GRE6TAP, FOU, GUE, GENEVE, ERSPAN и IP6ERSPAN.

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

Изначально в нашем IMAP-сервере использовался epoll-реактор собственной разработки. Как всегда, в процессе эксплуатации и роста нагрузки потихоньку набегают замечания, в результате чего со временем начинает накапливаться технический долг и замедляться разработка.

В нашем случае были также изначальные архитектурные замечания.

• Поток, обслуживающий реактор, никак не контролировался и при поступлении контрольных сигналов мог произойти race-condition. С другой стороны, останавливать или замедлять этот поток нельзя, поэтому возможные пути обхода выглядели неприемлемыми.
• Реактор не умел работать в full-duplex режиме. Это ограничивало его использование только интерактивными протоколами, каким является IMAP. Однако между серверами мы часто используем протокол IProto, который подразумевает full-duplex связь.

Лирическое отступление про IProto: протокол очень простой: заголовок из трёх полей типа uint32_t: команда, номер пакета, длина данных. За счет поля «номер пакета» сервер может отвечать на запросы в любом порядке, а клиент может ждать ответа в асинхронном стиле и слать следующий запрос. В Mail.Ru Group он используется повсеместно — начиная с нашей Tarantool, и заканчивая сервисом антибрутфорса.

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

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

Рекомендации на YouTube очень полезны, так как подсказывают релевантные видео к текущему, но и опасны потому что содержат ещё и в принципе интересные и отвлекающие ролики (не на тему видео).

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

Проект строился на базе достаточно известного в своих кругах другого проекта — linorobot (linorobot.org), при этом использовались доступные простому обывателю компоненты. Цели, которые были поставлены: добиться автономного перемещения робота в домашних условиях, используя low-cost компоненты, оценить производительность мини-пк для заявленных целей, настроить стек навигации для перемещения в узких пространствах хрущевок.


Статьи цикла:
Робот-тележка 2.0. Часть 3. Внутри навигационного стека ROS, немного majordomo
Робот-тележка 2.0. Часть 2. Управление в rviz и без.Элементы красоты в rviz
Робот-тележка 2.0. Часть 1. Автономная навигация домашнего робота на базе ROS

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

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

Задача каждого торгового алгоритма всегда одна и та же — принести денег владельцу. Алгоритм тем лучше, чем больше денег он в состоянии принести.