Lock

Всем привет. Уже сейчас в OTUS открывает набор в новую группу курса Highload Architect. В связи с этим я продолжаю серию своих публикаций, написанных специально для этого курса, а также приглашаю вас на свой бесплатный демо урок по теме: Индексы в MySQL: best practices и подводные камни. Записаться на вебинар можно тут.

---

Введение

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

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

Паттерн Сага

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

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

Типов транзакций в саге несколько, целых четыре:

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

Организовывать сагу можно с помощью хореографии или оркестрации.

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

Сага с оркестрацией выглядит чуть более интересно. На примере указанных выше сервисов может получиться так: сервис заказов получает запрос, создает сагу, которая создает заказ в состоянии PENDING, а затем отправляет команду резервирования товара для сервиса пользователей. Сервис пользователей пытается зарезервировать товар и отправляет ответное сообщение с указанием результата. Сага одобряет или отменяет заказ.

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

Сага позволяет добиться ACD-модели (Atomicity + Consistency + Durability в терминах ACID), но одну букву мы потеряли. Недостаток буквы I приводит к известным проблемам недостатка изолированности. К ним относятся: потерянные обновления (lost updates) одна сага перезаписывает изменения, внесенные другой, не читая их при этом, грязное чтение (dirty reads) транзакция или сага читают незавершенные обновления другой саги, нечеткое/неповторяемое чтение (fuzzy/nonrepeatable reads) два разных этапа саги читают одни и те же данные, но получают разные результаты, потому что другая сага внесла изменения. Существует ряд паттернов, позволяющих пофиксить те или иные аномалии: семантическая блокировка, коммутативные обновления, пессимистическое представление, повторное чтение значения, файл изменений и по значению. Вопрос обеспечения изоляции остается открытым.

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

Заключение

Мы поговорили о способах организации саги с применением хореографии и оркестрации, а также о проблемах, которые влечет применения данного паттерна. Далее мы поговорим о способах исправления некоторых аномалий и транзакционной отправки сообщений в брокер сообщений.

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

---

Введение

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

Согласованность

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

Причина проблемы

Почему обеспечение согласованности затруднено именно в микросервисной архитектуре? Дело в том, что данный архитектурный стиль зачастую предполагает применение паттерна database per service. Позволю себе напомнить, что этот паттерн заключается в том, что у каждого микросервиса своя независимая база или базы (базы, потому что помимо первичного источника данных может использоваться, например, кеш). Такой подход позволяет с одной стороны не добавлять неявные связи по формату данных между микросервисами (микросервисы взаимодействуют только явно через API), с другой стороны по максимуму использовать такое преимущество микросервисной архитектуры как technology agnostic (мы можем выбирать подходящую под особую нагрузку на микросервис технологию хранения данных). Но при всем при этом мы потеряли гарантию согласованности данных. Посудите сами, монолит общался с одной большой базой, которая предоставляла возможности по обеспечению ACID транзакций. Теперь баз данных стало много, а вместо одной большой ACID транзакции у нас много небольших ACID транзакций. Нашей задачей будет объединение всех этих транзакций в одну распределенную.

Оптимистичная согласованность

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

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

Варианты обеспечения консистентности

Если для бизнеса все-таки согласованность является критичной, можно попытаться ее обеспечить несколькими способами. Если мы говорим о ситуации, когда данные обновляются одним сервисом (например имеет место репликация базы данных), то можно применить стандартные алгоритмы обеспечения консистентности такие как Paxos или Raft. Такие транзакции называются гомогенными. Если данные обновляются несколькими сервисами (то есть имеет место гетерогенная транзакция), то как тут как раз и начинаются сложности, о которых мы говорили выше.

С одной стороны мы можем все-таки обойти необходимость обеспечения распределенной транзакции путем стремления к service-based архитектуры (объединяем сервисы таким образом, чтобы транзакция была гомогенная). Такое решение не очень каноничное с точки зрения принципов микросервисной архитектуры, но зато оно технически намного проще из-за чего часто применяется на практике. С другой стороны мы можем оставить каноничные микросервисы, но при этом применить один из механизмов обеспечения распределенных транзакций: двухфазный коммит или сагу. В этой статье будет изучен первый вариант, а второй мы обсудим в следующий раз.

Двухфазный коммит

Механизм предельно прост: есть некоторый transaction manager, который собственно оркестрирует транзакцию. На первом этапе (prepare) transaction manager подает соответствующую команду для resource manager'ов, по которой они в свои журналы записывают данные, которые будут закоммичены. Получив подтверждение ото всех resource manager'ов об успешном завершении первого этапа, transaction manager начинает второй этап и подает следующую команду (commit), по которой resource manager'ы применяют принятые ранее изменения.

Несмотря на кажущуюся простоту, такой подход обладает рядом недостатков. Во-первых, если хотя бы один resource manager даст сбой на втором этапе, вся транзакция должна быть отменена. Таким образом, нарушается один из принципов микросервисной архитектуры устойчивость к отказам (когда мы приходили к распределенной системе, мы сразу закладывались на то, что отказ в ней является нормой а не исключительной ситуацией). Более того, если отказов будет много (а их будет много), то процесс отмены транзакций необходимо будет автоматизировать (в том числе и писать транзакции, откатывающие транзакции). Во-вторых, сам transaction manager является единой точкой отказа. Он должен уметь транзакционно выдавать id-шники транзакциям. В-третьих, поскольку хранилищу подаются специальные команды, логично предположить, что хранилище должно уметь это делать, то есть соответствовать стандарту XA, а не все современные технологии ему соответствуют (такие брокеры как Kafka, RabbitMQ и NoSQL решения как MongoDB и Cassandra не поддерживают двухфазные коммиты).

Вывод, напрашивающийся из всех этих факторов, был отлично сформулирован Крисом Ричардсоном: 2PC not an option (двухфазный коммит не вариант).

Вывод

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

---

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

---

Читать ещё:

• Сортировка выбором
• Блокировки как один из способов обеспечения изоляции транзакций
• MVCC как один из способов обеспечения изоляции транзакций
• Что нужно знать об устройстве коллекций, основанных на хешировании
  
• Почему может понадобиться полусинхронная репликация?
• Сортировка вставками

Очень часто при обсуждении многопоточности на платформе .NET говорят о таких вещах, как детали реализации механизма async/await, Task Asynchronous Pattern, deadlock, а также разбирают System.Threading. Все эти вещи можно назвать высокоуровневыми (относительно темы хабрапоста). Но что же происходит на уровне железа и ядра системы (в нашем случае Windows Kernel)?

На конференции DotNext 2016 Moscow Гаэл Фретёр, основатель и главный инженер компании PostSharp, рассказал о том, как в .NET реализована многопоточность на уровне железа и взаимодействия с ядром операционной системы. Несмотря на то, что прошло уже пять лет, мы считаем, что никогда не поздно поделиться хардкорным докладом. Гаэл представил нам хорошую базу по работе процессора и атомным примитивам.

Вот репозиторий с примерами из доклада. А под катом перевод доклада и видео. Далее повествование будет от лица спикера.

Сегодня я хотел бы поговорить о многопоточности на самом низком уровне. В докладе не будет ничего принципиально нового, всё это уже было в версии .NET 1.0. Однако, я потратил несколько недель на то, чтобы изучить спецификацию AMD64 и структурировать информацию.

У этого доклада две цели:

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

Сначала мы разберем, что происходит на уровне железа: CPU и уровни памяти, всё, что с ними происходит. Далее перейдем к ядру Windows. А после этого обсудим на первый взгляд простые вещи, такие как lock. Скорее всего, вы и сами знаете, зачем нужно это ключевое слово. Я же собираюсь объяснить, как оно реализовано.

Микроархитектура

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

Это что-то вроде Intel Core i7 своего времени. Как вы видите, за 70 лет была проделана большая работа.

К чему это все? Обычно предполагают, что байт памяти представлен где-нибудь в ячейке оперативной памяти. Но на самом деле всё иначе: он может быть представлен в нескольких местах одновременно. Например, в шести ядрах, может быть в кэшах L1 и L2, в кэше L3, наконец, может быть в оперативной памяти. Важно упомянуть: в этой архитектуре процессора есть общий кэш L3, и между ними есть Uncore. Этот компонент отвечает за координацию ядер. Также есть QPI, который отвечает за разницу между CPU. Это относится только к мультипроцессорным системам.

Почему нас беспокоит архитектура процессора? По той же причине, по которой нам нужны несколько разных уровней кэшей. У каждого уровня своя задержка. Обращаю внимание на то, что цикл CPU на этой спецификации занимает 0,3 наносекунды и сравнивается с задержкой кэшей L1, L2, L3 и DRAM. Важно заметить, что извлечение конструкции из DRAM требует около 70 циклов процессора. Если вы хотите рассчитать эти значения для своего процессора, то могу посоветовать хороший бенчмарк SiSoft Sandra.

Теперь давайте посмотрим на это более подробно. Для простоты предположим, что здесь у меня есть двухпроцессорная система. У каждого из процессоров есть четыре ядра и L2-кэш, а L1-кэш отсутствует. Также есть L3-кэш и общая оперативная память.

Хорошая аналогия для понимания многопоточных систем распределенные системы.

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

Переупорядочивание памяти

С таким поведением процессора сложно получить последовательное представление о памяти. Для того чтобы лучше разобраться, представим, что у нас есть две простые программы, которые запущены на двух процессорах или двух ядрах. Они делают одно и то же: записывают в память значение объявленной переменной, а затем выгружают из памяти. Как вы думаете, в каком порядке и на каких процессорах будут выполнены эти операции, и какие будут значения этих переменных? Каковы возможные наборы значений? От чего будет зависеть ответ?

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

Итак, давайте рассмотрим одну архитектуру. Пусть это будет x86 или AMD64, здесь не так много Y. Это означает, что она дает нам много гарантий в разных вопросах. На самом деле, x86 изначально не разрабатывался под многоядерные процессоры, поэтому когда Intel начали добавлять новые ядра, они решили сохранить ту же семантику, что раньше.

По таблице видим, что процессор с этой архитектурой может переупорядочить операции сохранить (store), после операций загрузить (load). Когда вы хотите сохранить значение, достаточно отправить сообщение. Ждать ответа не обязательно. А когда вы загружаете данные, вам нужно отправить запрос и ждать ответа. Для этой операции процессор может применить различные оптимизации.

Теперь посмотрим на колонку ARM. Как видите, эта архитектура дает нам меньше гарантий. Причина очень проста: ARM не нацелена на совместимость с x86. Их целевые платформы были совершенно разные. А еще ARM использует слабую модель памяти, чтобы повысить производительность.

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

На Intel x86 вы можете быть уверены, что переменные A и B идут строго последовательно, то есть если удалось загрузить B, то переменная A точно инициализирована. А если всё это выполняется на ARM, то у нас нет никаких гарантий, в каком порядке все это будет выполняться и как процессор проведет оптимизацию.

Барьеры памяти

Помимо оптимизации процессора, существует ещё оптимизация компилятора и среды выполнения. В контексте данной статьи под компилятором и средой я буду понимать JIT и CLR. Среда может кэшировать значения в регистрах процессора, переупорядочить операции и объединять операции записи (coalesce writes).

Например, для цикла for CLR может решить заранее рассчитать значение и вынести локальную переменную за пределы цикла. Во избежание этого, конечно же, можно использовать ключевое слово volatile, но бывают и более сложные случаи.

Иногда бывает нужно, чтобы весь код был точно выполнен до какой-либо определенной инструкции, и для этого используются барьеры памяти. Барьер памяти это инструкция, которая реализуется процессором. В .NET она доступна с помощью вызова Thread.MemoryBarrier(). И что же он делает? Вызов этого метода гарантирует, что все операции перед этим методом точно завершились.

Давайте снова вернемся к программе с двумя переменными. Предположим, что эти процессоры выполняют команды сохранить A и загрузить B. Если между этими двумя командами находится барьер памяти, то процессор сначала отправит запрос сохранить B, подождет, пока она не выполнится. Барьеры памяти дают возможность поставить что-то вроде чекпоинта или коммита, как в базе данных.

Есть еще одна причина использовать барьеры памяти. Если вы пишете код на 32-битной машине с использованием long, DateTime или struct, то атомарность выполнения операций может нарушаться. Это значит, что даже когда в коде записана одна инструкция, на самом деле могут произойти две операции вместо одной, причем они могут выполняться в разное время.

Атомарные операции

Возникает вопрос: что же делать со всем этим беспорядком и неопределенностью? Как синхронизировать ядра? На помощь приходит System.Threading.Interlocked, и это единственный механизм в .NET, предоставляющий доступ к атомарным операциям и на аппаратном уровне.

Когда мы говорим, что операция атомарна, мы имеем в виду, что она не может быть прервана. Это означает, что во время выполнения операции не может произойти переключение потока, операция не может частично завершиться. О разнице между атомарностью, эксклюзивностью и изменением порядка выполнения вы можете узнать из доклада Саши Гольдштейшна Модели памяти C++ и CLR. Более подробно об атомарности рассказывал Карлен szKarlen Симонян в докладе Атомарные операции и примитивы в .NET.

Interlocked содержит такие операции, как инкрементирование (Increment), обмен (Exchange) и обмен через сравнение (CompareExchange).

Я собираюсь разобрать не очень часто используемую операцию CompareExchange, также известную как CAS. Она изменяет значение поля на новое только в том случае, если текущее поле равно какому-либо определенному значению. Эта операция необходима для всех параллельных структур.

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

Не стоит забывать про стоимость выполнения Interlocked-операций. Стоимость инкрементирования в кэше L1 примерно равна удвоенной задержке кэша L1. Вполне быстро! Но стоимость использования Interlocked-инкремента составляет уже целых 5,5 наносекунд, даже если это происходит в единственном потоке. Этот показатель близок к показателю задержки кэша L3. А если у вас два потока обращаются к одной кэш-линии, то стоимость удваивается: ядрам приходится ждать друг друга.

Проанализируем случай, когда двум ядрам приходится ждать друг друга. Для этого используем Intel Vtune Amplifier профайлер со счетчиками производительности процессора. Он подсчитывает частоту цикла процессора и частоту процессора, нужную для выполнения одной инструкции. На картинке ниже показатель подсвечен красным. Профайлер выдает дополнительную информацию, почему соответствующее значение это плохо. Если несколько ядер обращаются к одной кэш-линии, то возникнут проблемы с производительностью. Это особенно критично для приложений, которые обрабатывают большое количество транзакций в секунду.

Многозадачность

На уровне процессора нет таких понятий, как поток и процесс: всё, что мы называем многопоточностью, предоставляет операционная система. А Wait(), на самом деле, не может заставить процессор ждать. Эта команда переводит его в режим пониженного энергопотребления (lower energy state).

И один процессор делает одно и то же, за исключением Hyper-threading, который способен выполнять другие команды.

Для процессора существует только понятие задачи (Task). Вместо потоков есть сегмент состояния задачи, который позволяет сменить таск. Состояние процессора означает состояние доступа к регистрам и маппинга памяти.

Можно использовать compareExchange на примере очень простой реализации ConcurrentStack.

Весь код (финальная версия):

internal sealed class MyConcurrentStack<T>{   private volatile Node head;   public void Push(T value)   {       SpinWait wait = new SpinWait();       Node node = new Node {Value = value};       for ( ;; )       {           Node localHead = this.head;           node.Next = localHead;           if (Interlocked.CompareExchange(ref this.head, node, localHead)                == localHead)               return;           wait.SpinOnce();       }   }   public bool TryPop(out T value)   {       SpinWait wait = new SpinWait();       for ( ;; )       {           Node localHead = this.head;           if (localHead == null )           {               value = default(T);               return false;           }           if (Interlocked.CompareExchange(ref this.head,               localHead.Next, localHead) == localHead )           {               value = localHead.Value;               return true;           }           wait.SpinOnce();       }   }   #region Nested type: Node   private sealed class Node   {       public Node Next;       public T Value;   }   #endregion}

Класс Node (внутри класса MyConcurrentStack<T>) хранит значение и содержит ссылку на следующий элемент.

Давайте сначала посмотрим на неблокирующую реализацию стека:

private sealed class Node{   public Node Next;   public T Value;}

Посмотрим на неблокирующую реализацию стека, здесь мы не используем ключевое слово lock и wait-операции:

private volatile Node head;public void Push(T value){// первым делом создаем элемент стека, тут все просто   Node node = new Node {Value = value};   for ( ;; )   {// записываем ссылку на текущую верхушку стека в локальную//переменную       Node localHead = this.head;// для нового элемента указываем ссылку на следующий элемент,// которым будет являться текущая вершина стека       node.Next = localHead;// меняем верхушку стека (this.head) на новый элемент (node),// если верхушка стека уже не была изменена       if (Interlocked.CompareExchange(           ref this.head, node, localHead ) == localHead )           return;   }}

Зачем здесь нужен условный оператор? Может случиться так, что два потока пытаются запушить новое значение в стек. Эти два потока видят одно и то же поле head. Первый поток начал вставлять новое значение до того, как это начал делать второй поток. После того как первый поток вставил значение, актуальная ссылка на headесть только у этого потока. У второго потока будет ссылка на элемент, который теперь считается следующим после head, то есть head.Next. Такая ситуация показывает, насколько важно бывает иметь такие атомарные операции, как CompareExchange.

Этот способ решения задачи основан на неблокирующей структуре данных. В методе TryPop() мы используем тот же прием:

public bool TryPop(out T value)   {       for ( ;; )       {           Node localHead = this.head;           if (localHead == null)           {               value = default(T);               return false;           }           if (Interlocked.CompareExchange(ref this.head, localHead.Next, localHead)               == localHead )           {               value = localHead.Value;               return true;           }       }   }

Берем head и заменяем её следующим узлом, если, конечно, она уже не была изменена.

В время теста MyConcurentStack участвовало два ядра. Одно ядро выполняло операцию Push(), другое операцию Pop(), ожидание отсутствовало в течение 6 миллионов операций по обмену сообщениями между двумя ядрами.

У этой структуры данных есть два недостатка:

1. необходимость очистки
2. необходимость выделения памяти для элементов коллекции

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

В результате все работает гораздо быстрее: 9 миллионов транзакций в секунду.

public class TestMyConcurrentStack : TestCollectionBase{   private readonly MyConcurrentStack<int> stack =        new MyConcurrentStack<int>();   protected override void AddItems(int count)   {       for (int i = 0; i < count; i++)       {           this.stack.Push(i);       }   }   protected override void ConsumeItems(int count)   {       SpinWait spinWait = new SpinWait();       int value;       for (int i = 0; i < count; )       {           if (this.stack.TryPop(out value))           {               i++;               spinWait.Reset();           }           else           {               spinWait.SpinOnce();           }       }   }}

Операционная система (ядро Windows)

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

Здесь я хотел бы сделать одно замечание. Наверное, у многих сложилось впечатление, что поток делает какую-либо работу и выполняет задачи, но это не так. Основное предназначение потока это ожидание.

Давайте докажу это. На этом компьютере у меня четыре ядра с гипертредингом, то есть восемь логических процессоров. Всего в системе 2384 потока.Так как логических процессоров всего 8, то получается, что все 2376 потоков в данный момент ожидают, пока до них дойдет очередь выполнения. В 99,9% случаев основное занятие потоков это ожидание.

Одна из функций ядра Windows состоит в том, чтобы заставлять потоки ждать. У внутреннего ядра Windows есть граф зависимостей между потоками и объектами-диспетчерами (dispatcher objects) Среди этих объектов могут быть таймеры, объекты, семафоры и события.

В какой-то момент некоторые зависимости исчезают, и соответствующие потоки переходят из состояния ожидания (wait) в состояние готовности (ready). Потоки в состоянии готовности отправляются в очередь ожидания, а после этого они уходят на разные ядра и начинают выполняться.

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

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

Когда вы запускаете поток ожидания, фактически создается зависимость между потоком и объектом диспетчера.

Стоимость диспетчеризации уровня ядра

Сами объекты-диспетчеры, а это события, мьютексы, таймеры и семафоры это объекты ядра. Они разделимы между процессами, и по этой причине считаются дорогими объектами.

Посмотрите на график, посмотрите на стоимость инкрементирования или доступа к кэшу L1, а затем на стоимость присваивания объекта диспетчера ядра. Две наносекунды и 295 наносекунд огромная разница! А создание объекта диспетчера вообще занимает 2093 наносекунды.

При разработке важно писать код, который не будут создавать объекты диспетчера лишний раз, иначе можно ожидать большую потерю производительности. На уровне .NET у нас есть Thread.Sleep, который использует внутренний таймер. Thread.Yield возвращает выполняющийся поток обратно в очередь ожидания потоков. Thread.Join блокирует вызывающий поток. Но сейчас я хочу более подробно рассказать про Thread.SpinWait.

SpinWait

Представьте, что у вас есть у вас есть два процессора, и на нулевом вы выполняете присваивание A = 1, потом устанавливаете барьер памяти, а затем снова выполняете присваивание B = 1.

На первом процессоре вы получаете А, равное 1, а затем вы ждете, пока B не присвоят значение 1. Казалось бы, такие операции должны быстро выполниться и в кэше L1, и даже в кэше L3. Здесь загвоздка в том, что нулевой процессор может превентивно прерваться, и между операциями из строк 1 и 3 может пройти несколько миллисекунд. SpinWait() способен решать такие проблемы.

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

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

Монитор и ключевое слово lock

Теперь давайте вернемся к ключевому слову lock. Скорее всего, вы знаете, что это просто синтаксический сахар для try/catch Monitor.Enter/Monitor.Exit.

1. Выполняется Interlocked-операция: каждый объект в .NET имеет хедер, который говорит, на каком потоке он находится и для чего он заблокирован.

   
   

2. Идёт SpinWait, если операция завершится неудачей.

   
   

3. CRL создает kernel event, если выполнение SpinWait не дало ожидаемого результата. После нескольких миллисекунд ожидания создается еще один kernel event, но только в другом потоке.

   
   

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

Структуры данных из пространства имен System.Collections.Concurrent

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

Concurrent Stack

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

Concurrent Queue

В другой структуре данных ConcurrentQueue потребители конкурируют за разные узлы. Это увеличивает пропускную способность в два раза: производители и потребители конкурируют между собой только в своей группе.

Concurrent Bag

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

Заключение

1. На аппаратном уровне есть только операции Interlocked и барьеры памяти.
2. На уровне ядра Windows вводится такая абстракция, как поток. Основное предназначение потока это ожидание и хранение набора зависимостей.
3. Также мы рассмотрели некоторые коллекции из стандартной библиотеки.

Если доклад показался вам достаточно хардкорным, загляните на сайт конференции Dotnext 2021 Piter, которая пройдёт с 20 по 23 апреля. Основными темами станут настоящее и будущее платформы .NET, оптимизация производительности, внутреннее устройство платформ, архитектура и паттерны проектирования, нетривиальные задачи и best practices. На сайте начинают появляться первые доклады, со временем список будет пополняться.