1. Введение и применение
Redis — это база данных K-K в памяти, написанная на языке ANSI C, с отличной производительностью, сетевой поддержкой и устойчивостью, а также предоставляющая API на нескольких языках. Его обычно используемые типы - это в основном String, List, Hash, Set и ZSet.
Строка: Кэш, Текущий лимит, Счетчик, Распределенная блокировка, Распределенная сессия
Хэш: хранить информацию о пользователе, посещения домашней страницы пользователя, комбинированный запрос
Список: Хронология списка подписчиков Weibo, простая очередь
Набор: Нравится, Не нравится, Тег, Дружба
Zset: Таблица лидеров
В другом примере, когда в электронной коммерции проводится большое продвижение, для обеспечения стабильности системы будут использоваться некоторые специальные схемы.Следующие схемы могут быть рассмотрены для вычета запасов:
Из приведенных выше сценариев приложений видно, что Redis очень эффективен и стабилен.Как реализован нижний уровень Redis?
2. Объект Redis redisObject
Когда мы выполняем команду set hello world, мы получаем следующую модель данных:
sds: Ключ "hello" хранится в SDS (Simple Dynamic String), который будет подробно описан позже.
redisObject: значение val "world" сохраняется в файле redisObject. На самом деле обычно используемые redis 5 типов хранятся в redisObject, поле type в redisObject указывает на тип объекта Value, а поле ptr указывает на адрес, где находится объект.
Объект redisObject очень важен.Тип, внутреннее кодирование, восстановление памяти, общий объект и другие функции объекта Redis требуют поддержки redisObject. Преимущество этой схемы заключается в том, что для различных сценариев использования можно задать множество различных реализаций структур данных для пяти наиболее часто используемых типов, тем самым оптимизируя эффективность использования объектов в различных сценариях.
Будь то объект dictEntry, объект redisObject или SDS, для выделения памяти для хранения требуется распределитель памяти (например, jemalloc). Являясь распределителем памяти по умолчанию в Redis, jemalloc относительно хорошо справляется с уменьшением фрагментации памяти. Например, в 64-битной системе jemalloc делит пространство памяти на три диапазона: малый, большой и огромный; каждый диапазон делится на множество небольших блоков памяти; когда Redis сохраняет данные, он выбирает блок памяти наиболее подходящего размера. хранить.
Как упоминалось ранее, каждый объект Redis представлен структурой redisObject, а его указатель ptr указывает на структуру данных базовой реализации, а структура данных определяется атрибутом кодирования. Например, мы выполняем следующую команду, чтобы получить кодировку, соответствующую хранилищу «hello»:
Базовая реализация строкового объекта может быть int, raw, embstr (приведенная выше таблица соответствует введению имени). Кодировка embstr выделяет непрерывное пространство, вызывая функцию выделения памяти один раз, в то время как raw необходимо вызывать дважды.
Простая динамическая строка (SDS), эта структура больше похожа на C++ String или Java ArrayList, а ее длина динамически изменяется:
struct sdshdr {
// buf 中已占用空间的长度
int len;
// buf 中剩余可用空间的长度
int free;
// 数据空间
char buf[]; // ’\0’空字符结尾
};
получить: sdsrange---O(n) установить: sdscpy — O (n) создать: sdsnew---O(1) len: sdslen---O(1)
Постоянная сложность для получения длины строки: поскольку SDS записывает длину в атрибуте len, временная сложность получения длины SDS составляет всего O(1).
Распределение предварительного пространства: если SDS изменен, его можно разделить на следующие две ситуации:
1. Если длина SDS (значение len) меньше 1 МБ, программа выделит неиспользуемое пространство того же размера, что и атрибут len.В это время значения атрибута free и len совпадают. Например, len SDS станет равным 15 байтам, программа также выделит 15 байт неиспользуемого пространства, а фактическая длина массива буферов SDS станет 15+15+1=31 байт (дополнительный байт). сохраняет нулевые символы).
2. Если длина SDS (значение len) больше или равна 1 МБ, программа выделит 1 МБ неиспользуемого пространства. Например, после модификации len SDS становится равным 30 МБ, тогда его фактическая длина составляет 30 МБ + 1 МБ + 1 байт.
Ленивое свободное пространство: после выполнения sdstrim (перехвата строки) SDS не освобождает лишнее пространство немедленно. пригодиться. Операции перераспределения памяти, которые манипулируют строками, в некоторых случаях избегаются за счет ленивого освобождения места.
Избегайте переполнения буфера: при использовании строковых операций C, если длина строки увеличивается (например, операция strcat) и забывают перераспределить память, легко вызвать переполнение буфера; а SDS записывает длину, соответствующая операция может привести к переполнению буфера. , память будет автоматически перераспределена, что предотвратит переполнение буфера.
4. Список
Базовой реализацией объекта List является quicklist (быстрый список, представляющий собой комбинацию сжатого списка ziplist и двустороннего связанного списка linkedlist). Списки в Redis поддерживают вставку и извлечение с обоих концов и могут получать элементы в указанных позициях (или диапазонах), которые могут выступать в качестве массивов, очередей, стеков и т. д.
typedef struct listNode {
// 前置节点
struct listNode *prev;
// 后置节点
struct listNode *next;
// 节点的值
void *value;
} listNode;
typedef struct list {
// 表头节点
listNode *head;
// 表尾节点
listNode *tail;
// 节点值复制函数
void *(*dup)(void *ptr);
// 节点值释放函数
void (*free)(void *ptr);
// 节点值对比函数
int (*match)(void *ptr, void *key);
// 链表所包含的节点数量
unsigned long len;
} list;
rpush: listAddNodeHead ---O(1) lpush: listAddNodeTail ---O(1) push: listInsertNode ---O(1) index : listIndex ---O(N) pop: ListFirst/listLast ---O(1) llen: listLength ---O(N)
4.1 связанный список (двусторонний связанный список)
Эта структура похожа на LinkedList в Java.Если вам интересно, вы можете прочитать исходный код.
По сравнению с двусторонним связным списком сжатый список позволяет экономить место в памяти, но сложность выше при изменении, добавлении или удалении операций, поэтому при небольшом числе узлов можно использовать сжатый список; количество узлов велико, двусторонний связанный список по-прежнему используется экономически эффективно.
4.2 ziplist (сжатый список)
Когда ключ списка содержит лишь небольшое количество элементов списка и представляет собой небольшое целочисленное значение или строку относительно небольшой длины, тогда Redis использует ziplist (сжатый список) в качестве базовой реализации ключа списка.
5. Хэш
Базовой реализацией объекта Hash может быть ziplist (сжатый список) или хеш-таблица (словарь или также называемая хеш-таблицей).
Хеш-таблица с хеш-таблицей может выполнять операции чтения и записи O(1), поэтому она очень эффективна. Исходный код выглядит следующим образом:
typedef struct dict {
// 类型特定函数
dictType *type;
// 私有数据
void *privdata;
// 哈希表
dictht ht[2];
// rehash 索引
// 当 rehash 不在进行时，值为 -1
int rehashidx; /* rehashing not in progress if rehashidx == -1 */
// 目前正在运行的安全迭代器的数量
int iterators; /* number of iterators currently running */
} dict;
typedef struct dictht {
// 哈希表数组
dictEntry **table;
// 哈希表大小
unsigned long size;
// 哈希表大小掩码，用于计算索引值
// 总是等于 size - 1
unsigned long sizemask;
// 该哈希表已有节点的数量
unsigned long used;
} dictht;
typedef struct dictEntry {
void *key;
union {void *val;uint64_t u64;int64_t s64;} v;
// 指向下个哈希表节点，形成链表
struct dictEntry *next;
} dictEntry;
typedef struct dictType {
// 计算哈希值的函数
unsigned int (*hashFunction)(const void *key);
// 复制键的函数
void *(*keyDup)(void *privdata, const void *key);
// 复制值的函数
void *(*valDup)(void *privdata, const void *obj);
// 对比键的函数
int (*keyCompare)(void *privdata, const void *key1, const void *key2);
// 销毁键的函数
void (*keyDestructor)(void *privdata, void *key);
// 销毁值的函数
void (*valDestructor)(void *privdata, void *obj);
} dictType;
Приведенный выше исходный код можно упростить до следующей структуры:
Если словарь в Redis использует хэш-таблицу в качестве базовой реализации, каждый словарь будет иметь две хэш-таблицы, одну для обычного использования, а другую только для повторного хэширования (повторного хеширования). По мере манипулирования хэш-таблицей ключи постепенно увеличиваются или уменьшаются. Чтобы удерживать коэффициент загрузки хеш-таблицы в разумных пределах, Redis будет увеличивать или уменьшать размер хэш-таблицы (перехешировать), то есть разделять все значения ключа в ht[0] на несколько, прогрессивно Перефразировка ht[1].
6. Установить
Базовой реализацией объектов коллекции Set может быть intset (коллекция целых чисел) или хеш-таблица (словарь или также называемая хэш-таблицей).
typedef struct intset {
// 编码方式
uint32_t encoding;
// 集合包含的元素数量
uint32_t length;
// 保存元素的数组
int8_t contents[];
} intset;
sadd: intsetAdd---O(1) smembers: intsetGetO(1) --- O(N) srem: intsetRemove --- O(N) slen: intsetlen ---O(1) Базовая реализация intset — это упорядоченный неповторяющийся массив, содержащий элементы коллекции. Тип целочисленного массива в структуре intset может быть 16-битным, 32-битным или 64-битным. Если все целые числа в массиве имеют длину 16 бит, при добавлении нового 32-битного целого числа весь 16-битный массив будет обновлен до 32-битного массива. Обновление может улучшить гибкость intset и сэкономить память, но это необратимо.
7.ZSet
Базовая реализация объектов упорядоченного набора ZSet может быть ziplist (сжатый список) или skiplist (список пропуска).
typedef struct zskiplist {
// 表头节点和表尾节点
struct zskiplistNode *header, *tail;
// 表中节点的数量
unsigned long length;
// 表中层数最大的节点的层数
int level;
} zskiplist;
typedef struct zskiplistNode {
// 成员对象
robj *obj;
// 分值
double score;
// 后退指针
struct zskiplistNode *backward;
// 层
struct zskiplistLevel {
// 前进指针
struct zskiplistNode *forward;
// 跨度---前进指针所指向节点与当前节点的距离
unsigned int span;
} level[];
} zskiplistNode;
zadd---zslinsert--- среднее O(logN), наихудшее O(N) zrem---zsldelete--- среднее O(logN), худшее O(N) zrank--zslGetRank--- среднее O(logN), худшее O(N)