Comments 86
если данные распределённые то нужно использовать UUID. Он как раз для этого и предназначен. Остальное от лукавого.
Требования по увеличения (вместо случайности) скорей всего не являются значимыми. В случае распределённых данных эти требования невозможно выполнить.
Требования по увеличения (вместо случайности) скорей всего не являются значимыми. В случае распределённых данных эти требования невозможно выполнить.
UUID не гарантирует уникальность ключа. Просто шанс на коллизию очень мал. Поэтому проверка на сервере по любому нужна.
Это заблуждение. UUID как раз и придуман для того, чтобы «проверка на сервере» была не нужна (она невозможна в распределенной системе).
Почитайте как устроен UUID и вы поймете, что надо как-то очень хитро стараться (например, крутить часы), чтобы получить хотя бы не нулевую вероятность сгенерировать два одинаковых UUID.
Почитайте как устроен UUID и вы поймете, что надо как-то очень хитро стараться (например, крутить часы), чтобы получить хотя бы не нулевую вероятность сгенерировать два одинаковых UUID.
У UUID много разных схем, не только время. Но ни одна не может гарантировать, что при достаточно плотном потоке параллельных действий не будет сгенерировано два одинаковых ключа. Это в дизайне самой UUID и в этом нет ничего плохого. Это как использовать md5/sha1/любой хешь для генерации уникальных идентификаторов (кстати, тоже одна из схем UUID).
Другое дело, что можно сначала записать обьекты в sharded-базу параллельно, без блокировок, а затем за–claim'ить ID у арбитра. Если будет коллизия, то одна из транзакций либо откатиться назад (отбросит изменения), либо повторит себя (шанс, на две коллизии подряд вообще «астрономически» мал).
Иными словами, даже с UUID нужно подходит с умом.
Другое дело, что можно сначала записать обьекты в sharded-базу параллельно, без блокировок, а затем за–claim'ить ID у арбитра. Если будет коллизия, то одна из транзакций либо откатиться назад (отбросит изменения), либо повторит себя (шанс, на две коллизии подряд вообще «астрономически» мал).
Иными словами, даже с UUID нужно подходит с умом.
Во-первых, некоторые схемы включает ID хоста, что делает невозможной коллизию на разных хостах.
Во-вторых, в тех ситуациях, когда вероятность коллизии на десятки порядков меньше вероятности ошибок исполнения кода (я имею в виду ошибки процессора), то можно считать UUID строго уникальными.
Во-вторых, в тех ситуациях, когда вероятность коллизии на десятки порядков меньше вероятности ошибок исполнения кода (я имею в виду ошибки процессора), то можно считать UUID строго уникальными.
> Во-вторых, в тех ситуациях, когда вероятность коллизии на десятки порядков меньше вероятности ошибок исполнения кода (я имею в виду ошибки процессора), то можно считать UUID строго уникальными.
Хотелось бы увидеть ссылки на исследования, где ваше утверждение бы подтверждалось…
> Во-первых, некоторые схемы включает ID хоста.
Тогда на клиенте требуется знать о хостах, о шардинге и т.п. Но даже так, никто не запрещает двум клиентам, совершенно случайно получить два одинаковых UUID для одного хоста, куда они и обращаются. Пока это не решение.
Хотелось бы увидеть ссылки на исследования, где ваше утверждение бы подтверждалось…
> Во-первых, некоторые схемы включает ID хоста.
Тогда на клиенте требуется знать о хостах, о шардинге и т.п. Но даже так, никто не запрещает двум клиентам, совершенно случайно получить два одинаковых UUID для одного хоста, куда они и обращаются. Пока это не решение.
>исследования
Ну, для простоты UUIDv4, пространство значений 2^122. Вероятность коллизии 1.9*10^-37.
Частота ошибок, например, в оперативной памяти (то есть в том числе и в загруженной версии вашей программы) 10^-10 — 10^-17 error/bit·h, то есть ~10^25 (на такт) для одного бита.
Дальше учтите, что программа у вас, скорее всего, длиннее одного бита и выполняются дольше одного такта. Ещё учтите, что ошибки есть на диске, на шине, в памяти и в процессоре.
Но даже в самом худшем случае вероятность коллизии на ~10 порядков меньше.
Ну, для простоты UUIDv4, пространство значений 2^122. Вероятность коллизии 1.9*10^-37.
Частота ошибок, например, в оперативной памяти (то есть в том числе и в загруженной версии вашей программы) 10^-10 — 10^-17 error/bit·h, то есть ~10^25 (на такт) для одного бита.
Дальше учтите, что программа у вас, скорее всего, длиннее одного бита и выполняются дольше одного такта. Ещё учтите, что ошибки есть на диске, на шине, в памяти и в процессоре.
Но даже в самом худшем случае вероятность коллизии на ~10 порядков меньше.
Плюсую, но дополню.
Алгоритм генерации uuid хотя и отличается в разных реализациях (MSSQL и MySQL под Linux точно, и я знаю что в MySQL отличается между версиями и платформами), но в целом действительно обеспечивает уникальность надежнее других методов.
Более того, 99% процентов потенциальных проблем с «неуникальностью» могут быть вызваны только неправильной настройкой и ловятся в процессе именно настройки и не попадут в продакшн.
Алгоритм генерации uuid хотя и отличается в разных реализациях (MSSQL и MySQL под Linux точно, и я знаю что в MySQL отличается между версиями и платформами), но в целом действительно обеспечивает уникальность надежнее других методов.
Более того, 99% процентов потенциальных проблем с «неуникальностью» могут быть вызваны только неправильной настройкой и ловятся в процессе именно настройки и не попадут в продакшн.
> Ну, для простоты UUIDv4, пространство значений 2^122
Логично. Но я бы все равно не доверял будь это для денег. Ошибки в железе происходят постоянно, ломаются биты в памяти, сыпятся диски. Но мы используем журналы, держим базу в целостности, она или совсем слетает или работает правильно — это видно сразу.
С коллизией UUID есть более страшная проблема, такую коллизию не сразу получиться обнаружить. Кто-то за–seed'ил свой random от времени, а не от системной энтропии и все, коллизии неизбежны.
Итог: я с вами полностью согласен, UUID *практически* уникальны. Но они по прежнему не дают гарантий уникальности. Сравнивать шансы коллизии с шансом падения железа не внушает оптимизма, т.к. в кластере на 500 машин железные ошибки всплывают постоянно… не хочется того же и для UUID.
Логично. Но я бы все равно не доверял будь это для денег. Ошибки в железе происходят постоянно, ломаются биты в памяти, сыпятся диски. Но мы используем журналы, держим базу в целостности, она или совсем слетает или работает правильно — это видно сразу.
С коллизией UUID есть более страшная проблема, такую коллизию не сразу получиться обнаружить. Кто-то за–seed'ил свой random от времени, а не от системной энтропии и все, коллизии неизбежны.
Итог: я с вами полностью согласен, UUID *практически* уникальны. Но они по прежнему не дают гарантий уникальности. Сравнивать шансы коллизии с шансом падения железа не внушает оптимизма, т.к. в кластере на 500 машин железные ошибки всплывают постоянно… не хочется того же и для UUID.
Соотвественно у ECC памяти частота ошибок (должно 2 бита сбойнуть одновременно) составляет 10^-20 — 10^-34. У диска raid-edition 10^-15. Соответственно у простейшего рейда-зеркала 10^-30. Что близко к озвученным 1.9*10^-37.
Но нужно ещё учесть момент, что с увеличением количества серверов или интенсивности генерации UUID вероятность коллизии линейно растёт. Т.е. если увеличить интенсивность генерации UUID в 1000 раз мы получим ошибку 1.9*10^-34.
А если это гугл с его миллионом серверов, то если на всех них используется UUID, то веротность коллизии 1.9*10^-31, что больше, чем вероятность сбоя железа.
Логическая коллизия при генерации UUID — это узкое звено всей системы. Если всё железо я могу настроить таким образом, что при увеличении его количества надёжность системы будет возрастать (вплоть до дублирования и троирования), то вероятность коллизий при использовании UUID будет только возрастать с увеличением нагрузки.
Одна логическая коллизия намного страшнее, чем несколько физических ошибок, которые в десятки, если не тысячи раз проще обнаружить. Более того логическая ошибка может породить тысячи других ошибок, которые будут вытекать из первой, и когда весь этот ком будет замечен, то программисты поседеют распутывая сложные взаимосвязи на десятках таблиц и серверов.
Для финансовых нагруженных приложений использование UUID это что типа русского авось. Авось пронесёт.
Но нужно ещё учесть момент, что с увеличением количества серверов или интенсивности генерации UUID вероятность коллизии линейно растёт. Т.е. если увеличить интенсивность генерации UUID в 1000 раз мы получим ошибку 1.9*10^-34.
А если это гугл с его миллионом серверов, то если на всех них используется UUID, то веротность коллизии 1.9*10^-31, что больше, чем вероятность сбоя железа.
Логическая коллизия при генерации UUID — это узкое звено всей системы. Если всё железо я могу настроить таким образом, что при увеличении его количества надёжность системы будет возрастать (вплоть до дублирования и троирования), то вероятность коллизий при использовании UUID будет только возрастать с увеличением нагрузки.
Одна логическая коллизия намного страшнее, чем несколько физических ошибок, которые в десятки, если не тысячи раз проще обнаружить. Более того логическая ошибка может породить тысячи других ошибок, которые будут вытекать из первой, и когда весь этот ком будет замечен, то программисты поседеют распутывая сложные взаимосвязи на десятках таблиц и серверов.
Для финансовых нагруженных приложений использование UUID это что типа русского авось. Авось пронесёт.
Ну, например, в платежных системах ошибки измеряются, как «деньги, которые пришлось вернуть потерпевшим на каждые $100».
Если мне не изменяет память, для систем типа MasterCard эти потери составляют 7 центов на каждые $100 (а может даже больше).
Как вы понимаете, эти потери несравнимо больше, чем те, которые может (потенциально) вызвать коллизия UUID.
Плюс, вы не берет в расчет то, что я говорю об аппаратных проблемах, которые не были замечены. Понятно, что сбой сервера легко заметить. А вот допустим у вас был искажен бит при генерации UUID. Или, допустим, не сработало условие проверки его на уникальность (потому что условный переход случайно заменился на безусловный).
То есть здесь вы пытаетесь поставить железные двери на одноэтажный дом со стеклянными окнами. Это просто экономически неэффективно.
P.S. Я допускаю, что могут появиться системы, в которых уникальность UUID будет, действительно критична. Но для таких систем, возможно, придется писать новые языки программирования (что-нибудь типа ada с проверкой хэша перед исполнением кода) и использовать очень специфическое железо.
Если мне не изменяет память, для систем типа MasterCard эти потери составляют 7 центов на каждые $100 (а может даже больше).
Как вы понимаете, эти потери несравнимо больше, чем те, которые может (потенциально) вызвать коллизия UUID.
Плюс, вы не берет в расчет то, что я говорю об аппаратных проблемах, которые не были замечены. Понятно, что сбой сервера легко заметить. А вот допустим у вас был искажен бит при генерации UUID. Или, допустим, не сработало условие проверки его на уникальность (потому что условный переход случайно заменился на безусловный).
То есть здесь вы пытаетесь поставить железные двери на одноэтажный дом со стеклянными окнами. Это просто экономически неэффективно.
P.S. Я допускаю, что могут появиться системы, в которых уникальность UUID будет, действительно критична. Но для таких систем, возможно, придется писать новые языки программирования (что-нибудь типа ada с проверкой хэша перед исполнением кода) и использовать очень специфическое железо.
Если и есть такие потери у Мастеркарда, то они не от железных ошибок, а от мошенничеств.
Тем более мне непонятно зачем использовать технологию с дырами, если можно обойтись без них. Нет ничего сложного в реализации 100% непрерывных непересекающихся UUID. В твиттере же сделали, а у них сообщения генерятся с сумашедшей скоростью. И я думаю огромное количество сообщений заставило их не полагаться на авось.
В действительно серьёзных задачах все вычислительные процессы дублируются и по нескольку раз. Например в космических аппаратах все процессы считаются 3-мя компами и сравниваются результаты. Поэтому ошибка одного процессора, шины и т.п. не имеет значения.
Работники гугла говорят, что сбой компьютера у них — это не exception, а рядовая вещь, которая ни на что не влиет, т.к. всё многократно передублировано.
И это гугл, который в основном занимается сайтами, на которых редко бывает что ценное.
Тем более мне непонятно зачем использовать технологию с дырами, если можно обойтись без них. Нет ничего сложного в реализации 100% непрерывных непересекающихся UUID. В твиттере же сделали, а у них сообщения генерятся с сумашедшей скоростью. И я думаю огромное количество сообщений заставило их не полагаться на авось.
В действительно серьёзных задачах все вычислительные процессы дублируются и по нескольку раз. Например в космических аппаратах все процессы считаются 3-мя компами и сравниваются результаты. Поэтому ошибка одного процессора, шины и т.п. не имеет значения.
Работники гугла говорят, что сбой компьютера у них — это не exception, а рядовая вещь, которая ни на что не влиет, т.к. всё многократно передублировано.
И это гугл, который в основном занимается сайтами, на которых редко бывает что ценное.
Тезисно:
— Всегда нужно улучшать самое плохое звено. Всегда!
— Преждевременная оптимизация — это корень всех бед.
— Даже если UUID вас не устраивает, возьмите 256 битный UUID (+37 порядков).
— При изобретении велосипедов (распределенный непрерывный UUID) следует посчитать стоимость (цена ошибки*вероятность ошибки vs цена разработки). В крупных финансовых системах, скорее всего, не окупится. И на производительности и отказоустойчивости может сказаться.
— Твиттер имеет плохую архитектуру. Именно это объясняет его регулярные отказы и невозможность отобразить более 3200 последних твитов (эта проблема затрагивает на порядки больше людей). То есть разработчикам платили зарплату, пока они создавали свой UUID, а это время можно было потратить на что-то намного более важное.
— Троирование было модно в 70-х, когда вычислительные машины работали намного хуже. Сначала от него отказались в США, потом в СССР. Поверьте человеку, который писал софт для космической отрасли, троирование, может, и встречается где-то, но это экзотика.
— Про работников Google вообще не в тему. То, что BigTable переживает отказ оборудования никак не противоречит использованию UUID. Более того, подозреваю, что внутри AppEngine DataStore живет что-то типа UUID.
— Много хорошего софта имеет архитектуру с вероятностью коллизии. git, zfs, rsync и кучу другого.
— Мне кажется, в вас говорит максимализм (не обижайтесь, пожалуйста).
— Я думаю, мы флудим, если хотите продолжить дискуссию, пишите в личку. Обещаю ответить.
— Всегда нужно улучшать самое плохое звено. Всегда!
— Преждевременная оптимизация — это корень всех бед.
— Даже если UUID вас не устраивает, возьмите 256 битный UUID (+37 порядков).
— При изобретении велосипедов (распределенный непрерывный UUID) следует посчитать стоимость (цена ошибки*вероятность ошибки vs цена разработки). В крупных финансовых системах, скорее всего, не окупится. И на производительности и отказоустойчивости может сказаться.
— Твиттер имеет плохую архитектуру. Именно это объясняет его регулярные отказы и невозможность отобразить более 3200 последних твитов (эта проблема затрагивает на порядки больше людей). То есть разработчикам платили зарплату, пока они создавали свой UUID, а это время можно было потратить на что-то намного более важное.
— Троирование было модно в 70-х, когда вычислительные машины работали намного хуже. Сначала от него отказались в США, потом в СССР. Поверьте человеку, который писал софт для космической отрасли, троирование, может, и встречается где-то, но это экзотика.
— Про работников Google вообще не в тему. То, что BigTable переживает отказ оборудования никак не противоречит использованию UUID. Более того, подозреваю, что внутри AppEngine DataStore живет что-то типа UUID.
— Много хорошего софта имеет архитектуру с вероятностью коллизии. git, zfs, rsync и кучу другого.
— Мне кажется, в вас говорит максимализм (не обижайтесь, пожалуйста).
— Я думаю, мы флудим, если хотите продолжить дискуссию, пишите в личку. Обещаю ответить.
к слову говоря UUID не проверяются на уникальность, т.к. для подобной проверки нужно иметь базу данных всех ранее выданных UUID.
Кажется, ребята из Twitter рассуждали также и поэтому сделали свой сервер, который генерирует ключи (см. ссылку в тексте).
Это, по сути, и есть тот самый «арбитр», про который вы говорите, только ходить к нему надо «до», а не «после» (откат закоммиченой транзакции — лучше про это не думать вообще, чтобы с ума не сойти).
Это, по сути, и есть тот самый «арбитр», про который вы говорите, только ходить к нему надо «до», а не «после» (откат закоммиченой транзакции — лучше про это не думать вообще, чтобы с ума не сойти).
Ходить «до» — это плохая задумка. Есть такое понятие, как «eventual consistency». Приняв и записав данные мы уже сделали почти всю работу. Просто в крайне редких случаях кто-то может первым использовать наш UUID. В этом ничего плохого нет, просто надо сгенерить новый UUID и попробовать apply нашей транзакции снова. Если после третьей попытки опять не получится, то отвалиться с ошибкой в системе, ибо быть таким везунчиком это скорее один раз за все существование человечества (но, млин, возможно).
Если ходить «после», то все запросы к арбитру это успешные почти завершенные транзакции. Если ходит «до», то есть еще шанс отвалиться, зазря потревожив арбитра.
> откат закоммиченой транзакции — лучше про это не думать вообще, чтобы с ума не сойти.
Вполне такое безопасное действие. В чем сложность?
Если ходить «после», то все запросы к арбитру это успешные почти завершенные транзакции. Если ходит «до», то есть еще шанс отвалиться, зазря потревожив арбитра.
> откат закоммиченой транзакции — лучше про это не думать вообще, чтобы с ума не сойти.
Вполне такое безопасное действие. В чем сложность?
Ну, на самом деле я почти согласен везде UUID использовать. Но в том и дело, что не всегда получается или не всегда удобно.
> Требования по увеличения (вместо случайности) скорей всего не являются значимыми.
> В случае распределённых данных эти требования невозможно выполнить.
Распределение зачастую делается по хэшу, а не по самому ключу. Я имел ввиду ситуацию, когда у нас (на уровне приложения) уже есть список ключей, то иногда было бы круто при помощи простой сортировки получить их естественную последовательность.
> Требования по увеличения (вместо случайности) скорей всего не являются значимыми.
> В случае распределённых данных эти требования невозможно выполнить.
Распределение зачастую делается по хэшу, а не по самому ключу. Я имел ввиду ситуацию, когда у нас (на уровне приложения) уже есть список ключей, то иногда было бы круто при помощи простой сортировки получить их естественную последовательность.
Aвтоинкремент от Instagram очень похож на Object_id в mongodb, там об это всё заранее подумали к счастью.
В MongoDB ObjectId — 96 бит (12 байт) и скорее похож на самодельный UUID (который 16 байт).
В качестве уникального идентификатора между БД использую естественный ключ. Практически в любых бизнес-данных такой можно найти или сформировать.
Внутри каждой БД есть еще суррогатный ключ, уникальный в пределах БД или таблицы.
Внутри каждой БД есть еще суррогатный ключ, уникальный в пределах БД или таблицы.
Знаете, поиск естественного ключа в таблице-связке «многие-ко-многим» может быть несколько затруднен.
Даже больше скажу — естественные ключи можно использовать только в совсем мелких информационных системах.
Я в свое время очень долго смеялся, когда «внедренцы» очень серьезной, дорогостоящей ERP системы, рассказывали мне, что контрагента можно однозначно идентифицировать по ИНН/КПП
Даже больше скажу — естественные ключи можно использовать только в совсем мелких информационных системах.
Я в свое время очень долго смеялся, когда «внедренцы» очень серьезной, дорогостоящей ERP системы, рассказывали мне, что контрагента можно однозначно идентифицировать по ИНН/КПП
Я наверное немного не в тему, я разрабатывал не распределенную БД в общем смысле, это было множество автоматически реплицируемых баз данных. Так вот естественный ключ использовался только как уникальный идентификатор между реплицируемыми базами. Внутри каждой БД были свои суррогатные ключи по которым строились и все связи между таблицами и делались выборки и т.п.
Плюс такого решения в том, что грубо говоря в двух БД оператор завел одного и того же Иван Иваныча с номером паспорта 123456 (естественный ключ) и обе эти записи на уровне множества реплицирумых баз слились в одну сущность.
Плюс такого решения в том, что грубо говоря в двух БД оператор завел одного и того же Иван Иваныча с номером паспорта 123456 (естественный ключ) и обе эти записи на уровне множества реплицирумых баз слились в одну сущность.
Добавлю, кроме поиска естественных ключей при репликации, который действительно может быть достаточно затратным, после первой удачной репликации записи строилась специальная таблица соответствия ID в двух базах, между которыми происходит репликация. Таким образом при следующей репликации нужно всего лишь преобразовать ключ одной базы в ключ другой по этой таблице.
Да, пожалуй, естественный ключ можно рассматривать, как один из вариантов. Со своими плюсами и минусами.
А вы придумайте естественный ключ для события в календаре, например ;)
Да, не вариант :)
такие вещи в моей системе разруливались исключительно через таблицы соответствия (см коммент выше)
такие вещи в моей системе разруливались исключительно через таблицы соответствия (см коммент выше)
Автоинкремент на стороне базы данных по диапазонам значений
Минусы:
• БД должна поддерживать автоинкремент (не применимо для многих NoSQL-хранилищ)
естественная сортировка невозможна
• Клиент «не знает» ключ до вставки объекта. Чтобы узнать ключ нужно делать отдельный запрос.
Если вместо встроенного автоинкремента использовать SEQUENCE (а в большинстве современных СУБД они поддерживаются) этот минус исчезает.
Прокоментируйте за что минусы
> Если вместо встроенного автоинкремента использовать SEQUENCE (а в большинстве современных СУБД они поддерживаются) этот минус исчезает.
Ваше утверждение не решает предложенных минусов:
— БД должна поддерживать автоинкремент.
Sequences это продолжение атомарных счетчиков, абстракция. Генерализация автоинкремента для PK отдельно взятой таблицы.
— Клиент «не знает» ключ до вставки объекта. Чтобы узнать ключ нужно делать отдельный запрос.
С использованием sequences клиент по прежнему не знает какой ID он получит. Ему нужно делать либо отдельный запрос (атомарный инкремент счетчика), либо вставить строку и посмотреть на ID.
Итог: вы предложили те же яйца, только в профиль и не аргументированно отвергли минусы.
P.S. не стоит расстраиваться из-за минусов к комментариям, они мало влияют на карму. Просто дают вам повод задуматься над вашими словами.
Ваше утверждение не решает предложенных минусов:
— БД должна поддерживать автоинкремент.
Sequences это продолжение атомарных счетчиков, абстракция. Генерализация автоинкремента для PK отдельно взятой таблицы.
— Клиент «не знает» ключ до вставки объекта. Чтобы узнать ключ нужно делать отдельный запрос.
С использованием sequences клиент по прежнему не знает какой ID он получит. Ему нужно делать либо отдельный запрос (атомарный инкремент счетчика), либо вставить строку и посмотреть на ID.
Итог: вы предложили те же яйца, только в профиль и не аргументированно отвергли минусы.
P.S. не стоит расстраиваться из-за минусов к комментариям, они мало влияют на карму. Просто дают вам повод задуматься над вашими словами.
>>Sequences это продолжение атомарных счетчиков, абстракция. Генерализация автоинкремента для PK отдельно взятой таблицы.
Есть БД с поддержкой и автоинкремента и с последовательностей, есть либо с тем либо с другим, так что одно с другим вобщем-то напрямую не связано. Область применения SEQUENCE гораздо шире чем просто генерация автоинкремента.
>>С использованием sequences клиент по прежнему не знает какой ID он получит. Ему нужно делать либо отдельный запрос (атомарный инкремент счетчика), либо вставить строку и посмотреть на ID.
Но это не запрос к данным, запрос к счетчику во-первых принципиально быстрее, а во-вторых транзакционно независим, так что эта операция не сильно тяжелее генерации идентификатора на клиенте (при условии клиента и СУБД на одной машине).
Впрочем, вы правы, запроса все равно два. Но! Некоторые СУБД поддерживают конструкцию INSERT… RETURNING… которой можно получить вставленные значения в результатах запроса на вставку, выполнив таким образом всего 1 запрос.
>>не стоит расстраиваться из-за минусов к комментариям, они мало влияют на карму
Спасибо кэп, я не расстраиваюсь, мне интересно в чем я не прав. Благодарю, что ответили.
Есть БД с поддержкой и автоинкремента и с последовательностей, есть либо с тем либо с другим, так что одно с другим вобщем-то напрямую не связано. Область применения SEQUENCE гораздо шире чем просто генерация автоинкремента.
>>С использованием sequences клиент по прежнему не знает какой ID он получит. Ему нужно делать либо отдельный запрос (атомарный инкремент счетчика), либо вставить строку и посмотреть на ID.
Но это не запрос к данным, запрос к счетчику во-первых принципиально быстрее, а во-вторых транзакционно независим, так что эта операция не сильно тяжелее генерации идентификатора на клиенте (при условии клиента и СУБД на одной машине).
Впрочем, вы правы, запроса все равно два. Но! Некоторые СУБД поддерживают конструкцию INSERT… RETURNING… которой можно получить вставленные значения в результатах запроса на вставку, выполнив таким образом всего 1 запрос.
>>не стоит расстраиваться из-за минусов к комментариям, они мало влияют на карму
Спасибо кэп, я не расстраиваюсь, мне интересно в чем я не прав. Благодарю, что ответили.
Генерация id базой данных непосредственно при вставке (INSERT… RETURNING… или, вставка без указания id, например, в CouchDB) не всегда приемлема. В некоторых ситуациях надо знать идентификатор на клиенте еще до отправки записи на сервер. Иначе, в ситуации, когда клиент отправил запись на сервер и не получил ответ, не понятно, вставилась запись или нет, и нет возможности это узнать. Повторно посылать запись — может получиться две одинаковые записи с разными id.
К сожалению, единственное более-менее надежное кросс-платформенное/кросс-системное решение это uuid
В силу специфики работы имею несколько крупных проектов с гетерогенными информационными системами (MSSQL + MySQL + Paradox (Win/DOS)), соответственно, все это под Windows и Linux
Самый большой минус у uuid — его длина и «нестандартизованность» двоичного представления (из-за чего хранить его приходится в виде строки — кстати, привет «1С» которая в своей MS SQL базе «пакует» guid не так как Microsoft).
Таким образом, использовать uuid напрямую в «рабочих» запросах (как первичный ключ и FK) крайне не желательно (падает быстродействие). Так что — для кода занимающегося синхронизацией баз — отдельное поле с uuid, а для «внутренней» бизнес-логики «штатные» автоинкременты.
В силу специфики работы имею несколько крупных проектов с гетерогенными информационными системами (MSSQL + MySQL + Paradox (Win/DOS)), соответственно, все это под Windows и Linux
Самый большой минус у uuid — его длина и «нестандартизованность» двоичного представления (из-за чего хранить его приходится в виде строки — кстати, привет «1С» которая в своей MS SQL базе «пакует» guid не так как Microsoft).
Таким образом, использовать uuid напрямую в «рабочих» запросах (как первичный ключ и FK) крайне не желательно (падает быстродействие). Так что — для кода занимающегося синхронизацией баз — отдельное поле с uuid, а для «внутренней» бизнес-логики «штатные» автоинкременты.
К сожалению, если система действительно распределенная и с неизвестным заранее количеством компонентов, то без UUID не обойтись никак.
UUID или просто какой-то случайный хеш, как, например, в couchdb решает.
У нас в одном из проектов прокси делает Round Robin запись, поэтому используется комбинированный ключ, похожий на Aвтоинкремент от Instagram: timestamp — server_id — seq. Айдишка генерируется проксей.
Если упадет, софт переключится на второй прокси :) Такова политика компании — всегда имей бэкап )))
Такой вариант: таблицы соответствия ID между шардами, при этом внутри каждого шарда свой автоинкремент.
Получается максимальная скорость генерации ключей 1024 ключа на шард в милисекунду. Для некоторых, например, twitter, этой скорости может быть недостаточно.
Есть такое решение — генерировать ключ на одной из машин БД. При падении этой машины происходит голосование по одному из алгоритмов голосования, например по алгоритму забияки. Решение универсальное, но довольно сложное в реализации.
Т.е. генератором ключей становится другая машина? а как надежно достигается синхронизация генератора? Т.е. на новой машине значение генератора должно продолжать последовательность предыдущей машины-генератора
Что касается MS-SQL, — есть ф-я NEWSEQUENTIALID():
«NEWSEQUENTIALID() Creates a GUID that is greater than any GUID previously generated by this function on a specified computer since Windows was started. After restarting Windows, the GUID can start again from a lower range, but is still globally unique.»
«NEWSEQUENTIALID() Creates a GUID that is greater than any GUID previously generated by this function on a specified computer since Windows was started. After restarting Windows, the GUID can start again from a lower range, but is still globally unique.»
Ну а если сильно хочется генерировать без участия сервера БД, то в Windows последовательные UUID можно генерировать с помощью Win API UuidCreateSequential
Именно так (генератором ключей назначена выделенная БД) делают в Flickr
code.flickr.com/blog/2010/02/08/ticket-servers-distributed-unique-primary-keys-on-the-cheap/
code.flickr.com/blog/2010/02/08/ticket-servers-distributed-unique-primary-keys-on-the-cheap/
Я использую в одном из проектов на couchdb ключи, состоящие из timestamp и рандомного окончания. В итоге получается уникальность, последовательность и экономия на одном индексе — когда надо выбрать несколько документов за определенный диапазон времени.
NEWSEQUENTIALID() — msdn.microsoft.com/en-us/library/ms189786
1. Генерация UUID весьма дорогая операция (относительно инкрементирования атомарного счетчика).
2. UUID, насколько я помню, не может быть сгенерирован параллельно (по-крайней мере, те реализации, с которыми я сталкивался). Т.е. для их генерации ставятся блокировки.
Вот из-за этих двух пунктов генерация UUID на стороне клиента для высоконагруженных систем зачастую не вариант.
Как мне кажется, генерация через сервис на отдельной машине есть наиболее удачный вариант решения (тем более, что шанс отказа такого сервиса в разы меньше шанса отказа СУБД, например).
2. UUID, насколько я помню, не может быть сгенерирован параллельно (по-крайней мере, те реализации, с которыми я сталкивался). Т.е. для их генерации ставятся блокировки.
Вот из-за этих двух пунктов генерация UUID на стороне клиента для высоконагруженных систем зачастую не вариант.
Как мне кажется, генерация через сервис на отдельной машине есть наиболее удачный вариант решения (тем более, что шанс отказа такого сервиса в разы меньше шанса отказа СУБД, например).
как обращение к сервису на отдельной машине может стать быстрее чем вызов функции из длл«ки?
почему этот сервис будет отказоустойчивее чем Оракл, например?
почему этот сервис будет отказоустойчивее чем Оракл, например?
Если вызов из дллки идет последовательно, а запросы к отдельному серверу — параллельно — очень просто.
Особенно если вызываемая функция находится в kernel-space (а я подозреваю, что для генератора UUID это именно так).
Особенно если вызываемая функция находится в kernel-space (а я подозреваю, что для генератора UUID это именно так).
ну и как же этот выделенный сервер будет непоследовательно генерить функцию? Вызывать другой выделенный сервер штоль?
8)
и всё это через сеть до кучи. Есть стандарт на UUID, есть его реализация почти везде где надо. Незачем мудрить и пытаться решить проблему которой нет.
8)
и всё это через сеть до кучи. Есть стандарт на UUID, есть его реализация почти везде где надо. Незачем мудрить и пытаться решить проблему которой нет.
Перечитайте мой оригинальный комментарий, там не зря указан первый пункт.
К тому же никто не мешает несколько усложнить логику инкрементирования, дабы она эффективно параллелилась по количеству ядер.
Еще раз — генерация UUID _очень_ дорогая операция.
Задержки в нормальной локальной сети порядка 1мс. Это много меньше, чем время, затрачиваемое на генерацию, скажем, тысячи UUID.
К тому же никто не мешает несколько усложнить логику инкрементирования, дабы она эффективно параллелилась по количеству ядер.
Еще раз — генерация UUID _очень_ дорогая операция.
Задержки в нормальной локальной сети порядка 1мс. Это много меньше, чем время, затрачиваемое на генерацию, скажем, тысячи UUID.
даже не знаю что сказать
Вы как-то жестко бредите заблуждаетесь…
С чего вы взяли, что генерация UUID это «очень дорогая» операцией? Вы точно не путаете UUID с хэш-функцией?
Я вам, без всякого сарказма, советую мысленно проделать следующее упражнение. Представьте программу на ассемблере, которая формирует UUID. Не в точности до команды, а просто «крупными мазками», чтобы оценить масштаб.
А после этого представьте всю махину TCP-стека — тоже на ассемблере.
И сравните, просто по количеству машинных команд, что «дороже» — сходить куда-то за значением по сети или просто его сгенерить.
С чего вы взяли, что генерация UUID это «очень дорогая» операцией? Вы точно не путаете UUID с хэш-функцией?
Я вам, без всякого сарказма, советую мысленно проделать следующее упражнение. Представьте программу на ассемблере, которая формирует UUID. Не в точности до команды, а просто «крупными мазками», чтобы оценить масштаб.
А после этого представьте всю махину TCP-стека — тоже на ассемблере.
И сравните, просто по количеству машинных команд, что «дороже» — сходить куда-то за значением по сети или просто его сгенерить.
Учтите один момент. При генерации идентификатора на стороне БД клиенту не нужно знать его заранее, он присваивается прямо при записи и возвращается клиенту в том же вызове. Соответственно дополнительный вызов не нужен. Так что Aquilae прав, генерация на клиенте действительно «дороже».
Провел тестирование, насчет генерации UUID на стороне клиента действительно был не прав, извиняюсь.
Код тестов не приведу (впрочем, они примитивны, кто захочет — сам сваяет), но получается следующее:
1. Pure C: серьезный выигрыш (до 5 раз) UUID перед сервисом при последовательной обработке, при параллельной: выигрыш на 30-50%
2. C#/WinForms: небольшое преимущество UUID как при последовательной обработке, так и при параллельной
3. Python: жесткие тормоза генератора UUID при нескольких потоках, сервис работает быстрее.
Т.е. тормоза UUID в питоне — косяк реализации.
Код тестов не приведу (впрочем, они примитивны, кто захочет — сам сваяет), но получается следующее:
1. Pure C: серьезный выигрыш (до 5 раз) UUID перед сервисом при последовательной обработке, при параллельной: выигрыш на 30-50%
2. C#/WinForms: небольшое преимущество UUID как при последовательной обработке, так и при параллельной
3. Python: жесткие тормоза генератора UUID при нескольких потоках, сервис работает быстрее.
Т.е. тормоза UUID в питоне — косяк реализации.
P.S.: все тестировалось под Win 7 x64, подозреваю, что в *nix и win xp/2003 результаты могут сильно разниться, но проверить, увы, не могу
P.P.S.: если залезть дебаггером, почему-то иногда возникают одинаковые UUID в VC++. Вероятнее всего, что это моя ошибка при кодировании, конечно, но кто знает…
P.P.S.: если залезть дебаггером, почему-то иногда возникают одинаковые UUID в VC++. Вероятнее всего, что это моя ошибка при кодировании, конечно, но кто знает…
Это очень круто, что вы протестили!
Очень интересно про python — можно посмотреть на тестовый код?
Очень интересно про python — можно посмотреть на тестовый код?
Увы, нельзя — с питоном я игрался где-то год назад.
Если найду время на новогодних праздниках — постараюсь повторить.
Кстати вполне возможно, что в новых версиях питона (тестировал на 3.1, вроде) это пофиксили.
В принципе, тормоза объяснимы — скорей всего при генерации вешается GIL, который и добавляет лишний оверхед. Правда не совсем понятно тогда, почему сокеты не так сильно тормозят.
В общем будет время — попробую, выложу.
Если найду время на новогодних праздниках — постараюсь повторить.
Кстати вполне возможно, что в новых версиях питона (тестировал на 3.1, вроде) это пофиксили.
В принципе, тормоза объяснимы — скорей всего при генерации вешается GIL, который и добавляет лишний оверхед. Правда не совсем понятно тогда, почему сокеты не так сильно тормозят.
В общем будет время — попробую, выложу.
у меня в проекте ключ генерился в транзакции через sequence,
но так как в качестве БД использовался MySQL, в котором сиквенсов нет,
то генерация осуществлялась так:
UPDATE SEQ_1 SET counter = counter+1;
SELECT counter FROM SEQ_1
всегда имеем уникальный идентификатор на каждую новую вставку
А вот номер шарды (БД) отпределяем по заранее настроенному конфигу:
1- 500К БД1
500К+1 — 1М БД2
1М+1 — 1.5М БД3
…
но так как в качестве БД использовался MySQL, в котором сиквенсов нет,
то генерация осуществлялась так:
UPDATE SEQ_1 SET counter = counter+1;
SELECT counter FROM SEQ_1
всегда имеем уникальный идентификатор на каждую новую вставку
А вот номер шарды (БД) отпределяем по заранее настроенному конфигу:
1- 500К БД1
500К+1 — 1М БД2
1М+1 — 1.5М БД3
…
необходимо добавить, что уникальный ключ генерится в центральной БД
а не в расшарженных базах
а не в расшарженных базах
У вас получается не атомарная операция генерации нового счетчика. В некоторых случаях при частой генерации
«SELECT counter FROM SEQ_1» может вернуть одинаковые значения для разных клиентов…
«SELECT counter FROM SEQ_1» может вернуть одинаковые значения для разных клиентов…
В другом проекте за счетчик идентификатора данных отвечало NoSQL хранилище,
может быть например редис, у меня был тарантул
может быть например редис, у меня был тарантул
Так же в качестве счетчика можно использовать TokyoTyrant, или memcachedb
а вот в качестве распределенного хранилища хотел использовать tarantool, даже сделал проект,
который находится в стадии отладки — tarantool_proxy
распределение по шардам (хостам) идет либо по конфигу, либо с использованием пользовательской функции.
Можно, например, использовать алгоритм ketama.
а вот в качестве распределенного хранилища хотел использовать tarantool, даже сделал проект,
который находится в стадии отладки — tarantool_proxy
распределение по шардам (хостам) идет либо по конфигу, либо с использованием пользовательской функции.
Можно, например, использовать алгоритм ketama.
Ключ должен монотонно увеличиваться
Зачем это нужно:
Автоматическая естественная сортировка (в том числе хронологическая)
Быстрее вставка, чем при случайных ключах
Извините, но это условие является одним сложным/дорогим в децентрализованных системах, и в списке ваших решений единственное подходящее — выделение центрального сервера для выдачи идентификаторов (выше в комментариях выдавали компромиссный вариант с выбором текущего центра голосованием).
Aвтоинкремент от Instagram не предоставляет гарантий, что два близких по времени события получат идентификаторы том же порядке что и время, хотя в пределах секунды (можно было бы выделить больше бит на timestamp, увеличив точность времени до хотя бы миллисекунд, но это уже вопрос необходимости для задачи)
SYS_GUID generates and returns a globally unique identifier (RAW value) made up of 16 bytes. On most platforms, the generated identifier consists of a host identifier, a process or thread identifier of the process or thread invoking the function, and a nonrepeating value (sequence of bytes) for that process or thread.
Пост закрыт :)
Пост закрыт :)
Ну не у всех же есть денег купить oracle исключительно для генерации UUID :-D
Так это и есть UUID.
Тут надо понять, что UUID — это не какой-то конкретный алгоритм. Есть разные реализации и рекомендация RFC-4122. Более того, в общем смысле, UUID — это не обязательно 16 байт, можно и больше сделать, если необходимо.
Суть в том, что это идентификатор, который генерируется на клиенте и он гарантированно уникален.
Тут надо понять, что UUID — это не какой-то конкретный алгоритм. Есть разные реализации и рекомендация RFC-4122. Более того, в общем смысле, UUID — это не обязательно 16 байт, можно и больше сделать, если необходимо.
Суть в том, что это идентификатор, который генерируется на клиенте и он гарантированно уникален.
кстати, если я не ошибаюсь в лицокниге тоже глобальный идентификатор для всех объектов, как они это решили?
вот ещё довольно удобный способ.
пре-генерация id в базе наперёд блоками и кеширование этого блока на клиенте. Скажем, если вставляется 10 записей — один запрос на генерацию 1000 ids. 10 используются сразу, а 990 ждут следующего раза.
Для генерации используюется стандартная hi-lo процедура
пре-генерация id в базе наперёд блоками и кеширование этого блока на клиенте. Скажем, если вставляется 10 записей — один запрос на генерацию 1000 ids. 10 используются сразу, а 990 ждут следующего раза.
Для генерации используюется стандартная hi-lo процедура
>время в секундах
Парни из Instgram используют миллисекунду, а не секунды. Собственно именно поэтому у них такой короткий sequence в AUTO поле.
Парни из Instgram используют миллисекунду, а не секунды. Собственно именно поэтому у них такой короткий sequence в AUTO поле.
Sign up to leave a comment.
Уникальный ключ в условиях распределенной БД