Уникальный ключ в условиях распределенной БД

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


    Какие требования (кроме уникальности) могут предъявляться к ключам?



    Ключ должен монотонно увеличиваться
    Зачем это нужно:
    • Автоматическая естественная сортировка (в том числе хронологическая)
    • Быстрее вставка, чем при случайных ключах

    Вышесказанное актуально только для индексов с использованием деревьев.

    Ключ должен формироваться на стороне клиента
    Зачем это нужно:
    • Приложение может сразу обратиться на нужный шард (узел кластера), поскольку уникальный ключ известен еще до сохранения объекта
    • Приложение может сохранять несколько связанных объектов сразу (в одной транзакции или пакетном задании)


    Ограничение по размеру ключа (например, только 64 бита)
    Зачем это нужно:
    • В некоторых случаях 128- или 160-битные идентификаторы могут быть проблемой. Например, Sphinx search поддерживает только целочисленные идентификаторы документов (64 бита в 64-битной версии).
    • Индекс с 32- или 64-битными ключами теоретически должен работать быстрее, чем с ключами произвольной длины.
    • Индекс с 32- или 64-битными ключами компактнее и, в результате, целиком помещается в память (актуально для больших объемов данных).


    Какие существуют способы генерации уникальных ключей?



    Генерация ID на стороне приложения (UUID и т.п.)

    С UUID все относительно просто — берем библиотеку и генерируем ключи на стороне приложения. UUID широко используется во многих системах. Значение формируется таким образом, что коллизии невозможны.

    Минусы:
        • Длина стандартного UUID 128 бит (которые, на самом деле, часто хочется хранить прямо в виде строки шестнадцатеричных цифр, а это уже 32 байта)
        • Как правило, UUID не дает естественной сортировки ключей

    Отдельный сервис, для генерации ключей

    Такой вариант используют, например, Flick и Twitter.

    Минусы:
        • усложнение системы из-за введения дополнительных компонентов
        • потенциально единая точка сбоя, либо требуются дополнительные усилия, чтобы обеспечить высокую доступность генератора ключей

    Автоинкремент на стороне базы данных по диапазонам значений

    Весь диапазон значений делится на поддиапазоны и каждый шард (узел кластера) отвечает за свой диапазон, например:
        1 - 0        .. 3FFFFFFF,
        2 - 40000000 .. 7FFFFFFF,
        3 - 80000000 .. BFFFFFFF,
        4 - C0000000 .. FFFFFFFF
    

    Минусы:
        • БД должна поддерживать автоинкремент (не применимо для многих NoSQL-хранилищ)
    естественная сортировка невозможна
        • Клиент «не знает» ключ до вставки объекта. Чтобы узнать ключ нужно делать отдельный запрос.
        • Практически невозможно увеличить количество узлов кластера

    Aвтоинкремент от Instagram

    Об этом решении рассказано в техническом блоге команды Instgram (photo sharing application).

    Они используют 64-битный ключ, который формируется на стороне БД (PostgreSQL) и состоит из битовых полей

    63                          31                          0
    |======|======|======|======|======|======|======|======|
    |        CUSTOM TIMESTAMP          | SHARD ID  |  AUTO  |
    

    где
    CUSTOM TIMESTAMP (41 бита) — время в миллисекундах от 2011-01-01 00:00:00
    SHARD ID (13 бит) — идентификатор логического раздела (число шардов больше, чем число физических узлов)
    AUTO (10 бит) — последовательность (sequence), уникальная в пределах логического раздела (шарда)

    Плюсы (по сравнению с автоинкрементом по диапазонам):
        • Автоматическая хронологическая сортировка

    А вы какие варианты знаете и используете?
    Поделиться публикацией
    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее
    Реклама

    Комментарии 86

      +8
      если данные распределённые то нужно использовать UUID. Он как раз для этого и предназначен. Остальное от лукавого.

      Требования по увеличения (вместо случайности) скорей всего не являются значимыми. В случае распределённых данных эти требования невозможно выполнить.
        +2
        UUID не гарантирует уникальность ключа. Просто шанс на коллизию очень мал. Поэтому проверка на сервере по любому нужна.
          +5
          Это заблуждение. UUID как раз и придуман для того, чтобы «проверка на сервере» была не нужна (она невозможна в распределенной системе).
          Почитайте как устроен UUID и вы поймете, что надо как-то очень хитро стараться (например, крутить часы), чтобы получить хотя бы не нулевую вероятность сгенерировать два одинаковых UUID.
            +9
            У UUID много разных схем, не только время. Но ни одна не может гарантировать, что при достаточно плотном потоке параллельных действий не будет сгенерировано два одинаковых ключа. Это в дизайне самой UUID и в этом нет ничего плохого. Это как использовать md5/sha1/любой хешь для генерации уникальных идентификаторов (кстати, тоже одна из схем UUID).

            Другое дело, что можно сначала записать обьекты в sharded-базу параллельно, без блокировок, а затем за–claim'ить ID у арбитра. Если будет коллизия, то одна из транзакций либо откатиться назад (отбросит изменения), либо повторит себя (шанс, на две коллизии подряд вообще «астрономически» мал).

            Иными словами, даже с UUID нужно подходит с умом.
              +3
              Во-первых, некоторые схемы включает ID хоста, что делает невозможной коллизию на разных хостах.

              Во-вторых, в тех ситуациях, когда вероятность коллизии на десятки порядков меньше вероятности ошибок исполнения кода (я имею в виду ошибки процессора), то можно считать UUID строго уникальными.
                +1
                > Во-вторых, в тех ситуациях, когда вероятность коллизии на десятки порядков меньше вероятности ошибок исполнения кода (я имею в виду ошибки процессора), то можно считать UUID строго уникальными.
                Хотелось бы увидеть ссылки на исследования, где ваше утверждение бы подтверждалось…

                > Во-первых, некоторые схемы включает ID хоста.
                Тогда на клиенте требуется знать о хостах, о шардинге и т.п. Но даже так, никто не запрещает двум клиентам, совершенно случайно получить два одинаковых UUID для одного хоста, куда они и обращаются. Пока это не решение.
                  +10
                  >исследования
                  Ну, для простоты UUIDv4, пространство значений 2^122. Вероятность коллизии 1.9*10^-37.
                  Частота ошибок, например, в оперативной памяти (то есть в том числе и в загруженной версии вашей программы) 10^-10 — 10^-17 error/bit·h, то есть ~10^25 (на такт) для одного бита.
                  Дальше учтите, что программа у вас, скорее всего, длиннее одного бита и выполняются дольше одного такта. Ещё учтите, что ошибки есть на диске, на шине, в памяти и в процессоре.
                  Но даже в самом худшем случае вероятность коллизии на ~10 порядков меньше.
                    0
                    Плюсую, но дополню.
                    Алгоритм генерации uuid хотя и отличается в разных реализациях (MSSQL и MySQL под Linux точно, и я знаю что в MySQL отличается между версиями и платформами), но в целом действительно обеспечивает уникальность надежнее других методов.

                    Более того, 99% процентов потенциальных проблем с «неуникальностью» могут быть вызваны только неправильной настройкой и ловятся в процессе именно настройки и не попадут в продакшн.
                      0
                      > Ну, для простоты UUIDv4, пространство значений 2^122
                      Логично. Но я бы все равно не доверял будь это для денег. Ошибки в железе происходят постоянно, ломаются биты в памяти, сыпятся диски. Но мы используем журналы, держим базу в целостности, она или совсем слетает или работает правильно — это видно сразу.

                      С коллизией UUID есть более страшная проблема, такую коллизию не сразу получиться обнаружить. Кто-то за–seed'ил свой random от времени, а не от системной энтропии и все, коллизии неизбежны.

                      Итог: я с вами полностью согласен, UUID *практически* уникальны. Но они по прежнему не дают гарантий уникальности. Сравнивать шансы коллизии с шансом падения железа не внушает оптимизма, т.к. в кластере на 500 машин железные ошибки всплывают постоянно… не хочется того же и для UUID.
                        +2
                        Соотвественно у 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 это что типа русского авось. Авось пронесёт.
                          0
                          Ну, например, в платежных системах ошибки измеряются, как «деньги, которые пришлось вернуть потерпевшим на каждые $100».

                          Если мне не изменяет память, для систем типа MasterCard эти потери составляют 7 центов на каждые $100 (а может даже больше).

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

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

                          То есть здесь вы пытаетесь поставить железные двери на одноэтажный дом со стеклянными окнами. Это просто экономически неэффективно.

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

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

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

                            Работники гугла говорят, что сбой компьютера у них — это не exception, а рядовая вещь, которая ни на что не влиет, т.к. всё многократно передублировано.

                            И это гугл, который в основном занимается сайтами, на которых редко бывает что ценное.
                              +3
                              Тезисно:

                              — Всегда нужно улучшать самое плохое звено. Всегда!
                              — Преждевременная оптимизация — это корень всех бед.
                              — Даже если UUID вас не устраивает, возьмите 256 битный UUID (+37 порядков).
                              — При изобретении велосипедов (распределенный непрерывный UUID) следует посчитать стоимость (цена ошибки*вероятность ошибки vs цена разработки). В крупных финансовых системах, скорее всего, не окупится. И на производительности и отказоустойчивости может сказаться.
                              — Твиттер имеет плохую архитектуру. Именно это объясняет его регулярные отказы и невозможность отобразить более 3200 последних твитов (эта проблема затрагивает на порядки больше людей). То есть разработчикам платили зарплату, пока они создавали свой UUID, а это время можно было потратить на что-то намного более важное.
                              — Троирование было модно в 70-х, когда вычислительные машины работали намного хуже. Сначала от него отказались в США, потом в СССР. Поверьте человеку, который писал софт для космической отрасли, троирование, может, и встречается где-то, но это экзотика.
                              — Про работников Google вообще не в тему. То, что BigTable переживает отказ оборудования никак не противоречит использованию UUID. Более того, подозреваю, что внутри AppEngine DataStore живет что-то типа UUID.
                              — Много хорошего софта имеет архитектуру с вероятностью коллизии. git, zfs, rsync и кучу другого.
                              — Мне кажется, в вас говорит максимализм (не обижайтесь, пожалуйста).
                              — Я думаю, мы флудим, если хотите продолжить дискуссию, пишите в личку. Обещаю ответить.
                              0
                              к слову говоря UUID не проверяются на уникальность, т.к. для подобной проверки нужно иметь базу данных всех ранее выданных UUID.
                      0
                      Кажется, ребята из Twitter рассуждали также и поэтому сделали свой сервер, который генерирует ключи (см. ссылку в тексте).

                      Это, по сути, и есть тот самый «арбитр», про который вы говорите, только ходить к нему надо «до», а не «после» (откат закоммиченой транзакции — лучше про это не думать вообще, чтобы с ума не сойти).
                        0
                        Ходить «до» — это плохая задумка. Есть такое понятие, как «eventual consistency». Приняв и записав данные мы уже сделали почти всю работу. Просто в крайне редких случаях кто-то может первым использовать наш UUID. В этом ничего плохого нет, просто надо сгенерить новый UUID и попробовать apply нашей транзакции снова. Если после третьей попытки опять не получится, то отвалиться с ошибкой в системе, ибо быть таким везунчиком это скорее один раз за все существование человечества (но, млин, возможно).

                        Если ходить «после», то все запросы к арбитру это успешные почти завершенные транзакции. Если ходит «до», то есть еще шанс отвалиться, зазря потревожив арбитра.

                        > откат закоммиченой транзакции — лучше про это не думать вообще, чтобы с ума не сойти.
                        Вполне такое безопасное действие. В чем сложность?
                  0
                  Ну, на самом деле я почти согласен везде UUID использовать. Но в том и дело, что не всегда получается или не всегда удобно.

                  > Требования по увеличения (вместо случайности) скорей всего не являются значимыми.
                  > В случае распределённых данных эти требования невозможно выполнить.
                  Распределение зачастую делается по хэшу, а не по самому ключу. Я имел ввиду ситуацию, когда у нас (на уровне приложения) уже есть список ключей, то иногда было бы круто при помощи простой сортировки получить их естественную последовательность.
                  +3
                  Aвтоинкремент от Instagram очень похож на Object_id в mongodb, там об это всё заранее подумали к счастью.
                    +2
                    В MongoDB ObjectId — 96 бит (12 байт) и скорее похож на самодельный UUID (который 16 байт).
                    –1
                    В качестве уникального идентификатора между БД использую естественный ключ. Практически в любых бизнес-данных такой можно найти или сформировать.

                    Внутри каждой БД есть еще суррогатный ключ, уникальный в пределах БД или таблицы.
                      +4
                      Знаете, поиск естественного ключа в таблице-связке «многие-ко-многим» может быть несколько затруднен.

                      Даже больше скажу — естественные ключи можно использовать только в совсем мелких информационных системах.

                      Я в свое время очень долго смеялся, когда «внедренцы» очень серьезной, дорогостоящей ERP системы, рассказывали мне, что контрагента можно однозначно идентифицировать по ИНН/КПП
                        +2
                        Я наверное немного не в тему, я разрабатывал не распределенную БД в общем смысле, это было множество автоматически реплицируемых баз данных. Так вот естественный ключ использовался только как уникальный идентификатор между реплицируемыми базами. Внутри каждой БД были свои суррогатные ключи по которым строились и все связи между таблицами и делались выборки и т.п.

                        Плюс такого решения в том, что грубо говоря в двух БД оператор завел одного и того же Иван Иваныча с номером паспорта 123456 (естественный ключ) и обе эти записи на уровне множества реплицирумых баз слились в одну сущность.
                          0
                          Добавлю, кроме поиска естественных ключей при репликации, который действительно может быть достаточно затратным, после первой удачной репликации записи строилась специальная таблица соответствия ID в двух базах, между которыми происходит репликация. Таким образом при следующей репликации нужно всего лишь преобразовать ключ одной базы в ключ другой по этой таблице.
                          0
                          Да, пожалуй, естественный ключ можно рассматривать, как один из вариантов. Со своими плюсами и минусами.
                            0
                            А вы придумайте естественный ключ для события в календаре, например ;)
                              0
                              Да, не вариант :)

                              такие вещи в моей системе разруливались исключительно через таблицы соответствия (см коммент выше)
                            0
                            Автоинкремент на стороне базы данных по диапазонам значений
                            Минусы:
                            • БД должна поддерживать автоинкремент (не применимо для многих NoSQL-хранилищ)
                            естественная сортировка невозможна
                            • Клиент «не знает» ключ до вставки объекта. Чтобы узнать ключ нужно делать отдельный запрос.

                            Если вместо встроенного автоинкремента использовать SEQUENCE (а в большинстве современных СУБД они поддерживаются) этот минус исчезает.
                              0
                              Прокоментируйте за что минусы
                                +2
                                > Если вместо встроенного автоинкремента использовать SEQUENCE (а в большинстве современных СУБД они поддерживаются) этот минус исчезает.

                                Ваше утверждение не решает предложенных минусов:

                                — БД должна поддерживать автоинкремент.

                                Sequences это продолжение атомарных счетчиков, абстракция. Генерализация автоинкремента для PK отдельно взятой таблицы.

                                — Клиент «не знает» ключ до вставки объекта. Чтобы узнать ключ нужно делать отдельный запрос.

                                С использованием sequences клиент по прежнему не знает какой ID он получит. Ему нужно делать либо отдельный запрос (атомарный инкремент счетчика), либо вставить строку и посмотреть на ID.

                                Итог: вы предложили те же яйца, только в профиль и не аргументированно отвергли минусы.

                                P.S. не стоит расстраиваться из-за минусов к комментариям, они мало влияют на карму. Просто дают вам повод задуматься над вашими словами.
                                  +2
                                  >>Sequences это продолжение атомарных счетчиков, абстракция. Генерализация автоинкремента для PK отдельно взятой таблицы.

                                  Есть БД с поддержкой и автоинкремента и с последовательностей, есть либо с тем либо с другим, так что одно с другим вобщем-то напрямую не связано. Область применения SEQUENCE гораздо шире чем просто генерация автоинкремента.

                                  >>С использованием sequences клиент по прежнему не знает какой ID он получит. Ему нужно делать либо отдельный запрос (атомарный инкремент счетчика), либо вставить строку и посмотреть на ID.
                                  Но это не запрос к данным, запрос к счетчику во-первых принципиально быстрее, а во-вторых транзакционно независим, так что эта операция не сильно тяжелее генерации идентификатора на клиенте (при условии клиента и СУБД на одной машине).
                                  Впрочем, вы правы, запроса все равно два. Но! Некоторые СУБД поддерживают конструкцию INSERT… RETURNING… которой можно получить вставленные значения в результатах запроса на вставку, выполнив таким образом всего 1 запрос.

                                  >>не стоит расстраиваться из-за минусов к комментариям, они мало влияют на карму
                                  Спасибо кэп, я не расстраиваюсь, мне интересно в чем я не прав. Благодарю, что ответили.
                                    0
                                    Генерация id базой данных непосредственно при вставке (INSERT… RETURNING… или, вставка без указания id, например, в CouchDB) не всегда приемлема. В некоторых ситуациях надо знать идентификатор на клиенте еще до отправки записи на сервер. Иначе, в ситуации, когда клиент отправил запись на сервер и не получил ответ, не понятно, вставилась запись или нет, и нет возможности это узнать. Повторно посылать запись — может получиться две одинаковые записи с разными id.
                                      0
                                      Это не связанно с автоинкрементом и/или sequence, в таких случая надо либо менять логику (беря id заранее), либо использовать uuid (хотя наверное Вы это и имели ввиду).
                              +4
                              К сожалению, единственное более-менее надежное кросс-платформенное/кросс-системное решение это uuid

                              В силу специфики работы имею несколько крупных проектов с гетерогенными информационными системами (MSSQL + MySQL + Paradox (Win/DOS)), соответственно, все это под Windows и Linux

                              Самый большой минус у uuid — его длина и «нестандартизованность» двоичного представления (из-за чего хранить его приходится в виде строки — кстати, привет «1С» которая в своей MS SQL базе «пакует» guid не так как Microsoft).

                              Таким образом, использовать uuid напрямую в «рабочих» запросах (как первичный ключ и FK) крайне не желательно (падает быстродействие). Так что — для кода занимающегося синхронизацией баз — отдельное поле с uuid, а для «внутренней» бизнес-логики «штатные» автоинкременты.
                                0
                                С mysql автоинкременты лучше заменить генераторами (которых в mysql нет, но которые можно сделать самому, уверен Вы знаете как), если данных много тем более…
                                +1
                                К сожалению, если система действительно распределенная и с неизвестным заранее количеством компонентов, то без UUID не обойтись никак.
                                  0
                                  UUID или просто какой-то случайный хеш, как, например, в couchdb решает.
                                    0
                                    Что за «случайный хэш» в СouchDB вы имеете ввиду?
                                      0
                                      Ну в couchdb айдишки сгенерированы с помощью uuid, а он по сути и есть более умным вариантом «случайного хеша».
                                    0
                                    У нас в одном из проектов прокси делает Round Robin запись, поэтому используется комбинированный ключ, похожий на Aвтоинкремент от Instagram: timestamp — server_id — seq. Айдишка генерируется проксей.
                                      0
                                      Как по мне, такое решение ближе к централизованному генератору ключей — есть отдельный компонент, про который еще думать надо, А что будет, если он упадет?
                                      +1
                                      Если упадет, софт переключится на второй прокси :) Такова политика компании — всегда имей бэкап )))
                                        0
                                        Такой вариант: таблицы соответствия ID между шардами, при этом внутри каждого шарда свой автоинкремент.
                                          0
                                          Получается максимальная скорость генерации ключей 1024 ключа на шард в милисекунду. Для некоторых, например, twitter, этой скорости может быть недостаточно.
                                            0
                                            Это вы про какой вариант?
                                              0
                                              Aвтоинкремент от Instagram
                                                +1
                                                А, ну конечно. В том и затея — посмотреть на варианты и дельные комментарии, чтобы с умом разные варианты применять.
                                            +3
                                            Есть такое решение — генерировать ключ на одной из машин БД. При падении этой машины происходит голосование по одному из алгоритмов голосования, например по алгоритму забияки. Решение универсальное, но довольно сложное в реализации.
                                              0
                                              Т.е. генератором ключей становится другая машина? а как надежно достигается синхронизация генератора? Т.е. на новой машине значение генератора должно продолжать последовательность предыдущей машины-генератора
                                                0
                                                Что касается 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.»
                                                  0
                                                  Ну а если сильно хочется генерировать без участия сервера БД, то в Windows последовательные UUID можно генерировать с помощью Win API UuidCreateSequential
                                                0
                                                Именно так (генератором ключей назначена выделенная БД) делают в Flickr
                                                code.flickr.com/blog/2010/02/08/ticket-servers-distributed-unique-primary-keys-on-the-cheap/
                                                0
                                                Я использую в одном из проектов на couchdb ключи, состоящие из timestamp и рандомного окончания. В итоге получается уникальность, последовательность и экономия на одном индексе — когда надо выбрать несколько документов за определенный диапазон времени.
                                                  0
                                                    +1
                                                    1. Генерация UUID весьма дорогая операция (относительно инкрементирования атомарного счетчика).
                                                    2. UUID, насколько я помню, не может быть сгенерирован параллельно (по-крайней мере, те реализации, с которыми я сталкивался). Т.е. для их генерации ставятся блокировки.
                                                    Вот из-за этих двух пунктов генерация UUID на стороне клиента для высоконагруженных систем зачастую не вариант.

                                                    Как мне кажется, генерация через сервис на отдельной машине есть наиболее удачный вариант решения (тем более, что шанс отказа такого сервиса в разы меньше шанса отказа СУБД, например).
                                                      +1
                                                      как обращение к сервису на отдельной машине может стать быстрее чем вызов функции из длл«ки?

                                                      почему этот сервис будет отказоустойчивее чем Оракл, например?
                                                        –1
                                                        Если вызов из дллки идет последовательно, а запросы к отдельному серверу — параллельно — очень просто.
                                                        Особенно если вызываемая функция находится в kernel-space (а я подозреваю, что для генератора UUID это именно так).
                                                          0
                                                          ну и как же этот выделенный сервер будет непоследовательно генерить функцию? Вызывать другой выделенный сервер штоль?

                                                          8)

                                                          и всё это через сеть до кучи. Есть стандарт на UUID, есть его реализация почти везде где надо. Незачем мудрить и пытаться решить проблему которой нет.
                                                            –1
                                                            Перечитайте мой оригинальный комментарий, там не зря указан первый пункт.
                                                            К тому же никто не мешает несколько усложнить логику инкрементирования, дабы она эффективно параллелилась по количеству ядер.
                                                            Еще раз — генерация UUID _очень_ дорогая операция.

                                                            Задержки в нормальной локальной сети порядка 1мс. Это много меньше, чем время, затрачиваемое на генерацию, скажем, тысячи UUID.
                                                              0
                                                              даже не знаю что сказать
                                                                +3
                                                                Вы как-то жестко бредите заблуждаетесь…
                                                                С чего вы взяли, что генерация UUID это «очень дорогая» операцией? Вы точно не путаете UUID с хэш-функцией?

                                                                Я вам, без всякого сарказма, советую мысленно проделать следующее упражнение. Представьте программу на ассемблере, которая формирует UUID. Не в точности до команды, а просто «крупными мазками», чтобы оценить масштаб.
                                                                А после этого представьте всю махину TCP-стека — тоже на ассемблере.
                                                                И сравните, просто по количеству машинных команд, что «дороже» — сходить куда-то за значением по сети или просто его сгенерить.
                                                                  0
                                                                  Учтите один момент. При генерации идентификатора на стороне БД клиенту не нужно знать его заранее, он присваивается прямо при записи и возвращается клиенту в том же вызове. Соответственно дополнительный вызов не нужен. Так что Aquilae прав, генерация на клиенте действительно «дороже».
                                                                    +1
                                                                    Провел тестирование, насчет генерации UUID на стороне клиента действительно был не прав, извиняюсь.
                                                                    Код тестов не приведу (впрочем, они примитивны, кто захочет — сам сваяет), но получается следующее:
                                                                    1. Pure C: серьезный выигрыш (до 5 раз) UUID перед сервисом при последовательной обработке, при параллельной: выигрыш на 30-50%
                                                                    2. C#/WinForms: небольшое преимущество UUID как при последовательной обработке, так и при параллельной
                                                                    3. Python: жесткие тормоза генератора UUID при нескольких потоках, сервис работает быстрее.
                                                                    Т.е. тормоза UUID в питоне — косяк реализации.
                                                                      0
                                                                      P.S.: все тестировалось под Win 7 x64, подозреваю, что в *nix и win xp/2003 результаты могут сильно разниться, но проверить, увы, не могу

                                                                      P.P.S.: если залезть дебаггером, почему-то иногда возникают одинаковые UUID в VC++. Вероятнее всего, что это моя ошибка при кодировании, конечно, но кто знает…
                                                                        0
                                                                        Это очень круто, что вы протестили!
                                                                        Очень интересно про python — можно посмотреть на тестовый код?
                                                                          0
                                                                          Увы, нельзя — с питоном я игрался где-то год назад.
                                                                          Если найду время на новогодних праздниках — постараюсь повторить.
                                                                          Кстати вполне возможно, что в новых версиях питона (тестировал на 3.1, вроде) это пофиксили.
                                                                          В принципе, тормоза объяснимы — скорей всего при генерации вешается GIL, который и добавляет лишний оверхед. Правда не совсем понятно тогда, почему сокеты не так сильно тормозят.
                                                                          В общем будет время — попробую, выложу.
                                                            0
                                                            у меня в проекте ключ генерился в транзакции через 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

                                                              0
                                                              необходимо добавить, что уникальный ключ генерится в центральной БД
                                                              а не в расшарженных базах
                                                                0
                                                                Не очень понял, а зачем тогда определять диапазоны для каждой бд?
                                                                Если идентификатор в центральной БД генерится, то можно его просто использовать в остальных бд, он в них будет уникален.
                                                                  0
                                                                  Диапазоны определяются для того, чтоб по Ид определить номер шарды, т.е. номер БД куда коннектится;
                                                                  а новый Ид определяется один раз для новой текущей записи (например при вставки записи)
                                                                0
                                                                У вас получается не атомарная операция генерации нового счетчика. В некоторых случаях при частой генерации
                                                                «SELECT counter FROM SEQ_1» может вернуть одинаковые значения для разных клиентов…
                                                                  0
                                                                  Вы не заметили ключевое слово «ключ генерился в транзакции », так что все генерации ключа уникальные — проверено многолетней практикой
                                                                    0
                                                                    Извиняюсь, и вправду не заметил.
                                                                    С Новым Годом! :)))
                                                                      0
                                                                      С Новым Годом! :)
                                                                0
                                                                В другом проекте за счетчик идентификатора данных отвечало NoSQL хранилище,
                                                                может быть например редис, у меня был тарантул
                                                                  0
                                                                  Так же в качестве счетчика можно использовать TokyoTyrant, или memcachedb

                                                                  а вот в качестве распределенного хранилища хотел использовать tarantool, даже сделал проект,
                                                                  который находится в стадии отладки — tarantool_proxy
                                                                  распределение по шардам (хостам) идет либо по конфигу, либо с использованием пользовательской функции.
                                                                  Можно, например, использовать алгоритм ketama.
                                                                  0
                                                                  Ключ должен монотонно увеличиваться
                                                                  Зачем это нужно:
                                                                  
                                                                      Автоматическая естественная сортировка (в том числе хронологическая)
                                                                      Быстрее вставка, чем при случайных ключах
                                                                  

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

                                                                  Aвтоинкремент от Instagram не предоставляет гарантий, что два близких по времени события получат идентификаторы том же порядке что и время, хотя в пределах секунды (можно было бы выделить больше бит на timestamp, увеличив точность времени до хотя бы миллисекунд, но это уже вопрос необходимости для задачи)
                                                                    0
                                                                    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.

                                                                    Пост закрыт :)

                                                                      +1
                                                                      Ну не у всех же есть денег купить oracle исключительно для генерации UUID :-D
                                                                        0
                                                                        Так это и есть UUID.
                                                                        Тут надо понять, что UUID — это не какой-то конкретный алгоритм. Есть разные реализации и рекомендация RFC-4122. Более того, в общем смысле, UUID — это не обязательно 16 байт, можно и больше сделать, если необходимо.
                                                                        Суть в том, что это идентификатор, который генерируется на клиенте и он гарантированно уникален.
                                                                          0
                                                                          Прости, бро. Но по-моему скромному мнению, клиент вообще ничего не должен генерить.
                                                                          Впрочем, чур без холиваров. Просто про эту оракловую функцию куча народа не знает и изобретает велосипед Ж(
                                                                            0
                                                                            Я несколько неверно выразился. Конечно, UUID может генерить и БД — в каких-то случаях это более уместно. Другое дело, что если алгоритм тот же (или столь же годный), то этот UUID можно и клиентом генерить с тем же успехом. Особенно, если хранилище само этого не умеет.
                                                                        +1
                                                                        кстати, если я не ошибаюсь в лицокниге тоже глобальный идентификатор для всех объектов, как они это решили?
                                                                          0
                                                                          А вот бы вы нарыли и нам рассказали? :)
                                                                          0
                                                                          вот ещё довольно удобный способ.
                                                                          пре-генерация id в базе наперёд блоками и кеширование этого блока на клиенте. Скажем, если вставляется 10 записей — один запрос на генерацию 1000 ids. 10 используются сразу, а 990 ждут следующего раза.
                                                                          Для генерации используюется стандартная hi-lo процедура
                                                                            0
                                                                            >время в секундах

                                                                            Парни из Instgram используют миллисекунду, а не секунды. Собственно именно поэтому у них такой короткий sequence в AUTO поле.
                                                                              0
                                                                              о, спасибо, поправил

                                                                            Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                                                                            Самое читаемое