Комментарии 38
Сначала исчезли пакеты из ПВЗ. Потом сказали что доставка платная. Сейчас говорят что и UUID нам не нужен...
А можете рассказать чуть больше про целеполагание. Насколько понимаю задача получить некий уникальный идентификатор устройства?
На одной генерации вы сэкономили что-то около 2мс, в каком кейсе приложение делает большое количество итераций, чтобы это хоть как-то сказалось на производительности?
Цель - получение ID, уникального только в рамках конкретного устройства (то есть без гарантий уникальности между всеми устройствами, как у UUID).
Есть специфичный кейс (не из кода ВБ), например, если не доверяем бэку или есть гарантия повторов ID в списках (а они приведут к крашу, если оставить, а убирать повторы мы не хотим, так как можем случайно убрать не то), то нам нужно генерировать свой ID локально для множества элементов. Если мы не хотим добавлять логику с кэшем в SQLite (а там мы могли бы использовать автоинкремент), то получим влияние на метрику "время до контента" при генерации ID для всех элементов в списке даже на другом потоке + время до появления контента при скролле пострадает.
Также, даже если вызовов не так много, но если логика используется часто и во многих местах, то эффект накопительный вместе с другими микрооптимизациями в таких же общих компонентах. Я бы сравнил это с тем, как разработчики Jetpack Compose во время разработки новых версий делают множество микрооптимизаций (аллокаций, структур данных, алгоритмов), которые в сумме могут давать хороший прирост в каждой новой версии.
Если бы мне надо было сделать FastgenUuid, я бы выделил в куче пул, запоминал индекс последнего использованного и перезаписывал onidle из надёжного источника. Уж лучше так, чем закладывать мину на будущее, когда где-нибудь (где не ожидалось) криптонестойкость вылезет боком.
Интересный подход, хотя тут и нужно решить много корнер кейсов с генерацией новых id в пул (запросили ID, сгенеренные закончились, новые не успели сгенериться), и очисткой пула, чтобы не держать лишние id. Также чтобы не было проблем с этими корнер кейсами в многопоточке. Ещё нужно тонко настроить пул, чтобы не был очень большим для памяти, при этом не очень маленьким, чтобы не было деградаций производительности при быстром израсходовании сгенеренных ID
Вы не смотрели в сторону ULID?
Насколько я вижу по структуре UUIDv7 и ULID похожи (временная метка (48 бит) + рандом (74 бита у UUIDv7 и 80 бит у ULID), поэтому отличий по времени в плане генерации объекта особо быть не должно.
Но у ULID строковой ID кодируется в BASE32, что ускоряет генерацию строкового ID, но всё равно придётся конвертировать все биты в строку (не получился предгенерировать один префикс при запуске).
Поэтому тут лучше взять UUIDv7 и нагенерировать пул значений, как предлагали выше. Или на крайний случай сохранять UUIDv7 в BASE32 формате.
Вам может быть UUID не нужен, но вот бизнесу... Может быть такая история: у вас id пользователя задан целым числом int. Бизнес декларирует, что на его портале уже 100 000 пользователей. Но когда новый пользователь создаёт новый аккаунт у него id=17, а если создать ещё один аккаунт у него id=18. Нестыковочка получается. Бизнес есть бизнес, он такой. UUID помогает скрыть, сколько на самом деле юзеров на портале
Статья больше про применение этого метода на мобильных устройствах. Специально не затрагивал бэк, так как понимаю, что проблем будет куча и особо не пооптимизируешь тут. На мобилке в свою очередь прятать особо нечего, если ID не будет уходить на бэк. Поэтому тем уровнем безопасности UUID, который создавался для бэка, можно немного пренебречь в угоду производительности
Можно сделать seek, и потом продавать привелигированные 4х значные id. Бизнес так бизнес.
Если у вас
Цель - получение ID, уникального только в рамках конкретного устройства (то есть без гарантий уникальности между всеми устройствами, как у UUID).
то зачем вам вообще UUID? Секвенция в БД замечательно справится с генерацией новых уникальных id - это быстро и надежно. На вскидку смысл связываться с UUID появляется только в двух случайх - если у вас несколько инстансов БД, и есть риск задвоения генеренных из сиквенсов айдишников, и если вам нужна миграция с БД на БД попроще, без проблем с миграцией дочерних записей.
В SQLite (так как рассматриваем именно мобилки) нету полноценной поддержки фичи SEQUENCE как в других БД. Только через автоинкремент поля ID. Если реализовывать через таблицу чисто для ID, то встаёт вопрос производительности, так как при чтении и записи в SQLite будет очень много действий (нужно тестировать)
Я не понимаю, зачем вы используете временную метку при генерации? Ситуации всего две:
1) либо у вас редкие по времени операции, и тогда временная метка (которая скорее всего некое подобие юникс времени - число секунд с момента Х) помогает - в том смысле, что обеспечивает высокую селективность. Но тогда встает вопрос: а зачем вообще тут что-то оптимизировать, вы довольно слабо упираетесь в ограничение производительности и это легко обходится путем, как предложили выше - прегенерацией буфера новых меток).
2) либо у вас очень частые операции, но тогда временная метка сильно теряет селективность. Т.е. если вы пытаетесь вставить это в 1000rps сервис - то получаете 1000 одинаковых временных меток. А это треть размера уида и она работает крайне слабо.
Из того, что я прочитал о вашей ситуации - я бы выбрал mac+счетчик на вашем месте. Mac - это будет идентификатор телефона (ведь 2 приложения на телефоне не планируется запускать). Вы вместо этого ставите случайные данные будто бы давая предположение, что планируется запускать много копий на одном устройстве, ведь только в этом случае mac перестает эффективно разделять.
mac адрес не добавляет уникальности, если ID будет использован только на данном устройстве (это требование было поставлено, как начальное условие для нового способа генерации ID).
Частота генерации может быть любая (от генерации множества ID на нескольких потоков в один момент времени до редкой генерации раз в секунду) + время может меняться на устройстве по другим причинам, поэтому только время и не подошло.
Просто счётчик не спасёт, так как при смерти процесса в Android всё исчезает и после перезапуска счётчик начнётся с нуля, при этом через механизм сохранения данных (либо onSaveInstanceState (и его альтернативы), либо другие локальные хранилища) могут быть сохранены эти ID и тогда они начнут конфликтовать с обнулённым счётчиком
Ага, вы не можете гарантированно сохранить значения счетчика между перезапусками. Тогда метка времени подходит и даже ее упрощенный вариант - метка времени запуска приложения (т.к. именно перезапуски вносят проблему и их надо в разные области нумерации развести).
В течение работы приложения основную работу отлично выполняет счетчик. Врятли можно придумать что-то сравнимое с ним по быстродействию, все остальные методы медленнее. Случайные данные, я так понимаю, вы выбрали для организации многопоточности - что они как-то уберут коллизии между потоками.
Как альтернативы этому:
1) обращение всех потоков к однопоточному счетчику с мьютэксом. Может тормозить потоки (а может и нет, т.к. счетчик очень быстрый).
2) использование номера потока в уид. Тогда у каждого потока каждого запуска приложения - своя область номеров, а внутри работает счетчик. Что даст и многопоточность, и сохранит достоинства скорости счетчика.
Не пробовали эти варианты?
Метка времени запуска приложения может повториться на одном устройстве (с очень маленьким шансом). Поэтому было решено добавить случайное число. И так как префикс - Long, то просто решил до конца заполнить оставшиеся биты случайными числами.
Атомарный счётчик обычно медленнее, когда очень много потоков и большая конкурентность, что обычно не встретишь у мобилок. Поэтому атомарный счётчик вполне должен быть быстрее, чем мьютексы.
Если использовать номер потока, вместе с ним нужно получать временную метку каждый раз (а не только при запуске). Из-за этого нам придётся преобразовывать в строку больше значений, чем в случае, когда нам достаточно лишь время запуска и мы можем преобразовать в строку её одни раз при запуске.
вместе с ним нужно получить временную метку каждый раз
Зачем? Что не так с меткой времени при запуске всего приложения + номер потока? Да и в любом случае, генерируется это только 1 раз - при запуске потока, врятли у вас невероятно много потоков генерируется, так что на производительность влияет слабо (относительно варианта когда вы время получаете на каждую генерацию уид). Внутри потока будет только преобразование счетчика в строку, инкремент его, конкатенация 2х строк: счетчика, префикса потока (состоящего из метки времени запуска приложения и номера потока).
Если человек поменял время в настройках, то временная метка тоже может поменяться. И есть очень маленький риск запустить приложение в один и тот же момент времени после смены времени в настройках. Для этого нужно случайное число, чтобы риск нивелировать до минимума.
Насчёт изменения счётчика внутри потока: вы предлагаете хранить счётчик в ThreadLocal, чтобы использовать обычный Long, а не AtomicLong?
Если человек поменял время в настройках
...то можно поймать коллизию. Мне кажется, это настолько слабо вероятным, что можно пренебречь (это надо секунду в секунду попасть моментом запуска приложения после смены времени). Но если совсем не хотите пренебрегать - то я бы шел по идее префикса: если хотите случайное число, то лучше его один раз при запуске сгенерировать и сохранить в префиксе (а не дергать ГПСЧ на каждое создание уида).
Насчет изменения счетчика внутри потока...
Да. Раз каждый поток в своей области нумерации из-за префикса, содержащего номер потока - то можно использовать обычные примитивные типы для счетчика внутри пространства потока. Потокобезопасность тут уже не нужна, поэтому обертки вокруг примитивов, добавляющие блокировки совместного доступа - лишняя потеря производительности и лишние потенциальные ожидания потоков друг друга на этой блокировке.
По поводу префикса - он и генерируется один раз при запуске. Цитата из статьи:
Для оптимизации процесса временная метка и случайное число генерируются один раз при запуске приложения
По поводу ThreadLocal + Long vs AtomicLong будет интересно сравнить, чтобы быстрее (при малой конкуренции потоков и при высокой)
Ну очень спорное решение как с точки зрения анализа проблемы, так и с точки зрения архитектуры. Я не верю, что профилирование приложения показало что генерация UUID это узкое место. А с точки зрения архитектуры, вы заменили стандартный инструмент, про достоинства и недостатки знают все, на какой-то свой велосипед. Бизнес требования будут меняться и раньше или позже (скорее раньше) вы со своего велосипеда упадете. Палку в переднее колесо вы уже считай ткнули.
Я не верю, что профилирование приложения показало что генерация UUID это узкое место
Профилирование этого и не показывало (обычно на экранах всегда есть проблемы похуже). Здесь больше про то, что в некоторых ситуациях (при разработке общих элементов) может оказаться, что особо оптимизировать нечего больше, но при этом в коде есть генерация UUID. Поэтому почему бы не рассмотреть, а нужен ли он в данном месте и можно ли его чем-то заменить, чтобы ускорить. И статья в этом плане просто эксперимент.
Бизнес требования будут меняться и раньше или позже (скорее раньше) вы со своего велосипеда упадете.
Так можно сказать и про автоинкрементальный ID в БД. И как показывает практика, от того, что в SQLite у нас автоинкрементальный ID (даже для элементов с бэка, у которых свой ID), из-за новых хотелок бизнеса не приходилось переделывать его на UUID. По аналогии почему тогда в похожих кейсах, где неудобно использовать автоинкремент из бд не использовать свою генерацию ID.
вы заменили стандартный инструмент, про достоинства и недостатки знают все, на какой-то свой велосипед
Есть такой фактор, но это не повод не пробовать сделать своё. В больших приложениях столько своих велосипедов из-за того, что стандартные решения часто не подходят или медленны в конкретных кейсах. И тем не менее нормально живут такие приложения. И тут уже нужно от конкретного случая смотреть, нужно ли в вашем коде такое или нет. Стандартных методов генерации ID (через бэк, автоинкремент в локальной бд или UUID.randomUUID()), вполне хватит в 95+% мест и тем более для средних приложений.
Здесь больше про то, что в некоторых ситуациях (при разработке общих элементов) может оказаться, что особо оптимизировать нечего больше, но при этом в коде есть генерация UUID.
То есть это чисто гипотетический пример в статье, не решающий какой-то реального кейса?
Код с UUID, который побудил изучить эту тему был реальный (на одном из прошлых проектов). Но реализация собственного ID в реальном коде не применялась
речь не про использование UUID, а про пример в мобильнои приложении, где получение UUID существенно сказывается на производительности приложения и отражается на пользователе
Хотя, вероятно в мобильных играх или трейдинговых (есть такие под мобилку?) такое и может быть, но тут блог WB и, лично я, пока не могу представить такого кейса в вашем приложении...
где получение UUID существенно сказывается на производительности приложения и отражается на пользователе
Такого места нет. Это больше как один из этапов возможной оптимизации, который по отдельности вообще не будет заметен пользователю. Но несколько подобных этапов для слабый устройств вполне можно будет заметить.
В WB такого и вправду нету, так как использования UUID больше единичные (проверял по коду до выпуска статьи)
(не туда ответил)
(не туда ответил)
Чел, вы не в состоянии синхронизировать мобильную корзину с десктопной. О каком перформансе может быть речь?
А если просто сгенерировать в начале сессии честный рандомный guid, а потом инкрементально к нему конкатенировать инкремент или таймстемп?
Получится строка подлиннее, но уникальная + можно трейсить айдишники принадлежащие одной и той же сессии.
А генерироваться будут мгновенно.
По сути это такой же вариант, как и в статье по принципу (префикс (64 бита), сгенерированный один раз при запуске + счётчик (64 бита)). Только тут будет 128 бит рандомного префикса и 64 бита счётчика. Увеличение длины - это также дольше расчёт hashcode и больше памяти для хранения. Не уверен, насколько стоит так делать
Седьмая версия UUID в дополнение к каноническому виду имеет три альтернативных метода реализации, и их вдобавок можно комбинировать. Вполне можно было реализовать что-то для описанного случая, не отклоняясь от RFC 9562. Например, если тормозит криптостойкий генератор случайных чисел, то случайный сегмент можно было укоротить за счет добавления субмиллисекундного сегмента и/или счетчика, инициализируемого случайным числом (с использованием предусмотренных RFC 9562 мер защиты от переполнения счетчика). Или нагенерить случайных чисел впрок.
Тот самый случай когда один короткий комментарий полезнее статьи! Респект бро
Заменяя случайные биты в 7 версии на время мы лишь приблизимся к производительности версии 6. Основная проблема - строковое представление в BASE16, что дольше делать, чем BASE32 + невозможность предгенерации префикса (или любой другой части) при запуске приложения
А нагенерить пул объектов, как уже предлагали выше - вполне хорошая идея, но нужно будет решить несколько корнер кейсов (многопоточка и если не успели заполнить пул, а требуются новые ID, чтобы не было деградаций)
RFC 9562 рекомендует для БД бинарное 128-битовое представление UUID, если это возможно. Например, для этого хорошо подходит тип данных UUID в PostgreSQL. Для других систем я бы тоже посоветовал по возможности использовать бинарное внутреннее представление.
Для текстового представления могу посоветовать кодировку Crockford's Base32. Что-то близкое будет добавлено в RFC 9562 - сейчас авторы RFC 9562 это активно обсуждают. Но совместимость Crockford's Base32 с будущим стандартом маловероятна, так как алфавит, возможно, немного изменится, и последние два бита, возможно, будут использованы под контрольную сумму.
Зачем нужна предгенерация префикса (или любой другой части) при запуске приложения - мне непонятно.
А вообще тема производительности именно генерации UUID - надуманная. Для БД UUID генерятся заведомо быстрее, чем БД способна создать записи в таблице, где используются эти UUID. То есть, производительность генераторов UUID избыточная.
Вы пишите со стороны бэкенда. Я больше смотрел в контексте генерации и хранении в мобильном приложении, в том же UI слое (нечастые кейсы, но бывают).
Про обсуждение Base32 - спасибо, посмотрю драфт.
Зачем нужна предгенерация префикса (или любой другой части) при запуске приложения - мне непонятно.
Предгенерация префикса как один из способов оптимизации генерации. Но способ с предгенерацией пула UUID всё же кажется удачнее.
Пишем свой генератор ID для мобильных приложений