Оптимизация повторяющихся значений в хранилище ключей с ключом NoSql

Question

Я создаю хранилище для хранения карт, и вам нужно хранить капли размером 1,5 миллиарда ~ 3 КБ. Более 95% из них дублируются. Есть ли механизм хранения NoSQL, который позволит избежать сохранения одинаковых значений?

Я мог бы, конечно, реализовать двойное удаление ссылок, например. кнопочная> hash-> значение. Если хеш - MD5, хэш-байты по 16 байт будут использовать 24 гигабайта только для шахмат, плюс накладные расходы для каждого элемента, что, вероятно, намного больше. Что-нибудь более эффективное?

Спасибо!

Answer 1

Двойное удаление ссылок - это путь, который вы можете сохранить где-то между 4-5 ТБ данных, не сохраняя повторяющиеся данные, поэтому хранение 24 х х хэшей стоит затрат. Кроме того, вам нужно только вычислить хеш-функцию для вложений и обновлений, а не для поиска или удаления.

Чтобы уменьшить стоимость двойного удаления ссылок при поиске, вы можете дополнить свою базу данных ключа на диске с помощью кэша в памяти, например. Redis - вы можете либо кэшировать часто используемые пары key->hash, чтобы избежать двух поисков в первичной базе данных, либо вы можете напрямую сохранить всю структуру key->hash->blob в кеше (первый гораздо проще реализовать, поскольку вам не нужно реплицировать двойную удаление ссылок из первичной базы данных, тогда как последнее имеет больше смысла, если только небольшое подмножество blobs всегда активно).

Вы можете быть в состоянии использовать более простой/меньше хэш - probability of a hash collision является 1 - e^(-k^2/2N) где k этим число значений которые хэшируются и N является размером хэша, так что хороший 64-битный хэш имеет около 12% вероятность столкновения и хороший 128-битный хеш имеет бесконечно малую вероятность столкновения. MurmurHash имеет 64 и 128-битные версии, поэтому вы можете экспериментировать между ними, и он быстрее, чем MD5, в основном из-за того, что MD5 является криптографической хэш-функцией, тогда как Murmur не имеет дополнительных затрат/сложностей в криптографической защите (я предполагаю что вас не беспокоит никто, кто пытается преднамеренно генерировать хеш-коллизии или что-то в этом роде). Некоторые магазины с ключевыми значениями также делают относительно легким сделать ваш дизайн устойчивым к конфликтам, например, вы можете сохранить хэш в Riak Map с флагом, указывающим, были ли какие-либо столкновения с этим значением хэша - если false, то просто верните blob, else отпадает на опцию 2 (например, индексированный blob становится двумя блоками с хеш-коллизацией zipped/tarred вместе вместе с CSV, какие ключи соответствуют какому blob, даже с 64-битным хешем этот путь кода не будет осуществляются очень часто, и поэтому простота реализации, вероятно, превосходит производительность); возникает вопрос, уменьшает ли недостаток памяти/хеширования сложность толерантности к столкновению.