Как следует организовать базу и поиск по 1 000 000 000 000 (триллиону) записей на 100ТБ?
Всем привет, делаю проект связанный с распознаванием образов, подошел к проблеме очень интересной, думаю не только мне - поиск по огромным данным
В базу идут хэши, пока не знаю точной длины, думаю 32-64 символа utf-8.
С одного изображение будет примерно 5000 хэшей. Поскольку изображений будет очень много (ну реально очень много, как по мне) 720 000 000 (720 миллионов), то придется осуществлять поиск по более чем 1 триллиону записей, которые в свою очередь будут занимать примерно 100ТБ.
Как можно спроектировать структуру, что бы она была расширяема и вообще работала в таких условиях?
По идее поиск по хэшам должен быть за O(1), потащит ли MySQL?
В какую сторону копать? Спасибо!
Сергей Протько: да это просто заказ на госзакупках - разработка системы автоматического распознавания по морде лица и не только) включая собак и кошек)
sim3x: интересно. Т.е просто создаются файлы с названием хэша и значениями внутри файла? Как лучше сделать, больше серверов с меньшими обьемами памяти или все на одном сервере?
файл с названием хеша какой-то области в себе содержит хеш-как-имя изображения
Как делать? Все зависит от финансов и нагрузок. Можно и на одной, если дисков хватит
Если делать шардирование, то нужно будет выделить пару машин под маршрутизаторы-баллансеры запросов
Порадовало описание с википедии: "Apache Cassandra — распределённая система управления базами данных, относящаяся к классу noSQL-систем и рассчитанная на создание высокомасштабируемых и надёжных хранилищ огромных массивов данных, представленных в виде хэша." Похоже, это то что нужно!
ruboss: elasticsearch очень-очень плохо масштабируется. Сам возился с кластером с 16ти машин, и как одна из нод падает каждую неделю по 2-3 раза. Лучше сразу брать Solr и реализовывать нужный функционал в рамках приложения.
Юрий Ярош: По каким причинам подают ноды? У меня было подобное вначале, все решилось пересмотром архитектуры кластера и его настройкой. Сейчас работает ~пол года без простоев. И масштабируется он хорошо.
Леша Киселев: ноды падали по разным причинам: начиная от утечек памяти, и заканчивая проблемами синхронизации - на одной ноде было по 64Гб оперативки и ~2Тб данных. Проблемы со старту решались экстенсивным путём под предлогом "железо дешевле", в итоге пришлось писать кастомные граф-ориентированные индексы и MVP-tree based индексы для PostgreSQL с довольно большой допилкой его полнотекстового движка, хотя под OpenSource'ом это так и не опубликовалось - контора развалилась :)
PC-1 for routing
возвращает адреса машин, на которых лежат хеши и картинки по,
например, первым 4 байтам хеша
PC-1 for hashes
|-/file_with_hash_of_region: content hash of image
|-....
PC-n for hashes
|-/file_with_hash_of_region: content hash of image
|-....
PC-1 for images
|-/image_file_with_hash_as_name
|-....
PC-n for images
|-/image_file_with_hash_as_name
|-....
xmoonlight: Мы использовали в real time bidding для хранения профилей пользователей сначала Cassandra, но у нас были очень жесткие требования к задержкам и Cassandra нас не устраивала, т.к. ее stop the world GC очень сильно влиял на это. В каждом из 3 DC у нас было по 8 машин со 196 GB оперативки и в итоге мы заменили эти машины на пару аэроспайков. На каждом сервере стоит несколько SSD, с которых аероспайк напрямую в параллельном режиме читает данные. Единственное требование - это чтобы индекс ключей умещался в памяти.
Dimchansky: т.е. он с SSD копирует индексы в память при поднятии базы и далее "налету" синхронизирует постоянно память и SSD при новых индексах, правильно я понял?
xmoonlight: ну эти индексы не индексы с данными, они представляют собой просто указатель откуда с SSD можно прочитать данные для конкретного хеша ключа.
UPD: я бы добавил, что для обучения и эталонирования образа (на основе множества подобных из БД), нужно удалять из дальнейшей выборки (однократным проходом по всей базе) промежуточные "близкие" "похожие" экземпляры, оставляя определённый процент допуска по параметрам. Таким образом, она не будет расти от "копий" подобных экземпляров.
xmoonlight: ну на такой задаче должен справиться, главное шардирование организовать. Но с тем же успехом можно просто в файловой системе хранить, толку будет явно больше (искать по хэшу пофигу чем).
xmoonlight: ну тут сложно, тут поиск по хэшам, так что... Хотя я на месте автора просто уменьшил бы картинки, это дает и аппроксимацию нормальную и вообще... хотя это надо вдаваться в детали задачи.
Сергей Протько: еще сильно зависит от кол-ва критериев (контуры, цвета, области и т.д.), можно хэши формировать просто на основе данных и тогда будет как раз то, что ты пишешь. А критерии - слоями можно добавить в конец.
xmoonlight: это если мы по контурам делаем, а автор выделяет хэши как часть алгоритма. Он указал ссылку на метод выделения фич из изображения в комментариях к вопросу.
xmoonlight: хэши контуров, ибо получить контур нормально задачка может быть довольно сложной и это нужно только когда мы классифицируем объекты на картинках, и да, для этого есть другие методы. Помниться хороший вариант был с обучением нейронной сети через bag of words
Сергей Протько: значит я правильно понял. ну да, контур с разной степенью детализации (размер матрицы от крупной к более детальной) внутри одного хеша и единым алгоритмом поворота/наложения (вектор вращения) - это хороший способ получить качественный результат даже с слегка отличающимися хешами. (нашли 0 -> ищем частично: отсекая часть правой части хеша)
xmoonlight: я просто хочу сказать что хэши контуров это удобно... ну например когда мы распознаем текст, с другой стороны фичи вроде SIFT как раз таки учитывают контуры, так что я не вижу смысла в придумывании каких-то стремных вещей.
Думаю все в тайне догадываются что решение автора по сравнению картинок через 5000 хэшей не оптимально, я даже не вникая в тему могу сходу придумать 2-3 менее затратных варианта....
ruboss: постройте матрицу по части картинки раз, сократите выборку через цвета два, поработайте с exif три, постройте геометрию соотношений до самых тёмных и светлых частей четыре
Дмитрий: какую матрицу? цвета вообще не важны в этой задаче. зачем так усложнять все? Есть дескрипторы инвариантные к изменению размеров, поворота и т.д. Все что Вы написали, относится скорей к глобальным признакам и поиск по ним будет не возможен при малейшем изменении изображения - т.е добавление текста, обрезка и т.д. Думаю, локальные признаки самое оно. Если решение не оптимально, то зачем тогда в Яндексе его используют?
Если нужно получать идентификаторы картинок, чьи хеши встречаются наиболее часто в запрошенной выборке, то тут нужно строить не просто key-value, а более оптимальные индексы...
ruboss: Да все просто: строится обратный индекс "хеш" -> "список изображений, его содержащий". Шардирование по изображениям (чтобы все хеши одной картинки попадали в один шард). Приходит пачка хешей искомого изображения - мы проходимся по этим линиям индекса. При предварительной сортировке линий (отлично работает вставкой при добавлении нового элемента) получение ТОПа выполняется в один проход по этим линиям.
У меня как раз есть похожая задача (не картинки, речь про индекс), но там только 300 миллионов объектов, и с каждого порядка 10 тысяч 32битных хешей. Работает хорошо.
Лично меня еще смутили такме моменты:
1) а что это за хэши такие странные - в символах UTF8? Вкурсе, что _1 символ_ в этой кодировке может занять от 1 до 6 байт, что на таком кол-ве записей ведет к огромному разбросу. Если у вас хэш из ASCII, то тогда зачем притянули сюда UTF8?
2) 32-64 символа -- так 32 или 64? На вашем кол-ве это разница +- 50Тб . Это довольно серьезные объемы.
3) Как вы посчитали 100Тб? Вы учли место под индекс?
Идеи по проблеме:
1) тащить сюда реляционку не стоит, ибо...
2) очевидно, что это всё надо запускать не на одной машине, на глаз - минимум 2, не считая бэкапа (он нужен?) либо реплик => шардинг => kv-хранилища подойдут лучше (если мы правильно поняли, что вы хотите)
3) ничего не сказано про кол-во запросов - вставки/чтения. Но я бы подумал над размещением перед этим хранилищем предварительной проверке по фильтру Блума, чтобы лишний раз не стукаться в хранилище. Но это надо знать характер данных и запросов.
С хешем, не то написал. 32 бита* т.е строка вида (1001010101...) UTF-8 2 байта занимает по идее, как он может занимать 6, это разновидности ? тогда 32 бита я могу сложить в 2 символа ютф. Здесь Вы правы, скорей это будет не ютф (китайские иероглифы в базе мне не нужны =) ), а ASCII - 4 символа. Спасибо за советы
Простой
Простой
