Возможно ли увеличить количество чанков/чанков для коллизий?

[asyslinux]

Приветсвую, я сейчас меняю бекенд для поиска в своем проекте на Go.

Ключей у меня может быть до 100 000 000, они маленькие, база примерно до 100GB.

Возможно ли увеличить количество чанков/чанков для коллизий в таком случае? Или будут сплошные колиззии при таком количестве ключей. Или может быть мне модифицировать Вашу базу и изменить хеш на менее подверженный колиззиям типа crc64?

Спасибо.

[asyslinux]

Впринципе я сделал все уже у себя, в том числе заменил хеш murmur3 на highway hash (uint64), у меня дико много ключей , https://github.com/minio/highwayhash , https://godoc.org/github.com/minio/highwayhash + сделал функцию Walk по базе, завтра сделаю параллельный Walk. Walk я сделал через callback функцию, так чтобы в приложение сдавались ключи-значения налету(чтобы не генерить здоровенный мап с большим расходом памяти) при проходе всей базы. Например в моем случае я из базы снайпера загружаю всё полностью при старте своего софта, и сразу же строю radix дерево. Производтельность замечательная, быстрее не придумаешь. Спасибо за удачную разработку Вам, я в скором времени пришлю Вам пулреквесты с улучшениями, если Вы не против. Что касается хеш функции, ну она конечно ломает совместимость с вашим вариантом, потому что я тупо ее заменил, но остальные улучшения пришлю как протестирую, через недельку примерно, погоняю базу на 20-30 миллонах ключей значений.

[recoilme]

Привет.
По коллизиям:
Я смотрел 3-4 хешфункции - колво коллизий было сопоставимо и сильно зависело от данных. По моим расчетам 4 чанка под коллизии - хватит чтобы разрезолвить >1_000_000_000 шестибуквенных ключей. В тестах кажется лежит считалка коллизий, попробуйте для своего случая посчитать.

По хеш функциям:
Они все плюс-минус хорошие по скорости и дистрибьюции. Мурмур3 взял за минимум аллокаций. 8 байтный на 100 млн - памяти съест побольше

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

[asyslinux]

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

А с самим pudge я делаю сложную штуку, скорее всего я в него внедрю внешний проброшенный кеш типа ristretto из приложения, дело в том что у меня http серверы, и порядка 15 000 000 баз, именно мелких баз в каждой папке и подпапке в варианте базы pudge будет, счас это все на boltdb сделано и работает плохо. Там дело в том что объединить storeMode 0 и 2 недостаточно, чтобы и на диск писалось и в памяти временно жило, горутины не могут сами шарить в global открытую бд(объект), по крайней мере я не нашел способа как это сделать на Go. А так как баз 15+ млн, то и открываются они по требованию, а не заранее, но дело в том что к серверу в одну базу может прийти 20 запросов одновременно и каждая горутина будет делать Open + newDB, и все это дело подвиснет. MMap boltdb тоже не справляется в таких случаях. Поэтому я работаю над тем чтобы кешировать в общий кеш только fk индексы, то есть я туда добавлю что-то вроде OpenIndex() функции когда надо получить только список ключей например, размер, дату и прочее, а значения вообще не трогать, только в случае Delete использовать Open буду, с функций конечно уберу у себя все lazy Open, . А в значениях будут сами файлы хранится :) ну у меня уже за 350 млн файлов, поэтому я их пакую, только не в архивы, а в кучу boltdb и вот заменю скоро на pudge, а поиск на sniper + hashicorp iradix.

Да я как обещал пришлю для снайпера пулреквест с итератором только конечно, с тестами написанными, хеш функция это не принципиально для публичного проекта, murmur3 решит 99% задач у всех, но не у меня,мне колиззий чем меньше тем лучше :).

Что касается radix дерева, я вообще думал сначала взять разработку https://github.com/hashicorp/go-immutable-radix и допилить туда запись на диск и чтение - по сути полную базу сделать. Но вот незадача, radix дерево отлично подходит для его генерации из key-value полной базы данных(тех же путей на файловой системе как у меня, которых очень много) для максимально быстрого поиска, но вот что касается его персистентности - его или дампить и потом восстанавливать или делать из него key value на диске свое. В общем проще пока оказалось sniper+iradix отдельно сделать, не страшно что там больше памяти потребляться будет пока sniper открыт, для больших кластеров память уже не большая проблема обычно. То есть с радиксом не очень получается его персистентно сделать, чтобы строить радикс дерево при запуске программы нужно иметь полные ключи.

К pudge еще Shrink приделаю нормальный, тоже пришлю пулл-реквест.

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

Сейчас я иду по пути наименьших проблем, но пусть памяти побольше будет тратиться, потом можно подумать как прикрутить iradix в sniper или sniper в iradix, чтобы не иметь 2 открытых базы поиска по сути, а иметь одну :)

[recoilme]

У меня кажется похожие задачи. Памятью на таких объемах кмк пренебрегать не стоит

• в пудже есть проблема с хранением больших данных, я бы его вообще не брал для 100 млн. Там сортировки и на больших массивах он будет тупить- плюс он память не экономит. Второе - пудж не удаляет удаленное. Обе проблемы решены в снайпере, но он не умеет многое из того что сделано в пудже. Лично мне кажется что проще сбоку к снайперу дерево пристроить чем пудж починить.
• ристрето -мне не понравился. Ну типа если пишешь строку берет от нее хеш, если вставляешь инт - пишет как есть - все в кучу. Резолвинга коллизий, кажется нет вовсе!! - тупо вернет не то. Ристрето вернула мусор на конкаренси тестах. Может я конечно олень, но полез открывать ишью - а там уже были подобные ишью - закрытые дграфом. Мне больше нравится fastcache и freecache.
• Радиксные деревья - когда выбирал остановился на этом https://github.com/plar/go-adaptive-radix-tree - кажется там лучшее потребление памяти/скорость, но я не помню смотрел ли я выбранные вами. В моем форке есть иттератор по убыванию.
• Персистить деревья - задача сложная, так как они ребалансятся

[asyslinux]

Немного точнее опишу как это у меня все тут так получается:

Имеем 15 000 000 каталогов и подкаталогов и 350 000 000 файлов.

Базы пудж хранят сами файлы уже внутри и номеруются:

/var/storage/1/3/8/8_0000001.db
/var/storage/1/3/8/8_0000002.db
/var/storage/1/3/8/8_0000003.db

/var/storage/1/3/15/15_0000001.db
/var/storage/1/3/15/15_0000002.db

Radix:

_
 |
 var _
        |
        storage 1 
                     2
                     3 _8 = 3 (значит тут в этой директории есть 3 пудж базы)
                        _15 = 2 (значит тут в этой директории есть 2 пудж базы)

То есть само дерево минималистичное по потребляемой памяти.

В снайпере это все хранится полноценными ключами конечно, только в ключах хеши, а в значениях полные пути(так как они могут быть длинными очень и будут потреблять память). Сами значения из всех ключей при запуске сервера уже подгружаются в Radix с нуля итератором по снайперу, который я сделал. Понятно что снайпер наполняется через walk по файловой системе первично.

type Xdr struct {
	d string
	c uint32
}

Ключ: crc64(/var/storage/1/3/8) + crc64(random) значение: d = /var/storage/1/3/8 ; c = 3 (xdr2 сериализация)
Ключ: crc64(/var/storage/1/3/15) + crc64(random) значение d = /var/storage/1/3/15 ; c = 2 (xdr2 сериализация)

Со снайпером конечно потребление памяти будет больше, 16 байт ключи + 8 байт в моем случае ключ внутри снайпера.
Я могу попробовать взять из снайпера и сделать уже для себя механизм коллизий, но не сейчас.

В теории реально использовать 2 раза механизм разрешения колизии и если в обоих случаях использовать 4 байтные ключи, то суммарно получится в моих данных 4 байтовый ключ(crc32/murmur3) и внутри снайпера 4 байтовый ключ(murmur3).

В идеале будет 8 байт вместе crc32/murmur3+murmur3, 16 байт crc64/highway+highway, в не идеальном варианте как сейчас 24 байта.

При старте сервера радикс строится из снайпера. Снайпер тоже остается открытым так как надо изменения в дереве писать на диск тоже.

А вот все остальное уже (атрибуты файлов, права и прочее будет в ключах пуджа, я дополню его формат у себя), в значениях сами файлы.

Да на счет ristretto я погорячился, там колизии я уже почитал, посмотрю fastcache или аналоги.
Вот собственно кеш я проброшу внутрь пуджа из приложения, и добавлю в пудж методы загрузки индексов в кеш, а так же методы чтения из кеша по требованию, запросился 1 файл из архива, подгрузился весь индекс.

• кешей будет тоже штук 8 и соответственно параллельный поиск по ним. 1 пудж индекс грузится из каталога в 1 какой-то кеш.
• горутины будут параллельно подгружать данные из пуджей о файлах в кеш, если там несколько пудж баз в каталоге.

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

Шринк к пуджу я приделаю, конечно он будет пересоздавать файл базы, но это будет делаться не при каждом delete/update, это будет происходить только через шедулер, который может считать сколько там изменений накопилось, а может просто по времени через неделю запускать шринк конкретного пудж файлика, при условии что там было хоть одно изменение.

У меня не так много перезаписей или удалений. Так что пойдет механизм шринка через бекап, просто с заменой файла.

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

[recoilme]

А что за проект такой массивный не секрет?

[asyslinux]

https://github.com/eltaline/wzd/blob/master/README-RUS.md - тут общая информация, в текущем виде реализован на boltdb + nutsdb.

[asyslinux]

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

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

[recoilme]

Привет, я посмотрел только глазами, все красиво

Единственное, над чем хотелось бы подумать:

• мне показалось оверкилом импортировать целый пакет для лимита на горутины, я бы сделал на штатном пакете, вот так: https://gist.github.com/montanaflynn/56c2d0de37b7e078ab5c12bd27b4115c#file-concurrency-go
• обычно иттератором называют walk и немного другой интерфейс "привычен"- https://github.com/syndtr/goleveldb https://pkg.go.dev/mod/github.com/dgraph-io/badger#iterating-over-keys
• кмк было бы удобней сделать одну функцию итерэйт и для нее возможность указать параметры (причем с фолбеком в дефолтный без горутин) - в которых уже указать треды и тп, как здесь https://github.com/recoilme/sniper/blob/master/sniper.go#L186 а сама идея сперта отсюда https://gist.github.com/travisjeffery/8265ca411735f638db80e2e34bdbd3ae#gistcomment-3171484

[recoilme]

@asyslinux это так, навскидку.. Но спасибо за ПР, просто хочется найти время и сесть и как следует подумать как лучше сделать, я сам пока до конца не понимаю..

[asyslinux]

Рад слышать.

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

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

• одну функцию это можно сделать вместо двух, threads 0 по умолчанию будет без горутин, попозже сделаю.

[recoilme]

fixed at v0.2.0

sniper.Open(sniper.Dir("1"), sniper.SyncInterval(1*time.Second),sniper.SetChunkColCnt(6))