23.09.2024 09:06
tipapro 38 5900 Источник

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

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

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

Дисклеймер: статья больше направлена на изучение генерации ID в мобильной разработке. Генератор ID из статьи не был применён в реальном коде.

Содержание

Анализ популярных методов генерации 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. Для измерений использовался Jetpack 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, приведшую к её улучшениям.

Комментарии (38)


  1. turbo_nyasha
    23.09.2024 09:16
    #27329020
    +30

    Сначала исчезли пакеты из ПВЗ. Потом сказали что доставка платная. Сейчас говорят что и UUID нам не нужен...


    1. IvanZaycev0717
      23.09.2024 09:16
      #27329162
      +3

      Поосторожнее, там в людей постреливают


  1. positroid
    23.09.2024 09:16
    #27329120
    +13

    А можете рассказать чуть больше про целеполагание. Насколько понимаю задача получить некий уникальный идентификатор устройства?

    На одной генерации вы сэкономили что-то около 2мс, в каком кейсе приложение делает большое количество итераций, чтобы это хоть как-то сказалось на производительности?


    1. tipapro Автор
      23.09.2024 09:16
      #27329212

      Цель - получение ID, уникального только в рамках конкретного устройства (то есть без гарантий уникальности между всеми устройствами, как у UUID).

      Есть специфичный кейс (не из кода ВБ), например, если не доверяем бэку или есть гарантия повторов ID в списках (а они приведут к крашу, если оставить, а убирать повторы мы не хотим, так как можем случайно убрать не то), то нам нужно генерировать свой ID локально для множества элементов. Если мы не хотим добавлять логику с кэшем в SQLite (а там мы могли бы использовать автоинкремент), то получим влияние на метрику "время до контента" при генерации ID для всех элементов в списке даже на другом потоке + время до появления контента при скролле пострадает.

      Также, даже если вызовов не так много, но если логика используется часто и во многих местах, то эффект накопительный вместе с другими микрооптимизациями в таких же общих компонентах. Я бы сравнил это с тем, как разработчики Jetpack Compose во время разработки новых версий делают множество микрооптимизаций (аллокаций, структур данных, алгоритмов), которые в сумме могут давать хороший прирост в каждой новой версии.


      1. ImagineTables
        23.09.2024 09:16
        #27329330
        +3

        Если бы мне надо было сделать FastgenUuid, я бы выделил в куче пул, запоминал индекс последнего использованного и перезаписывал onidle из надёжного источника. Уж лучше так, чем закладывать мину на будущее, когда где-нибудь (где не ожидалось) криптонестойкость вылезет боком.


        1. tipapro Автор
          23.09.2024 09:16
          #27329426

          Интересный подход, хотя тут и нужно решить много корнер кейсов с генерацией новых id в пул (запросили ID, сгенеренные закончились, новые не успели сгенериться), и очисткой пула, чтобы не держать лишние id. Также чтобы не было проблем с этими корнер кейсами в многопоточке. Ещё нужно тонко настроить пул, чтобы не был очень большим для памяти, при этом не очень маленьким, чтобы не было деградаций производительности при быстром израсходовании сгенеренных ID


          1. egribanov
            23.09.2024 09:16
            #27332546

            Вы не смотрели в сторону ULID?


            1. tipapro Автор
              23.09.2024 09:16
              #27334222

              Насколько я вижу по структуре UUIDv7 и ULID похожи (временная метка (48 бит) + рандом (74 бита у UUIDv7 и 80 бит у ULID), поэтому отличий по времени в плане генерации объекта особо быть не должно.

              Но у ULID строковой ID кодируется в BASE32, что ускоряет генерацию строкового ID, но всё равно придётся конвертировать все биты в строку (не получился предгенерировать один префикс при запуске).

              Поэтому тут лучше взять UUIDv7 и нагенерировать пул значений, как предлагали выше. Или на крайний случай сохранять UUIDv7 в BASE32 формате.


  1. IvanZaycev0717
    23.09.2024 09:16
    #27329180
    +2

    Вам может быть UUID не нужен, но вот бизнесу... Может быть такая история: у вас id пользователя задан целым числом int. Бизнес декларирует, что на его портале уже 100 000 пользователей. Но когда новый пользователь создаёт новый аккаунт у него id=17, а если создать ещё один аккаунт у него id=18. Нестыковочка получается. Бизнес есть бизнес, он такой. UUID помогает скрыть, сколько на самом деле юзеров на портале


    1. tipapro Автор
      23.09.2024 09:16
      #27329234

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


    1. MxMaks
      23.09.2024 09:16
      #27329410
      +1

      Можно сделать seek, и потом продавать привелигированные 4х значные id. Бизнес так бизнес.


  1. AstarothAst
    23.09.2024 09:16
    #27329564
    +2

    Если у вас

    Цель - получение ID, уникального только в рамках конкретного устройства (то есть без гарантий уникальности между всеми устройствами, как у UUID).

    то зачем вам вообще UUID? Секвенция в БД замечательно справится с генерацией новых уникальных id - это быстро и надежно. На вскидку смысл связываться с UUID появляется только в двух случайх - если у вас несколько инстансов БД, и есть риск задвоения генеренных из сиквенсов айдишников, и если вам нужна миграция с БД на БД попроще, без проблем с миграцией дочерних записей.


    1. tipapro Автор
      23.09.2024 09:16
      #27329652
      +1

      В SQLite (так как рассматриваем именно мобилки) нету полноценной поддержки фичи SEQUENCE как в других БД. Только через автоинкремент поля ID. Если реализовывать через таблицу чисто для ID, то встаёт вопрос производительности, так как при чтении и записи в SQLite будет очень много действий (нужно тестировать)


      1. AstarothAst
        23.09.2024 09:16
        #27329702

        А, sqlite! Все ясно, простите, был не внимателен.


  1. mixsture
    23.09.2024 09:16
    #27329766

    Я не понимаю, зачем вы используете временную метку при генерации? Ситуации всего две:
    1) либо у вас редкие по времени операции, и тогда временная метка (которая скорее всего некое подобие юникс времени - число секунд с момента Х) помогает - в том смысле, что обеспечивает высокую селективность. Но тогда встает вопрос: а зачем вообще тут что-то оптимизировать, вы довольно слабо упираетесь в ограничение производительности и это легко обходится путем, как предложили выше - прегенерацией буфера новых меток).
    2) либо у вас очень частые операции, но тогда временная метка сильно теряет селективность. Т.е. если вы пытаетесь вставить это в 1000rps сервис - то получаете 1000 одинаковых временных меток. А это треть размера уида и она работает крайне слабо.

    Из того, что я прочитал о вашей ситуации - я бы выбрал mac+счетчик на вашем месте. Mac - это будет идентификатор телефона (ведь 2 приложения на телефоне не планируется запускать). Вы вместо этого ставите случайные данные будто бы давая предположение, что планируется запускать много копий на одном устройстве, ведь только в этом случае mac перестает эффективно разделять.


    1. tipapro Автор
      23.09.2024 09:16
      #27330000

      mac адрес не добавляет уникальности, если ID будет использован только на данном устройстве (это требование было поставлено, как начальное условие для нового способа генерации ID).

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

      Просто счётчик не спасёт, так как при смерти процесса в Android всё исчезает и после перезапуска счётчик начнётся с нуля, при этом через механизм сохранения данных (либо onSaveInstanceState (и его альтернативы), либо другие локальные хранилища) могут быть сохранены эти ID и тогда они начнут конфликтовать с обнулённым счётчиком


      1. mixsture
        23.09.2024 09:16
        #27330086
        +1

        Ага, вы не можете гарантированно сохранить значения счетчика между перезапусками. Тогда метка времени подходит и даже ее упрощенный вариант - метка времени запуска приложения (т.к. именно перезапуски вносят проблему и их надо в разные области нумерации развести).
        В течение работы приложения основную работу отлично выполняет счетчик. Врятли можно придумать что-то сравнимое с ним по быстродействию, все остальные методы медленнее. Случайные данные, я так понимаю, вы выбрали для организации многопоточности - что они как-то уберут коллизии между потоками.
        Как альтернативы этому:

        1) обращение всех потоков к однопоточному счетчику с мьютэксом. Может тормозить потоки (а может и нет, т.к. счетчик очень быстрый).
        2) использование номера потока в уид. Тогда у каждого потока каждого запуска приложения - своя область номеров, а внутри работает счетчик. Что даст и многопоточность, и сохранит достоинства скорости счетчика.

        Не пробовали эти варианты?


        1. tipapro Автор
          23.09.2024 09:16
          #27330274

          Метка времени запуска приложения может повториться на одном устройстве (с очень маленьким шансом). Поэтому было решено добавить случайное число. И так как префикс - Long, то просто решил до конца заполнить оставшиеся биты случайными числами.

          Атомарный счётчик обычно медленнее, когда очень много потоков и большая конкурентность, что обычно не встретишь у мобилок. Поэтому атомарный счётчик вполне должен быть быстрее, чем мьютексы.

          Если использовать номер потока, вместе с ним нужно получать временную метку каждый раз (а не только при запуске). Из-за этого нам придётся преобразовывать в строку больше значений, чем в случае, когда нам достаточно лишь время запуска и мы можем преобразовать в строку её одни раз при запуске.


          1. mixsture
            23.09.2024 09:16
            #27331146

            вместе с ним нужно получить временную метку каждый раз

            Зачем? Что не так с меткой времени при запуске всего приложения + номер потока? Да и в любом случае, генерируется это только 1 раз - при запуске потока, врятли у вас невероятно много потоков генерируется, так что на производительность влияет слабо (относительно варианта когда вы время получаете на каждую генерацию уид). Внутри потока будет только преобразование счетчика в строку, инкремент его, конкатенация 2х строк: счетчика, префикса потока (состоящего из метки времени запуска приложения и номера потока).


            1. tipapro Автор
              23.09.2024 09:16
              #27331266

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

              Насчёт изменения счётчика внутри потока: вы предлагаете хранить счётчик в ThreadLocal, чтобы использовать обычный Long, а не AtomicLong?


              1. mixsture
                23.09.2024 09:16
                #27333714

                Если человек поменял время в настройках

                ...то можно поймать коллизию. Мне кажется, это настолько слабо вероятным, что можно пренебречь (это надо секунду в секунду попасть моментом запуска приложения после смены времени). Но если совсем не хотите пренебрегать - то я бы шел по идее префикса: если хотите случайное число, то лучше его один раз при запуске сгенерировать и сохранить в префиксе (а не дергать ГПСЧ на каждое создание уида).

                Насчет изменения счетчика внутри потока...


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


                1. tipapro Автор
                  23.09.2024 09:16
                  #27334238

                  По поводу префикса - он и генерируется один раз при запуске. Цитата из статьи:

                  Для оптимизации процесса временная метка и случайное число генерируются один раз при запуске приложения

                  По поводу ThreadLocal + Long vs AtomicLong будет интересно сравнить, чтобы быстрее (при малой конкуренции потоков и при высокой)


  1. TerraV
    23.09.2024 09:16
    #27330240
    +2

    Ну очень спорное решение как с точки зрения анализа проблемы, так и с точки зрения архитектуры. Я не верю, что профилирование приложения показало что генерация UUID это узкое место. А с точки зрения архитектуры, вы заменили стандартный инструмент, про достоинства и недостатки знают все, на какой-то свой велосипед. Бизнес требования будут меняться и раньше или позже (скорее раньше) вы со своего велосипеда упадете. Палку в переднее колесо вы уже считай ткнули.


    1. tipapro Автор
      23.09.2024 09:16
      #27330464

      Я не верю, что профилирование приложения показало что генерация UUID это узкое место

      Профилирование этого и не показывало (обычно на экранах всегда есть проблемы похуже). Здесь больше про то, что в некоторых ситуациях (при разработке общих элементов) может оказаться, что особо оптимизировать нечего больше, но при этом в коде есть генерация UUID. Поэтому почему бы не рассмотреть, а нужен ли он в данном месте и можно ли его чем-то заменить, чтобы ускорить. И статья в этом плане просто эксперимент.

      Бизнес требования будут меняться и раньше или позже (скорее раньше) вы со своего велосипеда упадете.

      Так можно сказать и про автоинкрементальный ID в БД. И как показывает практика, от того, что в SQLite у нас автоинкрементальный ID (даже для элементов с бэка, у которых свой ID), из-за новых хотелок бизнеса не приходилось переделывать его на UUID. По аналогии почему тогда в похожих кейсах, где неудобно использовать автоинкремент из бд не использовать свою генерацию ID.

      вы заменили стандартный инструмент, про достоинства и недостатки знают все, на какой-то свой велосипед

      Есть такой фактор, но это не повод не пробовать сделать своё. В больших приложениях столько своих велосипедов из-за того, что стандартные решения часто не подходят или медленны в конкретных кейсах. И тем не менее нормально живут такие приложения. И тут уже нужно от конкретного случая смотреть, нужно ли в вашем коде такое или нет. Стандартных методов генерации ID (через бэк, автоинкремент в локальной бд или UUID.randomUUID()), вполне хватит в 95+% мест и тем более для средних приложений.


      1. Borz
        23.09.2024 09:16
        #27331030
        +2

        Здесь больше про то, что в некоторых ситуациях (при разработке общих элементов) может оказаться, что особо оптимизировать нечего больше, но при этом в коде есть генерация UUID.

        То есть это чисто гипотетический пример в статье, не решающий какой-то реального кейса?


        1. tipapro Автор
          23.09.2024 09:16
          #27331092

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


          1. Borz
            23.09.2024 09:16
            #27331628

            речь не про использование UUID, а про пример в мобильнои приложении, где получение UUID существенно сказывается на производительности приложения и отражается на пользователе

            Хотя, вероятно в мобильных играх или трейдинговых (есть такие под мобилку?) такое и может быть, но тут блог WB и, лично я, пока не могу представить такого кейса в вашем приложении...


            1. tipapro Автор
              23.09.2024 09:16
              #27334254
              +1

              где получение UUID существенно сказывается на производительности приложения и отражается на пользователе

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

              В WB такого и вправду нету, так как использования UUID больше единичные (проверял по коду до выпуска статьи)


  1. tipapro Автор
    23.09.2024 09:16
    #27330250

    (не туда ответил)


  1. tipapro Автор
    23.09.2024 09:16
    #27330258

    (не туда ответил)


  1. severgun
    23.09.2024 09:16
    #27330816
    +1

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


  1. exadmin
    23.09.2024 09:16
    #27331498

    А если просто сгенерировать в начале сессии честный рандомный guid, а потом инкрементально к нему конкатенировать инкремент или таймстемп?

    Получится строка подлиннее, но уникальная + можно трейсить айдишники принадлежащие одной и той же сессии.

    А генерироваться будут мгновенно.


    1. tipapro Автор
      23.09.2024 09:16
      #27334284

      По сути это такой же вариант, как и в статье по принципу (префикс (64 бита), сгенерированный один раз при запуске + счётчик (64 бита)). Только тут будет 128 бит рандомного префикса и 64 бита счётчика. Увеличение длины - это также дольше расчёт hashcode и больше памяти для хранения. Не уверен, насколько стоит так делать


  1. SergeyProkhorenko
    23.09.2024 09:16
    #27331696
    +6

    Седьмая версия UUID в дополнение к каноническому виду имеет три альтернативных метода реализации, и их вдобавок можно комбинировать. Вполне можно было реализовать что-то для описанного случая, не отклоняясь от RFC 9562. Например, если тормозит криптостойкий генератор случайных чисел, то случайный сегмент можно было укоротить за счет добавления субмиллисекундного сегмента и/или счетчика, инициализируемого случайным числом (с использованием предусмотренных RFC 9562 мер защиты от переполнения счетчика). Или нагенерить случайных чисел впрок.


    1. TerraV
      23.09.2024 09:16
      #27333272

      Тот самый случай когда один короткий комментарий полезнее статьи! Респект бро


    1. tipapro Автор
      23.09.2024 09:16
      #27334378

      Заменяя случайные биты в 7 версии на время мы лишь приблизимся к производительности версии 6. Основная проблема - строковое представление в BASE16, что дольше делать, чем BASE32 + невозможность предгенерации префикса (или любой другой части) при запуске приложения

      А нагенерить пул объектов, как уже предлагали выше - вполне хорошая идея, но нужно будет решить несколько корнер кейсов (многопоточка и если не успели заполнить пул, а требуются новые ID, чтобы не было деградаций)


      1. SergeyProkhorenko
        23.09.2024 09:16
        #27336656
        +2

        RFC 9562 рекомендует для БД бинарное 128-битовое представление UUID, если это возможно. Например, для этого хорошо подходит тип данных UUID в PostgreSQL. Для других систем я бы тоже посоветовал по возможности использовать бинарное внутреннее представление.

        Для текстового представления могу посоветовать кодировку Crockford's Base32. Что-то близкое будет добавлено в RFC 9562 - сейчас авторы RFC 9562 это активно обсуждают. Но совместимость Crockford's Base32 с будущим стандартом маловероятна, так как алфавит, возможно, немного изменится, и последние два бита, возможно, будут использованы под контрольную сумму.

        Зачем нужна предгенерация префикса (или любой другой части) при запуске приложения - мне непонятно.

        А вообще тема производительности именно генерации UUID - надуманная. Для БД UUID генерятся заведомо быстрее, чем БД способна создать записи в таблице, где используются эти UUID. То есть, производительность генераторов UUID избыточная.


        1. tipapro Автор
          23.09.2024 09:16
          #27337748

          Вы пишите со стороны бэкенда. Я больше смотрел в контексте генерации и хранении в мобильном приложении, в том же UI слое (нечастые кейсы, но бывают).

          Про обсуждение Base32 - спасибо, посмотрю драфт.

          Зачем нужна предгенерация префикса (или любой другой части) при запуске приложения - мне непонятно.

          Предгенерация префикса как один из способов оптимизации генерации. Но способ с предгенерацией пула UUID всё же кажется удачнее.