Pull to refresh

Comments 24

Я так понимаю, синхронизация между устройствами происходит напрямую, без участия сервера? А чем не подходит вариант с локальным на каждом устройстве rowid и unique indexed guid столбцом? Почему обязательно именно primary key делать из блоба? Предполагаю, что скорость слияния, но, может, еще были какие-то причины городить такой огород? :)

Как уже было сказано, rowid все таки имеет некоторые затраты (5-10% времени по моим тестам, ЕМНИП). Если локальный id не нужен, то зачем его хранить?
Ну и все таки было желание повторить технику Джимми Нильсона максимально близко к оригиналу.
Проект скорее исследовательский. В конце я и говорю, что в «продакшене» мне это пока что не пригодится. Как-то так.
а старым дедовским — pk = id_row + id_device нельзя?
Сливать вместе можно. А вот адресовать потом такие записи мне показалось неудобно. Надо всюду таскать эти два значения. А самое плохое, что, если в старом коде, например, забыли запрос, обращающийся только по id_row – он ведь продолжит работать, но будет всегда возвращать какую-то одну запись из нескольких с одинаковыми id_row. Инварианты гарантировать сложнее, короче.
UFO just landed and posted this here
UFO just landed and posted this here
GUID это случайное «число», длиной в 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.html
Можно. Но асимптотика скорости будет такой же, как у randomblob(16).
Плюс все неудобства работы с двумя столбцами вместо одного (комментарий выше).
А я использую два ключа… один обычный… и реляционные отношения строятся на нём… другой guid для синхронизации с центральной СУБД.(Она не sqllite)
GUID это случайное "число"

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}
?º¢?Né3?↑?ÿX¥??÷ 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 базе, чисто время исполнения запроса.

select * 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

Ну делать-то я положим тоже так делаю (когда оно оправдано)…
А вы при случае на 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).

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

Зависит от реализации. Если используется аппаратный источник энтропии, то результат случайный.

Иначе вы теоретически могли бы сгенерировать 2-а одинаковых GUID на двух разных устройствах (что на самом деле технически исключено).

Каким же образом это «исключено»? :) Вы сами себе противоречите. Любой PRNG (если мы говорим о них), очевидно, может сгенерировать один и тот же результат сколько угодно раз. Но даже и в случае с истинно случайным шумом вероятность получить одинаковый UUID на двух машинах ненулевая. Просто она настолько мизерная, что ей легко пренебрегают в любой практической задаче.

Про триггер: sqlite легко расширяется собственными функциями практически на любом языке программирования, т.е. триггер не нужен, достаточно добавить default (expr)

Я в курсе про внешние функции. Если бы вы внимательно читали, но заметили бы, что это невозможно на Android (без поставки с приложением собственной сборки SQLite).
Если используется аппаратный источник энтропии

Не используется там никакие источники энтропии — ибо GUID по определению криптографически нестоек.


Каким же образом это «исключено»? :) Вы сами себе противоречите.

Вы возможно слово "часть" пропустили в предложении "значительная часть которого действительно является псевдослучайной последовательностью".
Во всех известных мне реализациях оного, там еще замешивают pid, tid, mac, clicks и тому подобное.


Если бы вы внимательно читали, но заметили бы, что это невозможно на Android

Если вы чего-то не умеете (не можете) — это еще не значит, что оно не возможно.
И собственная сборка SQLite для этого абсолютно не нужна.

Если вы чего-то не умеете (не можете) — это еще не значит, что оно не возможно.
И собственная сборка SQLite для этого абсолютно не нужна.

Давайте по существу, покажите решение. Только без хаков в виде выковыривания закрытых методов через reflection.

Ну да SQLiteCustomFunction с рефлектом… А чему он хак-ом стал вдруг? Т.е. вы считаете trigger (который вообщето совсем для других целей придуман) менее хакиш вэй. Ну тады ОК.

А чему он хак-ом стал вдруг?

Тем, что его работоспособность не то, что не гарантируется, а даже не заявлена. Если сигнатура функции поменяется, или она просто пропадет, ваш код сломается.

А триггер это публичный АПИ общего назначения (где цель выбирает сам разработчик) с задокументированным и предсказуемым поведением.
Во всех известных мне реализациях оного, там еще замешивают pid, tid, mac, clicks и тому подобное.

Это называется «технически исключено» у вас?

В любом случае, я не очень понимаю, с чем вы спорите. С тем, что я написал «случайное число» вместо «псевдослучайный идентификатор»? :)
технически исключено

Ну оно к тому стремится… Просто цель-то у него — "глобально уникальный", а не "случайный" т.е. менее зависим от тех же начальный и текущий сид, энтропии и т.п.
Если у вас там даже хэш от uuid хоста замешан будет оно уже менее зависимо от "случайностей"…
Я про то, что законы Мерфи еще никто не отменял — "если есть вероятность того, что какая-нибудь неприятность может случиться, ...." (я про коллизию, как бы мизерна не была вероятность последней).


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


П.С. Вот в качестве примера: возьмем nginx-cache-модуль — раньше ключи там не сравнивали (т.е. тупо считалось, что т.к. вероятность коллизии хэша никакая, то достаточно сравнить хэш и все).
И всем известный персонаж спорил с пеной у рта, что оно достаточно, и не нужно это, про всякие "дни рождения" рассказывал и т.д.
Вот там я действительно спорил и настаивал, потому что во первых, хэш — это хэш — он там для скорости а не для крипто-стойкости, во вторых это очень просто и доп. сравнение стоит гроши. А в третьих я их (коллизии) там лично встречал (на очень большом и длинном кэш), причем доказуемо (хорошо еще что на тест-стенде, а не в продакшн).
При том что частью ключа кэша может быть например user-id и nginx тогда при возникновении той "невозможной" коллизии покажет к примеру приватную информацию другому пользователю.
И побоку тогда, что коллизии маловероятны — в корпоративном секторе вы за такое как минимум с работы вылетаете.
Подробнее тут и в мэйл-архивах nginx можно поискать.
Фикс то пустяковый, но нужно же сперва поспорить… Вероятности, это такое дело — их нужно уметь готовить.
Все хотел про то статью тиснуть, да некогда — пусть побудет комментом.

Вот только не надо про вероятности, интуитивное восприятие и т.п.


Вы кстати не поняли этот парадокс — он говорит как раз про обратное, что совпадения более вероятны, чем интуитивно воспринимается (ибо например для 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-й — и это прошу заметить в секунду.
И крайне важно во втором.

> Раз уж слово вероятность упало, попробуйте оценить разницу вероятностей: что два каких-то «случайных» 128-ми битных числа будут равны;

Так я ссылку вам и дал, что бы вы посмотрели. Там есть табличка в разделе «Применение», там все указано.

Для того, что бы была коллизия 128-битных значений с вероятностью 0,5 нужно сгенерировать более 10^19 значений.

Что бы была коллизия с вероятностью 10^-12 нужно сгенерировать более 10^13 значений (10 триллионов).

У вас в сообщении много букв, а сути мало.
Sign up to leave a comment.

Articles