предисловие

Только лысина может стать сильнее

Недавно я изучаю Redis, и я считаю, что любой, кто знаком с разработкой на Java, слышал о Redis как о технологии. Интервью также являются очень часто встречающимся источником знаний, который раньше всегда находился на стадии понимания. После осеннего рекрутского периода давления нет, поэтому я планирую систематически изучать Redis, что можно считать моими заметками для изучения Redis с нуля.

эта статьяСтремитесь прояснить каждый пункт знаний, я надеюсь, что каждый сможет что-то получить после прочтения.

1. Представьте Redis

Прежде всего, вы должны зайти на официальный сайт, чтобы увидеть, как официальный представитель представляет Redis.Redis.IO/topics/int R…

Если вы похожи на меня, ваш английский может быть не очень хорошим, и вы можете плохо понимать. Ничего страшного, наш браузер Chrome можно переключить на китайский язык, китайский язык наш родной, так что давления точно нет. Эмм...

Прочитав ее, я обнаружил, что китайский именно такой.

Много невиданных технологий: lua (скрипт Lua), replication (репликация), Redis Sentinel (сентри), Redis Cluster (кластер Redis), конечно, у нас будут и понятные технологии: транзакции (транзакции), разные уровни на- сохранение диска (сохранение данных), вытеснение LRU (механизм устранения LRU).

По крайней мере, первое предложение официального введения в Redis должно быть понятным: «Redis — это открытый исходный код (под лицензией BSD),in-memory data structure store, used as a database,cache and message broker."

Redis с открытым исходным кодом,Хранение структуры данных в памяти, которые можно использовать в базах данных,тайник, ПО промежуточного слоя сообщений.

• Из официального объяснения мы можем знать, что Redis основан на памяти и поддерживает несколько структур данных.
• С эмпирической точки зрения мы можем знать, что Redis часто используется для кэширования.

Насколько я лично считаю: чтобы изучить новую технологию, сначала усвойте общее знание (идею) технологии, а затем вычтите детали, чтобы легче было учиться. Итак, давайте начнем с «памяти», «структуры данных» и «кеша», чтобы начать работу с Redis.

1.1 Зачем использовать Redis?

Как видно из вышеизложенного: Redisна основе памяти, часто используется длятайникэто технология, и то, как Redis ее хранит,key-valueформа.

Мы можем обнаружить, что это не функция контейнера Java Map, так зачем нам Redis?

• Java-реализация картылокальный кеш, если имеется несколько экземпляров (машин), для каждого экземпляра требуетсясоответствующийсохранить кеш, кешнепоследовательный
• Redis реализованРаспределенный кеш, если имеется несколько экземпляров (машин), каждый экземпляробщийкеш, тайникс последовательностью.
• Карта реализована на JavaНе профессиональныйДля кеширования памяти JVM слишком много и ее легко повесить. Обычно он используется для контейнеров для хранения временных данных, а кэшированные данные заканчиваются, когда JVM уничтожается. Структура данных, хранимая Map, механизм истечения срока действия кеша и т. д. должны быть написаны самими программистами.
• Редис этоПрофессиональныйДля кэширования можно использовать десятки G памяти для кэширования. Redis обычно используется в качестве кэша, а кэшированные данные можно сохранить на жестком диске и восстановить после перезапуска Redis. Нативно предоставляет богатые структуры данных, механизмы истечения срока действия кэша и другие простые и удобные функции.

Использованная литература:

• Зачем использовать Redis вместо карты для кэширования?сегмент fault.com/please/101000000…

1.2 Зачем использовать кеш?

Если у нашего веб-сайта есть проблемы с производительностью (медленное время доступа), как правило, это связано сБаза данных не выдерживает. Поскольку общие операции чтения и записи базы данных должны проходить черездиск, а скорость диска можно сказать довольно медленная (относительно памяти)

• Популярная наука: пусть ЦП скажет вам, насколько медленны ваш жесткий диск и сетьzhuanlan.zhihu.com/p/24726196

Если вы изучали Mybaits и Hibernate, то можете знать, что у них есть такие функции, как кеш первого уровня и кеш второго уровня (в конце концов, локальный кеш). Цель состоит в том, чтобы:Не нужно проверять базу данных каждый раз, когда вы читаете.

С кешем наш доступ становится таким:

Во-вторых, структура данных Redis.

В этой статье не будет описано, как использовать команду, в частности, как использовать запрашиваемый API.

• Redis Command Reference:doc.redisfans.com/
• попробуйте Redis (без установки Redis команды Redis могут работать):try.redis.io/

Redis поддерживает богатые структуры данных,Обычно используетсяЕсть строка, список, хэш, набор, набор сортировок. Изучение этих структур данных имеет основополагающее значение для использования Redis!

«Redis написан на ANSI C» -> Redis написан на языке C

В первую очередь необходимо объявить, что хранилище Redis основано наkey-valueв виде. Ключ в Redis должен быть строкой, а значение может использоваться обычно, например, строка, список, хэш, набор и набор сортировок.

Но стоит отметить: Redis нене используется напрямуюЭти структуры данных реализуютkey-valueбаза данных, нона основеЭти структуры данных создаютсистема объектов.

• Проще говоря: Redis использует объекты для представления ключей и значений в базе данных. Каждый раз, когда мы создаем новую пару ключ-значение в базе данных Redis,Будет создано как минимум два объекта. Один из них — ключевой объект, а другой — объект-значение.

Каждый объект в Redis представлен структурой redisObject:

typedef struct redisObject{
	
	// 对象的类型
	unsigned type 4:;

	// 对象的编码格式
	unsigned encoding:4;

	// 指向底层实现数据结构的指针
	void * ptr;

	//.....


}robj;

Проще говоря, Redis правkey-valueИнкапсулированный в объект ключ является объектом, и значение также является объектом. Каждый объект имеет тип (тип), кодирование (кодирование), ptr (указатель на базовую структуру данных) для представления.

Позвольте мне рассказать об общих типах данных нашего Redis: строка, список, хэш, набор, набор сортировок. Какова их основная структура данных?

2.1SDS Простая динамическая строка

Простая динамическая строка (SDS)

Строки в Redis и строки в языке Cнемного другой.

Redis использует структуру sdshdr для представления значения SDS:

struct sdshdr{

	// 字节数组，用于保存字符串
	char buf[];

	// 记录buf数组中已使用的字节数量，也是字符串的长度
	int len;

	// 记录buf数组未使用的字节数量
	int free;
}

пример:

2.1.1 Преимущества использования SDS

Сравнение строкового представления между SDS и C

1. Длина строки записывается атрибутом len в структуре данных sdshdr. ТакПри получении длины строки временная сложность составляет всего O (1).
2. SDS не будет переполняться, если при изменении SDS недостаточно места. Он сначала расширит пространство, а потом модифицирует его! (Внутренний механизм динамического расширения).
3. SDS можетУменьшить количество выделений памяти(Механизм предварительного распределения пространства). При расширении места, помимо выделения места, необходимого для модификации, также выделяется дополнительное свободное место (свободный атрибут).
4. Паспорт безопасностибинарный сейф, все SDS API будут обрабатывать данные, хранящиеся в массиве buf, SDS в двоичном виде.

2.2 Связанный список

Мы не будем незнакомы со связанными списками. Во время учебы в колледже я, должно быть, читал курсы по структурам данных и алгоритмам, а также связные списки. В Java базовой структурой данных контейнера Linkedxxx также является связанный список +[xxx]. Посмотрим, как реализован связанный список в Redis:

Используйте структуру listNode для представления каждого узла:

typedef strcut listNode{

    //前置节点
    strcut listNode  *pre;

    //后置节点
    strcut listNode  *pre;

    //节点的值
    void  *value;

}listNode

Использование listNode может сформировать связанный список в RedisИспользуйте структуру списка для хранения связанного списка:

typedef struct list{

    //表头结点
    listNode  *head;

    //表尾节点
    listNode  *tail;

    //链表长度
    unsigned long len;

    //节点值复制函数
    void *(*dup) (viod *ptr);

    //节点值释放函数
    void  (*free) (viod *ptr);

    //节点值对比函数
    int (*match) (void *ptr,void *key);

}list

Конкретная структура показана на рисунке:

2.2.1 Особенности списка Redis

Связанный список Redis имеет следующие характеристики:

• Ациклический двусвязный список
• Временная сложность получения начального указателя, хвостового указателя и длины узла связанного списка составляет O(1).
• использование связанного спискаvoid *Указатель для сохранения значения узла, может сохранять различные типы значений.

2.3 Хэш-таблица

Отказ от ответственности: в «Проектировании и реализации Redis» есть понятие «словарь». Лично я считаю, что проще назвать его хеш-таблицей. С точки зрения кода: «словарь» — это просто еще один уровень абстракции на основе хеш-таблицы.

В РЕДИС,key-valueБазовая структура данных реализована в виде хеш-таблицы. Мы также не новички в хеш-таблицах. В Java хеш-таблица на самом деле строится в виде массива + связанный список. Давайте посмотрим, как устроена хэш-таблица Redis.

В Redis хеш-таблицы определяются с помощью структуры dicttht:

	typedef struct dictht{
	    
	    //哈希表数组
	    dictEntry **table;  
	
	    //哈希表大小
	    unsigned long size;    
	
	    //哈希表大小掩码，用于计算索引值
	    //总是等于size-1
	    unsigned long sizemark;     
	
	    //哈希表已有节点数量
	    unsigned long used;
	     
	}dictht

Продолжим писать и посмотрим, как реализованы узлы хеш-таблицы:

	typedef struct dictEntry {
	    
	    //键
	    void *key;
	
	    //值
	    union {
	        void *value;
	        uint64_tu64;
	        int64_ts64;
	    }v;    
	
	    //指向下个哈希节点，组成链表
	    struct dictEntry *next;
	
	}dictEntry;

Со структурной точки зрения мы можем обнаружить, что хэш-таблица, реализованная Redis, и таблица, реализованная в Java, отличаются друг от друга.похожийиз. Просто в Redis есть еще несколько атрибутов для записи часто используемых значений: sizemark (маска), used (количество существующих узлов), size (размер).

Аналогично, Redis для лучшего эксплуатации слоя UP избаковки от перепаковки хэш (см. Приведенный выше список REDIS) с использованием структуры Dict, представленной:

typedef struct dict {

    //类型特定函数
    dictType *type;

    //私有数据
    void *privdata;
  
    //哈希表
    dictht ht[2];

    //rehash索引
    //当rehash不进行时，值为-1
    int rehashidx;  

}dict;


//-----------------------------------

typedef struct dictType{

    //计算哈希值的函数
    unsigned int (*hashFunction)(const void * key);

    //复制键的函数
    void *(*keyDup)(void *private, const void *key);
 
    //复制值得函数
    void *(*valDup)(void *private, const void *obj);  

    //对比键的函数
    int (*keyCompare)(void *privdata , const void *key1, const void *key2)

    //销毁键的函数
    void (*keyDestructor)(void *private, void *key);
 
    //销毁值的函数
    void (*valDestructor)(void *private, void *obj);  

}dictType

Итак, в итоге мы можем обнаружить, что конечная структура данных хеш-таблицы, реализованная Redis, выглядит так:

Из реализации кода и примера диаграммы мы можем обнаружить, чтоВ Redis есть две хеш-таблицы.:

• ht[0]: используется для храненияреальностьизkey-vlaueданные
• ht[1]: дляРасширение (перефразирование)

Алгоритм хеширования и коллизия хэшей в Redis аналогичны реализованным в Java.разницаэто:

• Когда хэши Redis конфликтуют: в связанный список добавляется новый узелзаголовок.
• После JDK1.8 Java добавляет новый узел в связанный список при возникновении коллизии хэшей.нижний колонтитул.

2.3.1 Процесс перефразирования

Давайте подробно поговорим о том, как Redis рехэширует, потому что из вышеизложенного мы ясно видим,Redis использует хэш-таблицу специально для повторного хеширования.. Это отличается от одноразового прямого перефразирования в Java.

При расширении или сжатии хеш-таблицы процесс reash выполняется не за один раз, апрогрессивныйзавершенный.

Причины, по которым Redis прогрессивен в перефразировании:Если объем данных слишком велик, однократный повторный хэш будет иметь огромный объем вычислений, что, вероятно, приведет к остановке обслуживания сервера на определенный период времени..

Redis конкретно делает это при перефразировании:

• (1: Сохраните в словаре переменную индексного счетчика rehashidx и установите для нее значение 0, что указывает на начало повторного хеширования.
• (2: Каждый раз, когда словарь добавляется, запрашивается, удаляется и обновляется во время перефразирования,Помимо выполнения указанной команды; также преобразует значение по индексу rehashidx в ht[0]перефразировать в ht[1], rehashidx+1 после завершения операции.
• (3: Словарная операция выполняется постоянно, в какой-то момент времени все значения ключа завершаются, в это времяУстановите для rehashidx значение -1, указывая на то, что перефразирование завершено.
• (4: В процессе прогрессивного повторного хеширования словарь будет использовать две хеш-таблицы ht[0] и ht[1] одновременно, и все операции обновления, удаления и поиска также будут выполняться в этих двух хэш-таблицах. Для например, чтобы найти один ключ,Сервер сначала будет искать ht[0], если его нет, то искать ht[1], и так далее. Также при выполненииДобавить действиеВ то время новое значение ключевое значениеВсегда сохраняйте до HT [1], и не выполняйте никаких операций над ht[0], чтобы количество пар ключ-значение в ht[0] только уменьшалось и не увеличивалось до тех пор, пока таблица не станет пустой.

2.4 Список переходов (список кораблей)

Список пропусков — это реализация sortedset(аккуратныйКоллекция) одна из базовых структур данных!

Таблицы переходов могут быть необычными для большинства людей. Я нашел хорошую статью о таблицах переходов, когда учился. Я предлагаю вам сначала прочитать следующее, а затем продолжить чтение:

• Комический алгоритм: что такое таблица прыжков?blog.jobbole.com/111731/

Реализация таблицы пропуска Redis состоит из двух структур: zskiplist и zskiplistNode. вzskiplist сохраняет информацию о списке пропуска(заголовок, нижний колонтитул, длина),zskiplistNode представляет узел списка пропуска.

По соглашению, давайте взглянем на структуру узла списка пропуска zskiplistNode:

typeof struct zskiplistNode {
        // 后退指针
        struct zskiplistNode *backward;
        // 分值
        double score;
        // 成员对象
        robj *obj;
        // 层
        struct zskiplistLevel {
                // 前进指针
                struct zskiplistNode *forward;
                // 跨度
                unsigned int span;
        } level[];
} zskiplistNode;

Пример графика объекта zskiplistNode (с узлами разной высоты слоя):

Примерная схема выглядит следующим образом:

Структура zskiplist выглядит следующим образом:

typeof struct zskiplist {
        // 表头节点，表尾节点
        struct skiplistNode *header,*tail;
        // 表中节点数量
        unsigned long length;
        // 表中最大层数
        int level;
} zskiplist;

Наконец, примерная диаграмма всей нашей таблицы переходов выглядит следующим образом:

2.5 Целочисленный набор (intset)

Коллекция целых чисел является одним из основных структур данных набора. Когда набор (коллекция)Содержит только целочисленные элементы,ине много элементов, Redis будет использовать целочисленный набор (intset) в качестве базовой реализации набора (set).

Набор целых чисел (intset) гарантирует, что элементынет повторения, и являетсяаккуратный(отсортировано от меньшего к большему), структура intset такова:

typeof struct intset {
        // 编码方式
        unit32_t encoding;
        // 集合包含的元素数量
        unit32_t lenght;
        // 保存元素的数组
        int8_t contents[];
} intset;

пример схемы inset:

Объяснение: Хотя структура intset объявляет свойство содержимого как массив типа int8_t, в действительности массив содержимого не содержит никаких значений типа int8_t.Истинный тип массива содержимого зависит от значения свойства encoding:

• INTSET_ENC_INT16
• INTSET_ENC_INT32
• INTSET_ENC_INT64

Из названия формата кодировки мы можем знать, что диапазон чисел, которые могут храниться в кодировках 16, 32 и 64, различается. 16 явно меньше, а 64 больше всего.

Если он изначально INTSET_ENC_INT16 кодировка, и вы хотите сохранить целочисленное значение, больше, чем intset_enc_int16, кодировка может хранить, вы должны заканчивать его в это время.Обновить(Обновление с 16 до 32 или 64). Действуйте следующим образом:

• 1) Расширьте пространство базового массива целочисленной коллекции в соответствии с новым типом элемента и выделите место для нового элемента.
• 2) Преобразуйте все существующие элементы базового массива в тот же тип, что и новый элемент, и поместите элементы с преобразованным типом в правильное положение.Это необходимо для поддержания упорядоченного характера базового массива.
• 3) Добавьте новый элемент в базовый массив.

Кстати:Поддерживаются только операции обновления, а операции понижения версии не поддерживаются..

2.6 Список сжатия (ziplist)

Сжатый список (ziplist) — одна из базовых реализаций списка и хэша. Если каждый список представляет собой небольшое целочисленное значение или относительно короткую строку, в качестве базовой реализации списка используется ziplist.

Ziplist (зиплист) разработан Redis для экономии памяти и состоит из рядаСпециально закодированный непрерывный блок памятисостоит изпоследовательныйструктура данных.

Структура списка сжатия показана, например:

Давайте посмотрим на структурную схему узла:

Сжать список из узла нижнего колонтитулаОбход в обратном порядке, сначала указатель указывает на хвостовой узел через смещение zltail, а затем указывает наДлина предыдущего узла, записанного узлом, по очереди перемещается вперед для доступа ко всему сжатому списку..

3. Объекты структур данных в Redis

Снова глядя на эту картинку, как вы думаете, легко ли ее понять?

3.1 Строковые объекты

На приведенном выше рисунке мы знаем, что существует три типа строк.Формат кодирования:

• int: целое число, целочисленное значение может быть представлено с использованием длинного типа
  • Если он плавает, затем используйте Embster или Raw Coding. С определенной длиной которого зависит от количества
• embstr: строковое значение, длина этого строкового значения меньше 39 байт.
• RAW: длина строковые значения, строковые значения превышают 39 байтов

embstr и сырьеразница:

• Количество раз сырьевых распределяемых и памяти FreeS - это дважды, а embstr
• embstr закодированные данные, хранящиеся внепрерывныйв памяти

между кодамиконвертировать:

• Если тип int существуетбольше не целочисленное значение, он будет преобразован из int в raw
• embstr доступен только для чтения и при изменении преобразуется из embstr в raw.

3.2 Список объектов

На приведенном выше рисунке мы знаем, что существует два типа списка.Формат кодирования:

• ziplist: все строковые элементы имеют длину менее 64 байт.&&Общее количество 512
• связанный список: длина строкового элемента превышает 64 байта.||Общее количество больше 512

структура закодированного списка ziplist:

	redis > RPUSH numbers 1 "three" 5
	(integer) 3 

Структура закодированного списка Linkedlist:

между кодамиКонвертировать:

• Ziplist изначально закодирован, если сохраненный размер данных слишком большой или слишком много элементов преобразуется в кодированный LinkedList.

3.3 Хэш (хэх) объект

На приведенном выше рисунке мы знаем, что есть два типа хеша.Формат кодирования:

• ziplist: длина строки ключа и значения меньше 64 байт.&&Общее количество пар ключ-значение меньше 512.
• хеш-таблица: длина строки ключа и значения превышает 64 байта||Общее количество пар ключ-значение превышает 512.

хэш-структура, закодированная в ziplist:

Хеш-структура с кодировкой Hashtable:

между кодамиКонвертировать:

• Первоначально закодированный ziplist, если длина сохраненных данных слишком велика или количество элементов слишком велико, они будут преобразованы в кодировку хеш-таблицы.

3.4 Коллекция (установка) объектов

На приведенном выше рисунке мы знаем, что существует два типа набораФормат кодирования:

• intset: все сохраненные элементы являются целыми числами&&Общее количество меньше 512
• hashtable: сохраненный элемент не является целым числом||Общее количество больше 512

Структура коллекции в кодировке Intset:

Структура коллекции с кодировкой Hashtable:

между кодамиКонвертировать:

• Первоначально закодированный с помощью intset, если сохраненные данные не являются целочисленным значением или количество элементов больше 512, они будут преобразованы в кодировку хеш-таблицы.

3.5 Сортировка объектов

На приведенном выше рисунке мы знаем, что существует два типа набораФормат кодирования:

• ziplist: длина элемента меньше 64&&Общее количество меньше 128
• skiplist: длина элемента больше 64||Общее количество больше 128

ziplist кодирует упорядоченную структуру набора:

Упорядоченная структура коллекции, закодированная с помощью списка пропуска:

Сортированный набор (sortset) объектИспользуйте список пропусков и хеш-таблицу одновременно для достижения:

• Временная сложность списка пропусков может быть достигнута до O (logn), а временная сложность проверки значения оценки в соответствии с членом составляет O (1).

между кодамиКонвертировать:

• Первоначально закодированный ziplist, если длина сохраненных данных больше 64 или количество элементов больше 128, они будут преобразованы в кодировку Skiplist.

3.6 Некоторые подробности об объектах Redis

• (1: Когда сервер выполняет определенные команды, онсначала проверьте тип данного ключаМожет выполнить указанную команду.
  • Например, наша структура данных — sortset, но вы используете команду list. Это неправильно, сервер проверит, какая у нас структура данных, прежде чем выполнять команду дальше
• (2: объектная система Redis поставляется сподсчет ссылокосуществленныймеханизм восстановления памяти.
  • Когда объект больше не используется, память, занятая объектом, будет освобождена.
• (3: Redis будет делиться строковыми объектами со значениями от 0 до 9999
• (4: ОбъектЗапишет последний раз, когда к нему обращались, это время можно использовать для расчета времени простоя объекта.

Наконец

В этой статье в основном рассказывается о том, как REDIS обычно использует структуру данных, и какова основная структура этих структур данных. В целом это не будет слишком сложно, потому что эти структуры данных мы коснулись в процессе изучения «Проектирование и реализация Redis». Эта книга также проста для понимания.

Что касается того, какие структуры данных мы выбираем в качестве хранилища, когда мы их используем, мы можем просто посмотреть:

• строка --> простойkey-value
• список --> упорядоченный список (нижний слой представляет собой двусвязный список) --> может быть простой очередью
• set --> неупорядоченный список (дедупликация) --> предоставить серию команд для пересечения, объединения и различия
• хэш --> хеш-таблица --> хранить структурированные данные
• sortset --> Отображение упорядоченного набора (член-оценка) --> Ранжирующий список

Если у вас есть лучший способ понять или в статье есть ошибки, пожалуйста, не стесняйтесь оставлять сообщение в области комментариев, чтобы мы могли учиться друг у друга~~~

Справочный блог:

• Краткое руководство по Redisбридж для by.cai/2018/05/19/…
• Дядя Пятидесятница учит вас заглянуть в тайну Rediszhuanlan.zhihu.com/p/34762100

Использованная литература:

• «Проектирование и реализация Redis»
• "Редис бой"

ОдинПридерживайтесь общедоступной учетной записи оригинальной технологии Java: Java3y, приветствую всех, чтобы обратить внимание

Навигация по оригинальной технической статье:

• Навигация по каталогу статей (карта мозга + обширные видеоресурсы):GitHub.com/Zhongf UC очень…