DS Структуры данных Структура данных
Список с пропусками
Также: Skip list · skiplist · список с пропусками Пью · ZSET · sorted set · сортированное множество Redis · memtable · ConcurrentSkipListMap
Отсортированный связный список с экспресс-линиями: каждый элемент бросает монетку и решает, на сколько уровней подняться. Поиск идёт по верхним линиям и спускается вниз — в среднем за O(log n), а вставка и удаление меняют только соседние ссылки, без поворотов. Поэтому на списках с пропусками держатся сортированные множества Redis, таблицы в памяти LevelDB и RocksDB и упорядоченный словарь Java для многих потоков.
13 июля 1995 года стартовал шаттл Discovery — полёт STS-70, — и веб-сервер Космического центра Кеннеди за сутки получил 34 236 запросов к 735 своим страницам. Представьте, что сервер ведёт таблицу самых популярных страниц, как это делают с помощью Redis: каждый запрос — команда ZINCRBY, «прибавить странице очко», а таблица в любой момент отвечает, кто на первом месте и на каком месте любая страница. Внутри Redis такая таблица — список с пропусками. К концу дня первой была страница /shuttle/countdown/liftoff.html — 4878 запросов, — а страница самой миссии стояла четвёртой. Ниже весь этот день проходит через список заново.
Нижняя линия — обычный отсортированный связный список: страницы по возрастанию числа запросов. Над ней — экспресс-линии: на второй останавливается примерно каждая четвёртая станция, на третьей — каждая шестнадцатая. Когда страница обгоняет соседей, её узел вынимают и ищут новое место: поиск идёт по самой верхней линии, пока следующая станция не окажется дальше цели, спускается, снова идёт вправо — оранжевая ломаная в сцене. За день так переставлено 8458 раз, по 35,2 шага на перестановку — два спуска сверху вниз по семнадцать с небольшим шагов. Остальные 25 043 прибавления обошлись вовсе без поиска: страница и с новым очком осталась между теми же соседями, и Redis в этом случае просто исправляет число на месте.
Идея
Отсортированный связный список, над которым надстроены экспресс-линии. Каждый элемент при вставке бросает монетку: с вероятностью p он поднимается на второй уровень, с вероятностью p² — на третий, и так далее. Поиск начинается с верхнего уровня, идёт вправо, пока следующий элемент меньше искомого, и спускается на уровень ниже — как пассажир, который едет на экспрессе, пока не проскочит нужную станцию, и пересаживается на электричку. Уровней в среднем log1/p n, на каждом — несколько шагов, а вставка меняет только ссылки у соседей нового узла.
Обычный связный список вставляет в середину за O(1), если известно место, но найти место можно только проходом с начала — O(n). Отсортированный массив находит место двоичным поиском, но вставляет сдвигом хвоста. Деревья умеют и то и другое за O(log n), но платят за это поворотами и правилами балансировки. Список с пропусками получает ту же оценку случайностью — как декартово дерево, только вместо приоритета у каждого элемента высота башни, а вместо поворотов — ничего: однажды выпавшую высоту никто не меняет.
Поиск, вставка, удаление
У списка есть голова — фиктивный узел с башней на все уровни. Поиск ключа x: стоим в голове на верхнем уровне; пока следующий узел на этом уровне существует и его ключ меньше x, шагаем к нему; когда шагать некуда, спускаемся на уровень ниже. На нижнем уровне следующий узел — либо x, либо первый ключ больше него. Вставка проходит тот же путь и запоминает на каждом уровне последний узел перед местом вставки; потом бросает монетку, пока выпадает «орёл», — столько этажей будет у башни нового узла, — и на каждом её этаже вклинивает узел между запомненным узлом и его следующим. Удаление — тот же путь и обратная операция: на каждом уровне, где был узел, ссылка предшественника перекидывается через него.
Здесь монетка честная, p = 1/2: каждый второй узел попадает на второй уровень, каждый четвёртый — на третий. Найдите 52: путь пройдёт по верхней линии до 44 и спустится — в нижнем ряду не придётся проходить ни 3, ни 7, ни 12. Вставьте несколько чисел подряд и посмотрите, как монетка решает высоту новой башни. Никакие другие башни при вставке не меняются: в этом главное отличие от деревьев, где вставка может перестроить путь до корня.
А если узлу не повезло и он остался низким, а соседям повезло и они высокие, ничего страшного не происходит — поиск просто спустится раньше. Структура никогда не нарушает своих правил, их просто нет: любой набор высот даёт правильный список. От высот зависит только скорость, и о ней можно рассуждать вероятностно.
Почему в среднем логарифм
Высота башни — сколько раз подряд выпал «орёл», плюс один: вероятность, что башня достаёт до k-го уровня, равна pk−1, и у разных элементов монетки независимы. Из этого выводится всё.
В среднем у элемента 1/(1 − p) ссылок: при p = 1/2 — две, при p = 1/4 — 4/3.
Ссылок у элемента столько, какова высота H его башни. Для величины, принимающей значения 1, 2, 3, …, среднее равно сумме вероятностей P(H ≥ k) по всем k ≥ 1: каждый уровень, до которого башня дотянулась, добавляет единицу. Получается 1 + p + p² + … = 1/(1 − p).
В списке из n элементов поиск любого ключа делает в среднем не больше ⌈log1/p n⌉/p + 1/(1 − p) + 1 шагов — переходов вправо и вниз.
Пройдём путь поиска задом наперёд: от узла с ключом на нижнем уровне к голове на верхнем. Каждый шаг назад — либо вверх (вперёд был спуск), либо влево (вперёд был шаг вправо). Стоя в узле v на уровне ℓ, обратный путь идёт вверх, если башня v достаёт до уровня ℓ + 1: тогда и прямой поиск пришёл сюда сверху. Иначе он идёт влево, к предыдущему узлу этого уровня. О башне v к этому моменту известно только то, что она достаёт до ℓ, поэтому до ℓ + 1 она достаёт с вероятностью p — независимо от всего пройденного. Пока путь не упёрся в голову, каждый его шаг — вверх с вероятностью p и влево с вероятностью 1 − p.
Пусть m = ⌈log1/p n⌉, так что n·pm ≤ 1. Разобьём обратный путь на две части. Подъём до уровня m. Нужно m − 1 шагов вверх, а каждый шаг оказывается шагом вверх с вероятностью p; в среднем на это уходит (m − 1)/p шагов, а если путь раньше дойдёт до головы — ещё меньше. Всё, что выше. Шаги влево там идут только через узлы, чьи башни достают до уровня m, каждый не больше одного раза; таких узлов в среднем n·pm−1 ≤ 1/p. Шагов вверх выше m столько, на сколько самая высокая башня выше m; вероятность, что хоть одна башня достаёт до m + j, не больше n·pm+j−1 ≤ pj−1, а сумма этих вероятностей по j ≥ 1 — это 1/(1 − p). Сложив, получаем (m − 1)/p + 1/p + 1/(1 − p) обратных шагов. Прямой поиск делает на один шаг больше: последний спуск с нижнего уровня к самому узлу.
Это рассуждение придумал сам Уильям Пью, когда предлагал списки с пропусками, — смотреть на путь с конца, где каждый шаг решает одна монетка. Оценка грубая, но форма верная: число уровней растёт как log1/p n, и на каждом уровне в среднем около 1/p шагов. Чем меньше p, тем меньше уровней, но длиннее каждый — второй листинг ниже сравнивает:
5000 random keys, 5 lists for each p p levels steps per search bound links per node 1/(1-p) 1/2 14.8 25.53 29.0 2.012 2.000 1/4 7.0 23.66 30.3 1.335 1.333 1/8 4.6 30.13 42.1 1.142 1.143 1/16 3.6 41.35 66.1 1.069 1.067
p = 1/4 даёт самый короткий поиск и всего треть ссылки сверх одной на элемент — ровно это значение стоит и в Redis, и в LevelDB. Высоты в таблице лидеров ведут себя по учебнику: из 735 страниц 547 остались на одном уровне при ожидаемых 551, 141 поднялась на второй при ожидаемых 138, а самая высокая башня в шесть этажей досталась одной странице.
Слово «в среднем» здесь значит то же, что у декартова дерева: среднее по броскам монетки, а не по данным. Никакой порядок ключей не испортит список, если монетка честная и противник её не видит. Худший случай — все башни одной высоты, и тогда поиск — проход по связному списку, — но вероятность этого исчезающе мала.
Как это устроено в Redis
Сортированное множество Redis — это пары «элемент, очко», упорядоченные по очку, а при равных очках — по самому элементу. Маленькие множества — до 128 элементов, каждый не длиннее 64 байт, — хранятся сплошным массивом (listpack), а большие — двумя структурами сразу: словарём «элемент → очко» и списком с пропусками. В комментарии к файлу t_zset.c сказано, что список — почти дословный перевод на C алгоритма Пью, изменённый в трёх местах: очки могут повторяться, сравнение идёт не только по очку, но и по элементу, и на нижнем уровне есть ссылки назад, чтобы ходить с конца, — это нужно для ZREVRANGE, «первые десять с конца».
Четвёртое отличие — длина прыжка у каждой ссылки: сколько элементов она перепрыгивает. На нижнем уровне это единица, на верхних — больше, и сумма длин на пути поиска — это номер элемента по порядку. Так ZRANK, «какое место у страницы», стоит столько же, сколько поиск, а ZRANGE 0 9 находит десятый с начала элемент спуском по длинам прыжков. При вставке длины пересчитываются на том же пути, что и ссылки. Ещё одна оптимизация видна в сцене: если новое очко не меняет порядка — элемент по-прежнему больше левого соседа и меньше правого, — Redis просто исправляет число в узле, не вынимая его. В таблице лидеров так прошли три прибавления из четырёх.
Почему Redis выбрал список, а не сбалансированное дерево, его автор Сальваторе Санфилиппо объяснил в 2010 году тремя причинами. Список не прожорлив по памяти, и, подбирая вероятность, его можно сделать экономнее B-дерева. Сортированные множества часто читают подряд — ZRANGE, ZREVRANGE, — и тогда список идёт по нижнему уровню как обычный связный список, с кэшем не хуже, чем у деревьев. И его проще писать и отлаживать: поддержку ZRANK за O(log n) добавили небольшой правкой — теми самыми длинами прыжков.
Конкурентный доступ
Вставка в список с пропусками меняет только ссылки соседей нового узла, по одной на каждом этаже его башни, и ни одного узла не перестраивает — нет поворотов, нет пересчёта высот до корня. Поэтому списки с пропусками — любимая основа упорядоченных структур, в которые одновременно пишут и читают несколько потоков: сериализовать нужно гораздо меньше, чем в деревьях.
Один писатель, много читателей. В LevelDB таблица в памяти — список с пропусками, и комментарий к файлу db/skiplist.h описывает договор: запись требует внешней синхронизации, обычно мьютекса, а чтение идёт без всяких блокировок. Это работает, потому что узлы никогда не удаляются, пока жив весь список, содержимое узла не меняется после того, как узел вставлен, а сама вставка сначала заполняет новый узел и только потом публикует ссылку на него — так, что читатель видит либо старый список, либо новый, но не полуготовый узел. В LevelDB, как и в Redis, p = 1/4, а уровней не больше 12.
Много писателей. В RocksDB таблица в памяти по умолчанию тоже список с пропусками, и только он поддерживает одновременную запись из нескольких потоков — это включено по умолчанию. В Java есть ConcurrentSkipListMap: упорядоченный словарь, в котором, как сказано в документации, вставка, удаление и чтение безопасно выполняются одновременно многими потоками. Комментарий в его исходнике объясняет устройство. Нижний уровень — неблокирующий связный список: узел добавляют атомарной операцией сравнения с обменом (CAS) на ссылке предшественника, а удаляя, сначала помечают особым узлом-маркером, чтобы никто не успел вставить что-то после удаляемого. Верхние уровни — отдельные узлы-указатели, их добавляют уже после того, как элемент появился внизу, и тоже через CAS. Если из-за гонки указатель не добавится, ничего не ломается: поиск по-прежнему находит всё, просто эффективная вероятность p чуть меньше номинальной. Верхние уровни — только подсказки, правда хранится внизу. Деревьям так не повезло: поворот меняет три ссылки сразу, и сделать его атомарным без блокировки куда труднее.
Код
Первый листинг — список с пропусками в духе Redis: пары «очко, элемент», монетка с вероятностью 1/4 из двух нулевых битов подряд, длины прыжков для ранга, ссылки назад, исправление очка на месте и проверка, что каждая длина прыжка равна числу перепрыгнутых элементов. Демонстрация — день 13 июля 1995 года на сервере Космического центра Кеннеди, тот же, что в сцене.
13 July 1995: 34236 requests to 735 pages, each one a ZINCRBY 1 4878 /shuttle/countdown/liftoff.html 2 3107 /shuttle/countdown/ 3 2199 /ksc.html 4 2004 /shuttle/missions/sts-70/mission-sts-70.html 5 1694 / 6 1400 /shuttle/missions/missions.html 7 1124 /shuttle/countdown/countdown.html 8 1078 /shuttle/missions/sts-70/movies/movies.html 9 1028 /shuttle/missions/sts-70/images/images.html 10 771 /shuttle/technology/sts-newsref/sts-lcc.html /shuttle/missions/sts-70/mission-sts-70.html: 4th from the top updates: 33501, 25043 in place, 8458 moved, 35.2 steps per move
Второй — голый список с пропусками без рангов, чтобы сравнить разные p на 5000 случайных ключах; его вывод — таблица в разделе о доказательстве. Чтобы одна случайно высокая башня не исказила картину, каждое p проверено на пяти списках с разными монетками.
Сколько это стоит
| Операция | В среднем | Худший случай |
|---|---|---|
| поиск, вставка, удаление | O(log n) | O(n), с ничтожной вероятностью |
| ранг и элемент по рангу (с длинами прыжков) | O(log n) | O(n) |
| следующий и предыдущий элемент | O(1) | O(1) |
| k элементов подряд | O(log n + k) | O(n) |
| память | n/(1 − p) ссылок | до 32 ссылок на элемент в Redis |
По асимптотике список с пропусками — то же, что сбалансированное дерево, только в среднем, а не в худшем случае. На практике разница в константах и в памяти: узлы разного размера, переходы по ссылкам в разные места памяти. Замер — вставка n случайных ключей в список с пропусками и в отсортированный массив.
В Go список с пропусками догоняет массив к десяти тысячам ключей, а на ста тысячах вставляет почти в шесть раз быстрее: массив сдвигает в среднем половину хвоста. В Python картина та же, что у деревьев поиска: bisect.insort сдвигает хвост на скорости C, и список из объектов не обгоняет его даже на ста тысячах элементов. Для таблицы лидеров на тысячу страниц Python-программе хватило бы отсортированного массива; список с пропусками окупается там, где элементов сотни тысяч и больше или где пишут сразу много потоков.
История
Уильям Пью придумал списки с пропусками в конце 1980-х и опубликовал их в 1990 году в статье «Списки с пропусками: вероятностная альтернатива сбалансированным деревьям». Главным аргументом была простота: алгоритмы короче, чем у сбалансированных деревьев, а оценки времени — те же, только в среднем. Его же отчёт «Поваренная книга списков с пропусками» собрал варианты и приёмы для разных операций; на него до сих пор ссылается комментарий в исходнике ConcurrentSkipListMap. Неблокирующие версии появились в начале 2000-х вместе с неблокирующими связными списками Тима Харриса и Магеда Майкла; на их основе Даг Ли написал ConcurrentSkipListMap, вошедший в Java 6.
Задачи
Задача — о цене поиска. Высоты башен уже выпали; нужно для каждого элемента узнать, сколько шагов сделает его поиск, не проходя этот путь каждый раз: идея — смотреть на путь с конца, как в доказательстве выше.
Цена поискаДанные: Журнал веб-сервера Космического центра Кеннеди, 13 июля 1995: NASA-HTTP, Internet Traffic Archive, свободно распространяется