Сказка про Guid.NewGuid()

C#. Guid.NewGuid(). Linux. Windows. Randomness or Uniqueness. RNG and PRNG. Performance. Benchmarking.

Цель нашей сегодняшней сказки — развлечься как следует. Детективная история в поисках потерянного перфоманса с красивым финалом и эффектным результатом непосредственно связана с набором слов из предыдущего абзаца.

Художественное отступление, шутка на текущую тему. Читать совершенно не обязательно.

— О, Tux, давно не виделись! — Con, широко улыбаясь, выглядывал из распахнутого окна.

— Здравствуй, Con! Вот, вернулся ненадолго. Как дела, как жизнь?

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

— Знаешь, Con, я толком понять не успел. Жильё бесплатное. Но обустраивать самому приходится. В целом, всё также. И одновременно всё не так… точно могу сказать, что переезжать было не просто. Тосковал по старому дому, привыкал к новому климату. От некоторых старых вещей пришлось избавляться, потому что нельзя с ними переезжать. Ещё, точно могу сказать, что жить там тяжелее. Как будто на само существование нужно тратить больше сил, больше внутренних ресурсов.

Tux на секунду задумался. Но быстро спохватился и увлеченно продолжил говорить.

— А недавно я заметил вообще интересную вещь! Я стал очень много времени проводить в придумывании уникальных имен всяким своим штукам. Не знаю почему. Раньше раз, и выдумывалось быстро. А сейчас, как только пытаюсь дать уникальный идентификатор чему-нибудь, так сразу зависаю надолго.

— Во дела.. а чего ты именно туда-то поехал, а, Tux?

— Да просто. Пингвинов хотел посмотреть, очень их люблю.

Каждый раз, когда мы хотим выдумать уникальный идентификатор для какой-нибудь сущности, чтобы она уж точно не была ни на что не похожей, первым в голову приходит Guid. Или, если назвать его имя полностью, Globally Unique Identifier.

Guid — это конкретная реализация стандарта UUID (Universally Unique Identifier).

Guid — это «случайные» 128 бит. Или, 2^128 вариантов (на самом деле чуточку меньше, там есть зарезервированные биты). Это ОЧЕНЬ много. Вероятность сгенерировать два одинаковых Guid'а невероятно мала. Настолько мала, что все условились считать их уникальными.

Guid — это не про security, это про uniqueness. То есть его не стоит использовать для криптографических целей или даже для генерации паролей. Хотя, нам повезло и на Windows (и даже на Linux) по факту прямо сейчас нам дают 122 бит энтропии. И вроде даже обещают не ломать это в будущем (в том же XML документе).

Guid — весьма интересная штука. И продолжать накидывать про неё фактов можно очень долго.

Дело было вечером, делать было нечего

Как-то раз ковырялись в трейсах приложений в поисках ответа на вопрос «почему один и тот же код на Линуксе потребляет в полтора раза больше CPU, чем на Винде». Помимо прочего, в глаза бросалась большая разница во времени, проведённом приложением внутри функции Guid.NewGuid(). На Линуксе оно занимало аж 5.4% от всего времени работы приложения. А на Винде сильно меньше. Вот скриншот PerfView, на котором видно функцию генерации гуида:

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

Почему употребляется термин время, а не CPU?

Средства анализа .NET приложений показывают несколько разную картину в зависимости от ОС, на которой было запущено само приложение. Так, большинство CPU работы, проведённой внутри ОС Linux, неотличимы от всяческих ожиданий при изучении приложения с помощью PerfView. Например, Thread.Sleep() будет неотличим от CPU-bound функции в .nettrace артефактах.

Такие трейсы, снятые на Linux, померили нам время, проведённое всеми тредами приложения в этих стеках. Вне зависимости от того, работал ли CPU внутри этого стека. И в данный момент они попадают в категорию «UNMANAGED_CODE_TIME». В «CPU_TIME» находится только наш managed C# код.

На данный момент, на мой взгляд, на Windows дела со снятием и анализом трейсов обстоят несколько лучше.

Изучаем Guid.NewGuid()

Не то чтобы медленный Guid.NewGuid() был основной причиной нашей проблемы. Было очевидно, что разница в нескольких процентах от всего приложения — это не то, что мы ищем, расследуя разницу в полтора раза. Но всё-таки было интересно, что такого особенного в генерации гуида и откуда такая разница в зависимости от ОС.

Чтобы это выяснить, мы соорудили предельно простой бенчмарк одной функции: Guid.NewGuid(). Запустили на Windows и на Linux (Centos 7) на виртуалках одинаковой конфигурации.

Это важно!

Запускать в каком-нибудь WSL было бы неправильно. Это всё-таки эмулятор (на самом деле далеко нет, но такому бенчмарку доверять всё равно было бы нельзя). А процессоры машин разработчиков это не процессоры на проде.

Результат подтвердил то, что мы видели в трейсах:

Linux:
|              Method |        Mean | Allocated |
|-------------------- |------------:|----------:|
|         GuidNewGuid | 1,293.91 ns |         - |

Windows:
|              Method |     Mean | Allocated |
|-------------------- |---------:|----------:|
|         GuidNewGuid | 80.71 ns |         - |

// Колонка Allocated с прочерком оставлена намерено.
// Это значит, что при генеарции Гуида ничего не аллоцируется на хипе.
// Что прекрасно.

Извините, скриншоты потерялись, остались лишь текстовые представления

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

Разница просто колоссальная. Создание Guid'а на Линуксе в 16 раз медленнее, чем на Винде! Давайте разбираться, почему так.

Разбираемся

Хочется заглянуть внутрь реализации и посмотреть, что же там такого интересного. Раз производительность зависит от ОС, доверять декомпиляции метода Guid.NewGuid() на своей рабочей машине неправильно. Отправляемся на гитхаб, где можно найти исходники. Находим там два файла с кусочками partial class'ов: Guid.Unix.cs и Guid.Windows.cs.

Кстати, сразу видим интересный комментарий, что генерация Guid'а на Linux'е намеренно пользуется криптографически стойким генератором случайных чисел. Как и в Windows. Но генерация гуида это всё ещё не рекомендуемый способ придумывать «действительно» криптостойкие ключи. Как минимум потому, что в нём есть один предсказуемый бит версии, а утечка хотя бы одного бита информации может быть фатальной.

Linux

Если раскапывать цепочку системных вызовов в случае Linux ветки, можно докопаться до вот такого кода на C. Если кратко, то мы читаем случайные байты из /dev/urandom. Несмотря на то, что в man /dev/urandom говорится, что его не стоит использовать в криптографических целях, это не так. Исключения составляют, кажется, первые мгновения жизни Linux системы, когда генератор шумов ещё не набрал нужный уровень «случайности» (я не умею это доказывать и не имею ссылки на авторитетный источник).

Информация актуальна на момент написания статьи.

Если покопаться в истории коммитов, то там было множество различных вариантов реализации. Например, какое-то время случайные числа брались из /dev/random. Это генератор «действительно» случайных чисел из шумов процессора (RNG), однопоточный и блокирующий вызовы до тех пор, пока не накопится достаточно «случайности».

Также в истории коммитов можно найти, как добавлялись реализации для Apple, или как чинят билды под ARM. Всё-таки, как удобно иметь платформу, которая прячет от тебя весь этот кошмар в различиях операционных систем и даже архитектур.

Windows

Если кратко говорить про Windows, то тут мы пользуемся функцией CoCreateGuid, которая просто перевызывает RPC функцию UuidCreate. А она, в свою очередь, перевызывает генератор случайных чисел CryptGenRandom (или RtlGenRandom в каких-то очень старых версиях). Дальше и подробнее что-то рассказать сложно, потому что, кажется, те исходники, что я нашел в интернете, получены не самым честным путём.

Дак что в итоге?

Судя по ответам на гитхабе, цепочка вызовов на Windows просто быстрее, чем рассмотренное нами выше чтение из /dev/urandom на Linux, поскольку несет в себе меньше оверхеда на всякие системные штуки. Печально.

Как можно обойти эту нелепую ситуацию?

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

Vostok.Tracing - библиотека, имя которой говорит за себя. Она создаёт трейсы, а метод BeginSpan создаёт спаны. Аналогичные тем, что можно увидеть, например, в opentelementry. Vostok.Hercules.Client - библиотека, вспомогательная к сбору этой телеметрии.

В телеметрии нам уж точно не нужна криптостойкость. Нам просто хочется, чтобы гуиды редко совпадали. И кажется, что можно попробовать взять быстрый и простой псевдослучайный генератор случайных чисел (PRNG) и с помощью него создавать гуиды. В C# уже есть Random, генератор псевдослучайных чисел. Давайте его и попробуем.

Что такое гуид? 16 байт. Random предназначен для того, чтобы генерировать int, то есть 4 байта. Давайте вызовем Random.Next() 4 раза и соберем из них Guid. Даже не будем выставлять нужные битики, как того требует RFC, кому они нужны. И ещё, да, мы потеряем целых 4 бита на знаковых битах int'а, поскольку Random генерирует только положительные числа. Из 128 бит осталось 124 псевдослучайных. Этого уж точно хватит на нашу телеметрию.

Вспомним про многопоточность, ведь гуиды для телеметрии могут создаваться параллельно во всех потоках, а Random не потокобезопасный. Чтобы очень быстро и просто защититься от гонок, навесим на наш инстанс класса Random атрибут ThreadStatic. Крайне не рекоммендую слепо использовать этот атрибут в каждом месте. Он далеко не универсален и со своими недостатками. Просто здесь он пришелся очень кстати.

Реализация и снова бенчмарки

internal static class ThreadSafeRandom
{
    [ThreadStatic]
    private static Random random;
    
    public static int Next()
    {
        return ObtainRandom().Next();
    }

    private static Random ObtainRandom()
    {
        return random ?? (random = new Random(Guid.NewGuid().GetHashCode()));
    }
}

internal static class GuidGenerator
{
    public static unsafe Guid GuidRandom()
    {
        var bytes = stackalloc byte[16];
        var dst = bytes;
        for (var i = 0; i < 4; i++)
        {
            *(int*)dst = ThreadSafeRandom.Next();
            dst += 4;
        }

        return *(Guid*)bytes;
    }
}

Снова запускаем наш бенчмарк, смотрим, что получилось:

Linux:
|              Method |        Mean | Allocated |
|-------------------- |------------:|----------:|
|         GuidNewGuid | 1,293.91 ns |         - |
|          GuidRandom |   108.66 ns |         - |

Windows:
|              Method |     Mean | Allocated |
|-------------------- |---------:|----------:|
|         GuidNewGuid | 80.71 ns |         - |
|          GuidRandom | 79.96 ns |         - |

Отлично! Теперь мы умеем генерировать «Guid» на Linux почти так же быстро, как на Windows! Смущает разве что следующее. Используя метод Guid.NewGuid() на Windows, мы обращаемся в winapi, используем криптостойкий генератор случайных чисел, и вообще делаем interop за пределы .NET'а. А наш метод — чистый managed код. И работает с такой же позорной скоростью.

Нетрудно догадаться, на что потратилось много времени. Чтобы сгенерировать 16 байт нам нужно 4 раза вызвать Next(). А значит 4 раза обратиться к ThreadStatic полю. И доступ к ThreadStatic полю, очевидно, дорогой. Воспользуемся некоторыми знаниями устройства тредпула и работы потоков, чтобы обойти это.

Мы делаем 4 обращения к полю random в цикле. Это целиком и полностью синхронный код. Значит между итерациями цикла не может быть context switch'ей (на уровне .NET'а). А значит ThreadID всегда будет одинаковый. А значит мы все 4 раза будем доставать за дорого один и тот же инстанс класса Random. Дак давайте достанем его один раз.

internal static class ThreadSafeRandom
{
    [ThreadStatic]
    private static Random random;
    
    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public static Random ObtainThreadStaticRandom() => ObtainRandom();

    private static Random ObtainRandom()
    {
        return random ?? (random = new Random(Guid.NewGuid().GetHashCode()));
    }
}

internal static class GuidGenerator
{
    public static unsafe Guid GuidRandomCachedInstance()
    {
        var bytes = stackalloc byte[16];
        var dst = bytes;
      
        var random = ThreadSafeRandom.ObtainThreadStaticRandom();
        for (var i = 0; i < 4; i++)
        {
            *(int*)dst = random.Next();
            dst += 4;
        }
    
        return *(Guid*)bytes;
    }
}

Снова запускаем наш бенчмарк. Для сравнения запустим и старую и новую версию нашего собственного генератора Guid'ов.

Linux:
|                   Method |        Mean | Allocated |
|------------------------- |------------:|----------:|
|              GuidNewGuid | 1,293.91 ns |         - |
|               GuidRandom |   108.66 ns |         - |
| GuidRandomCachedInstance |    56.45 ns |         - |

Windows:
|                   Method |     Mean | Allocated |
|------------------------- |---------:|----------:|
|              GuidNewGuid | 80.71 ns |         - |
|               GuidRandom | 79.96 ns |         - |
| GuidRandomCachedInstance | 43.73 ns |         - |

Чудесно. Мы умеем генерировать не-криптостойкий «Guid» за 31 строчку кода. Который на Windows быстрее встроенного Guid.NewGuid() в ~2 раза. А на Linux быстрее встроенного Guid.NewGuid() в ~23 раза!

А можно ещё лучше?

Предложенная выше реализация справедлива для Netstandard2.0. Всё-таки, поддерживать старые проекты под .NET FW нужно, не все из них обновлены до современных версий .NET. Но, к счастью, мы можем писать код так, чтобы под свежей версией .NET использовался другой код. А в .NET 6 как раз появилось несколько полезных вещей.

Воспользуемся сразу двумя фичами .NET 6. Во-первых, появился специализированный Random.Shared. Больше не нужно извращаться с атрибутом [ThreadStatic]. Теперь код нашего ThreadSafeRandom можно написать так (или, при желании, вообще от него избавиться):

internal static class ThreadSafeRandom
{
#if NET6_0_OR_GREATER
#else
    [ThreadStatic]
    private static Random random;
#endif

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public static Random ObtainThreadStaticRandom() => ObtainRandom();

    private static Random ObtainRandom()
    {
#if NET6_0_OR_GREATER
            return Random.Shared;
#else
            return random ?? (random = new Random(Guid.NewGuid().GetHashCode()));
#endif
    }
}

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

В .NET 6 есть способы генерировать куда больше случайных байт за один вызов, чем 4. А именно, появился NextInt64(). А в паре с ним появился и NextBytes(Span<byte> buffer). Незамедлительно ими воспользуемся. Приведу пример только с NextBytes:

internal static class GuidGenerator
{
    public static unsafe Guid GenerateNotCryptoQualityGuid()
    {
        var bytes = stackalloc byte[16];
        var dst = bytes;

        var random = ThreadSafeRandom.ObtainThreadStaticRandom();

#if NET6_0_OR_GREATER
        random.NextBytes(new Span<byte>(bytes, 16));
#else
        for (var i = 0; i < 4; i++)
        {
            *(int*)dst = random.Next();
            dst += 4;
        }
#endif

            return *(Guid*)bytes;
        }
    }
}

Давайте проверим, стало ли лучше? Снова запустим бенчмарк.

Linux:
|        Method |            Runtime |        Mean |
|-------------- |------------------- |------------:|
|   GuidNewGuid |           .NET 6.0 | 1,274.87 ns |
| GenerateInt32 |           .NET 6.0 |    55.88 ns |
| GenerateInt64 |           .NET 6.0 |    28.97 ns |
| GenerateBytes |           .NET 6.0 |    18.85 ns |

Windows:
|        Method |            Runtime |     Mean |
|-------------- |------------------- |---------:|
|   GuidNewGuid | .NET Framework 4.8 | 81.36 ns |
| GenerateInt32 | .NET Framework 4.8 | 56.41 ns |
|-------------- |------------------- |---------:|
|   GuidNewGuid |           .NET 5.0 | 80.87 ns |
| GenerateInt32 |           .NET 5.0 | 45.13 ns |
|-------------- |------------------- |---------:|
|   GuidNewGuid |           .NET 6.0 | 80.38 ns |
| GenerateInt32 |           .NET 6.0 | 46.70 ns |
| GenerateInt64 |           .NET 6.0 | 23.35 ns |
| GenerateBytes |           .NET 6.0 | 16.76 ns |

Я не стал приводить весь код бенчмарка, чтобы не нагромождать статью однотипным кодом. Поэтому просто дам краткую расшифровку:

• GuidNewGuid — генерация вызовом метода Guid.NewGuid().

• GenerateInt32 — генерация вызовом метода random.Next() 4 раза.

• GenerateInt64 — генерация вызовом метода random.NextInt64() 2 раза.

• GenerateBytes — генерация вызовом метода random.NextBytes(Span<byte> buffer).

Чудесно. Мы умеем генерировать не-криптостойкий «Guid», который на Windows быстрее встроенного Guid.NewGuid() в ~5 раз. А на Linux быстрее встроенного Guid.NewGuid() в ~67 раз!

Извлечём практическую пользу

Не пропадать же добру.

Этот генератор Guid'ов уже давно крутится в куче сервисов. С помощью него мы генериуем идентификаторы спанов, трейсов, и прочих эвентов телеметрии. Код можно найти на гитхабе: GuidGenerator и одно из использований, генерация трейсов и спанов. И вся данная телеметрия успешно отправляется и обрабатывается в Hercules’е — системе сбора, хранения и обработки логов, метрик, распределённых трассировок и аннотаций.

Но тут не всё рассказано!

Как обычно, мы прошли мимо большого количества всяких интересностей:

• А можем ли мы генерировать псевдослучайные числа ещё быстрее? Что на счет максимально быстрой реализации на SIMD? Конечно можем. Всех интересующихся направляю на SIMDxorshift. Здесь не буду утомлять кодом на C и SIMD-инструкциями.

• А есть что-нибудь ещё в .NET'е, что неожиданно и кардинально меняет свою производительность при переходе с Windows на Linux? Конечно есть. И много чего. Да хотя бы работа со строками и кодировками чего только стоит. Но об этом, может быть, в другой раз.

• Что за заклинания с [MethodImpl(MethodImplOptions.AggressiveInlining)] и (int*)? Достойно отдельной статьи. Двух разных.

• Как снимать и как анализировать трейсы .NET приложений? Тоже достойно отдельной статьи.

• Почему на виртуалках одинаковой конфигурации наш полностью managed-код с использованием Random все равно имеет разную скорость исполнения на Linux и Windows? Сложно сказать. Разница небольшая и, возможно, виртуалки просто крутились на разных гипервизорах с разной производительностью железа.

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