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

Постановка задачи

Задача заключается в сортировке записей с минимальным нарушением существующей последовательности. Рассмотрим сценарий, в котором коллекция строк упорядочивается на основе индексного поля, а цель состоит в том, чтобы переместить или вставить новую строку, не затрагивая другие записи.

Зачем нам это может понадобиться?

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

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

Возникает вопрос: возможно ли добиться такой сортировки с минимальным нарушением существующей последовательности?

Идея построения алгоритма

Конечно, концепция дробного индексирования представляет собой простое и интуитивное решение нашей задачи. Представьте себе, как вы записываете какой-то список на бумаге и понимаете, что забыли или пропустили один пункт. Вместо перенумерации всей последовательности вы можете просто вписать его между строк и обозначить дробным индексом, например 1,5.

Этот подход лежит в основе дробного индексирования, но, к сожалению, его прямое применение затруднено ограничениями представления чисел с плавающей запятой. Числа с плавающей запятой имеют конечную точность, поэтому мы не сможем делить их бесконечно, и очень быстро упремся в ограничения.

Чтобы унифицировать эту концепцию, мы введем понятие недостижимых границ внутри диапазона индексов. Предполагая, что строки отсортированы в порядке возрастания индекса, мы обозначим ноль как недостижимую верхнюю границу и единицу как недостижимую нижнюю границу индекса.

Каждый новый индекс мы будем рассчитывать как среднее арифметическое между двумя ближайшими соседями. Например, для вставки строки в пустой список мы используем обе недостижимые границы и первый индекс будет равен.
Аналогично, при вставке строки поверх существующей новый индекс вычисляется как середина между недостижимой верхней границей и индексом предыдущей строки.
Вставка между существующими строками — среднее значение их индексов, что в данном случае дает.

При более внимательном рассмотрении полученных индексов заметим, что префикс «ноль точка» является общим для всех индексов и им можно пренебречь. Более того, если представить хвосты индекса в виде строк или массивов байтов, то можно обнаружить, что они упорядочены лексикографически. Эта особенность позволяет нам выйти за рамки обычных числовых индексов и использовать расширенные наборы символов. Например, такие как base64 или даже произвольные байты, при условии, что наше приложение или база данных поддерживает лексикографическую сортировку таких массивов.

Вставка между двумя индексами

Выравнивание длин массивов — это, по сути, умножение наших рациональных чисел на некоторую общую базу так, чтобы они стали целыми числами. При этом, рассматривая выровненные по длине индексы как большие целые числа, мы можем определить их среднее арифметическое:

Как видно из формулы выше, для этого достаточно выполнить две простые операции с массивами байтов: сложение и сдвиг вправо на один бит. Обе операции легко реализовать для произвольного набора байтов. Нужно просто выполнить операцию над парой байт, а остаток перенести на следующую и так далее. Важно отметить, что нет необходимости сохранять полученное число целиком. Как только встречается байт, который отличается оти, все последующие байты становятся незначительными и могут быть отброшены.

Например, использование этого метода в нашем примере дает новый индекс:

Оценка памяти

Наихудший сценарий алгоритма возникает при постоянной вставке новых строк в одну и ту же позицию. С каждой вставкой диапазон между индексами сужается, что приводит к увеличению его длины. Но насколько быстро происходит этот рост?

Реализовав алгоритм с байтовыми массивами и проведя 10 000 вставок в начало списка, я обнаружил, что максимальный размер индекса достигает 1250 байт. Таким образом, получается каждая вставка увеличивает длину индекса всего на один бит.

Это отличный результат, поскольку один бит представляет собой минимальный размер информации и его трудно улучшить. На самом деле, почти все описания алгоритма, которые я нашел в интернете, на этом и заканчиваются. Однако, важно отдельно рассмотреть крайние случаи, особенно вставки в самое начало или конец списка. В таких ситуациях существует одна открытая граница, которая может предоставить возможность для оптимизации.

Например, представьте одноранговый текстовый редактор, что-то типа «Блокнота», но строки сортируются по дробному индексу. Каждый раз, когда мы добавляем новую строку, наш индекс увеличивается на один бит. Если вставлять строки посередине, с этим ничего не поделаешь. Но при написании текста добавление строк в самый конец может оказаться более вероятным и естественным вариантом. Таким образом, оптимизируя добавление нового индекса в конец списка, мы сможем сократить накладные расходы на его хранение.

Вставка в конец списка

Рассмотрим простой случай, в котором последний индекс нашего списка обозначается как, а мы хотим создать следующий индекс. Если использовать предыдущий алгоритм, то мы получим новое значение индекса как. Однако, при ближайшем рассмотрении очевидно, что это слишком большой шаг. Вместо этого достаточно просто увеличить первый байт на единицу.

Учитывая, что первый добавляемый индекс находится ровно в середине диапазона, это наблюдение обеспечивает примерно 127 вставок в конец (или начало) списка на первый байт индекса. Что соответствует приблизительному значению 0,06 бита на вставку.

Более того, благодаря свойству рациональных чисел мы можем считать все последующие байты равными нулю, что позволяет выполнить дополнительные 255 вставок на каждый следующий байт индекса. А это соответствует значению примерно 0,03 бита на вставку.

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

Таким образом, мы можем значительно увеличить эффективность за счет использования пар байтов для инкремента. Этот подход позволяет достичь невероятных значений в 0,0001 бит на каждый новый индекс. Самое главное в этом случае — в качестве пары для инкремента использовать первый байт, который меньше FF, и следующий за ним.

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

Для нашего примера с «Блокнотом» это означает, что индексы будут увеличиваться на один бит при вставке в середину текста, а добавление строки в конец или начало будет практически бесплатным.

Другой пример, где этот подход может хорошо себя показать, — это какое-то приложение со списком задач или приоритетов. Представьте себе список из трех задач, которые вы постоянно меняете в случайном порядке. Без оптимизации каждое движение обходится вам в один бит индекса. Но так как в списке всего три задачи, вероятность того, что мы переместим одну из них в самое начало или конец, довольно велика. И этот оптимизированный случай позволит автоматически обрезать индекс до исходного размера в байтах.

Параллельные изменения

Еще одна тема, которую хотелось бы затронуть, — это одновременное редактирование списка несколькими пользователями. Что произойдет, если два независимых клиента попытаются вставить строку в одно и то же место одновременно?

Рассмотрим простейший сценарий со списком из двух строк:и. Предположим, два независимых клиента пытаются вставить новую строку междуи.

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

Чтобы решить эту проблему, необходимо обеспечить уникальность сгенерированных индексов. Для этого мы используем интересную особенность наших индексов: если у нас есть список уникальных значений, добавление любого суффикса к любому индексу не изменит порядок строк. Следовательно, мы можем вводить небольшие уникальные отклонения для каждого клиента, гарантируя уникальность генерируемых значений.

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

Для примера, в одном из моих проектов я реализовал генерацию уникального суффикса длиной 6 байт по следующим правилам:

• Первые два бита «ноль-один» постоянны. Это необходимо для устранения вырожденных случаев, когда суффикс состоит только из нулей или единиц. Поскольку мы знаем, что такие суффиксы могут существенно повлиять на длину индекса в начале или конце списка.

• Следующие 21 бит являются случайными. Этот порядок позволяет нам чуть-чуть уменьшить ожидаемую длину индекса, так как при вставке строки между двумя существующими мы отсекаем хвост как только находим первый отличающийся байт.

• А последние 25 бит — это урезанный Unix timestamp. По сути, это цикл длиной в один год, но он позволяет существенно снизить вероятность генерации одинаковых суффиксов, поскольку я произвожу расчет один раз при запуске приложения.

Заключение

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