Вам не нужен UUID23.09.2024 12:15

530e8bc0e569194d3a0b64b1c6508c5f.jpg

Привет, меня зовут Андрей Богомолов, я Android-разработчик в команде Performance приложения Wildberries. 

Однажды, работая с кодом, я обратил внимание на использование UUID в UI и задумался о его влиянии на производительность. Тесты показали, что стандартная реализация UUID в Java может стать узким местом на экранах с высоким DAU и в часто используемых компонентах. 

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

Содержание

Анализ популярных методов генерации ID

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

UUID существуют в нескольких версиях (от 1 до 8), каждая из которых имеет свои особенности, что делает их подходящими для различных сценариев. Краткая структура показана на таблице ниже.

Структура разных версий UUID

Структура разных версий UUID

UUID версии 1 создаётся на основе времени и MAC-адреса, но может раскрывать информацию об устройстве. UUID версии 2 похож на первую версию, но добавляет информацию о домене, что полезно в корпоративных системах, но ограничено в других областях. UUID версии 6 улучшает версию 1, обеспечивая более логичную сортировку по времени, но тоже может раскрывать системные данные. UUID версии 7 использует временные метки и случайные данные, предлагая баланс между уникальностью, конфиденциальностью и упорядоченностью, без зависимости от MAC-адреса.

UUID версии 3 и 5 используют хеширование для создания идентификаторов. В версии 3 используется MD5, который хоть и убирает зависимость от оборудования, уязвим к коллизиям, что делает его менее безопасным. Версия 5, с хешированием на основе SHA-1, более устойчива к коллизиям и подходит для задач, где важна безопасность.

UUID версии 4 создаётся случайным образом, что делает её популярной благодаря простоте и высокому уровню уникальности без привязки к системным данным. UUID версии 8 позволяет хранить произвольные данные, обеспечивая гибкость в использовании.

UUID версии 4 получила наибольшее распространение в Android-разработке из-за стандартной реализации в Java (UUID.randomUUID()). Версии 4 и 7 выглядят наиболее предпочтительными благодаря своей простоте, безопасности и отсутствию риска раскрытия системной информации. У UUID есть множество альтернатив, созданных крупными компаниями, но он остаётся оптимальным выбором в мобильной разработке, так как является стандартом и сбалансирован для частых задач.

Сравнение производительности

Для анализа производительности методов генерации ID использовалась библиотека com.github.f4b6a3 на Java. Сравнивались стандартная реализация UUID версии 4 в Java (UUID.randomUUID()), а также UUID версий 6 и 7. Целью было оценить влияние использования защищённого генератора случайных чисел на скорость генерации. Кроме того в тесте участвовали GUID аналогичных версий с незащищённым генератором случайного числа и метод инкрементальной генерации с использованием AtomicLong.

Основное отличие между защищённым (SecureRandom) и незащищённым (Random) генераторами случайных чисел заключается в уровне предсказуемости и безопасности. Защищённый генератор использует криптографически стойкие алгоритмы, обеспечивая непредсказуемость чисел, тогда как незащищённый генератор предсказуем и менее безопасен. Использование защищённого генератора в UUID версий 4 и 7 соответствует спецификации RFC 9562, которая рекомендует криптографически стойкий генератор (CSPRNG) для максимальной безопасности и уникальности.

Особое внимание уделялось времени преобразования идентификаторов в строку, так как это стандартный способ работы с ID в мобильной разработке. Хотя объекты ID более эффективны по производительности и памяти, строковые представления проще в использовании. Обычно UUID сразу преобразуется в строку при создании для упрощения работы с ним.

Тестирование проводилось на устройстве OnePlus 10 Pro с Android 14. Для измерений использовался Microbenchmark, Kotlin версии 2.0.20-RC. Тест включал 10 прогонов, каждый включал множество итераций (их число определяет сам Microbenchmark). Код, скрипт запуска тестов и замеры доступны по ссылке в конце статьи.

Сравнение времени генерации ID

Сравнение времени генерации ID

Результаты показали, что генерация UUID версий 4 и 7 занимает больше времени из-за использования защищённого генератора. UUID версии 6 быстрее, так как не полагается на генерацию случайных чисел. GUID с незащищённым генератором показали также более высокую скорость.

Однако даже GUID оказались в 20 и более раз медленнее при создании строковых ID по сравнению с инкрементальной генерацией через AtomicLong. Это может быть приемлемо в большинстве сценариев, например, при отправке данных в аналитику или стандартной функциональности приложений. Однако в контексте экранов с большим количеством активных пользователей, где важна каждая миллисекунда, замедление может ухудшить пользовательский опыт и повлиять на бизнес. Аналогично, даже небольшое ускорение на сотни наносекунд в общих компонентах может существенно улучшить производительность приложения.

Разработка собственного метода генерации ID

Цели и требования

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

Первое требование — уникальность на уровне одного устройства, что в большинстве случаев достаточно. Идентификатор будет использоваться для локальных сущностей, таких как пагинация или UI-компоненты, которые не отправляются на сервер. Глобальная уникальность усложнила бы задачу и не дала бы значительного прироста производительности по сравнению с UUID.

Второе требование — сохранение уникальности при перезапуске приложения. Приложение может перезапускаться по разным причинам: нехватка памяти, принудительное завершение пользователем или системой. При этом идентификатор может сохраняться в локальную базу данных или в SavedState для UI-моделей и не должен конфликтовать с новыми ID, которые будут сгенерированы после перезапуска.

Третье требование — поддержка генерации идентификаторов непосредственно в строковом формате, без преобразования из объекта. В мобильной разработке идентификаторы часто передаются и хранятся как строки, поэтому генерация строковых ID напрямую ускорит процесс.

Четвёртое требование — статичность. Это позволит избежать конфликтов между разными экземплярами генераторов и упростит их использование.

Подходы к обеспечению уникальности ID

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

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

Использование MAC-адреса устройства добавляет уникальность, привязанную к конкретному устройству. Однако, если ID используется только на самом устройстве, этот подход теряет смысл. Более того, MAC-адрес может раскрыть конфиденциальную информацию и привести к коллизиям из-за подмены или ошибок производителей.

Генерация случайных чисел также может обеспечить уникальность. Защищённая генерация (SecureRandom) использует криптографически стойкие алгоритмы, такие как CSPRNG, которые гарантируют безопасность и минимизируют риск коллизий за счёт высокой энтропии. Однако это требует больше времени. Незащищённая генерация (Random) работает быстрее, но менее надёжна, так как использует алгоритмы с меньшей энтропией, что увеличивает риск предсказуемости и коллизий.

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

Проектирование собственного метода генерации ID

Для генерации уникальных идентификаторов был выбран подход, комбинирующий несколько методов для достижения требуемой уникальности. Такой принцип используется в UUID и доказал свою эффективность. Простой вариант генерации идентификаторов только через Random был отброшен, так как не обеспечивает защиту от коллизий в нужной степени. Более надёжные методы (например, SecureRandom), минимизируют этот риск, но работают медленнее. Применение только случайных чисел фактически повторяет идею UUIDv4. 

В основе генерации было использовано время с устройства, что позволяет избежать дублирования ID при перезапуске процесса — каждая новая временная метка обеспечивает почти всегда монотонный рост значений. Чтобы снизить риски, связанные с возможными изменениями системного времени, временная метка дополняется случайным числом, схожим с «clock sequence»  в UUID. Это случайное число генерируется один раз при запуске, поэтому его можно создавать любым способом, не влияя на скорость формирования каждого ID. Также был добавлен инкрементальный счётчик для предотвращения коллизий при одновременной генерации ID.

Для оптимизации процесса временная метка и случайное число генерируются один раз при запуске приложения. Эти данные используются как префикс ID. Временная метка сокращена до 40 бит (около 30 лет), а «clock sequence» занимает 24 бита. Таким образом, префикс помещается в один Long (64 бита). При каждом запросе нового ID увеличивается только счётчик.

Структура нового ID

Структура нового ID

По итогу новый ID, названный LocalID, состоит из:

  • Префикса, включающего временную метку и случайное число, сгенерированные при запуске;

  • Счётчика, который инкрементируется с каждым запросом.

В пределах одного запуска приложения коллизии исключены благодаря счётчику. После перезапуска вероятность совпадений минимальна, так как временная метка при запуске почти всегда будет уникальной. Даже если временные метки совпадут, 24 бита случайного числа (около 16 млн вариантов) исключат дублирование.

Пример LocalID:

  • Объект ID: LocalId(mostSigBits=-7942364287448799468, leastSigBits=12345)

  • Строковой ID: lkizfzoHOTlzq-bJI

Код генерации LocalID (метод toCompactString() будет дальше в статье): 

private val counter = AtomicLong(INITIAL_COUNTER_VALUE)
private val mostSigBits = generateMSB()
private val prefix = mostSigBits.toCompactString() + "-"


private fun generateMSB(): Long {
    val random24Bits = SecureRandom().nextLong() and 0xFFFFFFL
    val currentTimeMillis = System.currentTimeMillis() and 0xFFFFFFFFFFL
    return (currentTimeMillis shl 24) or random24Bits
}


fun newId() = LocalId(
    mostSigBits = mostSigBits,
    leastSigBits = counter.getAndIncrement(),
)


fun newIdString(): String {
    return prefix + counter.getAndIncrement().toCompactString()
}

Итоговое сравнение производительности

Как видно из графиков ниже, метод генерации идентификаторов LocalID показал более высокую скорость по сравнению с UUID и GUID. Его производительность оказалась близка к инкрементальной генерации через AtomicLong. 

Сравнение времени генерации ID с LocalID

Сравнение времени генерации ID с LocalID

LocalID при генерации строки делает всего 3 аллокации, тогда как разные версии UUID требуют более 20:

  • atomicLong: 1

  • localId: 3

  • guid4: 21

  • guid7: 21

  • uuid6: 21

  • uuid4: 22

  • uuid7: 23

Также было проведено сравнение LocalID с UUID.randomUUID() на разных объёмах данных. LocalID превосходит UUID.randomUUID() по времени и аллокациям примерно в 10 раз.

Сравнение времени генерации LocalId c UUID.randomUUID() при разном числе итераций

Сравнение времени генерации LocalId c UUID.randomUUID() при разном числе итераций

Для HashMap важно равномерное распределение ID по бакетам, чтобы минимизировать коллизии и ускорить доступ к данным. У UUID коэффициент вариации распределения по 1024 бакетам при 1 млн объектов составляет 3,13% для строк и 3,17% для объектов. У LocalID эти показатели ниже: 2,15% для строк и 0,05% для объектов, что указывает на более равномерное распределение LocalID.

Распределение по бакетам

Распределение по бакетам

Для определения индекса бакета использовался алгоритм из HashMap: 

val hash = key.hashCode() xor (key.hashCode() ushr 16)
val bucketIndex = (bucketCount - 1) and hash

Код для расчёта хэшкода объекта LocalID аналогичен тому, что используется в UUID:  

(mostSigBits xor leastSigBits).hashCode()

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

Код генерации строки LocalID использует специальный набор символов, который обеспечивает хорошее распределение. Хотя его и можно ещё улучшить, это потребует значительных усилий. Чем больше символов в наборе, тем короче строковое представление и тем быстрее вычисляется хэш-код, что способствует повышению эффективности работы HashMap.

private const val CHARS = "BJmkQCdLHlPobfKZsiuRqDwtzINTWOYA"
private const val MASK = 0x1FL
private const val BASE32_MAX_LENGTH = 13


fun Long.toCompactString(): String {
    val result = CharArray(BASE32_MAX_LENGTH)
    var number = this
    var index = BASE32_MAX_LENGTH - 1


    do {
        result[index--] = CHARS[(number and MASK).toInt()]
        number = number ushr 5
    } while (number != 0L)


    return String(result, index + 1, BASE32_MAX_LENGTH - index - 1)
}

В целом скорость генерации hashcode() у LocalID сравнима с UUIDv4 как для объекта ID, так и для строкового ID, с небольшим выигрышем строковой LocalID из-за меньшей длины.

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

Пути оптимизации и дальнейшие исследования

Дальше можно исследовать следующие темы:

  • Разработка метода для генерации пакета (множества) ID за один вызов.

  • Исследование влияния Time-ordered ID по сравнению с рандомным UUID на производительность в SQLite.

  • Анализ наиболее эффективного формата хранения UUID в SQLite (полезные источники для начала: ссылка 1 и ссылка 2).

Ссылки

  • Все замеры и код доступны по ссылке.

  • Источник вдохновения для статьи: IncrementingUuidGenerator из Cucumber.

  • RFC 9562 — спецификация, определяющая структуру UUID и рекомендации по их реализации.

  • Реализации UUID (v6 и v7) и GUID (v4 и v7) взяты из библиотеки uuid-creator.

Заключение

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

Если у вас есть вопросы или предложения, буду рад вашим комментариям.

Отдельное спасибо коллегам из Wildberries за конструктивную критику первой реализации LocalID, приведшую к её улучшениям.

© Habrahabr.ru