CombGuid. Генерация “дружественных” к SQL серверам значений Guid в .net приложениях

    Использование uuid в качестве первичного ключа для таблиц имеет множество преимуществ, одним из которых является возможность получать идентификаторы для создаваемых в клиентском приложении объектов самостоятельно, без обращения к серверу баз данных. Но использование uuid в качестве первичного ключа имеет и недостаток: guid-ы, сгенерированные клиентским приложением, могут быть недостаточно “дружелюбны” к SQL серверу, что в свою очередь может привести к оверхеду при добавлении новой записи. Возможное удорожание операции insert вытекает из того, что SQL сервер для хранения таблиц, по которым задан первичный ключ, обычно использует структуры известные как b-деревья. При добавлении новой записи в таблицу, SQL сервер, в соответствии с сортировкой по первичному ключу, ищет лист, на котором должна быть размещена вставляемая запись. Учитывая псевдослучайный алгоритм генерации uuid, сортировочный порядок новой записи также случаен и возможна ситуация, что лист, на котором должна быть размещена запись, полностью заполнен. В подобных случаях SQL серверу приходится разделять лист надвое и перестраивать ветви b-дерева, ведущие к этому листу. Чтобы не сталкивать SQL сервер с необходимостью постоянно перестраивать кластерный индекс при добавлении новых записей, можно вести генерацию значений первичного ключа в нарастающей последовательности. Один из вариантов генерации Guid в нарастающем порядке — это привязывать сортировочный порядок сгенерированного Guid к текущему времени. Сгенерированные подобным образом идентификаторы часто называют CombGuid, намекая на то, что строятся они из двух половинок — псевдослучайной части, как у обычных Guid, и строки, привязанной ко времени.

    Как SQL сервер сравнивает uuid-ы

    SQL сервер сортирует значения uuid отличным от .net способом. Сравнение ведется по байтовым группам справа-налево. Внутри байтовой группы сравнение ведется уже слева-направо. (Байтовой группой называется последовательность, ограниченная символом ‘-’.) Если сравнить два значения uuid,
    @u1 = ‘206AEBE7-ABF0-47A8-8AA5-6FDDF39B9E4F’
    и
    @u2 =’0F8257A1-B40C-4DA0-8A37-8BBC55183CAE’, на выходе получится, что @u2> @u1, поскольку, как уже было сказано выше, SQL сервер начинает сравнение с крайних справа байтовых групп, где 6FDDF39B9E4F < 8BBC55183CAE. Если говорить более технически, наибольшее влияние на сортировочный порядок uuid в базах данных оказывают байты с 9 по 15, в порядке убывания.

    Реализация CombGuid в библиотеке Magnum

    В своем проекте мы используем библиотеку Magnum, частью которой является статический класс CombGuid с единственным методом Generate(), создающим привязанные ко времени Guid-ы. Magnum — библиотека с открытым исходным кодом, выложенная на GitHub. Я не поленился и посмотрел, как выглядит реализация метода создания Guid в этой библиотеке.

    public static class CombGuid
    {
    	static readonly DateTime _baseDate = new DateTime(1900, 1, 1);
    
    	public static Guid Generate()
    	{
    		byte[] guidArray = Guid.NewGuid().ToByteArray();
    
    		DateTime now = DateTime.Now;
    
    		// Get the days and milliseconds which will be used to build the byte string
    		var days = new TimeSpan(now.Ticks - _baseDate.Ticks);
    		TimeSpan msecs = now.TimeOfDay;
    
    		// Convert to a byte array
    		// Note that SQL Server is accurate to 1/300th of a millisecond so we divide by 3.333333
    		byte[] daysArray = BitConverter.GetBytes(days.Days);
    		byte[] msecsArray = BitConverter.GetBytes((long)(msecs.TotalMilliseconds/3.333333));
    
    		// Reverse the bytes to match SQL Servers ordering
    		Array.Reverse(daysArray);
    		Array.Reverse(msecsArray);
    
    		// Copy the bytes into the guid
    		Array.Copy(daysArray, daysArray.Length - 2, guidArray, guidArray.Length - 6, 2);
    		Array.Copy(msecsArray, msecsArray.Length - 4, guidArray, guidArray.Length - 4, 4);
    
    		return new Guid(guidArray);
    	}
    }
    

    Алгоритм довольно прост.
    В 9-10 байте закодировано число дней, прошедших с 1 января 1900 года. Надо не забыть пересобрать исходники в 2079 году, когда количество прошедших дней перестанет умещаться в двух байтах. 11-15 байт использованы для кодирования миллисекунд с начала суток, зачем-то поделенных на 3.333333. В комментариях в коде указано, что эта операция связана с тем, что точность хранения временных меток в SQL сервере составляет 1/300 секунды. Довольно странное решение, учитывая, что нам в процессе генерирования uuid абсолютно неважно как SQL сервер хранит временные метки, мы используем миллисекунды только для создания uuid. Я немного погуглил этот вопрос, но понял только то, что автор библиотеки Magnum Chris Patterson скопировал код генерации CombGuid из Nhibernate. Как видно здесь, метод GenerateComb содержит тот же самый код. Справедливости ради надо отметить, что деление миллисекунд на 3.333333 особого влияния на работу алгоритма не оказывает, это просто лишний, необязательный шаг.

    Guid vs CombGuid. Сравниваем скорость вставки в БД

    Наконец, мы подошли к тому, ради чего все это затевалось, к сравнению на сколько uuid-ы, сгенерированные методом Guid.NewGuid(), медленнее своих собратьев, созданных через CombGuid.Generate(), в контексте вставки записей в таблицу SQL сервера.
    Для теста я создал два скрипта, создающие таблицы на SQL сервере и вставляющие в эти таблицы 100000 строк. Первый скрипт вставляет в базу данных строки с Id, созданными с помощью метода CombGuid.Generate(), второй — с помощью метода Guid.NewGuid().

    Кусочек тестового скрипта.
    USE [CombIdTest]
    GO
    --сбрасываем кеши сервера
    DBCC DROPCLEANBUFFERS;
    DBCC FREEPROCCACHE;
    CREATE TABLE [dbo].[CombId](
    	[ID] [uniqueidentifier] NOT NULL,
    	[Value] [varchar](4000) NOT NULL,
     CONSTRAINT [PK_CombId] PRIMARY KEY CLUSTERED 
    (
    	[ID] ASC
    )WITH (PAD_INDEX = OFF, STATISTICS_NORECOMPUTE = OFF, IGNORE_DUP_KEY = OFF, ALLOW_ROW_LOCKS = ON, ALLOW_PAGE_LOCKS = ON) ON [PRIMARY]
    ) ON [PRIMARY]
    GO
    --вставку производим в рамках одной транзакции
    begin transaction
     insert into CombId Values ('5cb31d3d-3793-428e-beb0-a2e4047e255c','somevalue');
     insert into CombId Values ('1e905fa1-e4d4-4a2c-a185-a2e4047e255d','somevalue');
    -- еще 99998 операций insert
    commit transaction
    

    Перед выполнением вставки сброшены буферные кеши и сама вставка производится в одну транзакцию, дабы уменьшить количество обращений к журналу транзакций. Каждый скрипт был запущен трижды, в качестве времени выполнения взят параметр “Общее время выполнения” из статистики клиента. Замеры производились на MSSQL Server 2012.

    Результаты измерений (в миллисекундах).
    1 2 3 Среднее
    CombGuid 2795 2882 2860 2845,667
    RandomGuid 3164 3129 3111 3134,667

    Преимущество скрипта, вставляющего записи содержащие CombGuid, чуть более 10 процентов над скриптом с “обычными” uuid. Использование CombGuid также положительно сказалось и на размере таблицы — ее размер оказался почти в полтора раза меньше: 3.75 Мб против 5,25 Мб.

    Ну и пара вопросов напоследок

    Что вы используете в качестве первичных ключей в ваших БД?
    Если используете uuid или похожие на них байтовые структуры, как вы их генерируете?

    Поделиться публикацией

    Похожие публикации

    Комментарии 13

      +1
      В зависимости от необходимости используем варианты целочисленного или же guid.
      Генерируем стандартно, Guid.NewGuid(). Выигрыш слишком не велик, тест жесткая синтетика, попробуйте вставить тоже самое BULK INSERT.
      А что у вас за машина вообще? Кроме MS SQL, какие характеристики железа, особенно дисковой подсистемы. Посмотрите на результаты SSD + MS SQL, например;) Я считаю, что это не то место, где в реальности стоит что-то оптимизировать. Возможно, меня поправят те, у кого большие данные, но используют ли они тогда Guid?!
        0
        тест жесткая синтетика
        Синтетичность теста меня самого немного напрягает, но я не смог придумать ничего лучше. Да и возможно ли это?
        Возможно, меня поправят те, у кого большие данные, но используют ли они тогда Guid?!

        Для примера, как генерируют Id в инстаграмме. Они кроме времени кодируют внутри идентификатора еще и шарду, к которой должна относиться запись.
        instagram-engineering.tumblr.com/post/10853187575/sharding-ids-at-instagram

        Я считаю, что это не то место, где в реальности стоит что-то оптимизировать.

        10% на вставку, лучшая дефрагментация таблиц в БД (соответственно теоретически должен чуть быстрее работать и select) просто заменой Guid.NewGuid() на CombGuid.Generate() не так уж и плохо.
          0
          А накладные ресурсы? Ведь генерация становится зависимой от времени. А время имеет свойство меняться, то батарейка умрет на плате, то пользователь время переведет, то еще какие-то проблемы. Это приведет в конечном итоге в выделении какой-то службы, которая за это будет отвечать, да и она не всегда избавлена от такого риска.
          Да и возможно ли это? — возможно, я же написал, что ваш тест лучше попробовать вставить BULK и посмотреть, скажется ли в этом случае на 10% или еще как-то.
        0
        Спасибо за статью. В вопросе «Что вы используете в качестве первичных ключей в ваших БД?», наверное, имелось ввиду «Что вы используете в качестве первичных ключей в ваших БД при необходимости использования суррогатного ключа?»
          0
          Да, именно это и интересно. Но и чужой опыт по использованию естественных ключей, особенно в условиях масштабируемых шардингом приложений тоже интересен.
          0
            +1
            Creates a GUID that is greater than any GUID previously generated by this function on a specified computer since Windows was started. After restarting Windows, the GUID can start again from a lower range, but is still globally unique.
            Взято отсюда

            Краткий перевод — после перезагрузки сервера метод NEWSEQUENTIALID может начать генерировать GUID с меньшего чем до перезагрузки диапазона.

            Еще надо отметить, что метод NEWSEQUENTIALID машинно-зависимый, поэтому, в случае распределенных приложений использующих более чем один сервер, придется выделить специальный сервер-арбитр для создания uuid, к которому уже будут обращаться остальные сервера.
              0
              Краткий перевод — после перезагрузки сервера метод NEWSEQUENTIALID может начать генерировать GUID с меньшего чем до перезагрузки диапазона.

              И что? Все равно распределение становится существенно более линейным, так что индексы перестраиваются намного реже.

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

              А зачем?
                0
                А зачем?

                Представьте ферму из четырёх iis работающих с несколькими шардами. На каком сервере должен генерироваться uuid методом newsequentialid?
                  0
                  На том, на котором он создается первым.
                0
                Думаю вот этот ответ замечательно описывает ситуацию с генерацией CombGuid с помощью функции UuidCreateSequential, рекомендую ознакомится.
                0
                >> Краткий перевод — после перезагрузки сервера метод NEWSEQUENTIALID может начать генерировать GUID с меньшего чем до перезагрузки диапазона.
                Чуть менее краткий перевод — после перезагрузки сервера метод NEWSEQUENTIALID может начать генерировать GUID с меньшего чем до перезагрузки диапазона, но по-прежнему глобально уникальный.
                  0
                  Очень актуальная статья, спасибо. У меня сотрудники используют «полевой» клиент, установленный на рабочих ноутах и реплицируют новые данные с сервером по средствам идентификации по Guid'ам. Было интересно!

                  Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                  Самое читаемое