http://habrahabr.ru/post/222565/

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

Есть некоторое множество объектов, и некоторое множество тегов. Каждый объект может содержать несколько тегов. Какие-то теги очень редкие, а какие-то встречаются часто. Одному объекту один тег может быть сопоставлен несколько раз.
Новые объекты, теги и связи между ними непрерывно добавляются.
Задача — очень быстро отвечать на вопросы вида: «сколько есть объектов, у которых есть тег А или B, но нету тега С» и похожие. На такие запросы хотелось бы отвечать за десятые доли секунды, при этом не останавливая загрузку данных.

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

SELECT 
    COUNT(*) 
FROM (
    SELECT 
        object_id, 
        (MAX(tag == A) OR MAX(tag == B)) AND MIN(tag != C) AS good
    FROM tags
    WHERE tag IN (A, B, C)
    GROUP BY object_id
) WHERE good == 1;

Чтобы такой запрос выполнялся быстро, мы разбили данные между серверами кластера по object_id, а внутри каждого сервера отсортировали их по тегам. Таким образом сервер, выполняющий запрос, может отправить запрос без изменений на все сервера с данными, а затем просто сложить их результаты. На каждом сервере с данными для выполнения запроса достаточно найти строки для тегов A, B и C (а так как данные по тегу отсортированы, это быстрая операция), после чего выполнить запрос за один проход по этим строкам. Худший тег имеет несколько десятков миллионов объектов, несколько десятков миллионов строк обработать за десятые доли секунды видится возможным.
Стоит отметить, что подзапрос содержит GROUP BY object_id. GROUP BY в данной ситуации можно выполнить несколькими способами, например, если данные после тега отсортированы по object_id, то можно выполнить что-то похожее на merge sort. В данной ситуации, однако, мы данные по object_id не отсортировали, и оптимизатор разумно решил, что для выполнения GROUP BY надо построить хеш-таблицу.

Мы загрузили все данные в кластер, и запустили запрос. Запрос занял 25 секунд.

Что-то пошло не так.
Первым делом мы убрали GROUP BY object_id, чтобы локализовать, где возникла проблема. Запрос закончился за ожидаемые 0.3 секунды. Значит чтение данных работает достаточно быстро, и ничего лишнего по сети не передается. Проблема где-то в хеш-таблице.
Развернули отладочный сервер, и начали писать в лог различную статистику. Спустя некоторое время стало понятно, что в хеш таблице какие-то значения хеш-функции появляются гораздо чаще, чем другие. При том, что количество цепочек было больше, чем количество записей в таблице, самая длинная цепочка имела длину порядка 32. Значит, что-то с хеш функцией не так. Открыв реализацию, мы увидели примерно следующее:

uint64_t hash(uint64_t value) {
    return value * MULTIPLIER1;
}

uint64_t accumulateHash(uint64_t hash, uint64_t value) {
    hash ^= hash >> SHIFT1;
    hash += value;
    hash ^= hash >> SHIFT2;
    hash *= MULTIPLIER2;
    return hash;
}

Игра с битами показалась очень подозрительной. Кто-то явно думал, что это хорошая идея сделать функцию более запутанной, когда писал этот код, но похоже что перестарался. Мы закомментировали обе строки с XOR и SHIFT, и перезапустили кластер. Запрос закончился за 0.5 секунд, победа.

На следующее утро я решил узнать, кто же изначально написал эти две строки. Сделал git blame и нашел злополучный коммит. Интересно, что в этом коммите из всех изменений в код сервера были добавлены только эти две строки, до этого функция accumulateHash состояла из суммы и умножения. Однако, помимо добавления этих двух строк, автор коммита добавил еще и так называемый avalanche test — тест, который убеждается, что любые, даже самые незначительные, изменения входных чисел приводят к совершенно случайным изменениям в хеш-функции. Тест был основан на какой-то публикации какого-то кандидата наук, и казался разумным. При этом тест не проходил без XOR и SHIFT, но проходил с ними. То есть автор коммита не просто написал запутанную функцию, он понимал, что он делает. Но почему на практике функция повела себя так непредсказуемо?

Чтобы разобраться с этим вопросом, я скачал данные для одного из тегов на локальную машину, и начал эксперементировать. Действительно, наша текущая хеш-функция давала коллизии: все значения имели одинаковые старшие пять бит. Однако эта же функция с другими SHIFT1 и SHIFT2 уже давала хорошие результаты. Тогда я сгенерировал случайные 10 миллионов чисел, и построил хеш таблицу снова, используя нашу плохую хеш-функцию. В этот раз аномальных коллизий тоже не было. То есть на случайных числах хеш-функция ведет себя хорошо, проблема где-то на пересечении нашей хеш-функции и данных пользователя. Начал искать закономерности в данных пользователя. Закономерности есть: они все делятся на 64, и у них у всех одинаковые старшие пять бит. Генерирую набор случайных чисел, кратных 64 с теми же старшими пятью битами. Нет, все равно коллизий нет. В чем же еще может быть проблема? Неужели способ, которым генерируются айди объектов как-то нивелирует нашу хеш функцию?

Решив на следующий день узнать у клиента, как именно они генерируют эти айди, я уже почти собрался домой, когда один из коллег меня спросил: а этот столбик, по которому я делаю GROUP BY, это случайно не тот же столбик, по которому я данные разбил между серверами?
Да, это действительно тот же столбик. Оказывается, из-за бага в коде для разбиения по разделам и для выполнения GROUP BY использовалась одна и таже хеш функция. На каждом из четырех физических серверов было по 8 разделов, итого 32 раздела, для выбора раздела используются старшие биты хеш функции. В итоге для всех строк в одном разделе старшие пять бит у значения хеш-функции от object_id будут одинаковыми. Когда мы закомментировали XOR и SHIFT в хеш функции, и перезапустили кластер, мы не загрузили заново данные, тем самым сделав видимость того, что проблема исправилась, так как теперь данные были разбиты по хеш функции, отличной от той, которая применяется для GROUP BY, но если бы мы начали загружать свежие данные, то в итоге проблема бы опять дала о себе знать.

Хеш функцию мы вернули к виду, в котором она проходит avalanche test, и поменяли хеш-функцию для разбиения по разделам, а один из коллег поделился забавной историей: на соревновании по программированию он на Java строил хеш таблицу по двумерным координатам. Координаты представляли собой два числа по 32 бита каждое, и чтобы код работал эффективно, он их записывал в одно 64-битное число, и клал в хеш-таблицу. К сожалению, задача не прошла по времени, потому что в Java хеш-функция вычисляет XOR старших и младших 32 бит, тем самым всегда выдавая одинаковое значение для координат, у которых X равен Y.