Of Code & Men

2020-02-18 20:13:44 Продолжение аналогий из предыдущего поста. Речь пойдёт про параллельные вычисления. Они включают в себя не только собственно вычисления, но и достижение консенсуса в распределенных системах, а оттуда прямой путь до блокчейна. Так вот, алгоритмы этих систем описываются 2.5 свойствами. Почему половина? Напишу в конце.

Первые два свойства упоминаются во всех источниках:
• Safety (безопасность или корректность). Она гарантирует, что система никогда не перейдет в невалидное состояние. Например, в одну телефонную будку в конкретный момент времени может зайти максимум один человек. (Если это, конечно же, не ТАРДИС.) А вот бронирование билетов на самолёты часто не удовлетворяет свойству безопасности, так что авиакомпаниям приходится иметь дело с овербукингом. В целом, это очень важное свойство, и алгоритм чаще всего не имеет смысла, если ему не удовлетворяет.
• Liveness (живучесть). Это способность системы достигать прогресса в решении задачи с течением времени. Степени живучести те же самые, что и степени неблокирующей синхронизации из предыдущего поста. Пример “живучей” задачи - выкопать канаву от забора до забора. Когда-то это задача будет выполнена, потому что каждое движение лопаты идёт в зачет. А вот поиск внеземных цивилизаций вполне может оказаться “неживучей” задачей.

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

Осталось последнее свойство. Или даже половинка свойства, потому что его крайне редко упоминают. Однако, я всё же считаю его достаточно остроумным, чтобы включить сюда.
• Я бы назвал его usefulness (полезность). Допустим, вы с друзьями договорились посмотреть вечером кино. Договорились и… все остались по домам и смотрят кино дома. Свойство безопасности выполнено - никто не пострадал, свойство живучести тоже - вы достигли прогресса и посмотрели кино. Но была ли эта договоренность полезной?

Если серьезно, то это важная часть консенсусных систем. Цель консенсуса - чтобы все участники за конечное время пришли к одному значению. Существует тривиальное решение - все участники выбирают одно, наперёд заданное значение, например, ноль. Такую систему, естественно, никак не применить на практике. Поэтому, мне кажется, третье свойство тоже играет свою роль. Открыть/Комментировать

2020-02-14 18:50:31 Долго собирался с силами написать новый пост. То одно прилетает, то другое, то сил, то времени нет. И эта ситуация подсказала мне рассказать о степенях неблокирующей синхронизации*.

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

Существует три уровня синхронизации (от слабого к сильному):

* obstruction-free (без препятствий). Я взял задачу и, если ничто меня не будет отвлекать, закончу её за конечное число шагов. Примеры: чистка зубов, поездка на работу, просмотр очередной серии любимого сериала. Это самая слабая из гарантий, но даже она не всегда выполняется. Например, если я играю в “три-в-ряд” или MMORPG - я никогда не выполню задачу (не пройду игру) за конечное число шагов, потому что сами по себе они бесконечны.

* lock-free (без блокировок). Это тот уровень синхронизации, который присущ большинству людей. Он гарантирует, что с течением времени хотя бы одна задача будет продвигаться к своему завершению. То есть, если я не лежу на диване, не залипаю в интернете на котиков (и не играю в MMORPG), то я так или иначе делаю что-то полезное: работаю, готовлю, пишу статью или изучаю что-то новое. Казалось бы, что еще нужно? Но есть более строгая гарантия

* wait-free (без ожидания). Живу я, делаю в каждый момент времени что-то полезное и развивающее, а на пост новый времени нет. И так может продолжаться до бесконечности. Это всё потому, что мой алгоритм работы - не wait-free. А этот уровень гарантирует, что каждая взятая в работу задача будет завершена за конечное число шагов, не зависящее от других задач. Главное отличие от предыдущего уровня в моём случае, что, совершая ежедневно какую-то работу, я успокаивал себя тем, что продвигаюсь вперёд, но при этом новых постов тут не появлялось.
Думаю, каждый может привести пример, нарушающий гарантию wait-free - разобрать балкон, сходить к стоматологу, выучить язык…

Твой алгоритм жизни ложится в один из этих уровней. Но это лишь критерии, в них нет подсказки о том, как достичь нужного уровня. Над задачей “как всё успевать” каждому придётся работать самому.

*Неблокирующая синхронизация — подход в параллельном программировании на симметрично-многопроцессорных системах, в котором принят отказ от традиционных примитивов блокировки, таких, как семафоры, мьютексы и события. Разделение доступа между потоками идёт за счёт атомарных операций и специальных, разработанных под конкретную задачу, механизмов блокировки. (Википедия) Открыть/Комментировать

2020-01-30 17:54:23 Если вдуматься, то всё современное ПО построено на разработанных человеком алгоритмах. Эти алгоритмы, конечно же, могут содержать ошибки. То есть, баги могут быть в коде, который мы пишем, и в статическом анализаторе, анализирующем код. Баги могут быть в компиляторе, в операционной системе и даже в архитектуре процессора. Хрестоматийный пример бага в “железе” - история с “Протон-М” в 2013 году, когда в датчике угловой скорости при подключении перепутали плюс и минус.

Но еще в 1936 году (в том же году, кстати, Тьюринг предложил свою машину) появилась альтернатива - гидравлический интегратор Лукьянова. Это был аналоговый компьютер, основанный на принципах гидравлики, который решал дифференциальные уравнения. Если сильно упростить принцип работы такой машины, то он сводился к следующему:

• берётся модель бизнес-задачи, например, экономические факторы, которая переводится в дифференциальные уравнения;
• рассчитывается гидравлическая модель в виде цилиндров, трубок и поршней, которая будет описываться теми же самыми уравнениями;
• модель из цилиндров и трубок создается физически (это и есть аналоговый компьютер), в неё заливается жидкость и мы тут же получаем решение - уровень жидкости в одном из цилиндров. При этом скорость решения фактически будет O(1).

В таком варианте, конечно же, тоже остается место для багов - мы можем некорректно составить уравнения или ошибиться при проектировании машины. Но вот само получение решения зависит только от физики и свободно от человеческого фактора. Гидравлические интеграторы применялись в реальных прикладных задачах до середины 80-х, а потом как-то ушли в небытие. Но мне кажется, что совместное использование цифровых и аналоговых подходов может в будущем стать прорывом в вычислениях. Открыть/Комментировать

2020-01-24 17:34:13 Впервые с понятием строгой типизации я столкнулся в далёком 2007 году в университете на курсе (внезапно!) “Теория и практика проведения эксперимента“. На первой лекции преподаватель рассказал нам про несколько приемов, которые сейчас кажутся тривиальными. Одним из них был вывод формулы по размерности. Приведу простейший пример: если мы вcпомним, что единица давления [Па] = [Н]/[м2], то сможем восстановить формулу P = F/S. Реальные задачи могут быть сложнее, формулы могут содержать безразмерные константы, но суть не меняется.

С помощью размерностей можно проверять готовые физические формулы и аналитические вычисления. Типы в программировании фактически являются аналогом физических размерностей и используются для той же самой цели - проверять алгоритмы и функции. Более того, в ряде случаев в физике вводят различные размерности для одной и той же величины. Например, линейный размер и поперечный размер, хотя оба являются метрическими величинами [L], могут быть обозначены как размерности [L1] и [L2].

Но при написании кода мы поступаем абсолютно так же! Мы создаём отдельные типы под сущности, хотя они и одинаковы по структуре. Вместо использования одного типа 128-битного идентификатора Guid или Uuid, мы создаем типы OrderId или InvoiceId для сущностей Order и Invoice.
Функция приема заказа будет выглядеть вместо
takeOrder(Guid orderId)
вот так
takeOrder(OrderId orderId)
и туда уже невозможно будет по ошибке передать InvoiceId. То же самое, как [L1] и [L2] в примере выше.

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

2020-01-22 16:19:18 Некоторое время назад я писал об искусственном ограничении языка. Оно используется в Type Driven Development, а в более широком смысле и компиляторами, по сути обозначая границу между статической и динамической типизациями.

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

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

Собственно, такой алгоритм достижения в ненадежных распределенных системах уже существует. Он называется HotStuff и я надеюсь написать о нём в дальнейшем подробнее. Открыть/Комментировать

2019-12-23 21:30:54 Это должен был быть наш ответ xkcd. Простите) Открыть/Комментировать

2019-12-20 17:25:27 Тут такое дело. Мы для московского DotNext в ноябре запилили IT-вариацию старой-доброй игры “Алхимия“. А сегодня я опубликовал статью на Хабре про наш “проект-за-месяц“. Почитать, что у нас получилось, что не очень, и почему коты нам гадят даже в виртуальной жизни можно тут. А скачать, что у нас получилось, в Google Play. Открыть/Комментировать

2019-12-19 16:18:12 Я где-то читал о концепции искусственного языка, в котором нельзя допустить логических ошибок. Просто потому что конструкции языка, подлежащие и сказуемые, препятствуют этому. Предложение не будет “компилироваться“. Например, такой язык не позволит построить фразу типа “черное - это белое“. Все логические парадоксы, типа парадокса лжеца в принципе не смогут быть выражены этим языком.

На этой простой идее базируется Type Driven Development, когда не тесты, а сами оперируемые типы препятствуют ошибкам в коде. Этот подход позволяет избежать логических ошибок, но он бессилен против фактологических ошибок. Открыть/Комментировать

2019-12-16 11:28:46 Мы делим контент на “хардкорный” и “нехардкорный“. Если ты залез в исходники GC, прочитал от корки до корки RFC по OpenId – хардкор. В противном случае – всё, нехардкор, хуже только про софт скиллы размышлять.

Посетив какое-то количество докладов, которые были обозначены как “хардкорные“, я поделил их на две части:
1. Про концепцию. Там спикеры рассказывают про сложные вещи так, что ты чувствуешь, что реально набрался новых знаний. Даже если половину не понял.
2. Про конкретные технологии. Такие доклады напоминают мне какие-то сходки юристов или бухгалтеров, когда степень “хардкорности” определяется тем, кто лучше помнит “пятый пункт шестого параграфа” среды исполнения.

Я так и не определился в итоге, однозначно ли второй вариант хуже, чем первый. Любую концепцию можно реализовывать разными технологиями, поэтому я думаю, что в голове лучше держать целую картину, а не частные детали, привязанные к конкретным реализациям. Открыть/Комментировать

2019-12-15 15:40:24 Channel photo updated Открыть/Комментировать