Хэш фиксированной длины
Oct. 28th, 2011 06:01 am![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
ermouthНесколько соображений, почему я использую концепцию key-value БД и хэши фиксированной длины как главные ключи.
Чисто архитектурно-программистское, кто не в теме, забейте.
Ну, для начала. Хэш фиксированной длины как сквозной уникальный идентификатор в базе гораздо удобнее, чем автоинкрементный ид. Выборка идёт с такой-же скоростью по хэшам, как по числовым идентификаторам – при этом “хороший” (типа md5) хэш обладает кучей всяких волшебных свойств…
Во-первых, хэши короткие. Если их передавать как параметр в урле, получается избежать чудовищных нагромождений в урлах. Собсно, сокращатели ссылок как раз считают хэши.
Во-вторых, по списку “хороших” хэшей никак не определить порядок, в котором они были созданы и не предсказать, какой хэш будет следующим. Скажем, по алгоритму bizwood.ru числа 1, 2 и 3 превратятся yxyhoe6a, zcpyd069 и xx9btfpz. А текст “Мама мыла раму” – в ktu4jmwf. Такой подход к идентификаторам упрощает некоторые аспекты обеспечения безопасности хранения и доступа.
Ещё полезняшка. Например, если вы храните древовидную структуру, и её надо время от времени обновлять или синхронизировать, нужно быстро определять, какие ветки изменились, а какие – нет. Для этого прекрасно подходят деревья Меркле – то-есть мы для всех используемых для сравнения веток считаем хэши и сравниваем их, а не ветки по значениям. Это в некоторых случаях (если листья длинные или деревья ветвистые) даёт огромный (порядки) выигрыш в производительности.
Деревья Меркле определённой разновидности позволяют организовывать очень быструю проверку прав доступа, шустрые лайки и счётчики доступа, быстрые бан-листы итп. Простейший вариант – таблица, клавный ключ которой – тупо конкат хэшей объекта и субъекта, а значение – права доступа. Или там лайк. Или счётчик.
Ещё прекрасное.
Хэши в силу того, что похожи на слова, прекрасно индексируются даже встроенными средствами полнотекстового индекса баз данных. Это вот что даёт.
Скажем, нам надо сделать сложную выборку записей определённого типа с определёнными тегами. Ещё записи должны быть созданы определённым пользователем или принадлежать определённой компании, к примеру.
Классический подход предполагает или тщательное проектирование БД с заточкой под такие запросы (для этого их с самого начала надо продумать все возможные), либо страшные джоины и низкую производительность. Ну и хреновую доступность из-за множества блокировок при записи в разные вспомогательные таблицы.
С хэшами можно иначе. Если у нас есть таблица, поддерживающая полнотекстовый поиск и содержащая в строках список всех хэшей, имеющих отношение к записи, перечисленных через пробел, задача становится тривиальной почти при любых мыслимых комбинаций отбора. Например, при использовании MyISAM-таблицы в MySQL-базе всё решается за 1 (один) SQL-запрос, содержащий MATCH AGAINST. И этот запрос – очень, очень быстрый.
Ну то-есть, когда мы пишем в базу обновление строчки, мы ещё пишем куда-то в соседнюю табличку перечисленные через пробел хэш типа, хэш создателя, хэши тегов записи и тд, всё что может пригодится. Например, на myhome29.ru пишется ещё хэш управляющей компании – если он есть, конечно. И хэш улицы. И города. А если надо будет, то и район будет писаться. И категория – типа деревянный, панельный или ещё какой – тоже хэшем соответствующего типа.
Таким манером, если в будущем возникнет какая-нибудь экзотика типа “найти все деревяшки какой-то УК по улице Пупкина” – это всё решится одним запросом, вполне стандартным.
Синонимические поисковые запросы тоже прекрасно решаются с помощью такого трюка. То-есть, мы пишем ещё и хэши всех синонимичных поисковых запросов в список. Или один хэш корневого запроса – тогда поиск удлиняется на целое обращение к базе по главному ключу.
Жаль, я поздно такой подход стал использовать. В бизвуде – половинчато. В myhome29 – уже в полный рост.
Какие-то идеи мне ещё наверное Redis даст, как это можно юзать.
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
no subject
Date: 2011-10-28 02:20 am (UTC)Для небольших объёмов (не паримся по поводу коллизий), целиком влезающих в память (не паримся по поводу последовательного чтения с дисковых носителей) и нефинансовых приложениях (не паримся о транзакциях), описанный тобой вариант - отличный солюшн прямо таки для всего. Он достаточно хорош для скорости, и просто прекрасен для простоты имплементации.
Для больших объёмов density идентификаторов начинает играть весомую роль.
Коллизии тоже неприятная штука.
no subject
Date: 2011-10-28 02:33 am (UTC)вероятность коллизии уже при 10 знаках base32 10e-15. это хорошая цифра уже и для больших объемов.
не очень понял твое замечание про "целиком влезающих в память".
вообще, такое ощущение, что все простые цмс пишутся как финансовые приложения. я просто ну вообще ничего не нашел из массового, организванного по такому принципу.
no subject
Date: 2011-10-28 02:37 am (UTC)no subject
Date: 2011-10-28 02:40 am (UTC)no subject
Date: 2011-10-28 02:55 am (UTC)Но тогда идентификаторы подлинней.
Я знаю одно коммерческое приложение, где 256-битный хэш используется таким образом, что коллизия приведёт к потере данных. Это backup Windows Home Server'а (по крайней мере, если они ничего не поменяли недавно). Там для блоков определённого размера на диске вычисляется хэш и по хэшу сервер принимает решение, надо ли копировать этот кусок в новый бэкап.
no subject
Date: 2011-10-28 03:10 am (UTC)no subject
Date: 2011-10-28 03:00 am (UTC)Оно тебе надо???
no subject
Date: 2011-10-28 03:01 am (UTC)no subject
Date: 2011-10-28 03:12 am (UTC)no subject
Date: 2011-10-28 06:33 am (UTC)Дима, я не очень понимаю, зачем тебе вообще считать хэш в случае случайной соли, чем тебя не устраивает просто случайная соль? :) И вообще, зачем говорить о хэше в этом случае? Не лучше ли (для меньшей путаницы в терминологии) говорить о случайных ключах?
Хэш отличается от случайного ключа тем, что имея значение, от которого ты взял хэш, ты можешь взять его ещё раз в любой момент. Если значение доступно на клиенте, то вычисление хэша можно сделать на клиенте и сэкономить на серверном запросе.
Если же твой use-case использует именно хэш и это его свойство, то твой "трюк" для уменьшения вероятности коллизий, конечно, хорош, но несколько громоздкий в имплементации: тебе придётся везде в коде писать что-нибудь вроде "если не получилось, попробовать второй префикс". Ну, понятно, можно это инкапсулировать в класс, библиотеку и т.п. Ты это всё делаешь, я правильно понимаю?
no subject
Date: 2011-10-28 10:45 am (UTC)насчёт двух префиксов -- это тема для отдельного поста, который, вероятно будет. насчёт "очевидно" я, конечно, погорячился ) я это месяц обдумывал)
no subject
Date: 2011-10-28 10:49 am (UTC)no subject
Date: 2011-10-28 11:18 am (UTC)соль сохраняется для того, чтобы можно было вычислить хэш тех же данных повторно с той-же солью, чтобы определить, изменились данные относительно уже имеющихся или нет. если бы хэши были истинно случайные, эта их особенность потерялась бы.
no subject
Date: 2011-10-28 06:58 pm (UTC)no subject
Date: 2011-10-28 08:32 pm (UTC)-- при очередном полнотекстовом поисковом запросе мы его (текст запроса) хэшим с префиксом1
-- проверяем на наличие такого хэша
-- если он есть и данные по нему -- текст, значит мы это уже искали, дальше выбираем синонимы и тд
-- если хэш уже есть и данные по нему НЕ текст, мы запрос хэшим с префиксом 2, дальше очевидно
вероятность, что мы получим 2 столкновения подряд, просто ничтожна.
есть ещё вариант, который я изначально планировал, но от него отказался -- не смог кстати сейчас вспомнить, почему. возможно, хотелось унификации.
теперь кажется, что зря отказался.
хэши плоских строк генерятся чуть иным алгоритмом: скажем, первый символ всегда из тех, что в других хэшах гарантированно не встречаются. у меня base32, а не base 36, так что 4 символа у меня есть для этого.
no subject
Date: 2011-10-28 09:24 pm (UTC)Хотелось бы видеть конкретные и более сложные end-to-end cases, в которых хэши реально дают benefit.
no subject
Date: 2011-10-28 09:31 pm (UTC)у меня ну никак не выходила простая схема без хэшей.
no subject
Date: 2011-10-28 10:50 pm (UTC)У тебя весь data set (как исходные данные, в которых ты ищешь, так и списки синонимов) на клиенте или на сервере?
Если всё на клиенте, то синонимы - это набор слов (terms), для каждого слова список слов-синонимов. Слова - это короткие вещи, не вижу смысла в создании дополнительного хэша. Пользователь вводит query string из трёх слов, для каждого из них у тебя 5 вариаций, для всех 5*5*5=125 комбинаций составляешь новый query string из трёх слов, смотришь в кэше по query string, нет ли уже посчитанных результатов, если нет - считаешь.
Если считать должен сервер, то сервер может и генерировать синонимы. На сервер надо передать только query string.
Я тут упускаю что-то очевидное?
no subject
Date: 2011-10-28 11:23 pm (UTC)смотри.
скажем, пользователь делает запрос "двухэтажный деревянный дом". я строю полный хэш и последовательно-попарный и одинарный hash-tree:
kayu5xde -- двухэтажный деревянный дом
x16yz8r2 -- двухэтажный деревянный
ps0jezua -- деревянный дом
3au2jy2t, ph6ta6gr, 74trwhdx -- двухэтажный, деревянный, дом
делаю выборку по всем этим хэшам из бд и получаю, что по хэшам "двухэтажный" и "деревянный дом" у меня определены корневые синонимы -- "2 этажа" с хэшем 9fxmbece и "сруб" c хэшем указателя сразу на целый тип записей (типы тоже определены хэшами).
вот именно их я и вставляю в запрос на первые месте с префиксом +>.
дальше определяем, какие ещё хэши из первоначального списка ставить в запрос и с какими правилами -- et voila.
ещё момент. полнотекстовый индекс в MyISAM по умолчанию индексирует от 4 символов слова. это перенастраивается, конечно, но вообще это разумное ограничение. хэши важных лексем позволяют легко обойти его в важных случаях.
no subject
Date: 2011-10-29 12:24 am (UTC)Да, использовать хэши вместо фраз - отличная идея. Даёт тебе возможность использовать одно строковое поле и full text index для списков. В базах - чем меньше реляционных компонент, тем быстрей всё работает. В конкретно описанном приложении (suggestions по синонимам) на коллизии должно быть совсем наплевать. В худшем случае ты удивишь пользователя неправильной подсказкой, причём он, скорее всего, найдёт способ как решить свой вопрос по-другому. И вероятность этого случая, скорее всего, будет ниже, чем вероятность того, что site is down, или того, что пользователь сам ошибётся и что-то введёт не так, из-за чего у него будет плохой experience.
no subject
Date: 2011-10-29 12:31 am (UTC)я сейчас как раз прикидываю полную реализацию такого подхода к синонимии для следующего предполагаемого очень серьёзного публичного проекта.
no subject
Date: 2011-10-28 11:30 pm (UTC)с помощью весов на дереве меркле по текстовому описанию формирующий байесову сеть, позволяющую оценить пригодность вариантов, найти значащие факторы и по ним уже найти "синонимы" в той или иной степени.
no subject
Date: 2011-10-29 12:30 am (UTC)Мой алгоритм подбора шмоток и ботинок основан на цвете. Если все шмотки чёрные, а ботинки светлые - непорядок. Во всех остальных случаях всё OK :) Верх (рубашки) подбирается к низу (штаны) по принципу длины: внизу должно быть не короче, чем наверху. Скажем, к шортам не очень идёт рубашка с длинными рукавами. Вопрос с эстетичностью цветовой гаммы решается очень просто: лучше пусть всё будет чёрное, и не морочить себе голову :)
Более интересен был бы магазин, который будет подбирать мне план шоппинга. Скажем, он спросит у меня, что я покупаю и где, после этого подскажет, что лишнее, что можно добавить в набор, и как оптимизировать логистику, чтобы реже делать покупки (количество покупок и количество разных магазинов), но при этом не сильно захламлять storage (шкаф).
no subject
Date: 2011-10-29 12:40 am (UTC)и я так полагаю, что вариант "рубашка с длинным рукавом - шорты" не будет появляться в выдаче довольно быстро если её никто не выбирает (или быстро пролистывает, или ставит -1).
я кста достаточно чётко вижу, как это сделать о_О даже примерно социальный механизм накопления и уточнения синонимов примерно представляю.
no subject
Date: 2011-10-29 01:17 am (UTC)no subject
Date: 2011-10-28 08:41 pm (UTC)no subject
Date: 2011-10-28 06:37 am (UTC)no subject
Date: 2011-10-28 08:33 pm (UTC)no subject
Date: 2011-10-28 02:47 am (UTC)Понятно, что последствия иногда вообще не страшны. Например, хэшируешь user id, если новый пользователь попал на хэш старого, просто говоришь, что такой юзер уже есть, придумайте что-нибудь другое.
По поводу целиком влезающих в память: случайный доступ.
Как только у тебя появляется диск или несколько хостов, обменивающихся по сети, у тебя начинают возникать ситуации, когда разница по скорости между случайным доступом (вытащить N элементов из случайного места по ключу) и последовательным (обработать N элементов от i-го до j-го) начинает составлять несколько порядков.
Кроме того, когда у тебя большие объёмы, то возникают ситуации, когда отсортированные плотненькие списочки занимают очень мало места, а случайные занимают много, и тебе это важно (см. что ты написал по поводу списка хешей related объектов). Чтобы проиллюстрировать идею, последовательность 1, 2, 3, 4, 5, 7, 10, 11, 12, 13, 14, 16 можно записать как 1+4-2-3+4-2, где самая первая 1 - это нормер начального, +N означает следующие N чисел идут подряд, -N означает следующее одно число идёт через N от последнего. Ну и можно записать эффективным битовым кодом (см. коды Хаффмана), получится каких-нибудь 30-50 бит на всю последовательность. 12 значений, каждое 10 знаков в base32 - это 12*10*32 = 3840 бит, не считая ещё нескольких бит, чтобы сохранить само число 12 (количество значений). Понимаешь, о чём я? (Насчёт "плотных" (dense) идентификаторов).
* * *
Мне кажется, все простые цмс пишутся определёнными людьми и для определённых людей. Там должен быть довольно большой bias в сторону студенческого синдрома (я только что освоил реляционные базы данных! о! надо имплементнуть!) и в сторону перфекционизма (всё супер идеально теоретически верно, транзакционно, сплошная consistence/integrity, расширяемо, совместимо с ANSI стандартами и т.п.)
no subject
Date: 2011-10-28 02:57 am (UTC)и только в самых редких случаях -- обычно когда подлежащие данные просто плоская строка, хэш делается без соли.
очевидно, что при подходе с солью достаточно при генерации идентификатора-хэша просто проверять, нет ли уже такого, и если есть, то генерить хэш снова.
мы, конечно, можем столкнуться, что при генерации хэша без соли он уже будет занят -- но и для этого есть простой трюк. мы генерим такие хэши в двух вариантах с двумя скажем разными заранее известными префиками, дальше очевидно.
про случайный доступ. базы, у которых главный ключ так устроен, насколько я понимаю прекрасно шардятся. думаю, это отличная стратегия ускорения случайного доступа.
про плотность -- согласен.
no subject
Date: 2011-10-28 03:07 am (UTC)no subject
Date: 2011-10-28 10:39 am (UTC)no subject
Date: 2011-10-28 02:52 am (UTC)no subject
Date: 2011-10-28 02:34 am (UTC)Насколько я понимаю, если очень надо, ты можешь купить себе двухсокетный комп с 96ГБ памяти за ~4К и еще за столько же ты напихаешь в него пару терабайт SSD сториджа на Fusion I/O. Коллизиями в SHA1 пренебрежем.
С транзакциями да, засада. Но это действительно нефинансовые дела.
no subject
Date: 2011-10-28 02:48 am (UTC)no subject
Date: 2011-10-28 03:01 am (UTC)no subject
Date: 2011-10-28 03:02 am (UTC)no subject
Date: 2011-10-28 03:05 am (UTC)no subject
Date: 2011-10-28 06:53 am (UTC)Хэш фиксированной длины как сквозной уникальный идентификатор в базе гораздо удобнее, чем автоинкрементный ид
:)
no subject
Date: 2011-10-28 07:14 am (UTC)Человек не из целевой вообще должен был забить, прочтя второе предложение. Так что если дочитали до конца - сами виноваты, вам следует понимать процитированный текст :)
no subject
Date: 2011-10-28 07:16 am (UTC)no subject
Date: 2011-10-28 11:20 am (UTC)no subject
Date: 2011-10-28 05:19 pm (UTC)no subject
Date: 2011-10-28 07:51 am (UTC)no subject
Date: 2011-10-28 11:32 am (UTC)Мне это напомнило лекции по лингвистике:
Естественная соотнесенность ремы с неактивированным, а темы – с активированным или известным часто приводит в работах по теории актуального членения и коммуникативной структуры к подмене иллокутивного значения, выражаемого ремой (сообщение), его информационными коррелятами: неактивированным и неизвестным. Между тем рема не равна неактивированному, а тема – активированному, хотя часто они соответствуют одним и тем же фрагментам предложения. Рема – это носитель иллокутивного значения, а категория неактивированного описывает состояние сознания слушающего в определенной точке дискурса.
no subject
Date: 2011-10-28 11:38 am (UTC)