Ваш компьютер не является быстрой версией PDP-11

Привет, Хабр!

Меня зовут Антон Довгаль, я С (и не только) разработчик в Badoo.

Мне попалась на глаза статья Дэвида Чизнэлла, исследователя Кембриджского университета, в которой он оспаривает общепринятое суждение о том, что С — язык низкого уровня, и его аргументы мне показались достаточно интересными.

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

Производители процессоров не одиноки в этом. Разработчики компиляторов C/C++ тоже внесли свою лепту.

Другие части: Часть 2. Часть 3.

Пока продолжение рассказа о коммуникационных фабриках по не зависящим от меня причинам откладывается, хотелось бы осветить другую тему.
С 8 по 12 октября в Подмосковье проходила крупнейшая в России конференция, посвященная проблемам разработки микро- и наноэлектронных систем. И хоть сама конференция оставила скорее негативное впечатление, но одно из выступлений выделялось из общей массы и, вероятно, будет интересно уважаемым читателям. Речь об аналитическом докладе «Life with «dark» silicon. Power and termal problems in future platforms», который представлял Mike Kishinevsky (Principal Engineer, Strategic CAD Labs, Intel Corp.). Я постараюсь рассказать об основных идеях этого доклада, используя материалы конференции и сторонние источники.

Всем привет! Хочу рассказать про историю своей победы в ежегодном соревновании по написанию игровых ботов Russian AI Cup, в 2017. В финале бот выиграл 98% игр, что, как оказалось, наивысший результат по финалам среди всех годов проведения чемпионата. Также занял 1-е место в песочнице по завершению её работы, в пике переходя за 4000 очков рейтинга.



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

Привет, Друзья!

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

Пример использования на огромном графе:

Поиграться с демо можно здесь

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

Описание разных вариантов A* уже не раз встречалось на хабре. Мне очень понравилось вот это, потому повторяться в этой статье я не буду. Под катом расскажу подробнее почему библиотека работает быстро и о том, как было сделано демо.

Я расскажу о такой проблеме, как хеширование паролей в веб-сервисах. На первый взгляд кажется, что тут все «яснопонятно» и надо просто взять нормальный алгоритм, которых уже напридумывали много, написать чуть-чуть кода и выкатить все в продакшн. Но как обычно, когда начинаешь работать над проблемой, возникает куча подводных камней, которые надо обязательно учесть. Каких именно? Первый из них — это, пожалуй, выбор алгоритма: хоть их и много, но у каждого есть свои особенности. Второй — как выбирать параметры? Побольше и получше? Как быть с временем ответа пользователю? Сколько памяти, CPU, потоков? И третий — что делать с computational DoS? В этой статье я хочу поделиться некоторыми своими мыслями об этих трех проблемах, опытом внедрения нового алгоритма хеширования паролей в Яндексе и небольшим количеством кода.

Attacker & Defender

Прежде чем переходить к алгоритмам и построению схемы хеширования, надо вообще понять, от чего же мы защищаемся и какую роль в безопасности веб-сервиса должно играть хеширование паролей. Обычно сценарий таков, что атакующий ломает веб-сервис (или несколько веб-сервисов) через цепочку уязвимостей, получает доступ к базе данных пользователей, видит там хеши паролей, дампит базу и идет развлекаться с GPU (и, в редких случаях, с FPGA и ASIС).

Тем, кто знаком с криптографией с открытым ключом, наверно известны аббревиатуры ECC, ECDH и ECDSA. Первая — это сокращение от Elliptic Curve Cryptography (криптография на эллиптических кривых), остальные — это названия основанных на ней алгоритмов.

Сегодня криптосистемы на эллиптических кривых используются в TLS, PGP и SSH, важнейших технологиях, на которых базируются современный веб и мир ИТ. Я уже не говорю о Bitcoin и других криптовалютах.

До того, как ECC стала популярной, почти все алгоритмы с открытым ключом основывались на RSA, DSA и DH, альтернативных криптосистемах на основе модулярной арифметики. RSA и компания по-прежнему популярны, и часто используются вместе с ECC. Однако несмотря на то, что магия, лежащая в фундаменте RSA и подобных ей алгоритмов легко объяснима и понятна многим, а грубые реализации пишутся довольно просто, основы ECC всё ещё являются для большинства людей загадкой.

В этой серии статей я познакомлю вас с основами мира криптографии на эллиптических кривых. Моя цель — не создание полного и подробного руководства по ECC (в Интернете полно информации по этой теме), а простой обзор ECC и объяснение того, почему её считают безопасной. Я не буду тратить время на долгие математические доказательства или скучные подробности реализации. Также я представлю полезные примеры с визуальными интерактивными инструментами и скриптами.

Содержание

• Часть 1: Введение
  
• Часть 2: Manifold learning и скрытые (latent) переменные
  
• Часть 3: Вариационные автоэнкодеры (VAE)
  
• Часть 4: Conditional VAE
  
• Часть 5: GAN (Generative Adversarial Networks) и tensorflow
  
• Часть 6: VAE + GAN
  

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

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

В этой части попробуем взять лучшее от обоих подходов путем совмещения вариационных автоэнкодеров (VAE) и генеративных состязающихся сетей (GAN).

Подход, который будет описан далее, основан на статье [Autoencoding beyond pixels using a learned similarity metric, Larsen et al, 2016].



Иллюстрация из [1]

Поэзия — та же добыча радия.
В грамм добыча, в годы труды.
Изводишь единого слова ради
Тысячи тонн словесной руды.
Но как испепеляюще слов этих жжение
Рядом с тлением слова-сырца.
Эти слова приводят в движение
Тысячи лет миллионов сердца.

Владимир Маяковский

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

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

О чем статья

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

С этой точки зрения, очень интересным будет ресурс Kaggle[1], который превращает исследование данных в спорт. Там проводят соревнования по анализу данных. Некоторые соревнования — с обучающими материалами и предназначены для начинающих. Вот именно обучению анализу данных, на примере решения одной из обучающих задач, и будет посвящён цикл статей. Первая статья будет о подготовке данных и использованию СУБД для этой цели. Собственно, о том, как и с чего начать. Предполагается что читатель понимает SQL.

Недавно вышла новость про то, что webassembly теперь включен в firefox 52 из коробки. А потом еще и chrome 57 подтянулся (правда, там вроде бы были какие-то баги с запуском). Я решил, что обязательно надо попробовать.

Для тех, кто не знает, что такое webassembly краткая информация: webassembly (или wasm) — это низкоуровневый язык, который понимают браузеры, и в который можно будет скомпилировать программы, написанные на популярных языках. Это гораздо более выгодно по скорости парсинга и выполнения, чем компилировать эти языки в чистый javascript или какой-нибудь asm.js.

Wasm задумывался в основном для c/c++, но, на удивление, уже все готово, чтобы скомпилировать программу на rust. Давайте сделаем небольшое приложение и посмотрим, что получится. Все это будем компилировать на Ubuntu. Без теоретических деталей, просто "пощупаем".

Вы можете сказать, что “иногда бывает нужно...” Но на самом деле, вы хотите всегда видеть, что у вас в логах, через графический интерфейс. Это позволяет:

• Облегчить жизнь разработчикам и сисадминам, время которых просто жалко и дорого тратить на написание grep-конвейеров и парсеров под каждый отдельный случай.
  
• Предоставить доступ к информации, содержащейся в логах, умеренно-продвинутым пользователям — менеджерам и техподдержке.
  
• И видеть динамику и тенденции появления залогированых событий (например, ошибок).

Так что сегодня вновь поговорим о стэке ELK (Elasticsearch+Logstash+Kibana).
Но на этот раз — в условиях json-логов!

Такой use case обещает наполнить вашу жизнь совершенно новыми красками и заставит испытать полную гамму чувств.

Начнем с того, что все ваши объявления живут в базе PostgreSQL. До сих пор львиная часть бизнес-логики скрыта в хранимых процедурах, и не всегда их работу удобно контролировать.



Для нас хранимые процедуры удобны, в первую очередь тем, что не надо передавать гигабайты данных между базой и приложением. Удобно сделать несколько действий с разными таблицами в базе, а в приложение только отчитаться о том, что всё было выполнено успешно. Это действительно удобно, но в то же время это привносит и ряд проблем. Бизнес-логика частично прячется в базе, механизмы, которые используются для отладки и мониторинга на PHP/Go/Python/etc неприменимы на стороне СУБД. Конечно, есть свои замечательные средства, например, pg_stat_statements, но иногда они не могут в полной мере ответить на вопрос, какой именно кусок кода в нашей большой и сложной хранимке работает не так. Предложенное нами решение не претендует на звание «серебряной пули», но может помочь быстро определить среднее время выполнения кусков кода внутри хранимой процедуры, которая выполняется тысячи раз в секунду, и сделать это без создания лишней нагрузки. Интересно? Добро пожаловать!

Перевод статьи Andrew Hobden "Pretty State Machine Patterns in Rust". Ссылка на оригинал в конце.

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

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

Один интересный шаблон, часто применяемый к таким проблемам — "Конечный автомат". Предлагаю потратить немного времени, чтобы понять, что именно имеется ввиду под этим словосочетанием, и почему же это так интересно.

При разработке приложений необходимо уделять особое внимание архитектуре. Если изначально этого не сделать, проблемы масштабирования могут появиться внезапно (а иногда могут не иметь решения). Масштабирование приложения и эффективное использование ресурсов на начальном этапе — это сэкономленные месяцы работы в дальнейшем.
Для предотвращения подобных проблем часто используют распределенную архитектуру, то есть архитектуру с возможностью горизонтального масштабирования всех компонентов. Но к сожалению, при реализации SOA возникают новые проблемы, а именно: связность и сложность конфигурации сервисов.



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

Темой доклада Василия Лукьянчикова является индексирование в MySQL и расширенные возможности EXPLAIN, т.е. нашей задачей будет ответить на вопросы: что мы можем выяснить с помощью EXPLAIN'а, на что следует обращать внимание?

Многие ограничения EXPLAIN'а связаны с оптимизатором, поэтому мы предварительно посмотрим на архитектуру, чтобы понять, откуда следуют ограничения и что, в принципе, с помощью EXPLAIN'а можно сделать.

По индексам мы пройдемся очень кратко, исключительно в плане того, какие нюансы есть в MySQL, в отличие от общей теории.

Доклад, таким образом, состоит из 3х частей:

• Архитектура;
• Основы индексирования;
• EXPLAIN (примеры).

Как устроена MySQL-репликация

Андрей Аксенов (Sphinx), shodan

Мой доклад предназначен для тех людей, которые знают слово «репликация», даже знают, что в MySQL она есть, и, возможно, один раз ее настроили, 15 минут потратили и забыли. Больше про нее они не знают ничего.

Мы немного пройдемся по теории, попытаемся объяснить, как это все работает внутри, а после этого вы с утроенными силами сможете сами нырнуть в документацию.

Что такое репликация, в принципе? Это копирование изменений. У нас есть одна копия БД, мы хотим с какой-то целью еще одну копию.

Репликация бывает разных видов. Разные оси сравнения:

• степень синхронизации изменений (sync, async, semisync);
• количество серверов записи (M/S, M/M);
• формат изменений (statement-based (SBR), row-based (RBR), mixed);
• теоретически, модель передачи изменений (push, pull).

Kernel is the root of all evil ⊙.☉

Сейчас вряд ли кого-то удивить использованием epoll()/kqueue() в поллерах событий. Для решения проблемы C10K cуществует довольно много разнообразных решений (libevent/libev/libuv), с разной производительностью и довольно высокими накладными расходами. В статье рассматривается использование DPDK для решения задачи обработки 10 миллионов соединений (С10M), и достижение максимального прироста производительности при обработке сетевых запросов в распространённых прикладных решениях. Главной особенностью подобной задачи является делегирование ответственности обработки трафика с ядра ОС в пользовательское пространство (userspace), точный контроль обработки прерываний и каналов DMA, использование VFIO, и много других не очень понятных слов. В качестве целевого прикладного окружения было выбрано Java Netty с использованием Disruptor паттерна и offheap кэширования.



Если кратко — это очень эффективный способ обработки трафика, по производительности близкий к существующим аппаратным решениям. Накладные расходы от использования средств предоставленных самим ядром ОС — слишком велики, и для подобных задач оно является источником большинства проблем. Сложность заключается в поддержке со стороны драйверов целевых сетевых интерфейсов, и архитектурных особенностях приложений в целом.

В статье очень детально рассмотрены вопросы установки, настройки, использования, отладки, профилирования и разворачивания DPDK для построения высокопроизводительных решений.

RSA является широкоизвестным алгоритмом шифрования с открытым ключом. На его основе, кроме асимметричного шифрования, можно также реализовать электронную подпись (ЭЦП). Эти возможности привлекательны для встраиваемых систем, микроконтроллеров. Сам метод шифрования с виду чрезвычайно прост:

C = (Me) mod n

(1)

где C,M,e,n — целые числа, M — открытый текст, числа e и n представляют собой открытый ключ, C — шифротекст. mod — остаток от деления.

Расширование выглядит столь же просто:

M = (Cd) mod n

(2)

где C,M,n играют ту же роль, что и при шифровании, d — закрытый ключ.

При этом n=p*q, где p и q — простые числа (секретные), e обычно равно 65537, d вычисляется на основе e, p и q. Криптостойкость основана на том, что для достаточно больших p и q задача разложения n на множители или обращения формулы шифрования без знания p и q не решается за приемлемое время.

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

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

Google заменил начинающим программистам книги и справочники: в самом деле, почти любой вопрос кто-то уже решил до вас, остается только найти решение. Интересно другое: пользуются ли опытные программисты только своим опытом или предпочитают гуглить наравне с начинающими?