Lock-free структуры данных. Concurrent maps: skip list

Представьте, что ваш коллега-нытик пришел рассказать о своей непростой задаче - ему нужно не просто упорядочить по возрастанию набор целых чисел, а выдать все элементы упорядоченного набора с L-го по R-й включительно!
Вы заявили, что это элементарная задача и, чтобы написать решение на языке C#, вам нужно десять минут. Ну, или час. Или два. Или шоколадка «Алёнка»

К оценке решения есть несколько комментариев:

Ваш код будут оценивать и тестировать три программиста:

• Билл будет запускать ваше решение на тестах размером не больше 10Кб.
• В тестах Стивена количество запросов будет не больше 10^5, при этом количество запросов на добавление будет не больше 100.
• В тестах Марка количество запросов будет не больше 10^5.

Решение

Обозначим Add(e) - добавление элемента в хранилище, а Range(l, r) - взятие среза с l по r элемент.

Тривиальный вариант хранилища может быть таким:

• Основой хранилища будет упорядоченный по возрастанию динамический массив.
• При каждой вставке бинарным поиском находится позицию, в которую необходимо вставить элемент.
• При запросе Range(l, r) будем просто брать срез массива из l по r.

C Range(l, r) - взятие среза можно оценить, как O(r - l).

C Add(e) - вставка в худшем случае будет работать за O(n), где n - количество элементов. При n ~ 10^6, вставка - узкое место. Ниже в статье будет предложен улучшенный вариант хранилища.

Пример исходного кода можно посмотреть .

Skiplist

Эта структура данных не получила широкой известности (кстати, и на хабре достаточно обзорно о ней написано), хотя у нее хорошие асимптотические оценки. Любопытства ради захотелось ее реализовать, тем более имелась подходящая задача.

Пусть у нас есть отсортированный односвязный список:

В худшем случае поиск выполняется за O(n). Как его можно ускорить?

В одной из видео-лекций, которые я пересматривал, когда занимался задачкой, приводился замечательный пример про экспресс-линии в Нью-Йорке:

• Скоростные линии соединяют некоторые станции
• Обычные линии соединяют все станции
• Есть обычные линии между общими станциями скоростных линий

На примере изображен идеальный SkipList, в реальности всё выглядит подобным образом, но немного не так:)

Поиск

Вставка

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

Предположил, что монетка выпала два раза подряд. Значит нужно протолкнуть элемент на два уровня вверх:

Доступ по индексу

После того, как мы получаем доступ к i-му элементу (кстати, получаем мы его за O(ln n)), сделать срез не представляется трудным.

Пусть необходимо найти Range(5, 7). Сначала получим элемент по индексу пять:

А теперь Range(5, 7):

О реализации

SkipListNode {
int Element;
SkipListNode Next;
int Width;
}

Но в C# в массиве хранится еще и его длина, а хотелось сделать это за как можно меньшее количество памяти (как оказалось, в условиях задачи все оценивалось не так строго). При этом хотелось сделать так, чтобы реализация SkipList и расширенного RB Tree занимала примерно одинаковое количество памяти.

Ответ, как уменьшить потребление памяти, неожиданно был найден при ближайшем рассмотрении из пакета java.util.concurrent.

Двумерный skiplist

ListNode {
int Element;
ListNode Next;
}

Lane {
Lane Right;
Lane Down;
ListNode Node;
}

Нечестная монетка

Немного о генерации случайных чисел

int randomLevel() {
int x = randomSeed;
x ^= x << 13;
x ^= x >>> 17;
randomSeed = x ^= x << 5;
if ((x & 0x80000001) != 0)
return 0;
int level = 1;
while (((x >>>= 1) & 1) != 0) ++level;
return level;
}

Исходник получившегося хранилища можно глянуть .

Все вместе можно забрать с googlecode.com (проект Pagination).

Тесты

1. ArrayBased (динамический массив)
2. SkipListBased (SkipList c параметром ¼)
3. RBTreeBased (красно-черное дерево: реализация моего знакомого, который выполнял аналогичное задание).

1. Упорядоченные по возрастанию элементы
2. Упорядоченные по убыванию элементы
3. Случайные элементы

Также были проведены замеры: сколько каждое хранилище занимает в памяти при вставленных в него 10^6 элементах. Использовался студийный профайлер, для простоты запускался такой код:

var storage = ...
for (var i = 0; i < 1000000; ++i)
storage.Add(i);

Хеппи-энд с «Алёнкой»

P.S.: я был на стажировке в компании СКБ Контур. Это чтобы не отвечать на одинаковые вопросы =)

СКИП – это система контроля исполнения поручений на базе MS SharePoint, позволяющая полностью автоматизировать процесс работы с поручениями. Это продуманное, коробочное решение для организации работы с поручениями. Оно подходит как для работы в крупных и территориально-распределенных компаниях, так и для компаний среднего бизнеса за счет возможности осуществления максимально гибкой настройки всех модулей.

Система СКИП базируется на платформе Microsoft SharePoint, что автоматически означает возможность ее интеграции с продуктами Microsoft, в том числе Microsoft Office.

Функциональные возможности системы

Система СКИП является «коробочным» решением и в этом варианте содержит базовый набор функциональных возможностей, необходимых для автоматизации работы с поручениями:

• Назначение, исполнение, контроль поручения;
• Отслеживание статуса исполнения поручения;
• Возможность создавать вложенные («дочерние») поручения.

Список поручений с цветовой индикацией

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

• Каталогизация поручений (одно поручение может располагаться в различных папках);
• Фильтрация списков поручений;
• Экспорт списков поручений в MS Excel;
• Отчеты по исполнительской дисциплине;
• Цветовая индикация поручений в зависимости от срока исполнения и статуса поручения;
• Возможность прикрепления произвольного количества файлов любых форматов к Карточке поручения;
• Интеграция с календарями Outlook;
• Настраиваемые оповещения о назначении и ходе работы с поручением;
• Система замещения сотрудников на период отпуска или командировки;
• Создание периодических поручений (или поручений с расписанием) для мероприятий, которые имеют определенный период (совещания, встречи и т.д.);
• Отображение сроков исполнения поручений на диаграмме Ганта;
• и прочее

Список поручений с диаграммой Ганта

В предыдущих статьях (раз , два) мы рассматривали классический hash map с хеш-таблицей и списком коллизий. Был построен lock-free ordered list, который послужил нам основой для lock-free hash map.
К сожалению, списки характеризуются линейной сложностью поиска O(N) , где N - число элементов в списке, так что наш алгоритм lock-free ordered list сам по себе представляет небольшой интерес при больших N .
Или все же представляет?..

Существует довольно любопытная структура данных - skip-list , основанная на обычном односвязном списке. Впервые она была описана в 1990 году W.Pugh, перевод его оригинальной статьи есть на хабре. Эта структура представляет для нас интерес, так как, имея алгоритм lock-free ordered list, довольно легко реализовать lock-free skip-list.
Для начала - немного о принципах построения skip-list. Skip-list представляет собой многоуровневый список: каждый элемент (иногда называемый башней, tower) имеет некоторую высоту h .


Высота h выбирается случайным образом из диапазона , где Hmax - максимально возможная высота, обычно 16 или 32. Вероятность того, что высота башни равна единице, есть P = 1/2 . Вероятность высоты k есть:

Несмотря на кажущуюся сложность вычисления высоты, её можно рассчитать довольно просто, например, так: h = lsb(rand()) , где lsb - номер младшего значащего бита числа.

Magic 1/2

На самом деле, константа 1/2 - это мое упрощение, в оригинальной статье идет речь о 0 < p < 1 и исследуется поведение skip-list при различных значениях p . Но для практической реализации p = 1/2 - наилучшее значение, мне кажется.

Lock-free skip list

Как видим, процедуры вставки/удаления из lock-free skip-list многошаговые, на каждом шаге возможна интерференция с конкурирующими операциями, поэтому при программировании skip-list нужна особая аккуратность. Например, при вставке мы сначала ищем позиции в списках на всех уровнях и формируем массивы prev . Вполне возможно, что в процессе вставки список на каком-то уровне изменится и эти позиции станут невалидными. В этом случае следует обновить prev , то есть найти вставляемый элемент, и продолжить вставку, начиная с уровня, на котором произошел облом.
Более интересна ситуация, когда происходит одновременная вставка ключа K и его удаление. Такое вполне возможно: вставка считается успешно выполненной, когда мы связали элемент на уровне 0 списка. После этого элемент уже достижим и его вполне можно удалить, несмотря на то, что он ещё не до конца вставлен в верхние уровни. Для разрешения коллизии вставки и удаления очень важен порядок: вставка производится снизу вверх, а удаление (точнее, его первая фаза - логическое удаление, marked pointer) - противоходом, сверху вниз. В таком случае процедура вставки обязательно увидит на каком-либо уровне метку удаления и немедленно прекратит свою работу.
Процедура удаления также может быть конкурентной на обоих своих фазах. На фазе логического удаления, когда проставляются метки на башне сверху вниз, нам конкуренция не страшна. А вот на фазе исключения удаляемого элемента из списков любое изменение skip-list"а, то есть нарушение массивов prev и found , определяющих позицию удаляемого элемента, приводит к тому, что нам надо эти массивы сформировать заново. Но метки уже проставлены и функция поиска просто не найдет удаляемый элемент! Для разрешения этой ситуации мы наделяем функцию поиска несвойственной ей работой: при обнаружении помеченного на каком-либо уровне элемента функция поиска исключает (unlink) этот элемент из списка этого уровня, то есть помогает удалять элементы. После исключения функция возобновляет поиск с самого начала, то есть с самого верхнего уровня (здесь возможны вариации, но самое простое - начать с начала). Это типичный пример взаимопомощи, часто встречающийся в lock-free программировании: один поток помогает другому делать его работу. Именно поэтому функция find() во многих lock-free контейнерах не является константной - поиск может изменить контейнер.
Чем ещё характеризуется skip-list? Во-первых, это упорядоченный map, в отличие от hash map, то есть поддерживает операции извлечения минимального extract_min() и максимального extract_max() ключей.
Во-вторых, skip-list прожорлив для схемы Hazard Pointrer (HP): при максимальной высоте башни 32 элементы массивов prev и found , определяющих искомую позицию, должны быть защищены hazard pointer"ами, то есть нам требуется минимум 64 hazard pointer"а (на самом деле, в реализации libcds – 66). Это довольно много для схемы HP, см. подробнее её устройство . Для схемы RCU некоторую сложность представляет реализация метода find() , так как этот метод может удалять элементы, а схема RCU требует, чтобы удаление исключение (unlink) элемента из списка было под критической секцией RCU, а удаление деаллокация памяти - вне критической секции, иначе возможен deadlock.
Интересную практическую задачу представляет собой реализация башен для высоты более 1. Сейчас в реализации skip-list в библиотеке libcds память под башни высотой более 1 распределяется отдельно от памяти под элемент даже для интрузивного варианта. Учитывая вероятностную природу высоты, получается, что для 50% элементов делается распределение памяти, - это может сказаться на производительности, а также негативно влияет на фрагментацию памяти. Есть задумка башни высотой не более h_min распределять одним блоком и только для высоких «дораспределять» память под башню:
template struct tower { tower * next; tower * high_next; // массив для указателей уровней >= Hmin };
Если Hmin = 4 , то при таком построении 93% элементов не потребуют распределения дополнительной памяти под указатели next - high_next для них будет nullptr .

skip-list: библиография

W.Pugh спустя год-два после опубликования своей работы о skip-list представил другую работу, посвященную конкурентной реализации, основанной на аккуратной расстановке блокировок (fine-grained locks).
Наиболее цитируемая работа по lock-free skip-list – это диссертация K.Fraser Practical lock-freedom 2003 года, в которой представлено несколько алгоритмов skip-list как на основе транзакционной памяти, так и на программной реализации MCAS (CAS над несколькими ячейками памяти). Эта работа представляет сейчас, на мой взгляд, чисто теоретический интерес, так как программная эмуляция транзакционной памяти довольно тяжела, равно как и MCAS. Хотя с выходом Haswell реализация транзакционной памяти в железе пошла в массы…
Реализация skip-list в libcds сделана по мотивам неоднократно цитируемой мною монографии The Art of Multiprocessor Programming . «По мотивам» потому, что оригинальный алгоритм приведен для Java и имеет, как мне кажется, несколько ошибок, которые, быть может, были исправлены во втором издании. Или это вовсе не ошибки для Java.
Есть ещё диссертация Фомичева , посвященная вопросу возобновления поиска в случае обнаруженных конфликтов в skip-list. Как я упоминал выше, find() при обнаружении помеченного (marked) элемента пытается удалить его из списка и возобновляет поиcк с самого начала . Фомичев предлагает механизм расстановки back-reference – обратных ссылок, чтобы работу возобновлять с некоторого предыдущего элемента, а не с начала, что, в принципе, должно повлиять на производительность в лучшую сторону. Алгоритм поддержки back-reference в актуальном состоянии довольно сложный и непонятно, будет ли выигрыш или же его съест код поддержки актуальности.

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

Интересной разновидностью структуры данных эффективной реализации АТД «упорядоченный словарь» является skip^cnucoK (skip list). Эта структура данных организует объекты в произвольном порядке таким

образом, что поиск и обновление в среднем выполняются за 0(log п) времени, где п - количество объектов словаря. Интересно, что понятие усредненной временной сложности, используемое здесь, не зависит от возможного распределения ключей при вводе. Наоборот, оно продиктовано использованием генераторов случайных чисел в реализации процесса ввода, чтрбы облегчить процесс принятия решения о месте вставки нового объекта. Время выполнения в этом случае будет равно среднему значению времени выполнения ввода любых случайных чисел, используемых в качестве входных объектов.

Методы генерации случайных чисел встраиваются в большинство современных компьютеров, поскольку они широко применяются в компьютерных играх, криптографии и компьютерных симуляторах. Некоторые методы, называемые генераторами псевдослучайных чисел (pseudorandom number generators), генерируют псевдослучайно числа по некоторому закону, начиная с так называемого начального числа (seed). Другие методы используют аппаратные средства для извлечения «действительно» случайных чисел. В любом случае компьютер имеет числа, отвечающие требованиям, предъявляемым к случайным числам в приводимом анализе.

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

Пусть skip-список S для словаря D состоит из серии списков {iSo, S\, Si, З/j}. Каждый список S\ хранит набор объектов словаря D по ключам в неубывающей последовательности плюс объекты с двумя специальными ключами, записываемыми в виде «-оо» и «+оо», где «-оо» обозначает меньше, а «+оо» - больше любого возможного ключа, который может быть в D. Кроме того, списки в Sотвечают следующим требованиям:

Список S 0 содержит каждый объект словаря D (плюс специальные объекты с ключами «-оо» и «+оо»);

Для / = 1, …, h – 1 список Si содержит (в дополнение к «-оо» и «+оо») случайно сгенерированный набор объектов из списка S t _ ь

Список S h содержит только «-оо» и «+оо».

Образец такого skip-списка приведен на рис. 8.9, наглядно представляющем списодс S со списком в основании и списками S\, …, S^ над ним. Высоту (height) списка S обозначим как h.

Рис. 8.9. Пример skip-списка

Интуитивно списки организованы таким образом; чтобы?/+/ содержал хотя бы каждый второй объект 5/. Как будет показано при рассмотрении метода ввода, объекты в St+\ выбираются произвольно из объектов в Si с таким расчетом, чтобы каждый выбираемый объект 5/ входил в 5/ + \ с вероятностью 1/2. Образно говоря, помещать или нет объект из в Si + 1, определяем в зависимости от того, какой стороной упадет подкидываемая монетка - орлом или решкой. Таким образом, можно считать, что S\ содержит около я/2 объектов, S2 - я/4, и, соответственно, Sj - около п/2′ объектов. Другими словами, высота h списка S может составлять около logn. Хотя при этом деление пополам числа объектов от одного списка к другому не является обязательным требованием в виде явно выраженного свойства skip-списка. Наоборот, случайный выбор важнее.

Используя позиционную абстракцию применительно к спискам и деревьям, можно рассматривать skip-список как двухмерную коллекцию позиций, организованных горизонтально в уровни (levels) и вертикально в башни (towers). Каждый уровень - это список S^ а каждая башня - набор позиций, хранящих один и тот же объект и расположенных друг над другом в списках. Позиции skip-списка можно проходить с помощью следующих операций:

after(/?): возвращает позицию, следующую за р ца том же уровне; before(/?): возвращает позицию, предшествующую р на том же уровне; below(/?): возвращает позицию, расположенную под р в той же башне; above(/?): возвращает позицию, расположенную над р в той же башне.

Установим, что перечисленные выше операции должны возвращать null, если запрашиваемой позиции не существует. Не вдаваясь в подробности, заметим, что skip-список легко реализуется с помощью связной структуры таким образом, что методы прохода требуют 0(1) времени (при наличии в списке позиции р). Такая связная структура представляет собой коллекцию из h двусвязных списков, объедийёйй^ й^айШ, в свою очередь являющиеся двусвязными списками.

Структура skip-списка позволяет применять простые поисковые алгоритмы для словарей. В действительности все поисковые алгоритмы skip-списка основываются на достаточно элегантном методе SkipSearch, принимающем ключ к и находящим объект в skip-списке S с наибольшим ключом (который может оказаться «-оо»), меньшим или равным к. Допустим, имеется искомый ключ к. Метод SkipSearch устанавливает позицию р в самой верхней левой позиции в skip-списке S. То есть р устанавливается на позиции специального объекта с ключом «-оо» в S^. Затем выполняется следующее:

1) если S.below(/?) равен null, то поиск заканчивается - на уровень ниже обнаружен наибольший объект в Sс ключом, меньшим или равным искомому ключу к. В противном случае опускаемся на один уровень в данной башне, устанавливая р S.be\ow(p);

2) из позиции р продвигаемся вправо (вперед) до тех пор, пока не окажемся в крайней правой позиции текущего уровня, где кеу(/?) < к. Такой шаг называется сканированием вперед (scan forward). Указанная позиция существует всегда, поскольку каждый уровень имеет специальные ключи «+оо» и «-оо». И на самом деле, после шага вправо по текущему уровню р может остаться на исходном месте. В любом случае после этого снова повторяется предыдущее действие.

Рис. 8.10. Пример поиска в skip-списке. Обследованные во время поиска ключа 50 позиции выделены штриховым обозначением

Фрагмент кода 8.4 содержит описание поискового алгоритма skip-списка. Имея такой метод, несложно реализовать операцию findElement(/:). Выполняется операция р^- SkipSearch(A;) и проверяется равенство key{p)~ k. При ^равенстве возвращается /?.element. В противном случае возвращается сигнальное сообщение NO_SUCH_KEY.

Алгоритм SkipSearch(/:):

Input: поисковый кл?оч к.

Output: позиция р в S, объект которой имеет наибольший ключ, меньший или равный к.

Допустим, что р - самая верхняя левая позиция в S (состоящей как минимум из двух уровней), while below (р) * null do

р below(p) {просканировать вниз} while key(after(p)) < к do

Let p after(p) {просканировать вперед} return p

Фрагмент кода 8.4. Алгоритм поиска в skip-списке S

Оказывается, предполагаемое время выполнения алгоритма SkipSearch составляет 0(log п). Прежде чем обосновать это, приведем реализацию методов обновления skip-списка

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

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

Балансировать структуру данных вероятностно проще, чем явно обеспечивать баланс. Для многих задач списки пропуска это более естественное представление данных по сравнению с деревьями. Алгоритмы получаются более простыми для реализации и, на практике, более быстрыми по сравнению со сбалансированными деревьями. Кроме того, списки с пропусками очень эффективно используют память. Они могут быть реализованы так, чтобы на один элемент приходился в среднем примерно 1.33 указатель (или даже меньше) и не требуют хранения для каждого элемента дополнительной информации о балансе или приоритете.

Для поиска элемента в связном списке мы должны просмотреть каждый его узел:

Если список хранится отсортированным и каждый второй его узел дополнительно содержит указатель на два узла вперед, нам нужно просмотреть не более, чем ⌈n /2⌉ + 1 узлов(где n - длина списка):

Аналогично, если теперь каждый четвёртый узел содержит указатель на четыре узла вперёд, то потребуется просмотреть не более чем ⌈n /4⌉ + 2 узла:

Если каждый 2 i i узлов вперёд, то количество узлов, которые необходимо просмотреть, сократится до ⌈log 2 n ⌉, а общее количество указателей в структуре лишь удвоится:

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

Назовём узел, содержащий k указателей на впередистоящие элементы, узлом уровня k . Если каждый 2 i -ый узел содержит указатель на 2 i узлов вперёд, то уровни распределены так: 50% узлов - уровня 1, 25% - уровня 2, 12.5% - уровня 3 и т.д. Но что произойдёт, если уровни узлов будут выбираться случайно, в тех же самых пропорциях? Например, так:

Указатель номер i каждого узла будет ссылаться на следующий узел уровня i или больше, а не на ровно 2 i -1 узлов вперёд, как было до этого. Вставки и удаления потребуют только локальных изменений; уровень узла, выбранный случайно при его вставке, никогда не будет меняться. При неудачном назначении уровней производительность может оказаться низкой, но мы покажем, что такие ситуации редки. Из-за того, что эти структуры данных представляют из себя связные списки с дополнительными указателями для пропуска промежуточных узлов, я называю их списками с пропусками .

Операции

Каждый элемент списка представляет из себя узел, уровень которого был выбран случайно при его создании, причём независимо от числа элементов, которые уже находились там. Узел уровня i содержит i указателей на различные элементы впереди, проиндексированные от 1 до i . Мы можем не хранить уровень узла в самом узле. Количество уровней ограничено заранее выбранной константой MaxLevel . Назовём уровнем списка максимальный уровень узла в этом списке (если список пуст, то уровень равен 1). Заголовок списка (на картинках он слева) содержит указатели на уровни с 1 по MaxLevel . Если элементов такого уровня ещё нет, то значение указателя - специальный элемент NIL.

Инициализация

Поиск элемента

Search (list, searchKey)
x:= list→header
# инвариант цикла: x→key < searchKey
for i:= list→level downto 1 do
while x→forward[i]→key < searchKey do
x:= x→forward[i]
# x→key < searchKey ≤ x→forward→key
x:= x→forward
if x→key = searchKey then return x→value
else return failure

Вставка и удаление элемента

Insert (list, searchKey, newValue)
local update
x:= list→header
for i:= list→level downto 1 do
while x→forward[i]→key < searchKey do
x:= x→forward[i]
# x→key < searchKey ≤ x→forward[i]→key
update[i] := x
x:= x→forward
if x→key = searchKey then x→value:= newValue
else
lvl:= randomLevel()
if lvl > list→level then
for i:= list→level + 1 to lvl do
update[i] := list→header
list→level:= lvl
x:= makeNode(lvl, searchKey, value)
for i:= 1 to level do
x→forward[i] := update[i]→forward[i]
update[i]→forward[i] := x

Delete (list, searchKey)
local update
x:= list→header
for i:= list→level downto 1 do
while x→forward[i]→key < searchKey do
x:= x→forward[i]
update[i] := x
x:= x→forward
if x→key = searchKey then
for i:= 1 to list→level do
if update[i]→forward[i] ≠ x then break
update[i]→forward[i] := x→forward[i]
free(x)
while list→level > 1 and list→header→forward = NIL do
list→level:= list→level – 1

Для запоминания элементов перед вставляемым(или удаляемым) используется массив update . Элемент update[i] - это указатель на самый правый узел, уровня i или выше, из числа находящихся слева от места обновления.

Если случайно выбранный уровень вставляемого узла оказался больше, чем уровень всего списка (т.е. если узлов с таким уровнем ещё не было), увеличиваем уровень списка и инициализируем соответствующие элементы массива update указателями на заголовок. После каждого удаления проверяем, удалили ли мы узел с максимальным уровнем и, если это так, уменьшаем уровень списка.

Генерация номера уровня

randomLevel ()
lvl:= 1
# random() возвращает случайное число в полуинтервале }