Comments 12
Привязка ко времени верна, а к "случайному числу" нет.
Даже если у вас изредка бывают максимум две записи в секунду - рандом может сложится. Вы то вложились "в размер" потому колизии маловеоятны (но все еще вероятны)
Обычно такие веши строят так - уникальный указатель сегмента (сервер, кластер, просто соль) отрезок времени с нужной точностью (дни, минуты, секунды, наносекунды) и инкрементное значение. Асинхронный доступ с блокировками для значения инкремента реализовать не сложно.
Из моей практики в строку из 6 символов (a-z0-9) впихнули возможность хранения трилионного диазона, или до 9999 уникальных записей в секунду в рамках кластера (максимальное количество кластеров 1200) с привязкой ко времени.
Пример из моего проекта приведен просто для наглядности.
Я формировал суффикс на старте приложения и не менял его по ходу работы приложения. Коллизии возможны только если 2 клиента сгенерируют одинаковое случайное число и будут запущены в одну и ту же секунду. Для конкретно этого проекта это был приемлемый баланс между вероятностью коллизии и размером суффикса.
Вариантов как и когда его формировать уйма. Можно генерировать один раз на старте или на каждую запись. Хоть GUID приписывай, все дело в балансе уникальности и размера.
По этому поводу описывал - Standard Time как его видит IBM Там как раз время - 64бита где старшие 52 - количество микросекунд с начала эпохи, младшие 12 - "биты уникальности" (т.е. в рамках одной микросекунды можно сгенерировать 2048 последовательных уникальных значений с привязкой ко времени).
Реализовано это, естественно, на уровне системы (ниже SLIC - границы отделяющей доступные разработчику системные интерфейсы, не зависящие от конкретной платформы от платформенно-зависимого ядра).
я писал на Go, учитывая что в итоге сама блокировка вышла одноточечной - переписать эту часть на асемблер под определенные ядра не проблема))
Но в целом 4нс на генерацию при асинхронном вызове для 1000 потоков и так неплохо.
Вообще разработчики недооценивают потребление таких мелких и рутинных операций, особенно если их инициализация не очевидна. И как избыток проверок способен в подобной "простой" функции умножать потребление ресурсов.
Записи сортированные же, т.е. они не в хеш таблице лежат, верно?
Тогда чем этот подход лучше или хуже неявных индексов? В балансированном дереве можно реализовать операции "вставить элемент после i-ого", "удалить i-ый элемент", "найти i-ый элемент" - все за логарифм, все за логарифм, как и обычные операции по ключу.
При этом надо лишь в каждой вершине хранить одно число - количество элементов в поддереве. Для 10000 вставок это будет 16 бит, а не 1250 байт. При этом еще и никакие ключи у элементов не сравниваются вообще и не хранятся. Т.е. тут еще и экономия может получится по итогу. Основная идея: если в левом поддереве много элементов - i-ый элемент должен быть там, идем туда. Иначе, идем вправо.
Единственный минус, который я вижу - это редко есть в стандартной библиотеке, и не так просто какой-нибудь встроенный в язык контейнер для этого приспособить. Хотя в том же С++ варианты, оказывается, есть (но об этом мало кто знает и нагуглить это очень тяжело).
Но вообще, какое-нибудь декартово самобалансирующееся дерево итак весьма просто написать. И по сравнению с перегруженными на все случаи жизни стандартными структами оно даже быстрее работать будет.
Таким и схожими подходами пользуются в редакторах для совместной работы в реальном времени (realtime collaborative editor) или в одноранговых (peer-to-peer) редакторах, когда надо учесть все свои и чужие изменения, а единого места для синхронизации нет.
Например, Figma использует похожий подход.
Да, с параллельными изменениями могут быть проблемы, это важное замечание. Если один клиент прочитает что-то и решит вставить элемент после 10-ого, а в это время кто-то другой вставит новый элемент после 3-его, то новая вставка окажется перед тем элементом, который был 10-ым с точки зрения первого клиента.
С дробными индексами локально все оказывается упорядочено так, как клиент видит.
Задача заключается в сортировке записей с минимальным нарушением существующей последовательности. Рассмотрим сценарий, в котором коллекция строк упорядочивается на основе индексного поля, а цель состоит в том, чтобы переместить или вставить новую строку, не затрагивая другие записи.
Именно так хранятся исходники (и вообще тексты) на платформе IBM i. Там очень специфическая файловая система (там вообще все специфическое) - нет файлов, есть объекты.
Исходники, текстовые файлы хранятся не как файлы, а как ... таблица БД DB2 (объект типа *FILE с атрибутом pf-src - "физический файл исходных текстов", от "обычных" таблиц отличается только атрибутом - там pf-dta - "физический файл данных").
В DB2 таблица может содержать несколько форматов записей (партиций) одновременно. В PF-SRC каждый исходник (member - элемент) является отдельным форматом записи, партицией.
Т.о. если вы делаете "поставку" в которой несколько объектов, то все они будут хранится в одном pf-src в виде набора элементов.
К чему все это... Каждый элемент суть набор записей-строк в формате
SRCSEQ Numeric(6, 2) - номер строки
SRCDAT Numeric(6, 0) - дата
SRCDTA Char(...) собственно строка
Но дробных индексов тут нет - не догадались до такого... Хотя идея хорошая. Тут при каждом сохранении идет полная перенумерация :-(
Хотя сама идея что любой исходник можно прочитать SQL запросом прикольная. Достаточно создать alias на нужный элемент внутри pf-src и потом select по алиасу.
спасибо, интересно.
не очень понятно, зачем в многоюзеровском режиме рассчитывать значение индекса параллельно для разных юзеров. очевидно, что речь идет об учетной системе, где количество юзеров далеко не бесконечно. в warehouse индексы можно сделать, если они вообще используются, на этапе загрузки данных - здесь конкуренция минимальна.
для учетной системы, думаю, лучше рассчитывать значение индекса под блокировкой. это позволит в каждый момент времени иметь только один расчет и сократит длину значения индекса до минимально возможной. потуги юзеров разрулит другой механизм - блокировка ресурса.
а то получается, сначала вели разговор про 1 бит на вставку и меньше, а потом - бах и 25 бит timestamp на вставку, и то не факт, что 2 юзера в одну и ту же миллисекунду не вставят свои значения. хотя, вероятность, конечно. не большая. но по закону подлости в промышленной системе она наступит.
из недавних моих исследований следует, что при нагрузке 5-10 запросов в сек на операцию, блокировки справляются очень хорошо. особенно, если их очень правильно сделать. но это уже другая история😄
Выше уже отвечал, что таким и схожими подходами пользуются в редакторах для совместной работы в реальном времени (realtime collaborative editor) или в одноранговых (peer-to-peer) редакторах, когда надо учесть все свои и чужие изменения, а единого места для синхронизации нет.
Например, Figma использует похожий подход.
понятно. хотя доля таких - не велика. править один вордовый файл несколькими юзерами одновременно - сильно устаревший архитектурный подход. напомню, что сам пакет офиса уже переполз в облако. и уже сам производитель не рекомендует так делать. иначе, есть ненулевая вероятность просто запортить файл, даже если он хранится на надежном файл-сервере. были случаи.
у figma есть серверная часть. как и у git. как и у других подобных корпоративных продуктов. здесь проблем быть не должно.
Алгоритм формирования дробных индексов