Интро
Каждая таблица в SQLite по умолчанию содержит приватный ключ на основе автоматически генерируемого 64-битного целого. Это эффективно и удобно в большинстве ситуаций. Неудобства начинаются, пожалуй, только в двух случаях:
- когда диапазона 64 бит не хватает (тогда стоит задуматься о целесообразности SQLite задаче)
- когда хранилище становится "распределенным"
Может показаться, что и второй задачи в комбинации с SQLite не должно возникать, но распределенность не всегда означает что-нибудь вроде BigData. Типичный пример (из-за чего лично мне и понадобилось исследование на эту тему) это приложение с возможностью синхронизации данных между устройствами. Это может быть как что-то небольшое, как записная книжка, так и более нагруженное, как история браузера. Проблемой тут становится не столько объем данных, сколько слияние нескольких баз. Очевидно, что целочисленные счетчики записей, начинающие отсчет с 1, неизбежно будут выдавать конфликтующие последовательности, а значит использовать их в качестве уникального идентификатора записи на нескольких устройствах уже нельзя. Можно заморочиться с разделением на поддиапазоны или "сдвиганием" айдишников записей перед их передачей, но это все кривые и хрупкие костыли. Никто так не делает, конечно же. Вместо этого каждое устройство присваивает своим записям что-нибудь вроде GUID-а – просто и надежно.
GUID в качестве первичного ключа
GUID это случайное "число", длиной в 128 бит. То есть в БД это будет 16 байт в виде BLOB-а, либо минимум 32 байта в виде строки. Определенный оверхед (особенно, если остальные столбцы небольшие) по сравнению с дефолтным ключом, который хранится очень эффективно: обычно там не 8 байт, а столько, сколько требует для представления значение ключа. Этот оверхед ради решения задачи мы готовы платить, но не хотим усугублять – поэтому конечно же предпочитаем хранение в бинарном виде, а не текстовой строкой.
Что ж, объявить столбец с блобом несложно, сделаем примитивную табличку:
CREATE TABLE records (id BLOB PRIMARY KEY, data CHARACTER);Можно еще добавить WITHOUT ROWID в качестве спецификатора таблицы для оптимизации – чтобы SQLite не добавляла и не поддерживала неявный ключевой столбец.
Тему можно было бы закрывать, если бы не желание заставить БД самостоятельно генерировать айдишники, так же, как в случае с дефолтным целочисленным ключом. Что ж, если нет принципиального требования иметь настоящие GUID (которые не совсем просто рандомное число, а имеют несколько предопределенных бит), то это тоже легко:
CREATE TABLE records (id BLOB PRIMARY KEY DEFAULT (randomblob(16)), data CHARACTER);На этом можно было бы вновь остановиться, если бы не перфекционизм. Забегая вперед, скажу, что даже с перфекционизмом тяжелой формы на этом и стоит остановиться, если вы не собираетесь вставлять в БД миллионы записей. А вот если может быть так, что собираетесь, то стоит обратить внимание, что длинное случайное число не очень хорошо подходит в качестве ключа по той причине, что его дороже индексировать: просто складывать записи одну за другой и надеяться на быстрый поиск уже не выйдет.
Проблема эта к счастью давно и успешно решена и решение адаптировано на многие БД. Вкратце там все просто: первые 6 байт идентификатора заменяются на timestamp. В результате записи создаются сразу (частично) упорядоченными, что сильно облегчает их индексацию. Вероятность коллизий при этом увеличивается, но незначительно. И снова история закончилась бы ровно на этом месте, если бы в Android-ном API SQLiteDatabase позволяла определять внешние функции, чтобы сгенерировать гуидоподобный BLOB. Можно конечно генерить их и в Java-коде и биндить ко всем запросам на вставку, но это неспортивно. Кроме того, могут быть другие причины не делать этого. Например необходимость держать "глобальные" идентификаторы отдельно от "локальных", генерируя их по мере необходимости при помощи триггера.
Ну хорошо, взять 6 байт от unix timestamp с грехом пополам можно так:
SELECT round((julianday('now') - 2440587.5) * 86400000) & 0xFFFFFFFFFFFF AS ts;Результатом будет число. Например, такое: 1489877740453 – на момент написания статьи. Хорошие новости в том, что оно обычно будет неубывающим, и его можно считать средствами самой БД. Но дальше начинаются некоторые сложности. Дело в том, что в SQLite очень ограниченный набор функций для работы с BLOB: только обрезать (substr()) и склеить (||). И как заставить интерпретировать число в качестве строки байтов, непонятно. То есть можно конечно сделать CAST(... AS BLOB), но это не то: оно переведет число в строку, а потом возьмет байты полученной строки – то есть превратит 6 байт в 13. Даже если предварительно отформатировать в шестнадцатиричное представление, будет много – 12. Не катит.
Преобразование числа в BLOB
… в SQLite невозможно – ответит вам google и stackoverflow. Так-то оно, конечно, правда, но если очень хочется, то вообще-то можно. В Интернете мне ничего найти не удалось, и пришлось изобрести самому. Сразу скажу: это будет грязно :)
Итак, у нас есть склейка (||), значит, имея две байтовые строки – timestamp и случайную часть – мы могли бы получить COMB Джимми Нельсона:
SELECT ts_bytes || randomblob(10);Искомые ts_bytes это всего лишь строка из 6 байт, представляющая целое число. Давайте еще раз взглянем на него: 1489877740453. Или 0x 01 5A E3 A2 2B A5. Если бы могли взять по отдельности каждый байт в виде BLOB-а, и склеить их вместе – даже в ручном режиме это всего (и всегда) 6 склеек. Что ж, попробуем разделить число на байты. Их числовые значения можно получить при помощи небольшой арифметики:
- первый:
ts >> 40 == 1(0x01) - второй:
(ts >> 32) % 256 == 90(0x5A) - третий:
(ts >> 24) % 256 == 227(0xE3) - ...
Но, опять же, это пока не байты. Интерпретатор SQLite будет считать это просто числами:
SELECT typeof( (1489877740453 >> 24) % 256 );
integerА нам нужен BLOB. BLOB из одного байта, представляющего полученное число. Явно мы это сделать не можем, но если бы у нас было что-то вроде таблицы – значений байта-то всего 256 штук. Тут мы вспоминаем о второй операции, доступной в SQLite и возвращающей байты – substr, которая по индексу возвращает подстроку букв или байт. Бинго! Захардкодим все значения байта в строку, где индексом само значение этого байт и будет. К счатью, можно записывать бинарный литерал при помощи синтаксиса вида x'DEADBEEF':
SELECT X'
000102030405060708090A0B0C0D0E0F
101112131415161718191A1B1C1D1E1F
202122232425262728292A2B2C2D2E2F
303132333435363738393A3B3C3D3E3F
404142434445464748494A4B4C4D4E4F
505152535455565758595A5B5C5D5E5F
606162636465666768696A6B6C6D6E6F
707172737475767778797A7B7C7D7E7F
808182838485868788898A8B8C8D8E8F
909192939495969798999A9B9C9D9E9F
A0A1A2A3A4A5A6A7A8A9AAABACADAEAF
B0B1B2B3B4B5B6B7B8B9BABBBCBDBEBF
C0C1C2C3C4C5C6C7C8C9CACBCCCDCECF
D0D1D2D3D4D5D6D7D8D9DADBDCDDDEDF
E0E1E2E3E4E5E6E7E8E9EAEBECEDEEEF
F0F1F2F3F4F5F6F7F8F9FAFBFCFDFEFF' as b;Это слегка псевдокод, потому что переносить строки так нельзя, но так нагляднее, а в коде можно и в одну строку отформатировать. Зато теперь все, что осталось сделать, это "вырезать" нужный байт из таблицы и склеить с другими. Шесть раз:
SELECT
substr(b, (ts >> 40) + 1, 1) ||
substr(b, (ts >> 32) % 256 + 1, 1) ||
substr(b, (ts >> 24) % 256 + 1, 1) ||
substr(b, (ts >> 16) % 256 + 1, 1) ||
substr(b, (ts >> 8) % 256 + 1, 1) ||
substr(b, ts % 256 + 1, 1) ||
randomblob(10);Псевдо-GUID в бинарной форме готов! На самом деле SQLite пока что будет считать получаенную строку байт "текстом", но CAST(... AS BLOB) сделает все, как надо. Вообще-то это даже обязательно, потому что иначе чтение из этого столбца будет возвращать не 16 байт, как ожидается, а 17 – с нулевым терминатором строки. Осталось подставить выражение в качестве значения столбца по умолчанию.
Автовставка идентификаторов
Просто запихнуть весь этот "поезд" внутрь DEFAULT(...) в определении столбца таблицы нельзя, потому что там должны быть только "простые" выражения, а нам нужны вложенные SELECT-ы, чтобы избежать копипасты и множественных вычислений одного и того же.
К счастью, в SQLite есть триггеры, с помощью которых можно модифицировать строки на лету при вставке. К сожалению, ни фаза BEFORE INSERT, ни AFTER INSERT не подходят для обслуживания PRIMARY KEY, т.к. для удовлетворения неявного условия NOT NULL значение столбца нужно обязательно указывать в изначальном запросе. К тому же, для таких триггеров UPDATE-выражение снова позволяет только примитивные выражения. Зато доступен тип триггеров INSTEAD OF INSERT, который как раз может создать новую запись на основе переданных значений с добавлением сгенерированного блоба. Есть с ним только одна особенность, не указанная в документации: триггер INSTEAD OF INSERT нельзя создать на таблицу. Можно только на VIEW.
В итоге схема выстраивается следующая:
- основная таблица явно используется только для чтения
- запросы на запись идут во VIEW-пустышку с триггером на вставку
- триггер генерирует BLOB и делает вставку в основную таблицу
CREATE TABLE records (id BLOB PRIMARY KEY, data CHARACTER) WITHOUT ROWID;
CREATE VIEW fake AS SELECT NULL as ts, NULL as data;
CREATE TRIGGER auto_guids INSTEAD OF INSERT ON fake BEGIN
INSERT INTO records(id, data) SELECT CAST(new_guid AS BLOB), NEW.data FROM (
SELECT
substr(b, (ts >> 40) + 1, 1) ||
substr(b, (ts >> 32) % 256 + 1, 1) ||
substr(b, (ts >> 24) % 256 + 1, 1) ||
substr(b, (ts >> 16) % 256 + 1, 1) ||
substr(b, (ts >> 8) % 256 + 1, 1) ||
substr(b, ts % 256 + 1, 1) ||
randomblob(10) AS new_guid FROM (SELECT
round((julianday('now') - 2440587.5) * 86400000) & 0xFFFFFFFFFFFF as ts,
x'000102030405060708090A0B0C0D0E0F...' as b
)
);
END;Читаем как обычно:
SELECT * FROM records;А записываем так:
INSERT INTO fake (data) VALUES ('Hello COMBs!');Можно было положить таблицу байт в отдельную VIEW ради удобочитаемости, но это несколько негативно сказывается на производительности. Также можно было оставить первичный ключ на целоцисленном счетчике, сделать столбец guid просто уникальным и написать триггер ON AFTER INSERT, которы бы "передобавлял" строку с новым guid, но, забегая чуть вперед, скажу, что это медленнее примерно на 30%. Кстати, самое время посмотреть на производительность.
Производительность
Очевидно, что склейка байтов вручную медленнее встроенной функции randomblob(). Выигрыш должен появиться на большом количестве вставок. Проведем замеры. Сравнивать будем "обычный" целочисленный ROWID, ключ на основе randomblob(16) и наши частично упорядоченные блобы (COMBs, как их назвали в вышеупомянутой статье).
Тестовый сценарий таков:
- три транзакции вставок по миллиону записей
- случайная выборка всех вставленных записей по id
Время записи замеряется как для каждой серии, так и внутри через каждые 20% записей. Тесты запускались в эмуляторе Android 6.0 (SQLite 3.8.10). Исходники тут.
На графике: время вставки каждой последующей порции из 200 тысяч записей. Эталон производительности, понятное дело, дефолтный целочисленный индекс (синяя линия). Его скорость не зависит от количества последовательных вставок. Желтная линия (COMBs) это наш пациент. Его скорость также практически постоянна, хотя и ниже на 55-59%. А красная линия это таблица с первичным ключом на randomblob(16). Видно, что, начиная всего на 11% медленнее INTEGER PRIMARY KEY, где-то после первого миллиона вставок ее накладные расходы на поддержание индекса превышают частично упорядоченные последовательности и продолжают расти, достигая 75% замедления к концу 3го миллиона.
На самом деле COMB можно сделать еще быстрее. Текущая проблема заключается в том, что с миллисекундной точностью временных отметок соседние строки выстраиваются в кластеры по 18-20 штук, где первые 6 байт (таймстамп) – одинаковые, частично возвращая проблему упорядочивания случайных байт. Если к таймстампу каким-то образом прибавлять порядковый номер добавляемой записи (хотя бы внутри транзакции), это снизит оверхед до 29-34% по сравнению с "INT" и даст выигрыш по сравнению с randomblob(16) уже после 500 тысяч записей.
Недостаток в том, что в простейшем случае порядковый номер нужно передавать из управляющего кода, а этого делать не хочется по условиям задачи. Кроме того, уже и так можно сделать выводы.
Выводы
SQLite сама по себе очень неплохо управляется с индексированием даже чего-то GUID-о-подобного.
Если предполагаемый объем данных не превышает хотя бы 500 тысяч записей, чистый randomblob() обладает вполне приемлемой производительностью. Я в своем текущем проекте поэтому скорее всего его и выберу.
Даже если записей будет много, но вставляются они редко или, тем более, в виде единичных записей, тип первичного ключа не будет играть вообще никакой роли в производительности. Одна только фиксация транзакции (в Android с дефолтными настройками БД) занимает порядка 20-50 миллисекунд. И в разы больше, если система IO поднагружена. Вставка записи внутри массовой транзакции, которая происходит за микросекунды, по сравнению с этим занимает ничтожное время при любом раскладе.
В SQLite можно превращать числа в BLOB – было бы желание :)
Комментарии (24)
Ivan22
23.03.2017 12:24а старым дедовским — pk = id_row + id_device нельзя?
knuckles
23.03.2017 13:37+1Сливать вместе можно. А вот адресовать потом такие записи мне показалось неудобно. Надо всюду таскать эти два значения. А самое плохое, что, если в старом коде, например, забыли запрос, обращающийся только по id_row – он ведь продолжит работать, но будет всегда возвращать какую-то одну запись из нескольких с одинаковыми id_row. Инварианты гарантировать сложнее, короче.
oxidmod
23.03.2017 13:51-2Нужно просто завести VO Identifier, и вместо инта/строки тягать за собой его) Я правда не разбираюсь в разработке под яблоко, не знаю юзают ли там какието абстракции над бд и мапят ли строки на объекты… мож у вас там все на примитивах))
GreenStore
23.03.2017 13:24GUID это случайное «число», длиной в 128 бит. То есть в БД это будет 16 байт в виде BLOB-а, либо минимум 32 байта в виде строки.
… либо два столбца с 64-битным числом, являющимся составным ключом (composite primary keys)…
CREATE TABLE something ( column1 NOT NULL, column2 NOT NULL, column3, PRIMARY KEY (column1, column2) );
https://www.sqlite.org/lang_createtable.htmlknuckles
23.03.2017 13:46Можно. Но асимптотика скорости будет такой же, как у randomblob(16).
Плюс все неудобства работы с двумя столбцами вместо одного (комментарий выше).
irbis_al
23.03.2017 13:38А я использую два ключа… один обычный… и реляционные отношения строятся на нём… другой guid для синхронизации с центральной СУБД.(Она не sqllite)
sebres
23.03.2017 15:10+1GUID это случайное "число"
GUID это уникальный ID, значительная часть которого действительно является псевдослучайной последовательностью (но он однозначно не является случайным).
Иначе вы теоретически могли бы сгенерировать 2-а одинаковых GUID на двух разных устройствах (что на самом деле технически исключено).
Про триггер: sqlite легко расширяется собственными функциями практически на любом языке программирования, т.е. триггер не нужен, достаточно добавить default (expr), вот пример на TCL:
% db function UUID {uuid -binary} % db eval {CREATE TABLE records (id BLOB DEFAULT (UUID()) PRIMARY KEY, data CHARACTER)} % db eval {insert into records (data) values ('test')} % db eval {select * from records} ????Ne3?^?yX???? test
Ну и чтоб два раз не ходить, отвечу всем вышекомментировавшим про составной комби-PK по двум ключам:
- сложнее делать выборку по ID, например если join нежелателен (или невозможен) типа подзапроса.
Попробуйте переписать с составным ID:
select * from records where id in (select rec_id from subrecords where ... group by ...)
- будет не сильно но медленнее (как минимум если ID перерастут signed int32), вот ниже замеры для наглядности:
-- blob primary -- CREATE TABLE records (id BLOB PRIMARY KEY, data CHARACTER) ... insert into records values (x'9bbaa28c4ee9b394189aff58a58f85f7', 'test') insert into records values (x'bf8bdf314779cb74caac36844b60bd85', 'test') -- select 1 from records where id = x'bf8bdf314779cb74caac36844b60bd85' limit 1 -- 1.061206 µs/# 9151569 # 942323 #/sec 9711.703 nett-ms -- composite primary -- CREATE TABLE records2 (id INTEGER, id2 INTEGER, data CHARACTER, PRIMARY KEY (id, v1)) ... insert into records2 values (2147483647, 2147483647, 'test') insert into records2 values (2147483648, 2147483648, 'test') select 1 from records2 where id = 2147483647 and id2 = 2147483647 limit 1 -- 1.068456 µs/# 9091251 # 935929 #/sec 9713.603 nett-ms select 1 from records2 where id = 2147483648 and id2 = 2147483648 limit 1 -- 1.111840 µs/# 8746288 # 899410 #/sec 9724.472 nett-ms
Если что измерял prepared, на in-memory базе, чисто время исполнения запроса.
Ivan22
23.03.2017 18:25select * from records where id in (select rec_id from subrecords where… group by ...)
select *
from records
inner join
(
select rec_id, rec_id2 /* composite key */
from subrecords
where…
group by rec_id, rec_id2
) sub on sub.rec_id = id and rec_id2 = id2
— всегда так делаю вместо in
sebres
23.03.2017 19:05Ну делать-то я положим тоже так делаю (когда оно оправдано)…
А вы при случае на execution plan гляньте.
Вот простейший случай — без group by и т.д. (тупо слить из первой все, присутствующие и во второй таблице):
CREATE TABLE records (id BLOB PRIMARY KEY, data CHARACTER) CREATE TABLE subrecords (subid BLOB, ...) EXPLAIN QUERY PLAN select * from records where id in ( select subid from subrecords ) 0 0 0 SEARCH TABLE records USING INDEX sqlite_autoindex_records_1 (id=?) (~25 rows) 0 0 0 EXECUTE LIST SUBQUERY 1 1 0 0 SCAN TABLE subrecords (~1000000 rows) CREATE TABLE records2 (id INTEGER, id2 INTEGER, data CHARACTER, PRIMARY KEY (id, id2))} CREATE TABLE subrecords2 (subid INTEGER, subid2 INTEGER, ...)} EXPLAIN QUERY PLAN select * from records2 inner join (select subid, subid2 from subrecords2) sub on sub.subid = id and sub.subid2 = id2 0 0 1 SCAN TABLE subrecords2 (~1000000 rows) 0 1 0 SEARCH TABLE records2 USING INDEX sqlite_autoindex_records2_1 (id=? AND id2=?) (~1 rows)
Вопрос: почему и когда второй вариант может стать сильно медленнее (а главное когда это будет очень-очень критично). (Подсказка — N x M + concurrency).
knuckles
23.03.2017 19:10-1GUID это уникальный ID, значительная часть которого действительно является псевдослучайной последовательностью (но он однозначно не является случайным).
Зависит от реализации. Если используется аппаратный источник энтропии, то результат случайный.
Иначе вы теоретически могли бы сгенерировать 2-а одинаковых GUID на двух разных устройствах (что на самом деле технически исключено).
Каким же образом это «исключено»? :) Вы сами себе противоречите. Любой PRNG (если мы говорим о них), очевидно, может сгенерировать один и тот же результат сколько угодно раз. Но даже и в случае с истинно случайным шумом вероятность получить одинаковый UUID на двух машинах ненулевая. Просто она настолько мизерная, что ей легко пренебрегают в любой практической задаче.
Про триггер: sqlite легко расширяется собственными функциями практически на любом языке программирования, т.е. триггер не нужен, достаточно добавить default (expr)
Я в курсе про внешние функции. Если бы вы внимательно читали, но заметили бы, что это невозможно на Android (без поставки с приложением собственной сборки SQLite).sebres
23.03.2017 19:23+1Если используется аппаратный источник энтропии
Не используется там никакие источники энтропии — ибо GUID по определению криптографически нестоек.
Каким же образом это «исключено»? :) Вы сами себе противоречите.
Вы возможно слово "часть" пропустили в предложении "значительная часть которого действительно является псевдослучайной последовательностью".
Во всех известных мне реализациях оного, там еще замешивают pid, tid, mac, clicks и тому подобное.
Если бы вы внимательно читали, но заметили бы, что это невозможно на Android
Если вы чего-то не умеете (не можете) — это еще не значит, что оно не возможно.
И собственная сборка SQLite для этого абсолютно не нужна.knuckles
23.03.2017 20:09Если вы чего-то не умеете (не можете) — это еще не значит, что оно не возможно.
И собственная сборка SQLite для этого абсолютно не нужна.
Давайте по существу, покажите решение. Только без хаков в виде выковыривания закрытых методов через reflection.sebres
23.03.2017 20:22Ну да SQLiteCustomFunction с рефлектом… А чему он хак-ом стал вдруг? Т.е. вы считаете trigger (который вообщето совсем для других целей придуман) менее хакиш вэй. Ну тады ОК.
knuckles
23.03.2017 20:46А чему он хак-ом стал вдруг?
Тем, что его работоспособность не то, что не гарантируется, а даже не заявлена. Если сигнатура функции поменяется, или она просто пропадет, ваш код сломается.
А триггер это публичный АПИ общего назначения (где цель выбирает сам разработчик) с задокументированным и предсказуемым поведением.
knuckles
23.03.2017 20:17Во всех известных мне реализациях оного, там еще замешивают pid, tid, mac, clicks и тому подобное.
Это называется «технически исключено» у вас?
В любом случае, я не очень понимаю, с чем вы спорите. С тем, что я написал «случайное число» вместо «псевдослучайный идентификатор»? :)sebres
23.03.2017 20:59технически исключено
Ну оно к тому стремится… Просто цель-то у него — "глобально уникальный", а не "случайный" т.е. менее зависим от тех же начальный и текущий сид, энтропии и т.п.
Если у вас там даже хэш от uuid хоста замешан будет оно уже менее зависимо от "случайностей"…
Я про то, что законы Мерфи еще никто не отменял — "если есть вероятность того, что какая-нибудь неприятность может случиться, ...." (я про коллизию, как бы мизерна не была вероятность последней).
Да я и не спорю: то просто замечание было про между прочим (ибо режет глаз). В любом случае придумывать собственную реализацию guid, да еще и триггером обернуть имхо как-то не комильфо (о чем и поведал, выразив свое мнение, с которым совсем не обязательно нужно быть согласным).
П.С. Вот в качестве примера: возьмем nginx-cache-модуль — раньше ключи там не сравнивали (т.е. тупо считалось, что т.к. вероятность коллизии хэша никакая, то достаточно сравнить хэш и все).
И всем известный персонаж спорил с пеной у рта, что оно достаточно, и не нужно это, про всякие "дни рождения" рассказывал и т.д.
Вот там я действительно спорил и настаивал, потому что во первых, хэш — это хэш — он там для скорости а не для крипто-стойкости, во вторых это очень просто и доп. сравнение стоит гроши. А в третьих я их (коллизии) там лично встречал (на очень большом и длинном кэш), причем доказуемо (хорошо еще что на тест-стенде, а не в продакшн).
При том что частью ключа кэша может быть например user-id и nginx тогда при возникновении той "невозможной" коллизии покажет к примеру приватную информацию другому пользователю.
И побоку тогда, что коллизии маловероятны — в корпоративном секторе вы за такое как минимум с работы вылетаете.
Подробнее тут и в мэйл-архивах nginx можно поискать.
Фикс то пустяковый, но нужно же сперва поспорить… Вероятности, это такое дело — их нужно уметь готовить.
Все хотел про то статью тиснуть, да некогда — пусть побудет комментом.
- сложнее делать выборку по ID, например если join нежелателен (или невозможен) типа подзапроса.
GreenStore
23.03.2017 18:15-1Иначе вы теоретически могли бы сгенерировать 2-а одинаковых GUID
Вероятность этого настолько мала, что этим можно пренебречь.
См. Парадокс дней рождения.sebres
23.03.2017 23:03+1Вот только не надо про вероятности, интуитивное восприятие и т.п.
Вы кстати не поняли этот парадокс — он говорит как раз про обратное, что совпадения более вероятны, чем интуитивно воспринимается (ибо например для 23-х людей — на самом деле сравниваем 253 возможные пары).
И закроем тему интуитивного восприятия на этом. Расскажите про "день рожденья" кому-нибудь другому (когда поймете).
Теперь по теме: лично видел два одинаковых UUID, созданных на двух разных хостах в одном (правда большом и сильно нагруженном пуле) кластера.
И то было в industries API 80-го уровня. Я бы вам даже имя сказал, но низя (связан подписью о не разглашении)…
Однако с тех пор там та конкретная реализация UUID-api (рандомная кстати, ибо v4) — под строжайшим запретом (бьют по рукам если что).
А так-то да — теоретически невероятно...
Раз уж слово вероятность упало, попробуйте оценить разницу вероятностей:
1) что два каких-то "случайных" 128-ми битных числа будут равны;
2) например в сравнении с вероятностью, что два случайных 52-битных числа + цикличный инкремент (8 бит) про процесс, созданных в течении тех же десяти миллисекунд (48 бит), с одинаковым хэшем (20 бит) взятым от fqdn + thread-id — в результате тоже будут одинаковы;
Вам сразу вопрос: тут фактор времени или количества чисел вообще в выборке важен или нет? Т.е. вопрос два числа из скольких...
Поэтому, сделаем тут некоторые допущения — уточнения условий задачи:
- одно-поточно реально создать максимально 1000 ключей за одну миллисекунду (только вот что с ними делать с такой-то скоростью, ну да пусть)
- имеем 256 потоков на машинке
- имеем ну пусть будет 100 машин в кластере
- все это добро работает десятилетия.
И не забываем что:
Все это абсолютно не градиентно в первом случае, но чисто для оценки порядка:
(1000 * 1000000 * 256 * 100)— уже 2 в 45-й — и это прошу заметить в секунду.
И крайне важно во втором.GreenStore
24.03.2017 07:19-1> Раз уж слово вероятность упало, попробуйте оценить разницу вероятностей: что два каких-то «случайных» 128-ми битных числа будут равны;
Так я ссылку вам и дал, что бы вы посмотрели. Там есть табличка в разделе «Применение», там все указано.
Для того, что бы была коллизия 128-битных значений с вероятностью 0,5 нужно сгенерировать более 10^19 значений.
Что бы была коллизия с вероятностью 10^-12 нужно сгенерировать более 10^13 значений (10 триллионов).
У вас в сообщении много букв, а сути мало.
Bringoff
Я так понимаю, синхронизация между устройствами происходит напрямую, без участия сервера? А чем не подходит вариант с локальным на каждом устройстве
rowidиunique indexed guidстолбцом? Почему обязательно именно primary key делать из блоба? Предполагаю, что скорость слияния, но, может, еще были какие-то причины городить такой огород? :)knuckles
Как уже было сказано, rowid все таки имеет некоторые затраты (5-10% времени по моим тестам, ЕМНИП). Если локальный id не нужен, то зачем его хранить?
Ну и все таки было желание повторить технику Джимми Нильсона максимально близко к оригиналу.
Проект скорее исследовательский. В конце я и говорю, что в «продакшене» мне это пока что не пригодится. Как-то так.