Многопоточность в .NET: когда не хватает производительности
Платформа .NET предоставляет множество готовых примитивов синхронизации и потокобезопасных коллекций. Если при разработке приложения нужно реализовать, например, потокобезопасный кэш или очередь запросов — обычно используются эти готовые решения, иногда сразу несколько. В отдельных случаях это приводит к проблемам с производительностью: долгим ожиданием на блокировках, избыточному потреблению памяти и долгим сборкам мусора.
Эти проблемы можно решить, если учесть, что стандартные решения сделаны достаточно общими — они могут иметь избыточный в наших сценариях оверхед. Соответственно, можно написать, например, собственную эффективную потокобезопасную коллекцию для конкретного случая.
Под катом — видео и расшифровка моего доклада с конференции DotNext, где я разбираю несколько примеров, когда использование средств из стандартной библиотеки .NET (Task.Delay, SemaphoreSlim, ConcurrentDictionary) привело к просадкам производительности, и предлагаю решения, заточенные под конкретные задачи и лишённые этих недостатков.
На момент доклада работал в Контуре. Контур разрабатывает различные приложения для бизнеса, а команда, в которой работал я, занимается инфраструктурой и разрабатывает различные вспомогательные сервисы и библиотеки, помогающие разработчикам в других командах делать продуктовые сервисы.
Команда Инфраструктуры делает свое хранилище данных, систему хостинга приложений под Windows и различные библиотеки для разработки микросервисов. Наши приложения основаны на микросервисной архитектуре — все сервисы взаимодействуют между собой по сети, и, естественно, в них используется довольно много асинхронного и многопоточного кода. Некоторые из этих приложений довольно критичны по производительности, им нужно уметь обрабатывать много запросов.
О чём мы сегодня будем говорить?
- Многопоточность и асинхронность в .NET;
- Начинка примитивов синхронизации и коллекций;
- Что делать, если стандартные подходы не справляются с нагрузкой?
Разберем некоторые особенности работы с многопоточным и асинхронным кодом в .NET. Разберём некоторые примитивы синхронизации и concurrent-коллекции, посмотрим, как они устроены внутри. Обсудим, что делать, если не хватило производительности, если стандартные классы не справляются с нагрузкой и можно ли в этой ситуации что-либо сделать.
Расскажу четыре истории, которые произошли у нас на продакшене.
История 1: Task.Delay & TimerQueue
Эта история уже довольно известная, о ней рассказывали в том числе и на предыдущих DotNext. Тем не менее, она получила довольно интересное продолжение, поэтому я её добавил. Итак, в чём суть?
1.1 Polling и long polling
Сервер выполняет долгие операции, клиент — ждет их.
Polling: клиент периодически спрашивает сервер про результат.
Long polling: клиент отправляет запрос с большим таймаутом, а сервер отвечает по завершению операции.
Преимущества:
- Меньший объем трафика
- Клиент узнает о результате быстрее
Представьте, что у нас есть сервер, который умеет обрабатывать какие-то долгие запросы, например, приложение, которое конвертирует XML-файлы в PDF, и есть клиенты, которые запускают эти задачи на обработку и хотят дожидаться их результата асинхронно. Как такое ожидание можно реализовать?
Первый способ — это polling. Клиент запускает задачу на сервере, дальше периодически проверяет статус этой задачи, при этом сервер возвращает статус задачи («выполнена»/«не выполнена»/«завершилась с ошибкой»). Клиент периодически отправляет запросы, пока не появится результат.
Второй способ — long polling. Здесь отличие в том, что клиент отправляет запросы с большими таймаутами. Сервер, получая такой запрос, не сразу сообщит о том, что задача не выполнена, а попробует некоторое время подождать появления результата.
Так в чем же преимущество long polling’а перед обычным polling’ом? Во-первых, генерируется меньший объём трафика. Мы делаем меньше сетевых запросов — меньше трафика гоняется по сети. Также клиент сможет узнать о результате быстрее, чем при обычном polling’е, потому что ему не надо ждать промежутка между несколькими запросами polling’а. Что мы хотим получить — понятно. Как мы будем реализовывать это в коде?
Задача: timeout
Хотим подождать Task с таймаутом
await SendAsync ();
Например, у нас есть Task, который отправляет запрос на сервер, и мы хотим подождать его результата с таймаутом, то есть мы либо вернём результат этого Task’а, либо отправим какую-то ошибку. Код на С# будет выглядеть так:
var sendTask = SendAsync();
var delayTask = Task.Delay(timeout);
var task = await Task.WhenAny(sendTask, delayTask);
if (task == delayTask)
return Timeout;Данный код запускает наш Task, результат которого хотим ждать, и Task.Delay. Далее, используя Task.WhenAny, ждём либо наш Task, либо Task.Delay. Если получится так, что первым выполнится Task.Delay, значит, время вышло и у нас случился таймаут, мы должны вернуть ошибку.
Этот код, конечно, не идеален и его можно доработать. Например, здесь бы не помешало отменить Task.Delay, если SendAsync вернулся раньше, но это нас сейчас не очень интересует. Суть в том, что, если мы напишем такой код и применим его при long polling’е с большими таймаутами, мы получим некоторые перформансные проблемы.
1.2 Проблемы при long polling
- Большие таймауты
- Много параллельных запросов
- => Высокая загрузка CPU
В этом случае, проблема — высокое потребление ресурсов процессора. Может получиться так, что процессор загрузится полностью на 100%, и приложение вообще перестанет работать. Казалось бы, мы вообще не потребляем ресурсов процессора: мы делаем какие-то асинхронные операции, дожидаемся ответа с сервера, а процессор у нас всё равно загружен.
Когда мы с этой ситуацией столкнулись, мы сняли дамп памяти с нашего приложения:
~*e!clrstack
System.Threading.Monitor.Enter(System.Object)
System.Threading.TimerQueueTimer.Change(…)
System.Threading.Timer.TimerSetup(…)
System.Threading.Timer..ctor(…)
System.Threading.Tasks.Task.Delay(…)Для анализа дампа мы использовали инструмент WinDbg. Ввели команду, которая показывает stack trace’ы всех managed-потоков, и увидели такой результат. У нас есть очень много потоков в процессе, которые ждут на некотором lock’е. Метод Monitor.Enter — это то, во что разворачивается конструкция lock в C#. Этот lock захватывается внутри классов под названием Timer и TimerQueueTimer. В Timer’ы мы пришли как раз из Task.Delay при попытке их создания. Что получается? При запуске Task.Delay захватывается блокировка внутри TimerQueue.
1.3 Lock convoy
- Много потоков пытаются захватить один lock
- Под lock’ом выполняется мало кода
- Время тратится на синхронизацию потоков, а не на выполнение кода
- Блокируются потоки из тредпула — они не бесконечны
У нас произошёл lock convoy в приложении. Много потоков пытаются захватить один и тот же lock. Под этим lock’ом выполняется довольно мало кода. Ресурсы процессора здесь расходуются не на сам код приложения, а именно на операции по синхронизации потоков между собой на этом lock’е. Надо ещё отметить особенность, связанную с .NET: потоки, которые участвуют в lock convoy, — это потоки из тредпула.
Соответственно, если у нас блокируются потоки из тредпула, они могут закончиться — количество потоков в тредпуле ограничено. Его можно настроить, но при этом верхний предел всё равно есть. После его достижения все тредпульные потоки будут участвовать в lock convoy, и в приложении перестанет выполняться вообще какой-либо код, задействующий тредпул. Это значительно ухудшает ситуацию.
1.4 TimerQueue
- Управляет таймерами в .NET-приложении.
- Таймеры используются в:
— Task.Delay
— CancellationTocken.CancelAfter
— HttpClient
TimerQueue — это некоторый класс, который управляет всеми таймерами в .NET-приложении. Если вы когда-то программировали на WinForms, возможно, вы создавали таймеры вручную. Для тех, кто не знает, что такое таймеры: они используются в Task.Delay (это как раз наш случай), также они используются внутри CancellationToken, в методе CancelAfter. То есть замена Task.Delay на CancellationToken.CancelAfter нам бы никак не помогла. Кроме этого, таймеры используются во многих внутренних классах .NET, например, в HttpClient.
Насколько я знаю, в некоторых реализациях HttpClient handler’ов задействованы таймеры. Даже если вы ими не пользуетесь явно, не запускаете Task.Delay, скорее всего, вы их всё равно так или иначе используете.
Теперь давайте посмотрим на то, как TimerQueue устроен внутри.
- Global state (per-appdomain):
— Double linked list of TimerQueueTimer
— Lock object - Routine, запускающая коллбэки таймеров
- Таймеры не упорядочены по времени срабатывания
- Добавление таймера: O (1) + lock
- Удаление таймера: O (1) + lock
- Запуск таймеров: O (N) + lock
Внутри TimerQueue есть глобальное состояние, это двусвязный список объектов типа TimerQueueTimer. TimerQueueTimer содержит в себе ссылку на другие TimerQueueTimer, на соседние в связном списке, также он содержит время срабатывания таймера и callback, который будет вызван при срабатывании таймера. Этот двусвязный список защищается lock-объектом, как раз тем, на котором в нашем приложении случился lock convoy. Также внутри TimerQueue есть Routine, которая запускает callback’и, привязанные к нашим таймерам.
Таймеры никак не упорядочены по времени срабатывания, вся структура оптимизирована под добавление/удаление новых таймеров. Когда запускается Routine, она пробегается по всему двусвязному списку, выбирает те таймеры, которые должны сработать, и вызывает для них callback’и.
Сложности операции здесь получаются такие. Добавление и удаление таймера происходит за O от единицы, а запуск таймеров происходит за линию. При этом если с алгоритмической сложностью здесь всё приемлемо, есть одна проблема: все эти операции захватывают блокировку, что не очень хорошо.
Какая ситуация может произойти? У нас в TimerQueue скопилось слишком много таймеров, соответственно, когда запускается Routine, она захватывает lock на свою долгую линейную операцию, в это время те, кто пытается запустить или удалить таймеры из TimerQueue, ничего с этим сделать не могут. Из-за этого происходит lock convoy. Эта проблема была исправлена в .NET Core.
Reduce Timer lock contention (coreclr#14527)
- Lock sharding
— Environment.ProcessorCount TimerQueue’s TimerQueueTimer- Separate queues for short/long-living timers
- Short timer: time <= 1/3 second
https://github.com/dotnet/coreclr/issues/14462
https://github.com/dotnet/coreclr/pull/14527
Как её исправили? Расшардили TimerQueue: вместо одной TimerQueue, которая была статической на весь AppDomain, на всё приложение, сделали несколько TimerQueue. Когда туда приходят потоки и пытаются запустить свои таймеры, эти таймеры попадут в случайную TimerQueue, и у потоков будет меньше вероятность столкнуться на одной блокировке.
Также в .NET Core применили некоторые оптимизации. Разделили таймеры на долгоживущие и короткоживущие, для них теперь используются отдельные TimerQueue. Время короткоживущего таймера выбрали меньше ⅓ секунды. Не знаю, почему именно такую константу выбрали. В .NET Core проблемы с таймерами нам поймать никак не удалось.
https://github.com/Microsoft/dotnet-framework-early-access/blob/master/release-notes/NET48/dotnet-48-changes.md
https://github.com/dotnet/coreclr/labels/netfx-port-consider
Этот фикс бэкпортнули в .NET Framework, в версию 4.8. Выше в ссылке указан тег netfx-port-consider, если зайдёте в репозиторий .NET Core, CoreCLR, CoreFX, по этому тегу можете поискать issue, которые будут бэкпортиться в .NET Framework, сейчас их там порядка пятидесяти. То есть опенсорс .NET сильно помог, довольно много багов было исправлено. Можете почитать changelog .NET Framework 4.8: исправлено очень много багов, гораздо больше, чем в других релизах .NET. Что интересно, этот фикс по умолчанию в .NET Framework 4.8 выключен. Он включается во всем вам известном файле под названием App.config
Настройка в App.config, которая включает этот фикс, называется UseNetCoreTimer. До того, как вышел .NET Framework 4.8, чтобы наше приложение работало и не уходило в lock convoy, приходилось использовать свою реализацию Task.Delay. В ней мы попробовали использовать бинарную кучу, чтобы более эффективно понимать, какие таймеры нужно сейчас вызывать.
1.5 Task.Delay: собственная реализация
- BinaryHeap
- Sharding
- Помогло, но не во всех случаях
Использование бинарной кучи позволяет оптимизировать Routine, которая вызывает callback’и, но ухудшает время удаления произвольного таймера из очереди — для этого нужно перестраивать кучу. Скорее всего, именно поэтому в .NET используется двусвязный список. Конечно, только лишь использование бинарной кучи нам здесь бы не помогло, также пришлось расшардить TimerQueue. Это решение какое-то время работало, но потом всё равно всё снова упало в lock convoy из-за того, что таймеры используются не только там, где они запускаются в коде явно, но и в сторонних библиотеках и коде .NET. Чтобы полностью исправить эту проблему, необходимо обновиться до .NET Framework версии 4.8 и включить фикс от разработчиков .NET.
1.6 Task.Delay: выводы
- Подводные камни везде — даже в самых используемых вещах
- Проводите нагрузочное тестирование
- Переходите на Core, получайте багфиксы (и новые баги) первыми :)
Какие выводы из всей этой истории? Во-первых, подводные камни могут находиться реально везде, даже в тех классах, которые вы используете каждый день, не задумываясь, например, те же Task’и, Task.Delay.
Рекомендую проводить нагрузочное тестирование ваших предложений. Вот эту проблему мы как раз выявили ещё на этапе нагрузочного тестирования. Она у нас потом ещё несколько раз выстрелила на продакшне в других приложениях, но, тем не менее нагрузочное тестирование нам помогло отдалить время до того, как мы столкнулись с этой проблемой в реальности.
Переходите на .NET Core — вы будете получать исправления багов (и новые баги) самыми первыми. Куда же без новых багов?
На этом история про таймеры закончилась, и мы переходим к следующей.
История 2: SemaphoreSlim
Следующая история про широко известный SemaphoreSlim.
2.1 Серверный троттлинг
- Требуется ограничить число параллельно обрабатываемых запросов на сервере
Мы хотели реализовать троттлинг на сервере. Что это такое? Наверное, вы все знаете троттлинг по CPU: когда процессор перегревается, он сам снижает свою частоту, чтобы охладиться, и у него за счет этого ограничивается производительность. Так же и здесь. Мы знаем, что наш сервер умеет обрабатывать параллельно N запросов и не падать при этом. Что мы хотим сделать? Ограничить количество одновременно обрабатываемых запросов этой константой и сделать так, что, если к нему приходит больше запросов, они встают в очередь и ждут, пока выполнятся те запросы, которые пришли раньше. Как эту задачу можно решать? Надо использовать какой-то примитив синхронизации.
Semaphore — примитив синхронизации, на котором можно подождать N раз, после чего тот, кто придёт N + первым и так далее, будет ждать на нём, пока Semaphore не освободят те, кто зашли под него раньше. Получается примерно вот такая картина: два потока выполнения, два воркера прошли под Semaphore, остальные — встали в очередь.
Конечно, просто Semaphore нам не очень подойдёт, он в .NET синхронный, поэтому мы взяли SemaphoreSlim и написали такой код:
var semaphore = new SemaphoreSlim(N);
…
await semaphore.WaitAsync();
await HandleRequestAsync(request);
semaphore.Release();Создаём SemaphoreSlim, ждём на нём, под Semaphore обрабатываем ваш запрос, после этого Semaphore освобождаем. Казалось бы, это идеальная реализация серверного троттлинга, и лучше быть уже не может. Но всё гораздо сложнее.
2.2 Серверный троттлинг: усложнение
- Обработка запросов в LIFO порядке
- SemaphoreSlim
- ConcurrentStack
- TaskCompletionSource
Мы немного забыли про бизнес-логику. Запросы, которые приходят на троттлинг, являются реальными http-запросами. У них есть, как правило, некоторый таймаут, который задан тем, кто отправил этот запрос автоматически, или таймаут пользователя, который нажмёт F5 через какое-то время. Соответственно, если обрабатывать запросы в порядке очереди, как обычный Semaphore, то в первую очередь будут обрабатываться те запросы из очереди, у которых таймаут, возможно, уже истёк. Если же работать в порядке стека — обрабатывать в первую очередь те запросы, которые пришли самыми последними, такой проблемы не возникнет.
Кроме SemaphoreSlim нам пришлось использовать ConcurrentStack, TaskCompletionSource, навернуть очень много кода вокруг всего этого, чтобы всё работало в том порядке, как нам нужно. TaskCompletionSource — это такая штука, которая похожа на CancellationTokenSource, только не для CancellationToken, а для Task’а. Вы можете создать TaskCompletionSource, вытащить из него Task, отдать его наружу и потом сказать TaskCompletionSource, что надо выставить результат этому Task’у, и об этом результате узнают те, кто на этом Task’е ждёт.
Мы всё это реализовали. Код получился ужасным. и, что хуже всего, он оказался нерабочим.
Спустя несколько месяцев с начала его использования в довольно высоконагруженном приложении мы столкнулись с проблемой. Точно так же, как и в предыдущем случае, возросло потребление CPU до 100%. Мы проделали аналогичные действия, сняли дамп, посмотрели его в WinDbg, и снова обнаружили lock convoy.
В этот раз Lock convoy произошёл внутри SemaphoreSlim.WaitAsync и SemaphoreSlim.Release. Выяснилось, что внутри SemaphoreSlim есть блокировка, он не lock-free. Это оказалось для нас довольно серьезным недостатком.
Внутри SemaphoreSlim есть внутреннее состояние (счётчик того, сколько под него ещё могут пройти воркеров), и двусвязный список тех, кто на этом Semaphore ждёт. Идеи здесь примерно такие же: можно подождать на этом Semaphore, можно отменить своё ожидание — удалиться из этой очереди. Есть блокировка, которая как раз нам жизнь и попортила.
Мы решили: долой весь ужасный код, который нам пришлось написать.
Давайте напишем свой Semaphore, который сразу будет lock-free и который будет сразу работать в порядке стека. Отмена ожидания при этом нам не важна.
Определим данное состояние. Здесь будет число currentCount — это сколько ещё мест осталось в Semaphore. Если мест в Semaphore не осталось, то это число будет отрицательным и будет показывать, сколько воркеров находится в очереди. Также будет ConcurrentStack, состоящий из TaskCompletionSource’ов — это как раз стек waiter’ов, из которых они при необходимости будут вытаскиваться. Напишем метод WaitAsync.
var decrementedCount = Interlocked.Decrement(ref currentCount);
if (decrementedCount >= 0)
return Task.CompletedTask;
var waiter = new TaskCompletionSource,bool>();
waiters.Push(waiter);
return waiter.Task;Сначала мы уменьшаем счётчик, забираем себе одно место в Semaphore, если у нас были свободные места, и потом говорим: «Всё, ты прошёл под Semaphore».
Если мест в Semaphore не было, мы создаём TaskCompletionSource, кидаем его в стек waiter’ов и возвращаем во внешний мир Task’у. Когда придёт время, эта Task’а отработает, и воркер сможет продолжить свою работу и пройдёт под Semaphore.
Теперь напишем метод Release.
var countBefore = Interlocked.Increment(ref currentCount) - 1;
if (countBefore < 0)
{
if (waiters.TryPop(out var waiter))
waiter.TrySetResult(true);
}Метод Release выглядит следующим образом:
- Освобождаем одно место в Semaphore
- Инкрементим currentCount
Если по currentCount можно сказать, есть ли внутри стека waiter’ы, о которых нужно сигнализировать, мы такие waiter’а вытаскиваем из стека и сигнализируем. Здесь waiter — это TaskCompletionSource. Вопрос к этому коду: он вроде бы логичный, но он вообще работает? Какие здесь есть проблемы? Есть нюанс, связанный с тем, где запускаются continuation’ы и TaskCompletionSource’ы.
Рассмотрим этот код. Мы создали TaskCompletionSource и запустили два Task’а. Первый Task выводит единицу, выставляет результат в TaskCompletionSource, а дальше выводит на консоль двойку. Второй Task ждёт на этом TaskCompletionSource, на его Task’е, а затем навсегда блокирует свой поток из тредпула.
Что здесь произойдёт? Task 2 при компиляции разделится на два метода, второй из которых — continuation, содержащий Thread.Sleep. После выставления результата TaskCompletionSource, этот continuation выполнится в том же потоке, в котором выполнялся первый Task. Соответственно, поток первого Task’а будет навсегда заблокирован, и двойка на консоль уже не напечатается.
Что интересно, я пробовал поменять этот код, и если я убирал вывод на консоль единицы, continuation запускался на другом потоке из тредпула и двойка печаталась. В каких случаях continuation будет выполнен в том же потоке, а в каких — попадёт на тредпул — вопрос для читателей.
var tcs = new TaskCompletionSource(
TaskCreationOptions.RunContinuationsAsynchronously);
/* OR */
Task.Run(() => tcs.TrySetResult(true)); Для решения этой проблемы мы можем либо создавать TaskCompletionSource с соответствующим флагом RunContinuationsAsynchronously, либо вызывать метод TrySetResult внутри Task.Run/ThreadPool.QueueUserWorkItem, чтобы он выполнялся не на нашем потоке. Если он будет выполняться на нашем потоке, у нас могут возникнуть нежелательные side effect’ы. Вдобавок здесь есть вторая проблема, остановимся на ней подробнее.
Посмотрите на методы WaitAsync и Release и попробуйте найти в методе Release ещё одну проблему.
Скорее всего, найти ее так просто невозможно. Здесь есть гонка.
Она связана с тем, что в методе WaitAsync изменение состояния не атомарно. Вначале мы декрементим счётчик и только потом пушим waiter’а на стек. Если так получится, что Release выполнится между декрементом и пушем, то может выйти так, что он ничего не вытащит из стека. Это нужно учесть, и в методе Release дожидаться появления waiter’а в стеке.
var countBefore = Interlocked.Increment(ref currentCount) - 1;
if (countBefore < 0)
{
Waiter waiter;
var spinner = new SpinWait();
while (!waiter.TryPop(out waiter))
spinner.SpinOnce();
waiter.TrySetResult(true);
}Здесь мы это делаем в цикле, пока у нас не получается его вытащить. Чтобы лишний раз не тратить циклы процессора, мы используем SpinWait.
В первые несколько итераций он будет крутиться по циклу. Если итераций станет много, waiter долго не будет появляться, то наш поток уйдет в Thread.Sleep, чтобы лишний раз не расходовать ресурсы CPU.
На самом деле, Semaphore с LIFO-порядком — это не только наша идея.
LowLevelLifoSemaphore
- Синхронный
- На Windows использует в качестве стека Windows IO Completion port
https://github.com/dotnet/corert/blob/master/src/System.Private.CoreLib/src/System/Threading/LowLevelLifoSemaphore.cs
Такой Semaphore есть в самом .NET, но не в CoreCLR, не в CoreFX, а в CoreRT. Иногда бывает довольно полезно заглядывать в репозитории .NET. Здесь есть Semaphore под названием LowLevelLifoSemaphore. Этот Semaphore нам бы всё равно не подошёл: он синхронный.
Что примечательно, на Windows он работает через IO Completion-порты. У них есть свойство, что на них могут ждать потоки, и эти потоки будут релизиться как раз в LIFO-порядке. Эта особенность там используется, он действительно LowLevel.
2.3 Выводы:
- Не надейтесь, что начинка фреймворка выживет под вашей нагрузкой
- Проще решать конкретную задачу, чем общий случай
- Нагрузочное тестирование помогает не всегда
- Опасайтесь блокировок
Какие выводы из всей этой истории? Во-первых, не надейтесь, что какие-то классы из фреймворка, которые вы используете из стандартной библиотеки, справятся с вашей нагрузкой. Я не хочу сказать, что SemaphoreSlim плохой, просто он оказался неподходящим конкретно в данном сценарии.
Нам оказалась гораздо проще написать свой Semaphore для конкретной задачи. Например, он не поддерживает отмену ожидания. Эта возможность есть в обычном SemaphoreSlim, у нас её нет, но это позволило упростить код.
Нагрузочное тестирование, хоть оно и помогает, может помочь далеко не всегда.
.NET известен тем, что у него довольно часто в неожиданных местах есть блокировки — их лучше опасаться. Если в своём коде вы пишете конструкцию lock, лучше задуматься: «Какая реально здесь будет нагрузка?» И если вдруг потребление CPU 100%, все потоки стоят на lock’е, то, возможно, это происходит где-то внутри .NET. Просто имейте в виду такую возможность.
Переходим к следующей истории.
История 3: (A)sync IO
История про асинхронный ввод/вывод, который оказался не таким уж асинхронным.
Здесь также случился lock convoy, он произошёл по stack trace внутри класса под названием Overlapped и PinnableBufferCache. Там оказался lock. Что же это за классы: Overlapped и PinnableBufferCache?
OVERLAPPED — это структура в Windows, которая используется для всех операций ввода/вывода. У нас было довольно нагруженное приложение, это один из шардов нашей распределённой файловой системы. Он много работает и с файлами на диске, и сетью. И таких структур ему понадобилось очень много, вследствие этого и выявился lock convoy. Мы стали разбираться, в чём вообще причина этого lock convoy, почему раньше всё работало, а сейчас перестало.
Надо заметить, что эта история произошла уже довольно давно, во времена .NET 4.5.1 и 4.5.2. Тогда как раз вышел .NET 4.5.2, и отличие оказалось в изменениях, которые появились в .NET 4.5.2. В .NET 4.5.1 был класс под названием OverlappedDataCache, представлявший собой пул этих объектов Overlapped — действительно, зачем их создавать на каждую асинхронную операцию, проще сделать пул. Этот пул был хороший, был lock-free, основанный на ConcurrentStack, и с ним не возникало никаких проблем. В .NET 4.5.2 решили оптимизировать пуллинг этих объектов: убрали OverlappedDataCache и сделали PinnableBufferCache.
В чём отличие? PinnableBufferCache сделан с расчётом на то, что объекты Overlapped нужно передавать в нативный код, при этом объекты пиннятся, а пиннить объекты в младших поколениях — это дополнительная нагрузка на сборщик мусора. Соответственно, наружу бы неплохо отдавать объекты, которые уже попали во второе поколение. PinnableBufferCache был разбит на две части. Первая часть хорошая, lock-free, основанная на ConcurrentStack. Она предназначена для тех объектов, которые уже попали во второе поколение. Внутри этого пула есть вторая часть для объектов, которые ещё находятся в нулевом и первом поколении, и почему-то для них вместо lock-free структуры используется обычный list с lock’ом.
3.1 PinnableBufferCache
LockConvoy:
- Если закончились буферы
- При возврате объектов в пул
Здесь lock convoy происходил тогда, когда заканчивались буфер-объекты и нужно было создавать новые. В таком случае они попадают в плохой list при возврате этих объектов в пул, поскольку при возврате объектов lock захватывается для того, чтобы проверить, а не пора ли объекты из пула для нулевого и первого поколения переносить во второе поколение.
Мы стали изучать код PinnableBufferCache и обнаружили, что в нём есть обращение к недокументированной переменной окружения. Она называлась вот так:
PinnableBufferCache_System.ThreadingOverlappedData_MinCount
Эта переменная позволяла задать количество объектов, которые будут находиться в пуле изначально. Мы решили: «Отличная возможность! Давайте ей воспользуемся и поставим в эту переменную какое-нибудь большое число». Теперь у нас в приложении появился вот такой вуду-код:
Environment.SetEnvironmentVariable(
"PinnableBufferCache_System.Threading.OverlappedData_MinCount", :10000”);
new Overlapped().GetHashCode();
for (int i = 0; i < 3; i++)
GC.Collect(GC.MaxGeneration, GCCollectionMode.Forced);Что мы здесь делаем? Мы вначале выставляем переменную окружения, затем создаём объект Overlapped для того, чтобы пул инициализировался, а затем несколько раз вручную вызываем сборку мусора. Сборка мусора вызывается для того, чтобы все объекты, которые находятся в этом пуле, попали уже во второе поколение, и PinnableBufferCache от нас отстал со своим lock convoy’ем. Это решение оказалось рабочим, и оно до сих пор живо в нашем коде для фреймворка.
На .NET Core от PinnableBufferCache избавились тем, что перенесли OverlappedData в нативную память. Соответственно, пиннинг их в памяти уже стал не нужен, Garbage collector их никуда передвинуть не может, так как они в нативной памяти. На этом история в .NET Core и закончилась. В .NET Framework, если не ошибаюсь, ещё этот фикс не перенесли.
3.2 Выводы:
- Не все оптимизации одинаково полезны
- На этот раз просто повезло
- И снова .NET Core
Здесь явно хотели сделать как лучше, уменьшив нагрузку на сборщик мусора. Нам очень повезло, что разработчиками .NET была предусмотрена возможность задать минимальное количество объектов для этого пула через переменную, иначе нам бы пришлось писать хак пострашнее. И, опять же, попробуйте .NET Core. Возможно, это решит ваши перформансные проблемы, и вам даже не придётся для этого писать вуду-код.
Теперь перейдём к key-value коллекциям.
История 4: Concurrent key-value collections
В .NET есть несколько concurrent-коллекций. Это lock-free коллекции ConcurrentStack и ConcurrentQueuе, с которыми у нас не возникало проблем. Есть коллекция ConcurrentDictionary, с ней всё интереснее. Она не lock-free на запись, там есть блокировки, но сейчас речь не о них. Почему вообще используют ConcurrentDictionary?
4.1 ConcurrentDictionary
Применения:
- Кэш
- Индекс
Плюсы:
- Входит в стандартную библиотеку
- Удобные операции (TryAdd/TryUpdate/AddOrUpdate)
- Lock-free чтения
- Lock-free enumeration
Его часто используют под различные кэши, memory-индексы, прочие структуры, в которые нужно уметь обращаться из нескольких потоков. Его любят за то, что он абсолютно стандартный, есть даже в .NET Framework. У него есть довольно удобные операции именно для работы из нескольких потоков. И, что важно, у него чтение и перечисление (enumeration) lock-free. Конечно, есть и подвохи.
Давайте рассмотрим, как устроена коллекция, основанная на хэш-таблице в .NET. Большинство key-value коллекций основано на хэш-таблицах и выглядят примерно так:
Вычисляется хэш-код, берётся по модулю количество bucket’ов. В самой коллекции есть несколько bucket’ов, в которых хранятся элементы. Если происходит коллизия, то в один bucket попадает несколько элементов, связанных между собой по принципу связанного списка.
Здесь каждый квадрат — это отдельный объект, почти ConcurrentDictionary. В ConcurrentDictionary на каждую пару «ключ-значение» создаётся отдельный объект. Причем при замене значений, если сами значения больше определённого размера, они постоянно пересоздаются, и от этого возникает ещё и memory traffic. Чтобы это был совсем ConcurrentDictionary, я нарисовал lock’и. Один квадрат — это один объект.
Теперь посмотрим на то, как устроен обычный Dictionary.
Обычный Dictionary устроен похитрее, чем Concurrent, но он более компактный по памяти. В нём есть два массива: массив buckets, массив entries. В массиве buckets находится индекс первого элемента в этом bucket’е в массиве entries. Все пары «ключ-значение» хранятся в массиве entries. Связные списки здесь организованы через ссылки на индексы в массиве. То есть дополнительно с парой «ключ-значение» хранится число int, индекс следующего элемента в bucket’е.
Давайте сравним memory overhead, который возникает при использовании ConcurrentDictionary и обычного Dictionary.
Начнём с обычного Dictionary. Memory overhea’ом я называю здесь всё, что не является самими ключами и значениями. В случае обычного Dictionary этот overhead составляет хэш-код и индекс следующего элемента, два int’а. Это 8 байт.
Теперь посмотрим на ConcurrentDictionary. В ConcurrentDictionary элемент хранится внутри объекта ConcurrentDictionary.Node. Это именно объект, класс. В этом классе находятся int hashCode и ссылка на следующий объект в связном списке. То есть у нас есть заголовки объекта, ссылка на метод table (это уже 16 байт), есть int hashCode и есть ссылка на объект. Если я не перепутал никакие размеры, то на 64-битной платформе это будет 28 байт overhead’а. Довольно много по сравнению с обычным Dictionary.
Кроме memory overhead’а, ConcurrentDictionary способен создавать нагрузку на GC за счёт того, что в нём есть очень много объектов. Я написал очень простой Benchmark. Я создаю ConcurrentDictionary определённого размера, а дальше замеряю время работы метода GC.Collect. Что же я получил?
Я получил вот такие результаты. Если у нас в процессе есть ConcurrentDictionary размером 10 млн элементов, то сборка мусора на моём компьютере занимает полсекунды, на сервере при этом эти полсекунды вполне могут уже превратиться в несколько секунд, что уже может быть довольно неприемлемо. С обычным Dictionary такого не происходит. Сколько элементов в него ни клади, там обычные массивы, два объекта, и всё очень хорошо. На время работы сборщика мусора не влияет.
Как можно справиться с проблемами, которые возникают при использовании ConcurrentDictionary?
4.2 Простые решения
- Ограничение на размер
- TTL
- Dictionary+lock
- Sharding
Давайте разберём простые эффективные решения. Мы можем ограничить размер нашего ConcurrentDictionary. Вряд ли нам нужно держать кэш на 10 миллионов элементов. Можно держать тысячу, и никаких проблем не будет. Можно сделать TTL для элементов, и периодически их вычищать. В некоторых случаях довольно эффективно использовать обычный Dictionary с lock’ом. Естественно, надо убедиться, что lock здесь не ухудшит производительность. Можно развить этот подход и расшардировать Dictionary с lock’ом самостоятельно перед размещением элементов по словарям, по некоторому хэш-коду раскладывать их в несколько словарей, тогда мы не будем конкурировать за один и тот же lock. Но при этом иногда бывает так, что простые решения не работают.
4.3 Индекс
- Нужно хранить in-memory индекс
- В индексе >106 элементов
- Постоянно происходят редкие чтения из нескольких потоков
- Записи редкие
- Нужно уметь перечислять все элементы в коллекции
Мы столкнулись с подобной ситуацией. У нас очень важное приложение — это мастер нашей распределённой файловой системы, и ему нужно хранить в памяти in-memory индекс из Guid’а в Guid, помнить расположение файлов на серверах. В этом индекс
