Если вы хотите подсчитать объем чтения статьи, вы можете напрямую использовать команду Redis incr для ее завершения. Если требуется, чтобы том для чтения был дедуплицирован пользователем, вы можете использовать set для записи всех идентификаторов пользователей, прочитавших эту статью, а длина набора наборов равна объему для чтения с дедупликацией. Но если популярные статьи читаются слишком много, набор будет тратить слишком много места для хранения. В настоящее время нам нужно использовать структуру данных HyperLogLog, предоставляемую Redis, вместо набора, который занимает всего до 12 КБ дискового пространства для полной статистики дедупликации. Но это жертвует точностью, это нечеткие подсчеты с частотой ошибок около 0,81%.
Значит, нет точного метода подсчета, который бы не занимал много места? Сначала мы думаем о растровом изображении, вы можете использовать битовое изображение для представления идентификатора пользователя. Если идентификатор пользователя составляет 32 байта, используйте растровое изображение, которое должно занимать только 1/256 пространства для завершения точного подсчета. Но как сопоставить идентификатор пользователя с расположением растрового изображения? Если идентификатор пользователя представляет собой непрерывное целое число, это очень хорошо, но обычно идентификатор пользователя пользовательской системы представляет собой не целое число, а строку или большое число случайных чисел.
Мы можем принудительно присвоить каждому идентификатору пользователя последовательность целых чисел, а затем сохранить соответствие между идентификаторами пользователей и целыми числами в Redis.
$next_user_id = incr user_id_seq
set user_id_xxx $next_user_id
$next_user_id = incr user_id_seq
set user_id_yyy $next_user_id
$next_user_id = incr user_id_seq
set user_id_zzz $next_user_id
Здесь вы можете задавать вопросы. Вы сказали, что это делается для экономии места. Не является ли пустая трата места для хранения отношения сопоставления между идентификаторами пользователей и целыми числами? Это хороший вопрос, но в то же время мы также должны видеть, что это отношение сопоставления можно использовать повторно: оно может подсчитывать объем чтения всех статей, а также ежедневные и ежемесячные действия зарегистрированных пользователей. Его также можно использовать во многих других статистических случаях, когда пользователям требуется дедупликация. В этом смысл так называемой «заслуги в современности и пользы в будущем».
С помощью этого отношения сопоставления мы можем легко построить растровое изображение точек чтения для каждой статьи.Когда пользователь приходит, соответствующая позиция в соответствующем растровом изображении устанавливается как единица. Если бит меняется с 0 на 1, то к счетчику чтения можно добавить 1. Таким образом, вы можете легко получить количество прочитанных статей.
И мы также можем динамически подсчитать, сколько публичных пользователей прочитали две статьи? Выполните вычисление И для двух растровых изображений, а затем подсчитайте количество битов 1 в растровом изображении. Точно так же возможны вычисления ИЛИ, XOR и т. д.
Вот проблема! Растровое изображение Redis — это плотное растровое изображение, что это значит? Если есть большой битмап, только последний бит равен 1, а остальные нулевые, то этот битмап все равно будет занимать все место в памяти, что не является общей тратой. Вы можете себе представить, что большинство статей мало читается, но их следы очень близки, как память, занимаемая популярными статьями.
Похоже, что это решение не будет работать, нам нужно подумать о других решениях! Здесь поставляется рентгенбизн.
Это будет целый большой битовой блок, если весь блок равна нулю, то он не сохранил бы весь блок. Однако, если 1-битный разбросанный, каждый блок, который представляют 1, хотя редко один блок в 1, поэтому только блок недостаточно, то как это сделать? Давайте подумаем о одном блоке, не может продолжать оптимизировать? Если отдельные ячейки в небольшом количестве бит, мы можем хранить все биты смещения блока (целое число), которое сохраняется в списке целых чисел, а затем сохраняется в блоке. Это форма одного блока памяти редкая растровое изображение - сохранение списка смещения целых чисел. Только один бит в блоке превышает пороговое значение, он преобразует в одноразовую редкую память с интенсивным хранением.
Ревущие растровые изображения могут не только сэкономить много места, но и снизить вычислительную эффективность битовых операций, таких как И и ИЛИ. Если раньше нужно было вычислять все растровое изображение, то теперь нужно вычислять только частичные блоки. Если блок очень разреженный, то необходимо только выполнять операции И и ИЛИ над наборами в этих небольших целочисленных списках, а объем вычислений можно продолжать уменьшать.
Здесь ни пространство не заменяется временем, ни время не заменяется пространством, но сложность логики заменяется пространством и временем одновременно.
Максимальная длина в битах растрового изображения — 2^32, соответствующее пространство — 512 МБ (обычное растровое изображение), смещение в битах делится на старшие 16 бит и младшие 16 бит, старшие 16 бит представляют смещение блока, а младшие 16 бит. биты представляют блок. В данном местоположении один блок может выражать битовую длину 64 КБ, что составляет 8 КБ байт. Будет не более 64k блоков. Кэш L1 современных процессоров, как правило, больше 8 КБ, что гарантирует возможность помещения одного блока в кеш L1, что может значительно повысить производительность.
Если все биты одного блока равны нулю, то его не нужно сохранять. Что-то может быть выражено в растровом изображении, когда блок небольшой, обозначен целым списком, который может быть преобразован в обычный битовый массив, когда блок больше. Целочисленный список занимает меньше места, который также имеет механизм динамического расширения, аналогичный ArrayList, чтобы избежать повторного развертывания содержимого массива репликации. Когда число в списке превышает 4096, оно немедленно преобразуется в обычный битовый массив.
Строительный блок, используемый для выражения наличия или отсутствия структуры данных, и выражение одного блока данных могут быть одинаковыми, независимо от того, существует ли блок в природе, как 0 и 1, является нормальным флагом.
Но Redis изначально не поддерживает растровую структуру данных? Как мы можем это использовать?
Это правда, что у Redis нет родного, но у Redis Module of Roaring Bitmap есть.
Количество звезд у этого проекта не очень большое, давайте посмотрим на его официальное сравнение производительности.
| OP | TIME/OP (us) | ST.DEV. (us) |
|---|---|---|
| R.SETBIT | 31.89 | 28.49 |
| SETBIT | 29.98 | 29.23 |
| R.GETBIT | 29.90 | 14.60 |
| GETBIT | 28.63 | 14.58 |
| R.BITCOUNT | 32.13 | 0.10 |
| BITCOUNT | 192.38 | 0.96 |
| R.BITPOS | 70.27 | 0.14 |
| BITPOS | 87.70 | 0.62 |
| R.BITOP NOT | 156.66 | 3.15 |
| BITOP NOT | 364.46 | 5.62 |
| R.BITOP AND | 81.56 | 0.48 |
| BITOP AND | 492.97 | 8.32 |
| R.BITOP OR | 107.03 | 2.44 |
| BITOP OR | 461.68 | 8.42 |
| R.BITOP XOR | 69.07 | 2.82 |
| BITOP XOR | 440.75 | 7.90 |
Очевидно, сравнение здесь разреженное битовое изображение, только разреженное битовое изображение может представить такие красивые числа. Если это плотное растровое изображение, производительность рычащего растрового изображения определенно немного слабее, чем у обычного растрового изображения, но обычно ненамного.
Давайте посмотрим на исходный код, чтобы увидеть, на что похожа его внутренняя структура.
// 单个块
typedef struct roaring_array_s {
int32_t size;
int32_t allocation_size;
void **containers; // 指向整数数组或者普通位图
uint16_t *keys;
uint8_t *typecodes;
uint8_t flags;
} roaring_array_t;
// 所有块
typedef struct roaring_bitmap_s {
roaring_array_t high_low_container;
} roaring_bitmap_t;
Очевидно, что наличие или отсутствие блока и данные в блоке выражаются с помощью одной и той же структуры данных, которые оба являются roaring_bitmap_t. В этой структуре есть несколько форм кодирования, а тип представлен полем typecodes.
#define BITSET_CONTAINER_TYPE_CODE 1
#define ARRAY_CONTAINER_TYPE_CODE 2
#define RUN_CONTAINER_TYPE_CODE 3
#define SHARED_CONTAINER_TYPE_CODE 4
Глядя на определение типа здесь, мы обнаруживаем, что это не только обычные растровые изображения и список массивов, упомянутые выше, но также два типа RUN и SHARED. Форма RUN представляет собой сжатую форму растрового изображения. Например, несколько последовательных битов 101, 102, 103, 104, 105, 106, 107, 108 и 109 выражаются как 101, 8 после RUN (за 1 следуют 8 собственных битов). -инкрементные целые числа), так что его можно значительно сжать в пространстве. При нормальных обстоятельствах внутри растрового изображения рычания нет блоков типа RUN. Только тот API оптимизации, который явно вызывает ревущий битмап, будет преобразован в формат RUN, этот API — roaring_bitmap_run_optimize.
Хотя тип SHARED используется для разделения блоков между несколькими растровыми изображениями рычания, он также обеспечивает функциональность копирования при записи. При изменении блока будет создана новая копия.
Есть более подробная информация о логике расчета ревущего растрового изображения, и мы продолжим вводить ее позже, когда у нас будет время.