Внутри Dolt, первой в мире базе данных SQL с полнофункциональными возможностями контроля версий, таится много интересной computer science. Недавно я писал о системе хранения Dolt, в ней есть очень тонкая особенность — применение вероятностного поиска на больших выборках 64-битных целых чисел.

В любом учебном плане по Computer Science есть курс алгоритмов. Моим был CS 102, и одним из пунктов, который объяснялся в нём досконально, было то, что поиск — это, по сути, задача O(log2(N)) при условии, если данные отсортированы. За свою карьеру я многократно встречался с этим в том или ином виде — если сортируешь информацию и сохраняешь её, то стоит ожидать, что для поиска потребуется время O(log2(N)). В общем случае мы соглашаемся на время поиска O(log2(N)), потому что оказывается, что можно перебрать большой объём данных с логарифмическим коэффициентом масштабирования. Эта система работает, потому что мы уже почти автоматически сортируем всё заранее.

Но что если мы добавим дополнительные ограничения на наши данные, которые позволят нам выполнять поиск за константное время?

Будет ли эта статья историей о необязательной оптимизации? Да, будет. В этом конкретном случае поиск будет занимать гораздо меньше времени, чем чтение с диска. Мы говорим о величинах менее чем 0,1% от суммарного времени. Будет ли эта статья историей о преждевременной оптимизации? Нет, не будет. Это бы подразумевало, что мы не осознаём, что время тратится не на то. Эта статья — история о заманчивости алгоритма константного времени.

Двоичный поиск

Для начала объясним причину того, что в общем случае поиск занимает O(log2(N)).

При работе с блоком отсортированных данных (мы будем использовать uint32) классический двоичный поиск работает, потому что на каждом шаге мы можем делить весь датасет пополам. Каждый последующий шаг, по сути, снова делит пространство поиска пополам. Вот пример двоичного поиска на Go:

func binarySearch(slice []uint32, target uint32) int {
	left := 0
	right := len(slice) - 1
	for left <= right {
		middle := left + (right-left)/2
		if slice[middle] == target {
			return middle // Найдено
		} else if slice[middle] < target {
			left = middle + 1 // Поиск в правой половине
		} else {
			right = middle - 1 // Поиск в левой половине
		}
	}
	return -1 // Not found
}

В качестве примера давайте поищем значение 61:

Первая средняя точка — это первый шаг, и к концу цикла мы исключаем половину пространства поиска:

На втором цикле средняя точка оказывается по индексу 11, значение в котором выше, чем нужное нам, поэтому мы сразу же перемещаемся, снова избавляясь от половины пространства поиска.

На третьем и последнем цикле мы находим нужное нам число:

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

Время для выполнения поиска — это, по сути, количество циклов, необходимых, чтобы добраться до места, где находится значение. Чтобы последовательно делить миллион, пока мы не найдём окончательный ответ, нам в среднем нужно примерно 19,93 шагов. Но если данных станет в два раза больше, то понадобится выполнить всего примерно 20,93 шагов, то есть время обработки увеличится всего на 5%, несмотря на увеличение объёма данных на 100%. Это очень удобно и позволяет выполнять поиск по большому объёму данных; необходимым требованием здесь остаётся только предварительная сортировка данных.

Вероятностный поиск

Можно ли придумать что-то лучше, чем двоичный поиск? Что если мы добавим ещё одно требование к нашим данным — обязательность их равномерного распределения? Если мы можем принять допущение о том, что у каждого значения во множестве примерно та же самая разность с соседом, что и у всех других элементов, то сможем делать более осознанные предположения, нежели просто на каждой итерации делить множество пополам.

Одним из базовых строительных блоков Dolt стали Prolly Tree, что расшифровывается как Probabilistic B-Tree (вероятностное B-дерево). Я буду использовать новый термин: Prolly Search — сокращение от Probabilistic Search («вероятностный поиск»).

Вот код:

func prollySearch(slice []int32, target int32) int {
	found := func() int {
		items := len(slice)
		if items == 0 {
			return 0
		}
		left, right := 0, items
		lo, hi := slice[0], slice[items-1]
		if target > hi {
			return right
		}
		if lo >= target {
			return left
		}
		for left < right {
			// Предполагаем, где, вероятно, может находиться значение, учитывая целевое значение и диапазон.
			valRangeSz := int64(hi - lo)
			idxRangeSz := uint64(right - left - 1)
			shiftedTgt := target - lo
			offset := (int64(shiftedTgt) * int64(idxRangeSz)) / valRangeSz
			guess := int(offset) + left

			if slice[guess] < target {
				left = guess + 1
				// Не нужно обновлять lo, если left == items, потому что этот цикл будет заканчиваться.
				if left < items {
					lo = slice[left]
					if lo >= target {
						return left // Нашли значение или оно не существует.
					}
				}
			} else {
				right = guess
				hi = slice[right]
			}
		}
		return left
	}()
	// Приведённый выше код хорошо сочетается с интерфейсом sort.Search,
	// но эта проверка делает его поведение идентичным с binarySearch.
	if found < len(slice) && slice[found] == target {
		return found
	}
	return -1
}

По сути, общая идея этого кода такая же, как у двоичного поиска — мы перемещаем курсоры left и right, сужая пространство поиска. Небольшое различие заключается в том, что right всегда на 1 правее. Так сделано для удобства работы с интерфейсом sort.Search, который возвращает место вставки элемента. Наша настоящая реализация рассчитана на значения uint64, поэтому для угадывания мы используем 128-битные значения. Использование значений uint32 позволяет нам применять для избегания переполнений uint64, чтобы код был понятнее.

В начале left и right находятся в крайних точках.

Далее мы вычисляем предположение:

			valRangeSz := int64(hi - lo)                                   // valRangeSz = 97
			idxRangeSz := uint64(right - left - 1)                         // idxRangeSz = 15
			shiftedTgt := target - lo                                      // shiftedTgt = 60
			offset := (int64(shiftedTgt) * int64(idxRangeSz)) / valRangeSz // offset = 9
			guess := int(offset) + left                                    // guess = 9

slice[guess] не меньше target, поэтому:

				right = guess                                             // right = 9
				hi = slice[right]                                         // hi = 61

Затем мы делаем ещё одно предположение:

			valRangeSz := int64(hi - lo)                                   // valRangeSz = 60
			idxRangeSz := uint64(right - left - 1)                         // idxRangeSz = 8
			shiftedTgt := target - lo                                      // shiftedTgt = 60
			offset := (int64(shiftedTgt) * int64(idxRangeSz)) / valRangeSz // offset = 8
			guess := int(offset) + left                                    // guess = 8

slice[guess] меньше target, поэтому мы увеличиваем значение left  и находим совпадение

				left = guess + 1                                           // left = 9

Используя те же данные и начальные условия, prollySearch нашёл совпадение за 2 шага, в то время как binarySearch потребовалось 3 шага. Это критически важно для производительности — чем больше циклов, тем больше времени. Делая обоснованные предположения на основании наших знаний о данных, мы можем быстрее прийти к вероятному местоположению, чем при простом уменьшении множества вдвое при каждой итерации.

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

Результаты

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

Вот график среднего времени на поиск в зависимости от количества элементов:

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

Если же мы рассмотрим стандартное отклонение каждого поиска в своём множестве, то получим вот такой любопытный результат:

Стандартное отклонение Prolly Search всегда выше, чем у двоичного поиска. Это означает, что хотя в среднем он быстрее, время от времени возникают выбросы, требующие больше времени, чем остальные во множестве. Это логично, потому что итерации двоичного поиска можно вычислять достаточно механически вне зависимости от данных. «Волны» на графике двоичного поиска чётко демонстрируют, что на дисперсию поиска влияет размер выборки. Спады в дисперсии двоичного поиска совпадают со степенями двойки, то есть с 33 миллионами и 67 миллионами (2^25 и 2^26).

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

На графиках представлен поиск среди значений до 100 миллионов. Среднее количество итераций Prolly никогда не поднималось выше 4,9. Я провёл тест на выборке в 1 миллиард, и среднее количество итераций стало примерно равным 5,1. Что ж... Не думаю, что можно заявлять доказуемость константного времени, но меня это вполне устраивает.

Недостатки

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

Кроме того, если у вас бывают скопления плотных данных, то алгоритм регрессирует до производительности O(N), что гораздо хуже, чем надёжное поведение O(log2(N)). Двоичный поиск оказывается крайне устойчивым к плохому распределению данных. Именно поэтому он много десятилетий остаётся «рабочей лошадкой» отрасли баз данных. Каждый поисковый индекс, когда-либо задействованный вами, использует двоичный поиск; вероятно, так будет и дальше.

В заключение

То, что в Dolt используются объекты адресов контента, обеспечивает ему интересные свойства. Мы много говорили о Prolly Tree в своём блоге; они возможны только благодаря тому распределению значений, которое мы получаем при работе с криптографическими контрольными суммами.