Summary

Добавить новый метод Object.longHashCode для генерации 64-битных хэш-кодов. Предоставить набор функций JVM, которые оптимизируют генерацию хэш-кодов для широкого круга типов с помощью инструкций современных процессоров. Обеспечить необходимое прямое и обратное взаимодействие с существующим API Object.hashCode.

Goals

• Общность: новая хэш-функция, как и существующие стандартные хэш-функции, будет работать (по крайней мере потенциально) со всеми типами полей и элементов массивов.

• Размер: новая хэш-функция будет выдавать полные 64 бита перемешанного результата, что позволит ей масштабироваться до приложений облачного масштаба.

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

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

• Поддержка «соли»: хэш-функцию можно будет создавать в нескольких вариантах с помощью необязательного статического параметра «соли» (salt). Так экземпляры VM и отдельные структуры данных смогут в некоторой степени защититься от атак, основанных на коллизиях хэшей.

• Совместимость: существующее специфицированное поведение Object.hashCode не изменится. Существующие классы будут использовать новый алгоритм только по явному выбору (opt-in). Будут пути перехода, не требующие замены существующих иерархий классов или интерфейсов.

Non-goals

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

• Невоспроизводимость: результат хэш-функции не будет специфицирован так, чтобы независимые соответствующие спецификации реализации библиотек Java или VM обязательно выдавали одинаковые хэши для одинаковых входных данных. В этом отношении хэш-функция сможет выдавать произвольные результаты, назначаемые VM, во многом как сегодняшний System::identityHashCode. (С точки зрения хорошей инженерной практики случайно невоспроизводимых результатов следует избегать.)

Success Metrics

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

• Хэш-код пригоден для использования в качестве хэш-кода подстановочности (substitutability) для value types.

• Некоторые алгоритмы пакетной обработки работают значительно быстрее.

Motivation

У существующих стандартных реализаций API Object.hashCode есть хорошо известные недостатки, которые приводят к избыточным коллизиям хэшей, неэффективному использованию процессорного времени и избыточному потреблению памяти в хэшированных структурах.

Во многих случаях каждый бит входных данных влияет не более чем на один бит результата (Integer.hashCode) и/или может быть тривиально погашен другим битом (Long.hashCode). Даже для типов переменного размера, таких как строки и списки, это наблюдение часто справедливо для последних элементов.

Даже если входные биты немного перемешиваются, в большинстве случаев они перемешиваются нетщательно, поскольку обычной функцией перемешивания служит исключающее ИЛИ между параллельными входными значениями или простое рекуррентное соотношение h=h*31+x для последовательностей входных значений. В этих функциях много воронок между входными данными и мёртвых битов в результате.

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

При этом у JVM здесь особая роль. Для любой заданной раскладки объекта (или раскладки value type) она знает, как загрузить хэшируемые входные данные за минимальное число обращений к памяти, и знает, доступны ли специализированные инструкции (например, шаги AES), чтобы ускорить алгоритм хэширования с сохранением хороших свойств перемешивания. JVM может даже определить, когда может подойти векторизованный алгоритм хэширования. Все эти соображения несовместимы с алгоритмом хэширования, заданным извне, таким как XOR или h*31+x, и все они важны для достижения наилучшего возможного компромисса между скоростью и качеством хэширования. Из этого следует, что нам нужна не просто ещё одна библиотечная функция для нескольких сценариев, а глубоко встроенный механизм, который JVM может оптимизировать для (потенциально) любого объекта, значения или массива Java.

Description

Низкоуровневая точка API System.primitiveHashCode будет определена рядом с точкой API System.identityHashCode как способ получить быстрый и качественный хэш-код для публично читаемого содержимого объекта, значения или массива. Вариант точки входа (см. ниже) будет по явному выбору (opt-in) направлять JVM к приватно читаемому содержимому.

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

Любые непубличные поля, а также любые поля или элементы ссылочного типа в объекте, значении или массиве будут игнорироваться primitiveHashCode. Это может показаться серьёзной проблемой удобства использования, но на самом деле позволяет использовать primitiveHashCode как строительный блок для целого ряда полезных вариантов поведения хэш-кода, включая те, которые рассматривают ссылки как идентичности объектов, или как указатели на содержимое, пригодное для хэширования, или как сочетание того и другого.

Точка API System.primitiveHashCode(Object,Lookup) будет предоставлять вариант алгоритма хэширования, который просматривает все поля заданного объекта, при условии что аргумент Lookup подтверждает доступ к этим полям. Эта точка API предназначена для использования в качестве строительного блока для классов, внутренняя структура которых содержит примитивы.

Любые поля value type, объявленные в классе объекта или value-классе, рекурсивно просматриваются в поисках нессылочных входных данных для алгоритма хэш-кода. Аналогично рекурсивно просматриваются массивы value types. Массивы Object или интерфейсных типов просматриваться не будут, даже если некоторые элементы могут ссылаться на value types.

Класс операнда, переданного в System.primitiveHashCode, влияет на хэш-код. То есть два объекта с эквивалентными полями, но разных классов, дадут независимые хэш-коды. Два массива одинаковой длины и с одинаковым числовым содержимым, но разных типов (short и long) дадут независимые хэш-коды. Аналогично на хэш-код влияет длина массива, а также все его нессылочные (примитивные или value) элементы.

В качестве особого случая ссылочные массивы могли бы распространять алгоритм хэширования на каждый из своих ссылочных элементов, а не игнорировать их. Но этот особый случай, по-видимому, лучше реализовать как отдельный метод; см. ниже. Для единообразия передача ссылочного массива в System.primitiveHashCode будет просто хэшировать класс и длину массива.

Поскольку публичные поля в стандартных API Java встречаются сравнительно редко, есть также API для адаптации primitiveHashCode к значениям или объектам с приватными полями. Этот API включает проверку прав на основе второго аргумента — Lookup, который должен точно совпадать с классом операнда. Он System.primitiveHashCode(Object,Lookup). Он не зависит от вызывающего кода (не caller sensitive).

Внутри JVM для реализации System.primitiveHashCode сделает два ключевых выбора. Во-первых, она статически определит все параметры конфигурации, которые добавляют «соль» в алгоритм хэширования для данного экземпляра JVM. Во-вторых, для каждого операнда она определит класс и направит вызов (при необходимости для эффективности) к соответствующей специализированной реализации хэш-функции. Этот второй шаг часто будет опускаться, если доступна информация о типах во время JIT-компиляции.

Если параметр lookup присутствует, требуется третий шаг: сравнение класса lookup с классом объекта и проверка того, что у lookup установлен необходимый бит «private», дающий полный доступ.

Точка API MethodHandles.primitiveHashCode(String) будет предоставлять экземпляр алгоритма длинного хэш-кода, использующий заданную строку в качестве «соли». Если строка пуста, алгоритм будет вести себя так же, как System.primitiveHashCode.

Также может быть предоставлена комбинированная точка API, принимающая и строку, и объект Lookup, а также (возможно) точки API, позволяющие выбрать набор значимых полей и других входных данных хэш-функции, например хэшей, рекурсивно полученных из ссылочных полей.

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

Для классов объектов и value-классов набор публичных нессылочных полей или набор всех полей часто является лишь первым приближением к набору входных данных, необходимых для корректной хэш-функции. В таких случаях пользовательский код (или method handle, сгенерированный bootstrap-методом) может с помощью primitiveHashCode извлечь все примитивные поля сразу, а затем перемешать их с хэшами, полученными из других источников, например из связанных объектов или массивов. Это перемешивание можно выполнить над промежуточным массивом типа long[].

Поверх этого при необходимости можно построить дополнительные точки API:

• Object.longHashCode — новая переопределяемая точка API в Object, имеющая такое же гарантированное соответствие Object.equals, как и Object.hashCode. Для совместимости её реализация по умолчанию должна строиться на вызове Object.hashCode с дополнительным перемешиванием через primitiveHashCode. Классы могут легко перейти на неё со временем.

• Collection.longHashCode — новая переопределяемая точка API с подходящими реализациями по умолчанию на основе длинных хэшей элементов. К существующим методам абстрактных суперклассов для hashCode добавятся методы для longHashCode. Для списков определение таково: вызвать longHashCode для каждого элемента, а затем вызвать его ещё раз для полученной последовательности 64-битных хэш-кодов, как если бы они находились во временном массиве long[].

• Objects.longHash(Object...) вызовет longHashCode для каждого отдельного аргумента, а затем объединит все полученные 64-битные хэш-значения в одно хэш-значение, как если бы через временный массив значений long той же длины, что и исходный массив, к которому применяется финальный вызов primitiveHashCode (или mixHashCodes, см. ниже).

• Arrays.longHashCode(T[]) выдаст тот же результат, что и System.primitiveHashCode, если тип компонента примитивный или value, иначе тип компонента ссылочный, и результат будет таким же, как у Objects.longHash.

• Arrays.deepLongHashCode(T[]) выдаст тот же результат, что и System.primitiveHashCode, если тип компонента примитивный или value, иначе тип компонента ссылочный, и результат будет таким же, как при вызове deepLongHashCode для каждого элемента ссылочного массива, то есть с обходом динамической вложенной структуры. Для некоторых входных данных возможно переполнение стека.

• Collectors.longHash(), если используется как терминальная операция потока, выдаст тот же результат, что и Collectors.toList() с последующим longHashCode (или mixHashCodes, см. ниже) для полученного списка.

• HashMap(int,float,boolean) позволит отдельным хэш-таблицам использовать longHashCode вместо hashCode, если новый логический параметр равен true. (Как вариант, можно создать отдельный класс LongHashMap, но это кажется излишним.)

• System.mixHashCodes(long...) позволит пользователям объединять хэш-коды, полученные из разных источников, в один хэш-код. Его можно реализовать как перенаправление на вызов primitiveHashCode для массива long[] или сделать что-то более эффективное, исходя из предположения, что входные данные уже хорошо обработаны.

• Дополнительные перегрузки mixHashCodes для значений long в количестве от одного до пяти будут эквивалентны вызову mixHashCodes для массива операндов, но помогут избежать накладных расходов на упаковку (boxing). В частном случае mixHashCodes для одного значения long — приемлемый способ улучшить перемешивание результата устаревшего Object.hashCode, хотя он и не может волшебным образом идеально перемешать устаревший результат.

Общедоступные алгоритмы хэширования блоков данных, такие как xxHash или алгоритмы из CityHash от Google, скорее всего, пригодятся для реализации описанной выше функциональности.

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

В качестве конкретного алгоритма для шагов хэширования отметим, что на многих значимых платформах, которые Java поддерживает сегодня, доступны инструкции пользовательского режима для одного шага 128-битного алгоритма шифрования AES, и они хорошо интегрированы с векторными блоками. (В некоторых случаях векторный блок может выполнять несколько шагов параллельно.) 128-битный шаг AES, вероятно, примерно так же дёшев, как многие традиционные шаги хэширования, например 64-битное умножение с последующей перестановкой битов. Шаг AES обрабатывает сразу 128 бит, что даёт ему преимущество на некоторых платформах. Первые эксперименты с SMHasher показывают, что двух шагов AES (но не одного) обычно достаточно для надёжного перемешивания битов.

Таким образом, для описанных выше API, по-видимому, хорошо подошёл бы алгоритм на основе AES примерно такого вида:

primitiveHashCode(x) {
  cls = x.getClass()
  mask1 = vectorMaskForInstance(cls)
  bits = unsafe_vector_load(x, mask1)
  bits = aes_step(bits, SALT1)
  if (cls.isArray()) {
    mask2 = vectorMaskForArrayBody(cls)
    for (off in vectorOffsetsFor(cls, x.length)) {
      bits2 = unsafe_vector_load(x + off, mask2)
      bits = aes_step(bits, bits2)
      bits2 = aes_step(bits2, SALT2)
      bits = aes_step(bits, bits2)
    }
  }
  bits = aes_step(bits, SALT3)
  return bits
}

Более того, в проекте CityHash, судя по всему, недолго экспериментировали с использованием AES в качестве шага перемешивания.

Значения SALT выше могут быть любыми псевдослучайными 128-битными значениями. Они определяют, какой экземпляр алгоритма хэширования используется. Их можно получать от генератора случайных чисел или хэшированием (криптографическим или иным) упомянутой ранее строки соли.

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

Экземпляр JVM, работающий на оборудовании без аппаратного ускорения AES, может переключиться на стандартный алгоритм хэширования, интенсивно использующий ALU, например MurmurHash или xxHash. Такая свобода отступления — неотъемлемое условие получения хэша наилучшего качества, доступного на конкретной платформе.

Стойкость к коллизиям можно повысить, добавив больше инструкций, в том числе шаги XOR, переносящие дубликаты значений предыдущих шагов (конструкция Davies-Mayer и похожие), и/или дополнительные инструкции раундов AES. Эта конструкция не предназначена для криптографически стойкого хэширования, и коллизии могут возникать. Использование случайно выбранных значений соли затруднит, хотя и не сделает невозможным, намеренное создание коллизий злоумышленниками.

Сейчас размер примитивов в Java ограничен 64 битами, но будущие value-типы легко превысят этот размер. Тогда набросанные выше API можно будет расширить, чтобы они выдавали «сверхдлинные» хэши произвольного размера, если это покажется желательным. Такие гигантские хэши сравнительно просто получить из описанных выше алгоритмов хэширования, используя отдельные значения соли для каждого канала гигантского хэша.

Alternatives

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

Различные предложенные выше точки API можно отложить, пока не будет доказана их полезность.

Мы могли бы и дальше мириться с коллизиями хэшей от h*31+x.

Авторы библиотек могли бы и дальше создавать собственные хэш-функции, которые не будут хорошо оптимизированы JVM и/или будут давать хэши худшего качества, чем могла бы обеспечить JVM.

Смешивать хэширование элементов массивов с хэшированием полей экземпляра, и всё в одном месте, — необычное решение для API. Возможно, эти задачи стоит разделить. Возможно, полиморфизм следует выражать статически, в виде фабрик дескрипторов методов (method handle), а не через динамические проверки типов в единственной волшебной точке входа. Заметим, что у волшебной точки входа есть прецеденты, например System.arraycopy и Class.newInstance. Общая идея, объединяющая то, что делает предлагаемый System.primitiveHashCode, в том, что только JVM может знать самый быстрый и лучший способ действий для каждой отдельной раскладки объекта, значения или массива (и для каждого выбора между открытыми полями и всеми полями).