Серия статей по анализу исходного кода Redis
Строковая базовая реализация — динамическая строковая SDS
Двусвязный список Redis знает все
Интервьюер: Расскажите о нижнем слое Redis Hash. Я: ... (вопросы интервью от Reading)
Я уверен, что не понимаю таблицу прыжков 😏
предисловие
Здравствуй, Да Кар, сегодня еще полный день жизненных сил, отложи в сторону потребности бесконечного письма, отказывайся просить воров и извращенных клиентов, просто изучай технологии и чувствуй прелесть технологий. (Хахаха, кожа очень открытая)
За последние несколько недель мы рассмотрели базовую структуру данных Redis, такую как动态字符串SDS,双向链表Adlist,字典Dict,跳跃表, если вы не понимаете общие типы или базовые структуры данных Redis, посетите портал выше.
Сегодня поговорим о базовой реализации set整数集合, если вы не понимаете набор, здесь не будет рассматриваться общее использование API, просто посмотрите на портал выше.
Концепция целочисленной коллекции
Целочисленный набор — это базовая структура, разработанная Redis, которая является базовой реализацией набора.Эта структура используется, когда набор содержит только элементы целочисленного значения и в элементах набора не так много данных. Однако, если только что условия не будут соблюдены, будут использоваться другие структуры, которые здесь пока не обсуждаются.
На следующем рисунке показана фактическая композиция набора целых чисел, включая три части, а именно формат кодирования, включая количество элементов, длину, и содержимое массива, в котором хранятся элементы. (Кратко посмотрите здесь, далее подробное описание каждого модуля 😝)
Реализация коллекции целых чисел
Давайте посмотрим на определение целочисленных наборов в Intset.h, код выше:
//整数集合结构体
typedef struct intset {
uint32_t encoding; //编码格式，有如下三种格式，初始值默认为INTSET_ENC_INT16
uint32_t length; //集合元素数量
int8_t contents[]; //保存元素的数组，元素类型并不一定是ini8_t类型，柔性数组不占intset结构体大小，并且数组中的元素从小到大排列。
} intset;
#define INTSET_ENC_INT16 (sizeof(int16_t)) //16位，2个字节，表示范围-32,768~32,767
#define INTSET_ENC_INT32 (sizeof(int32_t)) //32位，4个字节，表示范围-2,147,483,648~2,147,483,647
#define INTSET_ENC_INT64 (sizeof(int64_t)) //64位，8个字节，表示范围-9,223,372,036,854,775,808~9,223,372,036,854,775,807кодировка формат кодировка
Включая три типа INTSET_ENC_INT16, INTSET_ENC_INT32, INTSET_ENC_INT64, которые соответствуют разным диапазонам, подробности см. в комментариях к приведенному выше коду.
Поскольку размер вставляемых данных отличается,为了尽可能的节约内存(Ведь это все деньги, поэтому нам обычно нужно их экономить 😭), поэтому нам нужно использовать разные типы для хранения данных.
Количество элементов в длине коллекции
Записывает длину содержимого сохраненных данных, то есть количество элементов.
Содержимое массива, содержащего элементы
Там, где данные фактически хранятся, массив основан на从小到大отсортировано, и不包含任何重复项(Поскольку набор не содержит дубликатов, его базовая реализация также не содержит включений).
Процесс обновления целочисленного набора (выделение, ручная звездочка)
Давайте еще раз посмотрим на приведенный выше рисунок, кодировка формата кодировки INTSET_ENC_INT16, то есть каждые данные занимают 16 бит. Длина length равна 4, то есть в содержимом массива четыре элемента: 1, 2, 3 и 4. Если мы хотим добавить число 40000, оно явно находится за пределами диапазона от -32 768 до 32 767 в формате кодирования INTSET_ENC_INT16, который должен быть в формате кодирования INTSET_ENC_INT32. Так как же он обновился с INTSET_ENC_INT16 до INTSET_ENC_INT32?
1. Узнайте об устаревших форматах хранения
Во-первых, давайте посмотрим, как хранятся четыре элемента 1, 2, 3 и 4. Прежде всего, вам нужно знать, сколько цифр.length*编码格式的位数,Сейчас4*16=64. Таким образом, каждый элемент занимает 16 бит.
2. Определите новый формат кодировки
Новый элемент — 40000, что превышает диапазон INTSET_ENC_INT16 от -32 768 до 32 767, поэтому новый формат кодирования — INTSET_ENC_INT32.
3. Добавить память в соответствии с новым форматом кодирования
Выше было объяснено, что формат кодирования — INTSET_ENC_INT32, а правило расчета —length*编码格式的位数,Сейчас5*32=160. Итак, новое количество цифр 64-159.
4. Установите соответствующее значение в соответствии с форматом кодирования.
Из вышеизложенного известно, что согласно новому формату кодирования каждые данные должны занимать 32 бита, а в старом формате кодирования каждые данные занимают 16 бит. Итак, мы начинаем с конца и получаем 32 бита за раз для хранения данных.
Это слишком сложно для понимания, смотрите картинку ниже ☺.
Во-первых, последние 32 бита, то есть 128-159, хранят 40000. Тогда стр. 49-127 пусты.
Далее возьмите последние 32 бита пустых 49-127, то есть 32 бита с 96 по 127, чтобы сохранить 4. Так之前4存储的位置48-63а также49-127剩下的64-95Эти две части составляют основную часть, а именно48-95, сейчас пусто.
В следующей части 48-95 возьмите последние 32 бита, то есть 64-95, чтобы сохранить 3. Так之前3存储位置32-47а также48-95剩下的48-63Эти две части составляют основную часть, а именно32-63, сейчас пусто.
Далее берем большую часть 32-63 бит, а затем берем последние 32 бита, то есть 32-63, для хранения 2. Тогда предыдущие 2 ячейки памяти 16-31 пусты.
Наконец, объедините 16-31 с исходным 0-31 и сохраните 1.
На этом весь процесс обновления заканчивается. В целом, он разделен на 3 этапа: определение нового формата кодирования, добавление необходимого объема памяти и корректировка данных в обратном направлении.
Тут есть небольшой вопрос, а зачем подгонять данные с тыла на перед?
Причина в том, что данные могут быть перезаписаны при переходе от начала к концу. Также в приведенном выше примере данные 1 находятся в битах 0–15, а данные 2 — в битах 16–31.Если мы знаем от начала до конца, что новый формат кодирования INTSET_ENC_INT32 требует, чтобы каждый элемент занимал 32 бита, тогда данные 1 должны занимать 0-31, данные 2 в это время перезаписываются, а данные 2 в дальнейшем не будут известны.
Однако при перемещении сзади вперед, поскольку часть памяти добавляется позже, перезаписи не происходит.
Преимущества обновления
сохранить память
Целочисленные коллекции позволяют коллекции хранить три разных типа значений, а также гарантируют, что обновления выполняются только при необходимости, что экономит память.
Понижение не поддерживается
После обновления массива кодировка всегда будет сохранять обновленное состояние. Даже если 40000 будет удалено позже, формат кодирования не будет INTSET_ENC_INT16.
Анализ исходного кода целочисленных коллекций
Создает пустую коллекцию intsetnew
Этот метод относительно прост и представляет собой этап инициализации набора целых чисел, который является частью рисунка ниже.
Основными шагами являются выделение памяти, установка формата кодирования по умолчанию и инициализация длины массива.
intset *intsetNew(void) {
intset *is = zmalloc(sizeof(intset));//分配内存空间
is->encoding = intrev32ifbe(INTSET_ENC_INT16);//设置默认编码格式INTSET_ENC_INT16
is->length = 0;//初始化length
return is;
}
Добавьте элементы и обновите блок-схему insetAdd (курсив)
Добавить элементы и обновить insetДобавить анализ исходного кода
Согласно приведенной выше блок-схеме, по сравнению со следующим анализом исходного кода, это не будет здесь написано.
//添加元素
//输入参数*is为原整数集合
//value为要添加的元素
//*success为是否添加成功的标志量 ，1表示成功，0表示失败
intset *intsetAdd(intset *is, int64_t value, uint8_t *success) {
//确定要添加的元素的编码格式
uint8_t valenc = _intsetValueEncoding(value);
uint32_t pos;
//如果success没有初始值，则初始化为1
if (success) *success = 1;
//如果新的编码格式大于现在的编码格式，则升级并添加元素
if (valenc > intrev32ifbe(is->encoding)) {
//调用另一个方法
return intsetUpgradeAndAdd(is,value);
} else {
//如果编码格式不变，则调用查询方法
//输入参数is为原整数集合
//value为要添加的数据
//pos为位置
if (intsetSearch(is,value,&pos)) {//如果找到了，则直接返回，因为数据是不可重复的。
if (success) *success = 0;
return is;
}
//设置length
is = intsetResize(is,intrev32ifbe(is->length)+1);
if (pos < intrev32ifbe(is->length)) intsetMoveTail(is,pos,pos+1);
}
//设置数据
_intsetSet(is,pos,value);
is->length = intrev32ifbe(intrev32ifbe(is->length)+1);
return is;
}
//#define INT8_MAX 127
//#define INT16_MAX 32767
//#define INT32_MAX 2147483647
//#define INT64_MAX 9223372036854775807LL
static uint8_t _intsetValueEncoding(int64_t v) {
if (v < INT32_MIN || v > INT32_MAX)
return INTSET_ENC_INT64;
else if (v < INT16_MIN || v > INT16_MAX)
return INTSET_ENC_INT32;
else
return INTSET_ENC_INT16;
}
//根据输入参数value的编码格式，对整数集合is的编码格式升级
static intset *intsetUpgradeAndAdd(intset *is, int64_t value) {
//当前集合的编码格式
uint8_t curenc = intrev32ifbe(is->encoding);
//根据对value解析获取新的编码格式
uint8_t newenc = _intsetValueEncoding(value);
//获取集合元素数量
int length = intrev32ifbe(is->length);
//如果要添加的数据小于0，则prepend为1，否则为0
int prepend = value < 0 ? 1 : 0;
//设置集合为新的编码格式，并根据编码格式重新设置内存
is->encoding = intrev32ifbe(newenc);
is = intsetResize(is,intrev32ifbe(is->length)+1);
//逐步循环，直到length小于0，挨个重新设置每个值，从后往前
while(length--)
_intsetSet(is,length+prepend,_intsetGetEncoded(is,length,curenc));
//如果value为负数，则放在最前面
if (prepend)
_intsetSet(is,0,value);
else//如果value为整数，设置最末尾的元素为value
_intsetSet(is,intrev32ifbe(is->length),value);
//重新设置length
is->length = intrev32ifbe(intrev32ifbe(is->length)+1);
return is;
}
//找到is集合中值为value的下标，返回1，并保存在pos中，没有找到返回0，并将pos设置为value可以插入到数组的位置
static uint8_t intsetSearch(intset *is, int64_t value, uint32_t *pos) {
int min = 0, max = intrev32ifbe(is->length)-1, mid = -1;
int64_t cur = -1;
//如果集合为空，那么位置pos为0
if (intrev32ifbe(is->length) == 0) {
if (pos) *pos = 0;
return 0;
} else {
//因为数据是有序集合，如果要添加的数据大于最后一个数字，那么直接把要添加的值放在最后即可，返回最大值下标
if (value > _intsetGet(is,intrev32ifbe(is->length)-1)) {
if (pos) *pos = intrev32ifbe(is->length);
return 0;
} else if (value < _intsetGet(is,0)) { //如果这个数据小于数组下标为0的数据，即为最小值 ，返回0
if (pos) *pos = 0;
return 0;
}
}
//有序集合采用二分法
while(max >= min) {
mid = ((unsigned int)min + (unsigned int)max) >> 1;
cur = _intsetGet(is,mid);
if (value > cur) {
min = mid+1;
} else if (value < cur) {
max = mid-1;
} else {
break;
}
}
//确定找到
if (value == cur) {
if (pos) *pos = mid;//设置参数pos，返回1，即找到位置
return 1;
} else {//如果没找到，则min和max相邻，随便设置都行，并返回0
if (pos) *pos = min;
return 0;
}
}Эпилог
В этой статье в основном рассказывается о базовой реализации целочисленного набора типа данных Redis SET.Во-первых, что такое целочисленный набор, анализируются его основные компоненты, а затем объясняется, как intset обновляется с помощью нескольких диаграмм процессов, и, наконец, объединяется исходный код. Описаны наборы, такие как процесс создания, процесс обновления, вкрапленные примеры и диаграммы процессов.
Если вы считаете, что сочинение в порядке, пожалуйста, поставьте лайк 👍, ваше одобрение является движущей силой для моего письма!
Если вы считаете, что что-то не так, пожалуйста, прокомментируйте.
Хорошо, пока.
Спасибо всем ❤
1. Если эта статья была вам полезна, пожалуйста, поддержите ее лайком, ваш "лайк" - движущая сила моего творчества.
2. Подпишитесь на официальный аккаунт «Miss Sister Learning Java», чтобы добавить меня в друзья, и я приглашу вас в «Группу обмена технологиями Java», чтобы все могли общаться и вместе добиваться прогресса.