Может ли быть так, что в большинстве популярных языков отсутствует самый эффективный механизм синхронизации? Что инженеры Microsoft, Oracle и мн. др., не говоря уже об остальных, вплоть до 2024 года так и не догадались, как же эффективнее всего синхронизировать доступ к данным? А все что знает абсолютное большинство программистов, в том числе топовых IT компаний (за исключением редких разработчиков платформ Apple) о синхронизации - ошибочно? Сегодня попробуем разобраться.

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

Вступление

На C# я уже давно не пишу, но около 12 лет назад я начал заниматься кроссплатформенной мобильной разработкой на Xamarin. В задачах часто требовалось реализовывать всевозможные синхронизации доступа к состоянию из главного и фоновых потоков, а также синхронизацию работы с базой SQLite. На тот момент в Xamarin были доступны как инструменты из нативной разработки - например Grand Central Dispatch с параллельными и последовательными очередями и NSOperationQueue на их основе, так и из языка C# - Monitor, SpinLock, Mutex, Semaphore, TPL Dataflow, Thread, потокобезопасные коллекции, RxUI и многое другое. Имея такое огромное разнообразие, разработчики использовали “то, что могли” и что быстрее находилось в поисковике и на StackOverflow: блокировка примитивами всех вызовов из главного потока или из пула потоков, создание отдельных потоков, синхронизация главным потоком, да и весь остальной зоопарк, что я перечислил ранее. Все это периодически сопровождалось ошибками типа заморозки пользовательского интерфейса, состояния гонки, взаимной блокировки.

Но все таки я любил докапываться до сути и находить лучшее решение, и довольно быстро пришел к выводу, что:

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

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

Но с блокирующими операциями такое не пройдет - во время полноценных блокировок (Mutex) пул потоков вынужден создавать дополнительные потоки, чтобы ядра процессора не простаивали, а во время циклических блокировок (SpinLock) процессор попусту гоняет циклы. И если для операций ввода-вывода решение очевидно - использовать неблокирующие альтернативы, то все стандартные механизмы синхронизации популярных языков типа C# блокируют ожидающий поток на время ожидания очереди выполнения операции, которое может длится довольно долго - часто даже дольше чем сама операция.

Знакомство с GCD

Разбираясь в возможностях библиотеки GCD от Apple, и разрабатывая на Xamarin, параллельные очереди не показались чем то необходимым для использования - по сути это тот же ThreadPool либо TaskPool на C#. Но вот последовательные очереди меня заинтересовали - они легковесны, следуют принципу «первым пришёл — первым ушёл» (FIFO), не блокируют поток вызова на время ожидания выполнения операции и, самое главное, вызывают операции последовательно, что позволяет их использовать как механизм синхронизации. Делают они это в других потоках, при этом не создают их на каждую операцию, а используют либо имеющийся пул, либо свой собственный поток в случае очереди главного потока.

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

Логично сделать вывод, что на практике в большинстве случаев лучшим решением для синхронизации являются именно последовательные очереди, так как следуют ранее перечисленным требованиям "лучшего решения". Исключения могут составить лишь самые короткие операции, но даже для них, в абсолютном большинстве случаев, при разработке с уже имеющейся очередью главного потока (например под iOS), не имеет никакого смысла использовать более низкоуровневые, и соответственно более сложные и багоемкие конструкции, о которых могут не знать другие разработчики в команде - операцию в наносекунду лучше кинуть в эту самую очередь главного потока, и это никак не отразится на кадрах в секунду. Причем практика показывает, что даже те, кто думает что знают о примитивах синхронизации, часто заблуждаются и выдают некачественный, багоемкий и медленный код. А баги в “мнотопоточке” часто очень нестабильны и тяжелы в воспроизведении и исправлении. Также это хорошо сочетается с общепринятым правилом всегда вызывать методы обратного вызова (callback) в главном потоке, что позволяет не гадать в каком потоке ты сейчас находишься, и не думать лишний раз о синхронизациях. Кстати, в Xamarin для async/await при вызове из главного потока это работало по умолчанию, что довольно удобно.

Реальные примеры проблем с блокировками потоков и синхронизацией

Несколько примеров ошибки блокировки потоков, отразившихся на качестве продукта, из реальной жизни:

• Одно из самых популярных приложений каршеринга в России - годами главный поток постоянно блокировался, и только относительно недавно они наконец смогли решить проблему. Приложение работало настолько отвратительно, что пользователей пришлось удерживать самой низкой ценой на рынке, за что, впрочем, хочу высказать коллегам “руки-не-из-того-места” благодарность ? - несмотря на страдания, экономия была приличная. Хотя их помешанные на решении алгоритмов-на-бумажке конкуренты, видимо из солидарности, делали крайне тормозные и глючные встроенные в автомобиль планшеты, чем немного “спасали” положение конкурента.

• Ну плюсовики то точно пишут самые быстрые приложения? Вот одна из проблем официального кошелька биткоина. Приложение полностью блокирует интерфейс при поиске и присоединении к пирам, а так же при других операциях ввода/вывода. А происходит это довольно часто, иногда даже постоянно. После недолгого знакомства с данным приложением очень захотелось, чтоб кто нибудь уже переписал его на “тормозной” Electron, а разработчики сменили профессию. Впрочем, свято место пусто не бывает, и неофициальных кошельков на BTC создано великое множество, вот только с меньшим уровнем доверия.

• Давайте и бэкэнд не обойдем стороной. Думаю уже многие слышали, что Paypal когда то переписал свои приложения с Java Spring на NodeJS (как и другие компании), и неожиданно производительность выросла чуть ли не в 10 раз (x2 RPS при 5-кратном уменьшении рабочих ядер). Почему? Одной из основных причин является то, что в Java Spring принято вызывать блокирующие операции ввода-вывода (например JDBC не имеет не блокирующего интерфейса вовсе) и блокирующие же механизмы синхронизации. С таким подходом, помимо огромного перерасходов ресурсов, добавляются так же баги, влияющие на стабильность приложений, например такие. Когда я осознаю этот инженерный кошмар актуальных до сих пор стандартов разработки бэкэнда на Java (хоть и иногда с костылями типа Loom), я надеюсь что технологически развитых инопланетян не существует, ибо если они увидят чем мы тут занимаемся - в их глазах мы будем неудавшимся видом, и пощады не будет. И дело кстати не только в производительности - судя по информации от того же Paypal скорость разработки значительно увеличилась, количество кода уменьшилось, при уменьшении размера команды. И это не удивительно, глядя на то как реализуется одна и та же задача на двух этих технологиях вспоминается анекдот про удаление гланд через задний проход.

• Ну и из личного, наболевшего. Приложение SourceTree на Mac. Когда то, до отказа Apple от скевоморфизма, я считал его лучшим приложением на моем макбуке - очень удобным, быстрым, отзывчивым. Но после появления новых, плоских гайдлайнов видимо было решено (по моей теории), совместно с редизайном, переписать все новой командой “с нуля” (другой причины я не вижу), и с тех пор, в течение многих лет, железо все ускоряется, а SourceTree до сих пор “фризит” главный поток и работает медленнее, чем 10 лет назад на стареньком Macbook Air.

• [Оффтоп-бонус] Грех будет не притянуть за уши сравнить здесь производительность двух конкурирующих операционных систем - iOS от компании Apple, в которой эти очереди придумали и используют, эталон и пример для подражания в плане производительности операционных систем, отзывчивости пользовательского интерфейса и потребления батарейки (по крайней мере раньше), и Android от компании Google - тоже самое, только наоборот (по крайней мере раньше (с)). Тем, у кого был и iPhone 3GS (600MHz, 256Mb), и LG GT540 (600MHz, 256Mb), "не подобрать слов чтобы описать боль и унижение", что можно было испытать при "использовании" второго, даже поставив кастомный Android 4.4 и разогнав до 800MHz (да уж, было время), и отсутствие каких либо фризов и лагов на первом (пока не "догонит" запланированное устаревание с новым обновлением). А батарейка у Android девайсов так вообще была главным драйвером роста размера устройств. Впрочем, время идет, железо ускоряется, батареи смартфоны в руку не лезут, с 4+ ядрами и 8+ Gb памяти в принципе уже можно жить. И да, стандарты разработки клиентских приложений и ОС на Java недалеко ушли от бэкенда.

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

В чем проблема?

Как ни странно, в стандартных библиотеках многих языков ни тогда, ни сейчас, при всем разнообразии средств синхронизации, отсутствует данное решение из коробки, хоть его и очень просто реализовать имеющимися средствами. Например в C# это можно сделать и через SemaphoreSlim, и через ActionBlock, и банально объединяя Task в цепочку вызовов. Более того, в Microsoft чувствовали, что что то подобное необходимо, и создали класс с ужасным названием SynchronizationContext. Вот только не смогли развить эту идею до конца и использовать в том числе как один из базовых механизмов синхронизации. Был бы, например, SerialTheadPoolSynchronnizationContext? Нет, SerialQueue все таки куда лучше.

И даже на платформе от Apple, где эти очереди появились, у самой популярной библиотеки для работы с SQLite (около 10к звезд), очереди используют, но совершенно неправильно - в блокирующем режиме, сводя на нет все их преимущества. Более того, даже опытные нативные разработчики iOS часто считают, что очереди очень тяжелые, а крутой разработчик должен использовать примитивы синхронизации, так как они намного быстрее. На самом же деле они часто работают куда медленнее очередей, и это у многих не укладывается в голове. Даже при собеседовании в топовые технологические компании я устал спорить об этом, а отвечать так, как хотят услышать собеседующие, чтобы пройти фильтр, считаю ниже своего достоинства.

Написание библиотеки

Закончив работу с Xamarin, около 8 лет назад, я написал свою реализацию последовательных очередей для синхронизации доступа к данным на C#, чтобы восполнить пробел для всех остальных платформ языка C#, до которого, к сожаленю, смогли додуматься только в Apple (возможно и где то еще и сильно раньше, поделитесь в комментариях).

И только недавно, спустя много лет, после очередного обсуждения с разработчиком, решившим что я несу какую то ерунду, и получив очередной минус на StackOverflow, я решил все таки написать нагрузочный тест, чтобы проверить свои убеждения, и в дальнейших дискуссиях ссылаться на него. Тем более те, кто хоть раз плотно занимался оптимизацией, понимают, что часто даже очевидные улучшения на практике могут делать только хуже, и всегда лучше тестировать свои гипотезы. Заодно и написал более легковесную реализацию без использования Task.

Результаты теста производительности (Apple M1, 16Gb)

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

Ось X - длительность операции, которую нужно синхронизировать, в миллисекундах.

Ось Y - примерные затраты на синхронизацию в тактах (ticks) процессора.

Механизмы синхронизации:

• SpinLock, Monitor, Mutex - стандартные примитивы синхронизации.

• SemaphoreSlim - упрощенная альтернатива Semaphore. Является лидирующим ответом на соответствующий вопрос на StackOverflow.

• TPL Dataflow ActionBlock - реализация очереди используя TPL Dataflow ActionBlock.

• SerialQueue (by @borland) - схожая реализация очереди от пользователя Github с ником @borland, представленная в NuGet. Просто чтоб было с кем сравнить.

• SerialQueue - моя легковесная реализация serial queue.

• SerialQueue Tasks - моя реализация serial queue на основе Task.

Пример как читать графики:

• на синхронизацию операции в 0.001 миллисекунды SpinLock дополнительно тратит 4 такта процессора, Monitor - 133, SerialQueue - 101.

• на синхронизацию операции в 100 миллисекунд SpinLock дополнительно тратит 144129 тактов процессора, Monitor - 25018, SerialQueue - 194.

Какие выводы можно сделать из данных результатов:

1. Самым эффективным способом синхронизации до 0.1 миллисекунды включительно является SpinLock. На втором месте - SerialQueue. Не очень понимаю как она оказалась даже эффективнее Monitor для всех тестируемых операций, думаю можно считать их примерно равными до 500 наносекунд, далее очередь предпочтительнее.
   
   Но стоит учесть, что операции менее 100 наносекунд не замерялись - на таких масштабах дополнительные расходы на само тестирование сильно превышают длину операций - нужно писать отдельные тесты, а результаты вряд ли будут отличаться.

2. Для операций более 0.1 мс эффективнее всего SerialQueue.

3. Моя реализация очередей на основе Task превосходит SpinLock для операций от 0.5 мс, а Monitor - уже от 0.05 мс.

4. Эффективность блокирующих примитивов синхронизации очень сильно деградирует в зависимости от длины операции. К 500 мс пришлось обрезать график, так как затраты на синхронизацию возрастают до более чем 7x10^7 тактов.

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

6. Mutex и SemaphoreSlim хуже прочих для любых операций.

7. Схожая реализация SerialQueue от пользователя Github @borland показывает себя хуже всех с огромным отрывом, пока не догоняет очереди на основе Task ближе к 50 мс. При этом она не использует Task.

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

Выводы

Итого, что же правильнее использовать для:

• синхронизации работы с SQLite?

  • очередь, так как операции обычно занимают длительное время.

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

  • очередь, по той же причине.

• просто увеличить значение счетчика или обновить ссылку?

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

  • И только если нет уже существующей очереди - легковесные блокирующие способы синхронизации типа SpinLock, Interlocked и тп.

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

  • очередь, так как ее производительность не деградирует с длиной операции (O(1)), при этом являясь очень высокой даже для коротких.

Вот только я прекрасно отдаю себе отчет в том, что последовательная очередь является асинхронным средством синхронизации, и не все программисты готовы писать асинхронный код, и не все языки и фреймворки позволяют это удобно делать. И к сожалению часто у удобной асинхронности (без "callback hell") есть цена, как в случае с Task в C#, которой могло бы не быть сделай они трансляцию async/await в методы обратного вызова (callback). Но при этом на платформах от Apple к методам обратного вызова все давно привыкли и очереди используются регулярно, и даже цена за Task в C# сводится на нет эффективностью очередей уже для операций от 0.05 мс в сравнении с тем же Monitor, судя по тестам.

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

А что же с Concurrent Collections и ReaderWriterLock?

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

ReaderWriterLock тоже видится мне бесполезным. Во первых подход с неизменяемыми структурами данных позволяет читать их из любых потоков, и здесь можно обойтись простой очередью. Во вторых, если использовать изменяемый подход, то полагаю реализации ReaderWriter[Serial]Queue и ReaderWriterSpinLock были бы куда производительнее. Но писать эти реализации и проверять данную гипотезу уже не буду.

Послесловие

Как же так вышло, что про такие базовые вещи практически никто не знает? Почему разработчики топовых мировых IT компаний продолжают писать все больше мусорного кода наподобие Concurrent Collections вместо добавления и пропаганды использования лучших способов синхронизации? Я бы ответил, что по настоящему хороших разработчиков на самом деле единицы, большинство же ограничены решением задач с LeetCode и бездумным использованием самых популярных фреймворков. Далее такие же люди проводят собеседования, отбирая похожих на себя, кто то становятся CTO и выбирает и популяризирует откровенно неудачные технологии в самых крупных компаниях, плодя разработчиков на подобных технологиях.

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

Впрочем, есть и положительные тренды в решении проблем блокировок:

• Зеленые потоки.

• Отсутствие средств синхронизации, ограничение доступа к данным из разных потоков и [почти] принудительная асинхронность операций ввода-вывода (пример - NodeJS).

Оказалось, что научить типичного leetcode-driven разработчика грамотной работе с многопоточностью - занятие почти невыполнимое, и все идет к тому, что проще искоренить эту проблему в корне, хоть и за счет небольшой просадки производительности (прямая, грамотная работа с пулом потоков и эффективными средствами синхронизации в любом случае производительнее). Виртуальные потоки, виртуальный DOM, что дальше?

Что бы я посоветовал людям, принимающим архитектурные решения:

1. Выбирать технологии, в которых “умные дяди” все продумали и подобные проблемы практически полностью отсутствуют как класс, например: Typescript (NodeJS, React Native, Electron и т.д.), Go (зеленые потоки) и т.п.

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