Мы знаем, что крупная компания часто имеет сложную организационную структуру с сотнями тысяч сотрудников.Чтобы быть большой и не хаотичной, мы должны опираться на разумную организационную структуру для оптимизации затрат на внутреннюю коммуникацию. Redis также имеет внутреннюю организационную структуру, разница в том, что эта организационная структура должна поддерживать сотни миллионов объектов вместо сотен или тысяч. Сегодня я покажу вам, как Redis управляет сотнями миллионов объектов, не путаясь.
В Redis много объектов, но типы объектов ограничены, на данный момент существует всего 7 типов объектов.
#define OBJ_STRING 0 /* String object. */
#define OBJ_LIST 1 /* List object. */
#define OBJ_SET 2 /* Set object. */
#define OBJ_ZSET 3 /* Sorted set object. */
#define OBJ_HASH 4 /* Hash object. */
#define OBJ_MODULE 5 /* Module object. */
#define OBJ_STREAM 6 /* Stream object. */
Увидев это, многие люди обязательно поднимут руки в знак протеста! Старые деньги, вы не правы, где ГиперЛогЛог? Куда пропал Гео?
Отличный вопрос! На самом деле, я задавал себе этот вопрос, когда писал эту статью. Когда я задавал этот вопрос, я не знал, почему. Я просто смутно чувствовал, что в Redis нужно смешать три вышеуказанные расширенные структуры данных. структуры, то есть они являются составными структурами данных. Но мне нужно было подтверждение, поэтому я прочитал исходный код, чтобы подтвердить свою догадку.
HyperLogLog, как и Bitmap, использует обычную динамическую строку, а Geo использует zset. Еще одна замечательная вещь заключается в том, что когда вы используете pfadd для создания объекта-счетчика, вы можете напрямую использовать строковые команды для отображения всех его внутренних компонентов.
127.0.0.1:6379> pfadd codehole python java golang
(integer) 1
127.0.0.1:6379> get codehole
"HYLL\x01\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x80C\x03\x84MK\x80P\xb8\x80^\xf3"
Вы также можете использовать команды, связанные с zset, для отображения содержимого геоданных.
127.0.0.1:6379> GEOADD city 13.361389 38.115556 "Palermo" 15.087269 37.502669 "Catania"
(integer) 2
127.0.0.1:6379> zrange city 0 -1 withscores
1) "Palermo"
2) "3479099956230698"
3) "Catania"
4) "3479447370796909"
На этот вопрос был дан ответ. Теперь я задам другой вопрос. Какова связь между «списком пропуска», «сжатым списком zip» и «быстрым списком быстрого списка», которые мы обычно слышим о типе объекта?
Чтобы ответить на этот вопрос, следующим шагом будет знакомство с объектной структурой Redis. Все объекты Redis имеют одинаковую «структуру головы», и в структуре головы есть указатель на каждую другую «структуру тела».
typedef struct redisObject {
unsigned type:4; // 对象类型
unsigned encoding:4; // 对象编码
unsigned lru:24; // LRU时间戳
int refcount; // 引用计数
void *ptr; // 指向体结构的指针
} robj;
Мы заметили, что поле типа состоит всего из 4 бит, что может представлять не более 16 типов объектов.Возможно, поэтому тип объекта следует сохранить.Если он слишком расточительный, его будет нелегко расширить.
Мы также заметили, что есть поле кодирования, также 4-битное, которое представляет тип внутренней структуры объекта. В целях экономии памяти Redis использует специальную структуру для хранения, когда объект коллекции относительно небольшой. Например, когда у хэш-объекта мало внутренних ключей (размер
Тип — внешний унифицированный интерфейс — образ, Кодирование — внутренняя конкретная реализация — плоть и кровь.
Давайте пролистать исходный код, чтобы увидеть, какие кодировки имеют
#define OBJ_ENCODING_RAW 0 // 可修改的长字符串
#define OBJ_ENCODING_INT 1 // 整型字符串
#define OBJ_ENCODING_HT 2 // hashtable
#define OBJ_ENCODING_ZIPMAP 3 // 压缩map，已经废弃不用，改用ziplist
#define OBJ_ENCODING_LINKEDLIST 4 // 双向链表，已废弃不用，改用quicklist
#define OBJ_ENCODING_ZIPLIST 5 // 压缩列表
#define OBJ_ENCODING_INTSET 6 // 整数集合，个数少全是整数的set
#define OBJ_ENCODING_SKIPLIST 7 // 跳跃列表，zset的标准内部结构
#define OBJ_ENCODING_EMBSTR 8 // 只读短字符串
#define OBJ_ENCODING_QUICKLIST 9 // 快速列表，存储list
#define OBJ_ENCODING_STREAM 10 // 流
Увидев это, я начал немного осторожничать, кодировка всего 4 бита, а использовано 11 значений, а вдруг в будущем расширение изменится? На этот вопрос здесь ответить непросто, вы можете обсудить его сами.
Соответствие между Типом и Кодировкой следующее
1. string ==> raw|embstr|int
2. list ==> quicklist
3. hash ==> ziplist|hashtable
4. set ==> intset|hashtable
5. zset ==> ziplist|skiplist
6. stream => stream
Далее мы начнем погружаться во внутреннюю структуру и пройдемся по каждой структуре.Из-за нехватки места мы не можем вдаваться в подробности.
Первое, о чем мы хотим поговорить, это словарь, потому что он слишком важен. Основой дерева объектов Redis является структура словаря. Ключ — это имя объекта, а значение — различные объекты. Все объекты связаны к словарю. В дополнение к магистральному словарю, который содержит все объекты, существует также магистральный словарь с истекающим сроком действия, который содержит все объекты со сроком действия.Его ключом является имя объекта, а значением является отметка времени истечения срока действия объекта.
typedef struct redisDb {
dict *dict;
dict *expires;
...
} redisDb;
Значение словаря показывает полиморфизм, это может быть простое целое или число с плавающей запятой, или объект, будет унифицированный заголовок объекта, то есть предыдущая структура redisObject, которая будет основываться на поле типа и поле кодировки , чтобы определить конкретную структуру данных, на которую указывает поле ptr. Давайте посмотрим на определение кода структуры словаря.
// dict
typedef struct dict {
dictType *type; // 字典的接口实现，为字典带来多态性
void *privdata; // 存储字典的附加信息
dictht ht[2]; // 注意这里不是指向指针的数组，为什么？
long rehashidx; // 渐进式rehash时记录当前rehash的位置
unsigned long iterators;
} dict;
// dict hashtable
typedef struct dictht {
dictEntry **table; // 指向第一维数组
unsigned long size; // 数组的长度
unsigned long sizemask; // 用于快速hash定位 sizemask = size - 1
unsigned long used; // 数组中的元素个数
} dictht;
// 定义了字典功能的接口
typedef struct dictType {
uint64_t (*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;
// key-value wrapper
typedef struct dictEntry {
void *key;
union {
void *val; // sds|set|dict|zset|quicklist
uint64_t u64; // 用于过期字典，val存储过期时间戳
int64_t s64; // Don't watch me!
double d; // 用于zset，存储score值
} v;
struct dictEntry *next;
} dictEntry;
Внутренняя реализация структуры словаря - две хеш-таблицы, зачем две хэш-таблицы, это предполагает прогрессивное расширение и размещение словаря, о чем мы поговорим позже. Обычно мы используем только ht[0], простую хеш-таблицу
Давайте посмотрим на внутреннюю структуру хеш-таблицы. Структура хеш-таблицы такая же, как и у основной версии HashMap на языке Java, подробно объяснять не буду, если интересно, можно поискать нужную информацию.
Давайте посмотрим на внутреннюю структуру словаря, это двухмерный
Процесс поиска выглядит следующим образом.Для удобства чтения я аккуратно убрал дополнительную часть кода, которая должна учитывать "инкрементальную миграцию"
dictEntry *dictFind(dict *d, const void *key)
{
dictEntry *he;
uint64_t h, idx, table;
if (d->ht[0].used == 0) return NULL; /* dict is empty */
h = dictHashKey(d, key); // 计算hash值
idx = h & d->ht[0].sizemask; // 定位数组位置
he = d->ht[0].table[idx]; // 获取链表表头
while(he) {
if (key==he->key || dictCompareKeys(d, key, he->key))
return he; // 找到了就返回
he = he->next; // 找不到继续遍历
}
return NULL;
}
Среди них dictHashKey и dictCompareKeys будут соответственно вызывать полиморфную функцию соответствующего словаря
#define dictHashKey(d, key) (d)->type->hashFunction(key)
#define dictCompareKeys(d, key1, key2) \
(((d)->type->keyCompare) ? \
(d)->type->keyCompare((d)->privdata, key1, key2) : \
(key1) == (key2))
Следует отметить, что массив позиционирования использует побитовую операцию, потому что длина массива первого измерения словаря будет 2^n. Для массивов длины 2 ^ n операция по модулю длины массива эквивалентна побитовой операции
sizemask = size - 1;
idx = h & d->ht[0].sizemask ==> idx = h % d->ht[0].size
Когда мы используем HashMap в Java, мы будем осторожны, так как если хэш-код объекта неравномерен, длина связанного списка будет сильно различаться, а отдельные связанные списки будут особенно длинными, что окажет большее влияние на производительность. Поэтому Java 8 соответствующим образом преобразовал связанный список HashMap.Если длина связанного списка превышает 8, он будет преобразован в красно-черное дерево для повышения эффективности поиска.
Так почему же Redis не нужно это учитывать?
Это связано с тем, что ключевой объект, содержащийся в HashMap Java, является неуправляемым и может быть любым объектом.Если значение, возвращаемое методом hashCode объекта, неоднородно, это вызовет проблемы с производительностью.
Однако все ключи, содержащиеся в словаре Redis, представляют собой динамические строки sds, а их хэш-код является однородным и управляемым.Встроенный алгоритм хеширования (siphash) Redis может гарантировать, что хеш-значение строки будет очень однородным.
Далее поговорим о расширении словаря.
В HashMap в Java расширение заключается в применении нового массива, который в два раза превышает размер старого массива, а затем одновременном переносе всех элементов, присоединенных к старому массиву, в новый массив. Если в словаре слишком много элементов, расширение будет потреблять больше вычислительных ресурсов, что обычно называют «заиканием».
Redis может хранить в памяти миллиарды объектов, и эти объекты организованы с помощью словарей. Если стратегия расширения словаря Redis такая же, как у Java HashMap, такой огромный словарь обязательно столкнется с «проблемой заикания».
Чтобы решить эту проблему, Redis использует стратегию добавочной миграции. Когда словарь необходимо расширить, он подаст заявку на новую хэш-таблицу и поместит ее в ht[1] словаря.До завершения миграции старые и новые хэш-таблицы будут сосуществовать, то есть два значения поля ht[1] и ht[0] существуют одновременно.
int dictExpand(dict *d, unsigned long size)
{
if (dictIsRehashing(d) || d->ht[0].used > size)
return DICT_ERR;
dictht n;
unsigned long realsize = _dictNextPower(size);
if (realsize == d->ht[0].size) return DICT_ERR;
// 分配一个新的hashtable
n.size = realsize;
n.sizemask = realsize - 1;
n.table = zcalloc(realsize*sizeof(dictEntry*));
n.used = 0;
// 如果是空字典的第一次扩容，那就挂到ht[0]上
if (d->ht[0].table == NULL) {
d->ht[0] = n;
return DICT_OK;
}
// 挂在ht[1]上，准备进行渐进式迁移
d->ht[1] = n;
d->rehashidx = 0;
return DICT_OK;
}
В каждой последующей инструкции словаря Redis будет переносить часть пар ключ-значение из старой хэш-таблицы в новую хеш-таблицу. В настоящее время добавочная миграция каждый раз переносит 10 слотов, то есть максимум 10 связанных списков, а средняя длина связанного списка составляет около 1. Видя это, я не могу не опасаться того, сколько дополнительных миграций требуется для завершения большого словаря. Если не будет последующих операций чтения и записи, миграция никогда не будет завершена? Этот читатель может продолжать думать.
Когда в Redis накапливаются сотни миллионов объектов, костяком дерева объектов является словарь, который очень велик и нуждается в расширении. Если это инкрементное расширение займет много времени, каждую инструкцию Redis необходимо будет постепенно мигрировать, что неизбежно повлияет на общую производительность, и память будет находиться в состоянии относительно высокой избыточности в течение длительного времени.
Поэтому Redis применяет метод обычной активной миграции для этого магистрального словаря и выполняет добавочную миграцию каждую 1 мс, и каждая миграция не превышает 1 мс, чтобы не застревать обычные инструкции.
// 渐进式rehash，最多持续时间ms
int dictRehashMilliseconds(dict *d, int ms) {
long long start = timeInMilliseconds();
int rehashes = 0;
// 每次执行100步(每步10个槽位)，停下来看看时间，如果超出时间就中断
while(dictRehash(d,100)) {
rehashes += 100;
if (timeInMilliseconds()-start > ms) break;
}
return rehashes;
}
// 对指定db进行渐进式rehash
// 优先迁移所有对象的主干字典，再考虑过期对象字典
int incrementallyRehash(int dbid) {
if (dictIsRehashing(server.db[dbid].dict)) {
dictRehashMilliseconds(server.db[dbid].dict,1);
return 1;
}
if (dictIsRehashing(server.db[dbid].expires)) {
dictRehashMilliseconds(server.db[dbid].expires,1);
return 1;
}
return 0;
}
В то же время, если Redis запускает bgsave или bgaofrewrite для запуска дочернего процесса для выполнения операций сохранения, ему необходимо пройти все дерево объектов. Во избежание разделения слишком большого количества страниц родительско-дочернего процесса и увеличения общего использования памяти, при выполнении этих двух инструкций старайтесь не выполнять расширение словаря dict_can_resize = false, если только словарь уже сильно не переполнен , порог этой степени скученности по умолчанию — dict_force_resize_ratio = 5, то есть отношение количества элементов словаря к длине одномерного массива.
static int _dictExpandIfNeeded(dict *d)
{
// 如果正在执行渐进式rehash，那就暂时不要扩容
if (dictIsRehashing(d)) return DICT_OK;
// 如果是空字典，那就进行第一次扩容
if (d->ht[0].size == 0) return dictExpand(d, DICT_HT_INITIAL_SIZE);
// 综合考虑字典的拥挤程度以及实例是否处于bgsave/bgaofrewrite
// 来决定是否进行扩容
if(dict_can_resize ||
d->ht[0].used/d->ht[0].size > dict_force_resize_ratio))
{
return dictExpand(d, d->ht[0].used*2);
}
return DICT_OK;
}
Вот и все о содержании словаря, в следующей статье мы продолжим рассмотрение ключей, содержащихся в словаре. Все ключи словаря — это строки, поэтому в следующей статье мы поговорим о внутренней структуре строк, так что следите за обновлениями.
Техническая брошюра Nuggets Online выдержки из этой статьи«Глубокое приключение Редиса», если вы заинтересованы в Redis, нажмите на ссылку, чтобы узнать больше«Глубокое приключение Редиса»
Прочтите более подробные технические статьи, отсканируйте приведенный выше QR-код и подпишитесь на общедоступную учетную запись WeChat «Code Cave».