Memcached와 redis는 최근 몇 년 동안 가장 많이 사용되는 캐시 서버로 모두가 익숙할 것이라고 생각합니다. 2년 전 제가 학교에 다닐 때 주요 소스 코드를 읽었는데, 지금은 개인적인 관점에서 구현 방법을 간략하게 비교하기 위해 메모를 작성하고 있습니다. 이해하고 수정을 환영합니다.
본 글에 사용된 대부분의 아키텍처 사진은 인터넷에서 가져온 것입니다. 일부 사진은 글에서 지적한 최신 구현과 다릅니다.
소프트웨어의 소스 코드를 읽으려면 먼저 해당 소프트웨어가 어떤 용도로 사용되는지 이해해야 합니다. memcached와 redis는 무엇을 위해 사용됩니까? 우리 모두 알고 있듯이 데이터는 일반적으로 데이터베이스에 저장되지만 데이터를 쿼리하는 속도는 상대적으로 느립니다. 특히 사용자가 많은 경우 쿼리를 자주 수행하면 시간이 많이 걸립니다. 무엇을 해야 할까요? 신속하게 쿼리할 수 있도록 데이터가 어디에 배치되어 있습니까? 그건 기억 속에 있을 거에요. Memcached와 redis는 데이터를 메모리에 저장하고 키-값 방식으로 쿼리하므로 효율성이 크게 향상됩니다. 따라서 일반적으로 자주 사용되는 데이터를 캐시하는 캐시 서버로 사용되며, 쿼리가 필요할 때 직접 가져오므로 데이터베이스 쿼리 수를 줄이고 쿼리 효율성을 향상시킵니다.
Memcached와 Redis는 어떻게 서비스를 제공하나요? 필요한 경우 데몬 프로세스로 전환할 수 있습니다. 따라서 사용자 프로세스가 memcached 및 redis 서비스를 사용하려면 프로세스 간 통신이 필요합니다. 사용자 프로세스, memcached 및 redis가 반드시 동일한 시스템에 있을 필요는 없다는 점을 고려하면 네트워크 간 통신이 지원되어야 합니다. 따라서 memcached와 redis 자체는 네트워크 서버이며 사용자 프로세스는 이들과 함께 네트워크를 통해 데이터를 전송합니다. 가장 간단하고 일반적으로 사용되는 것은 tcp 연결을 사용하는 것입니다. 또한 memcached와 redis는 모두 udp 프로토콜을 지원합니다. 그리고 사용자 프로세스가 memcached 및 redis와 동일한 시스템에 있는 경우 Unix 도메인 소켓 통신도 사용할 수 있습니다.
구현 방법부터 시작해 보겠습니다. 먼저 이벤트 모델을 살펴보겠습니다.
epoll이 나온 이후 거의 모든 네트워크 서버는 select와 poll을 포기하고 epoll로 대체했습니다. 선택 및 폴링에 대한 지원도 제공한다는 점을 제외하면 Redis에서도 마찬가지입니다. 사용할 항목을 구성할 수 있지만 일반적으로 epoll이 사용됩니다. 또한 BSD의 경우 kqueue 사용도 지원됩니다. Memcached는 libevent를 기반으로 하고 있지만 libevent의 하위 레이어도 epoll을 사용하고 있으므로 모두 epoll을 사용하고 있다고 볼 수 있다. 여기서는 epoll의 특징을 소개하지 않겠습니다. 온라인에는 소개 글이 많이 있습니다.
모두 이벤트 루프에 epoll을 사용하지만 redis는 단일 스레드 서버입니다(redis도 다중 스레드이지만 기본 스레드를 제외하고 다른 스레드에는 이벤트 루프가 없고 일부 백그라운드 저장소 작업만 수행함). 반면 memcached 멀티 스레드입니다. Redis의 이벤트 모델은 단 하나의 이벤트 루프와 간단한 리액터 구현으로 매우 간단합니다. 그러나 redis 이벤트 모델에는 epoll이 fd용이고 반환되는 준비 이벤트는 fd라는 것을 알고 있습니다. redis의 fd는 서버와 클라이언트를 연결하는 소켓의 fd입니다. 처리하려면 이 fd를 기반으로 해야 합니다. 특정 클라이언트 정보를 찾는 방법은 무엇입니까? 일반적인 처리 방식은 레드-블랙 트리(red-black tree)를 이용해 fd와 클라이언트 정보를 저장하고, fd를 통해 검색하는 것이며 효율은 lgn이다. 그러나 redis는 특별합니다. redis 클라이언트 수의 상한선을 설정할 수 있습니다. 즉, redis가 여는 fd의 상한선을 동시에 알 수 있습니다. (fd는 닫힌 후에만 복원할 수 있습니다.) 따라서 redis는 배열을 사용하고 배열의 첨자로 fd를 사용합니다. , 클라이언트 정보는 fd를 통해 직접 찾을 수 있습니다. 검색 효율성은 O(1)이며, 이는 또한 레드-블랙 트리의 구현을 제거합니다(한번은 C를 사용하여 네트워크 서버를 작성했습니다. fd와 connect 사이의 해당 관계가 있었고 레드-블랙 트리를 직접 작성하고 싶지 않았으며 STL에서 세트를 사용하여 프로젝트가 C++가 되었습니다. 결국 프로젝트는 g++를 사용하여 컴파일되었습니다. 말 안 해?) 분명히 이 방법은 연결 수의 상한이 결정되어 있고 너무 크지 않은 네트워크 서버에만 사용할 수 있습니다. nginx와 같은 HTTP 서버는 자체 레드-블랙 트리를 작성하는 데 적합하지 않습니다.
Memcached는 마스터-작업자 방법을 사용하는 다중 스레드입니다. 기본 스레드는 포트를 수신하고 연결을 설정한 다음 이를 각 작업자 스레드에 순차적으로 할당합니다. 각 슬레이브 스레드에는 다양한 클라이언트에 서비스를 제공하는 이벤트 루프가 있습니다. 파이프라인 통신은 마스터 스레드와 작업자 스레드 간에 사용됩니다. 각 작업자 스레드는 파이프를 생성한 다음 쓰기 끝과 읽기 끝을 저장하고 읽기 끝을 이벤트 루프에 추가하여 읽을 수 있는 이벤트를 수신합니다. 동시에 각 슬레이브 스레드에는 준비된 연결 큐가 있습니다. 메인 스레드가 연결되면 연결된 항목을 이 큐에 넣은 다음 스레드 파이프의 쓰기 끝에 연결 명령을 작성하여 파이프가 추가됩니다. 이벤트 루프 리더는 준비 상태가 되며 스레드에서 명령을 읽고 명령을 구문 분석하여 연결이 있는지 확인한 다음 자체 준비 대기열로 이동하여 연결을 가져오고 처리합니다. 멀티스레딩의 장점은 멀티코어의 장점을 최대한 살릴 수 있다는 점이지만, 프로그램 작성이 좀 더 번거롭습니다. Memcached에는 스레드 동기화를 위한 다양한 잠금 및 조건 변수가 있습니다.
memcached와 redis의 핵심 업무는 메모리에서 데이터를 운용하는 것이고, 메모리 관리는 당연히 핵심 내용이다.
먼저 메모리를 할당하는 방법을 살펴보세요. Memcached에는 자체 메모리 풀이 있습니다. 즉, 큰 메모리 블록을 미리 할당한 다음 메모리 풀에서 메모리를 할당합니다. 이는 메모리 할당 수를 줄이고 효율성을 향상시킬 수 있습니다. 그러나 각 메모리 풀의 관리 방법은 특정 상황에 따라 다릅니다. Redis에는 자체 메모리 풀이 없지만 사용될 때 직접 할당합니다. 즉, 필요할 때 할당합니다. 메모리 관리는 커널에 맡겨져 있으며 가져오기 및 해제만 담당합니다(redis는 단일 스레드이며 이를 수행합니다. 자체 메모리 풀이 없습니다. 구현이 너무 단순하다고 느껴지나요? 데이터베이스 모듈에 중점을 두기 때문인가요? 그러나 redis는 glibc의 malloc을 대체하기 위해 tcmalloc 사용을 지원합니다. 전자는 Google 제품이며 glibc의 malloc보다 빠릅니다.
Redis에는 자체 메모리 풀이 없기 때문에 메모리 적용 및 해제 관리가 훨씬 간단합니다. 단지 malloc과 free만 직접 수행할 수 있어 매우 편리합니다. Memcached는 메모리 풀을 지원하므로 메모리 풀에서 메모리 응용프로그램을 얻고, 메모리 풀에 free도 반환되므로 추가 관리 작업이 많이 필요하고 구현하기가 매우 번거롭습니다. 자세한 내용은 나중에 설명하겠습니다. memcached의 슬래브 메커니즘을 분석합니다.
다음으로 핵심 콘텐츠인 각 데이터베이스의 구현을 살펴보겠습니다.
Memcached는 키-값만 지원합니다. 즉, 하나의 키만 하나의 값에 대응할 수 있습니다. 해당 데이터는 메모리에 키-값 쌍으로 저장되며 슬랩 메커니즘을 사용합니다.
먼저 memcached가 데이터를 저장하는 방법, 즉 키-값 쌍을 저장하는 방법을 살펴보겠습니다. 아래 그림에 표시된 것처럼 각 키-값 쌍은 관련 속성과 키 및 값 값을 포함하여 항목 구조에 저장됩니다.
항목은 키-값 쌍을 저장합니다. 항목이 많은 경우 특정 항목을 찾는 방법이 문제입니다. 따라서 memcached는 항목을 빠르게 찾는 데 사용되는 해시 테이블을 유지 관리합니다. 해시 테이블은 키 충돌을 해결하기 위해 오픈 체인 방식(redis와 동일)을 적용합니다. 각 해시 테이블 버킷은 연결된 목록을 저장합니다. 위 그림에서 볼 수 있듯이 h_next는 항목의 포인터입니다. 버킷에 있는 연결 목록의 다음 노드입니다. 해시 테이블은 확장(항목 수가 버킷 수의 1.5개 이상인 경우 확장)을 지원합니다. 기본_hashtable과 old_hashtable이 있지만 확장 시에는 old_hashtable=primary_hashtable이 설정됩니다. Primary_hashtable을 새로 적용한 해시 테이블로 설정(버킷 수에 2를 곱함)한 후 old_hashtable의 데이터를 새 해시 테이블로 순차적으로 이동하고 변수expand_bucket을 사용하여 버킷 수를 기록합니다. 이동이 완료되면 원래 old_hashtable을 해제합니다(Redis에도 이동된 두 개의 해시 테이블이 있지만 이는 백그라운드 스레드에 의해 수행되지 않고 한 번에 하나의 버킷으로 이동됩니다). 확장 작업은 백그라운드 확장 스레드에 의해 완료됩니다. 확장이 필요한 경우 조건 변수를 사용하여 확장이 완료된 후 확장을 기다리는 조건 변수를 차단합니다. 이러한 방식으로 확장할 때 항목이 Primary_hashtable 또는 old_hashtable에서 발견될 수 있습니다. 버킷의 위치와 Expand_bucket의 크기를 비교하여 해당 항목이 어느 테이블에 있는지 확인해야 합니다.
아이템은 어디서 할당되나요? 슬래브에서. 아래 그림과 같이 memcached에는 slab을 관리하는 slabclass가 많이 있는데, 각 slab은 실제로는 트렁크의 집합체이고, 각 트렁크에는 항목이 할당되어 있다. 슬라브의 트렁크 크기는 동일합니다. 다른 슬라브의 경우 트렁크 크기가 비례하여 증가합니다. 새 항목을 신청해야 하는 경우 해당 크기에 따라 트렁크를 선택합니다. 그것보다 더 크다. 이러한 방식으로 다양한 크기의 항목이 다양한 슬래브에 할당되고 다양한 슬래브 클래스에서 관리됩니다. 이 방법의 단점은 그림 2와 같이 트렁크가 해당 항목보다 클 수 있기 때문에 일부 메모리가 낭비된다는 점입니다. 100B 항목을 할당할 때 112 트렁크를 선택하면 12B의 낭비가 발생하게 되며 이로 인해 메모리 리소스의 일부가 사용되지 않습니다.
위 그림과 같이 전체 구조는 slabclass가 slab을 관리하는데, slabclass에는 여러 개의 slab을 관리할 수 있는 slab_list가 있습니다. slabclass에는 해제된(실제로는 사용 가능한 메모리가 아니라 더 이상 사용되지 않는) 할당되지 않은 항목을 저장하는 포인터 슬롯이 있습니다. 현재 슬래브에 항목을 할당할 때 항목이 할당 해제되었거나 해제되었는지 여부에 관계없이 슬롯에 직접 액세스할 수 있습니다.
그런 다음 각 slabclass는 연결된 목록의 헤드 노드와 꼬리 노드를 각각 저장하는 헤드 배열과 테일 배열이 있는 연결된 목록에 해당합니다. Linked List의 노드는 변경된 slabclass에 의해 할당된 항목이며, 새로 할당된 항목은 Linked List에서 더 뒤쪽에 있는 항목이 오랫동안 사용되지 않았음을 의미합니다. slabclass의 메모리가 부족하여 만료된 일부 항목을 삭제해야 하는 경우 연결 목록 끝에서 삭제할 수 있습니다. 예, 이 연결 목록은 LRU를 구현하도록 설계되었습니다. 연결된 목록의 쿼리는 O(n)이므로 이것에만 의존하는 것만으로는 충분하지 않으므로 항목을 찾을 때 이미 할당된 항목이 모두 해시 테이블에 있으므로 사용 가능합니다. 해시는 항목을 찾는 데 사용되며 연결 목록은 가장 최근에 사용된 항목 순서를 저장할 수 있으며 이는 lru의 표준 구현 방법이기도 합니다.
새로운 아이템을 할당해야 할 때마다 slabclass에 해당하는 연결리스트를 찾아 맨 끝부터 앞쪽까지 검색해 아이템이 만료됐는지 확인한다. 만료된 아이템을 바로 새 아이템으로 사용한다. 만료되지 않은 경우 슬래브에서 트렁크를 할당해야 합니다. 슬래브가 모두 사용된 경우 슬래브 클래스에 슬래브를 추가해야 합니다.
Memcached는 만료 시간, 즉 만료 시간 설정을 지원하지만 내부적으로 데이터가 만료되었는지 정기적으로 확인하지는 않습니다. 대신 클라이언트 프로세스가 해당 데이터를 사용할 때 memcached는 만료 시간을 확인하고 만료되면 이를 수행합니다. 직접 오류를 반환합니다. 이것의 장점은 만료 시간을 확인하기 위해 추가 CPU가 필요하지 않다는 점입니다. 단점은 만료된 데이터가 오랫동안 사용되지 않을 수 있으며 해제되지 않고 메모리를 점유하지 않는다는 것입니다.
Memcached는 멀티스레드이고 하나의 데이터베이스만 유지하므로 동일한 데이터에 대해 여러 클라이언트 프로세스가 작동할 수 있어 문제가 발생할 수 있습니다. 예를 들어, A가 데이터를 변경했고, B도 데이터를 변경한 경우, A의 작업이 덮어쓰기가 되어 A의 태스크 데이터의 현재 상태가 자신이 변경한 후의 값이라는 것을 A가 알지 못하므로 문제가 발생할 수 있습니다. . 이 문제를 해결하기 위해 memcached는 CAS 프로토콜을 사용합니다. 간단히 말해서 항목은 업데이트(데이터 값이 수정됨)될 때마다 버전 번호를 표시하기 위해 64비트 unsigned int 값을 저장합니다. 그러면 매번 데이터가 변경됩니다. 클라이언트 프로세스에서 보낸 버전 번호와 서버 측 항목의 버전 번호가 일치하는지 비교해야 합니다. 작업을 변경하지 않으면 더티 데이터가 표시됩니다.
위는 memcached가 키-값 데이터베이스를 구현하는 방법에 대한 소개입니다.
우선, redis 데이터베이스는 문자열 저장만 지원하는 memcached와 달리 string, list, set, sorted set, hash table의 5가지 데이터 구조를 지원하기 때문에 더 강력합니다. 예를 들어, 사람의 정보를 저장하려면 해시 테이블을 사용하고, 사람의 이름을 키로 사용한 다음, super라는 이름을 나이 24로 하면 됩니다. 키와 이름을 통해 슈퍼라는 이름을 얻을 수도 있고, 키와 나이를 통해 이름을 얻을 수도 있고, 24세를 얻을 수 있다. 이런 방식으로 나이만 얻으면 그 사람의 전체 정보를 검색한 다음 내부에서 나이를 찾을 필요 없이 직접 나이를 얻으면 효율적이고 편리합니다.
이러한 데이터 구조를 구현하기 위해 redis는 아래와 같이 추상 객체 redis 객체를 정의합니다. 각 객체에는 문자열, 연결 목록, 집합, 순서 집합, 해시 테이블의 총 5가지 유형이 있습니다. 동시에 효율성을 높이기 위해 redis는 각 유형에 대해 여러 구현 방법을 준비하고 특정 시나리오에 따라 적절한 구현 방법을 선택합니다. 그런 다음 객체의 LRU, 즉 마지막으로 액세스한 시간이 Redis 서버에 기록됩니다(대략적인 값). 이 시간은 서버가 수행할 때 특정 간격으로만 업데이트되기 때문입니다. 자동 유지 관리) 둘 사이의 차이는 개체에 액세스하지 않은 기간을 계산하는 데 충분합니다. 그런 다음 redis 객체에는 참조 계산이 있는데, 이는 객체를 공유하고 객체의 삭제 시간을 결정하는 데 사용됩니다. 마지막으로 void* 포인터는 객체의 실제 내용을 가리키는 데 사용됩니다. 공식적으로는 추상적인 Redis 객체를 사용하므로 데이터베이스 내의 데이터를 조작하는 것이 훨씬 편리하며, 모든 Redis 객체 객체를 통일적으로 사용할 수 있으므로 객체 유형을 구분해야 할 경우 유형을 기준으로 판단합니다. 그리고 공식적으로 이러한 객체 지향 접근 방식의 채택으로 인해 redis 코드는 C++ 코드와 매우 유사해 보이지만 실제로는 모두 C로 작성되었습니다.
아아아아결국 Redis는 얼마나 많은 데이터 구조를 지원하든 관계없이 최종 저장소는 여전히 키-값 모드이지만 값은 연결된 목록, 집합, 정렬된 집합, 해시 테이블 등이 될 수 있습니다. . memcached와 마찬가지로 모든 키는 문자열이며 문자열은 set, sorted set, hash table 등과 같은 특정 저장소에도 사용됩니다. C에는 미리 만들어진 문자열이 없으므로 redis의 첫 번째 작업은 sds(간단한 동적 문자열)라는 문자열을 구현하는 것입니다. 다음 코드는 문자열의 전체 메모리 길이를 저장하고 해제합니다. 이는 여전히 사용되지 않은 바이트 수를 의미하며 buf는 특정 데이터를 저장합니다. 분명히 len-free는 문자열의 현재 길이입니다.
struct sdshdr {
int len;
int free;
char buf[];
};字符串解决了，所有的key都存成sds就行了，那么key和value怎么关联呢？key-value的格式在脚本语言中很好处理，直接使用字典即可，C没有字典，怎么办呢？自己写一个呗（redis十分热衷于造轮子）。看下面的代码，privdata存额外信息，用的很少，至少我们发现。 dictht是具体的哈希表，一个dict对应两张哈希表，这是为了扩容（包括rehashidx也是为了扩容）。dictType存储了哈希表的属性。redis还为dict实现了迭代器（所以说看起来像c++代码）。
哈希表的具体实现是和mc类似的做法，也是使用开链法来解决冲突，不过里面用到了一些小技巧。比如使用dictType存储函数指针，可以动态配置桶里面元素的操作方法。又比如dictht中保存的sizemask取size（桶的数量）-1，用它与key做&操作来代替取余运算，加快速度等等。总的来看，dict里面有两个哈希表，每个哈希表的桶里面存储dictEntry链表，dictEntry存储具体的key和value。
前面说过，一个dict对于两个dictht，是为了扩容（其实还有缩容）。正常的时候，dict只使用dictht[0]，当dict[0]中已有entry的数量与桶的数量达到一定的比例后，就会触发扩容和缩容操作，我们统称为rehash，这时，为dictht[1]申请rehash后的大小的内存，然后把dictht[0]里的数据往dictht[1]里面移动，并用rehashidx记录当前已经移动万的桶的数量，当所有桶都移完后，rehash完成，这时将dictht[1]变成dictht[0], 将原来的dictht[0]变成dictht[1]，并变为null即可。不同于memcached，这里不用开一个后台线程来做，而是就在event loop中完成，并且rehash不是一次性完成，而是分成多次，每次用户操作dict之前，redis移动一个桶的数据，直到rehash完成。这样就把移动分成多个小移动完成，把rehash的时间开销均分到用户每个操作上，这样避免了用户一个请求导致rehash的时候，需要等待很长时间，直到rehash完成才有返回的情况。不过在rehash期间，每个操作都变慢了点，而且用户还不知道redis在他的请求中间添加了移动数据的操作，感觉redis太贱了 :-D
typedef struct dict {
dictType *type; // 哈希表的相关属性
void *privdata; // 额外信息
dictht ht[2]; // 两张哈希表，分主和副，用于扩容
int rehashidx; /* rehashing not in progress if rehashidx == -1 */ // 记录当前数据迁移的位置，在扩容的时候用的
int iterators; /* number of iterators currently running */ // 目前存在的迭代器的数量
} dict;
typedef struct dictht {
dictEntry **table; // dictEntry是item，多个item组成hash桶里面的链表，table则是多个链表头指针组成的数组的指针
unsigned long size; // 这个就是桶的数量
// sizemask取size - 1, 然后一个数据来的时候，通过计算出的hashkey, 让hashkey & sizemask来确定它要放的桶的位置
// 当size取2^n的时候，sizemask就是1...111，这样就和hashkey % size有一样的效果，但是使用&会快很多。这就是原因
unsigned long sizemask;
unsigned long used; // 已经数值的dictEntry数量
} dictht;
typedef struct dictType {
unsigned int (*hashFunction)(const void *key); // hash的方法
void *(*keyDup)(void *privdata, const void *key); // key的复制方法
void *(*valDup)(void *privdata, const void *obj); // value的复制方法
int (*keyCompare)(void *privdata, const void *key1, const void *key2); // key之间的比较
void (*keyDestructor)(void *privdata, void *key); // key的析构
void (*valDestructor)(void *privdata, void *obj); // value的析构
} dictType;
typedef struct dictEntry {
void *key;
union {
void *val;
uint64_t u64;
int64_t s64;
} v;
struct dictEntry *next;
} dictEntry;有了dict，数据库就好实现了。所有数据读存储在dict中，key存储成dictEntry中的key（string），用void* 指向一个redis object，它可以是5种类型中的任何一种。如下图，结构构造是这样，不过这个图已经过时了，有一些与redis3.0不符合的地方。
유형 5의 각 객체에는 두 개 이상의 기본 구현이 있습니다. 문자열에는 REDIS_ENCODING_RAW, REDIS_ENCIDING_INT, REDIS_ENCODING_EMBSTR의 세 가지 유형이 있습니다. 목록에는 일반 양방향 연결 목록과 압축 연결 목록이 포함됩니다. 압축 연결 목록은 단순히 배열을 연결 목록, 연속 공간으로 변환한 다음 연결 목록을 시뮬레이션하는 것을 의미합니다. 문자열의 크기 정보를 저장함으로써 일반 연결리스트에 비해 공간을 절약할 수 있지만 연속적인 공간이기 때문에 메모리 크기를 변경할 때 재할당이 필요하고 바이트 크기도 커진다는 단점이 있다. 문자열이 저장되면 지속적인 업데이트가 발생할 수 있습니다. (구체적인 구현은 코드를 자세히 살펴보시기 바랍니다.) 세트에는 dict 및 intset(모든 정수를 저장하는 데 사용)이 있고, 정렬된 세트에는 Skiplist 및 ziplist가 있으며, 해시 테이블 구현에는 압축된 목록, dict 및 ziplist가 있습니다. Skiplist는 스킵 리스트인데, 레드-블랙 트리에 가까운 효율성을 가지지만, 레드-블랙 트리에 비해 구현이 훨씬 간단해서 채택합니다(이상한데 여기서는 휠이 재발명되지 않았기 때문인가요?) 이 휠은 좀 어렵나요?). 해시 테이블은 dict를 사용하여 구현할 수 있습니다. dict에서 각 dictentry의 키는 키(해시 테이블의 키-값 쌍의 키)를 저장하고 값은 둘 다 문자열입니다. 집합의 dict의 경우 각 dictentry의 키는 집합의 특정 요소 값을 저장하며 값은 null입니다. 그림의 zset(순서 있는 집합)이 잘못되었습니다. zset은 우선 Skiplist와 ziplist를 사용하여 구현됩니다. 우선, Skiplist는 이해하기 쉽기 때문에 Red-Black 트리를 대체한다고 생각하면 됩니다. 정렬할 수도 있습니다. zset을 저장하기 위해 ziplist를 사용하는 방법은 무엇입니까? 첫째, zset에서 세트의 각 요소에는 정렬에 사용되는 점수가 있습니다. 따라서 ziplist에서는 점수에 따라 요소가 먼저 저장되고 그 다음 점수, 다음 요소, 점수가 저장됩니다. 지속적인 저장이기 때문에 삽입하거나 삭제할 때 메모리를 재할당해야 합니다. 따라서 요소 수가 특정 수를 초과하거나 요소의 문자 수가 특정 수를 초과하면 redis는 Skiplist를 사용하여 zset을 구현하도록 선택합니다(현재 ziplist가 사용되는 경우 ziplist의 데이터가 제거되고 새로운 Skiplist에 저장된 다음 ziplist를 삭제하고 변경합니다. 이것이 기본 변환이며 다른 유형의 redis 객체도 변환될 수 있습니다. 또한 ziplist는 해시 테이블을 어떻게 구현합니까? 사실 매우 간단합니다. 키를 저장하고 값을 저장한 다음 키를 저장하고 값을 저장하면 됩니다. zset 구현과 유사하게 여전히 순차적으로 저장되므로 요소가 특정 수를 초과하거나 요소의 문자 수가 특정 수를 초과하면 구현을 위해 해시 테이블로 변환됩니다. 다양한 기본 구현 방법을 변환할 수 있으며, redis는 상황에 따라 가장 적합한 구현 방법을 선택할 수 있습니다. 이는 유사한 객체 지향 구현 방법을 사용하는 이점이기도 합니다.
zset을 구현하기 위해 Skiplist를 사용할 때 동일한 키-값 쌍을 저장하는 dict가 실제로 사용된다는 점을 지적해야 합니다. 왜? Skiplist의 검색은 lgn(n이 될 수 있음)이고 dict는 O(1)일 수 있으므로 검색 속도를 높이기 위해 dict를 사용합니다. Skiplist와 dict가 동일한 Redis 객체를 가리킬 수 있으므로 메모리가 너무 많으면 낭비하지 마십시오. 또한 zset을 구현하기 위해 ziplist를 사용할 때 검색 속도를 높이기 위해 dict를 사용하는 것은 어떨까요? ziplist는 소수의 요소를 지원하고(숫자가 크면 Skiplist로 변환됨) 순차 순회도 빠르기 때문에 dict가 필요하지 않습니다.
이러한 관점에서 볼 때 위의 dict, dictType, dictHt, dictEntry 및 redis 객체는 모두 매우 사려 깊고 객체 지향 색상으로 유연하고 효율적인 데이터베이스를 구현합니다. Redis 데이터베이스의 디자인은 여전히 매우 강력하다고 말씀드리고 싶습니다.
memcached와 달리 redis에는 둘 이상의 데이터베이스가 있으며 기본적으로 0-15까지 번호가 매겨진 16개가 있습니다. 어떤 데이터베이스를 사용할지는 고객이 선택할 수 있으며, 기본적으로 0번 데이터베이스가 사용됩니다. 서로 다른 데이터베이스 데이터는 공유되지 않습니다. 즉, 동일한 키가 서로 다른 데이터베이스에 존재할 수 있지만 동일한 데이터베이스에서 키는 고유해야 합니다.
Redis는 만료 시간 설정도 지원합니다. 위의 redis 객체에는 만료를 저장할 필드가 없습니다. 그러면 Redis는 데이터의 만료 시간을 어떻게 기록합니까? Redis는 각 데이터베이스에 또 다른 dict를 추가합니다. dict 항목의 키는 키 쌍이고 값은 데이터가 64비트 int인 redis 객체입니다. . 이런 방식으로 키가 만료되었는지 확인할 때 만료 딕셔너리에서 이를 찾아 만료 시간을 꺼내 현재 시간과 비교할 수 있습니다. 왜 이런 일을 하는가? 모든 키에 만료 시간이 설정되어 있지 않기 때문에 만료 시간을 설정하지 않은 키의 경우 만료 시간을 저장하면 공간이 낭비됩니다. 대신 만료 딕셔너리를 사용하여 별도로 저장하고 필요에 따라 메모리를 유연하게 사용할 수 있습니다. 감지됨 키가 만료되면 만료 딕셔너리에서 삭제됩니다.
redis的expire 机制是怎样的呢？ 与memcahed类似，redis也是惰性删除，即要用到数据时，先检查key是否过期，过期则删除，然后返回错误。单纯的靠惰性删除，上面说过可能会导致内存浪费，所以redis也有补充方案，redis里面有个定时执行的函数，叫servercron，它是维护服务器的函数，在它里面，会对过期数据进行删除，注意不是全删，而是在一定的时间内，对每个数据库的expire dict里面的数据随机选取出来，如果过期，则删除，否则再选，直到规定的时间到。即随机选取过期的数据删除，这个操作的时间分两种，一种较长，一种较短，一般执行短时间的删除，每隔一定的时间，执行一次长时间的删除。这样可以有效的缓解光采用惰性删除而导致的内存浪费问题。
以上就是redis的数据的实现，与memcached不同，redis还支持数据持久化，这个下面介绍。
redis和memcached的最大不同，就是redis支持数据持久化，这也是很多人选择使用redis而不是memcached的最大原因。 redis的持久化，分为两种策略，用户可以配置使用不同的策略。
4.1 RDB持久化
用户执行save或者bgsave的时候，就会触发RDB持久化操作。RDB持久化操作的核心思想就是把数据库原封不动的保存在文件里。
那如何存储呢？如下图， 首先存储一个REDIS字符串，起到验证的作用，表示是RDB文件，然后保存redis的版本信息，然后是具体的数据库，然后存储结束符EOF，最后用检验和。关键就是databases，看它的名字也知道，它存储了多个数据库，数据库按照编号顺序存储，0号数据库存储完了，才轮到1，然后是2, 一直到最后一个数据库。
每一个数据库存储方式如下，首先一个1字节的常量SELECTDB，表示切换db了，然后下一个接上数据库的编号，它的长度是可变的，然后接下来就是具体的key-value对的数据了。
int rdbSaveKeyValuePair(rio *rdb, robj *key, robj *val,
long long expiretime, long long now)
{
/* Save the expire time */
if (expiretime != -1) {
/* If this key is already expired skip it */
if (expiretime < now) return 0;
if (rdbSaveType(rdb,REDIS_RDB_OPCODE_EXPIRETIME_MS) == -1) return -1;
if (rdbSaveMillisecondTime(rdb,expiretime) == -1) return -1;
}
/* Save type, key, value */
if (rdbSaveObjectType(rdb,val) == -1) return -1;
if (rdbSaveStringObject(rdb,key) == -1) return -1;
if (rdbSaveObject(rdb,val) == -1) return -1;
return 1;
}由上面的代码也可以看出，存储的时候，先检查expire time，如果已经过期，不存就行了，否则，则将expire time存下来，注意，及时是存储expire time，也是先存储它的类型为REDIS_RDB_OPCODE_EXPIRETIME_MS，然后再存储具体过期时间。接下来存储真正的key-value对，首先存储value的类型，然后存储key（它按照字符串存储），然后存储value，如下图。
在rdbsaveobject中，会根据val的不同类型，按照不同的方式存储，不过从根本上来看，最终都是转换成字符串存储，比如val是一个linklist，那么先存储整个list的字节数，然后遍历这个list，把数据取出来，依次按照string写入文件。对于hash table，也是先计算字节数，然后依次取出hash table中的dictEntry，按照string的方式存储它的key和value，然后存储下一个dictEntry。 总之，RDB的存储方式，对一个key-value对，会先存储expire time（如果有的话），然后是value的类型，然后存储key（字符串方式），然后根据value的类型和底层实现方式，将value转换成字符串存储。这里面为了实现数据压缩，以及能够根据文件恢复数据，redis使用了很多编码的技巧，有些我也没太看懂，不过关键还是要理解思想，不要在意这些细节。
保存了RDB文件，当redis再启动的时候，就根据RDB文件来恢复数据库。由于以及在RDB文件中保存了数据库的号码，以及它包含的key-value对，以及每个key-value对中value的具体类型，实现方式，和数据，redis只要顺序读取文件，然后恢复object即可。由于保存了expire time，发现当前的时间已经比expire time大了，即数据已经超时了，则不恢复这个key-value对即可。
RDB 파일을 저장하는 것은 거대한 프로젝트이므로 Redis는 백그라운드 저장 메커니즘도 제공합니다. 즉, bgsave가 실행되면 redis는 하위 프로세스를 포크하여 하위 프로세스가 저장된 작업을 수행하도록 하고, 상위 프로세스는 계속해서 redis의 일반 데이터베이스 서비스를 제공합니다. 자식 프로세스는 부모 프로세스의 주소 공간을 복사하므로, 즉 부모 프로세스가 분기될 때 자식 프로세스가 데이터베이스를 소유하므로 자식 프로세스는 저장 작업을 수행하고 부모 프로세스에서 상속받은 데이터베이스를 임시 파일에 씁니다. 하위 프로세스를 복사하는 동안 redis는 데이터베이스의 수정(더티) 수를 기록합니다. 하위 프로세스가 완료되면 상위 프로세스에 SIGUSR1 신호를 보냅니다. 상위 프로세스가 이 신호를 받으면 하위 프로세스가 복사를 완료했음을 알게 됩니다. 그런 다음 상위 프로세스는 하위 프로세스가 저장한 임시 파일의 이름을 바꿉니다. 실제 rdb 파일(즉, 실제 저장이 성공한 경우) 그런 다음에만 대상 파일로 변경하는 것이 안전한 접근 방법입니다. 그런 다음 이 저장의 종료 시간을 기록하십시오.
여기서 문제가 발생합니다. 자식 프로세스의 저장 기간 동안 부모 프로세스의 데이터베이스가 수정되었으며, 부모 프로세스에서는 수정 작업 없이 수정(더티) 횟수만 기록합니다. RDB가 저장하는 것은 실시간 데이터베이스가 아닌 것 같은데, 좀 가식적이네요. 그러나 나중에 소개할 AOF Persistence는 이 문제를 해결합니다.
고객이 sava 또는 bgsave 명령을 실행하는 것 외에 RDB 저장 조건도 구성할 수 있습니다. 즉, 구성 파일에 구성되어 있으며, t 시간 내에 데이터베이스가 더티 타임에 수정되면 백그라운드에 저장됩니다. Redis가 cron을 제공할 때 더티 항목 수와 마지막 저장 시간을 기준으로 조건을 충족하는지 판단합니다. 조건이 충족되면 bg 저장은 하나의 하위 프로세스만 수행될 수 있습니다. 여러 프로세스에서 많은 수의 IO 작업을 수행하면 비효율적이고 관리하기 어렵습니다.
4.2 AOF 지속성
먼저, 데이터베이스를 저장하려면 RDB처럼 데이터베이스에 있는 모든 데이터를 저장해야 합니까? 다른 방법이 있나요?
RDB는 결과인 최종 데이터베이스만 저장합니다. 결과는 어떻게 나왔나요? 사용자의 다양한 명령어를 통해 설정되므로 결과를 저장할 필요는 없고, 결과를 생성한 명령어만 저장된다. Redis의 AOF는 RDB처럼 DB 데이터를 저장하지 않고, 데이터베이스를 구축하기 위한 명령어를 하나씩 저장하는 개념입니다.
먼저 AOF 파일의 형식을 살펴보겠습니다. 먼저 명령 길이가 저장되고 그 다음에는 특정 구분 기호를 직접 연구할 수 있습니다. , AOF 파일이 어떻게 저장되는지 알 수 있습니다. 이는 redis 클라이언트가 실행하는 명령입니다.
Redis 서버에 sds aof_buf가 있습니다. aof 지속성이 켜져 있으면 데이터베이스를 수정하는 각 명령이 이 aof_buf에 저장되고(aof 파일에 명령 형식의 문자열이 저장됨) 이벤트 루프가 수행됩니다. 서버 크론에서 플러시aofbuf를 호출하고 aof_buf의 명령을 aof 파일에 쓴 다음(실제로 쓴 것은 커널 버퍼입니다) aof_buf를 지우고 다음 루프에 들어갑니다. 이러한 방식으로 모든 데이터베이스 변경 사항은 aof 파일의 명령을 통해 복원되어 데이터베이스를 저장하는 효과를 얻을 수 있습니다.
Flushaofbuf에서 호출된 쓰기는 커널 버퍼에만 데이터를 쓰는 작업이며 커널 자체에 의해 결정되며 일정 기간 동안 지연되어야 할 수도 있습니다. 그러나 redis는 각 쓰기 후에 동기화를 구성한 다음 redis에서 동기화를 호출하여 커널의 데이터를 파일에 쓸 수 있으며 이는 시스템 호출만 필요합니다. 매초마다 동기화하도록 정책을 구성할 수도 있습니다. 그러면 redis는 백그라운드 스레드를 시작하고(따라서 redis는 단일 스레드가 아니라 단일 이벤트 루프일 뿐입니다), 이 백그라운드 스레드는 매초마다 동기화를 호출합니다. RDB를 사용할 때 왜 동기화가 고려되지 않았는지 묻고 싶습니다. RDB는 한 번 저장되기 때문에 AOF와는 달리 RDB 중에 sync를 한 번 호출해도 아무런 효과가 없으며, bg save를 사용하면 자식 프로세스가 스스로 종료(exit)하게 되는데, 이때 exit 함수에서 버퍼가 플러시됩니다. . 영역을 사용하면 자동으로 파일에 기록됩니다.
다시 살펴보면 aof_buf를 사용하여 각 수정 명령을 저장하고 싶지 않다면 aof persistence를 사용할 수도 있습니다. Redis는 기존 데이터베이스를 기반으로 명령을 생성한 다음 명령을 aof 파일에 쓰는 aof_rewrite를 제공합니다. 아주 이상하지 않나요? 네, 정말 좋아요. aof_rewrite를 수행할 때 각 데이터베이스에서 redis 변수를 사용한 후 list와 같은 키-값 쌍의 특정 유형의 값을 기반으로 서로 다른 명령을 생성한 다음 해당 목록을 저장하는 명령을 생성합니다. 목록을 저장하는 데 필요한 정보입니다. 목록 데이터가 너무 길면 여러 명령으로 나누어집니다. 먼저 목록을 만든 다음 목록에 요소를 추가합니다. 데이터를 기반으로 역방향으로. 그런 다음 이 명령을 aof 파일에 저장하면 aof 추가와 동일한 효과를 얻을 수 있지 않습니까?
再来看，aof格式也支持后台模式。执行aof_bgrewrite的时候，也是fork一个子进程，然后让子进程进行aof_rewrite，把它复制的数据库写入一个临时文件，然后写完后用新号通知父进程。父进程判断子进程的退出信息是否正确，然后将临时文件更名成最终的aof文件。好了，问题来了。在子进程持久化期间，可能父进程的数据库有更新，怎么把这个更新通知子进程呢？难道要用进程间通信么？是不是有点麻烦呢？你猜redis怎么做的？它根本不通知子进程。什么，不通知？那更新怎么办？ 在子进程执行aof_bgrewrite期间，父进程会保存所有对数据库有更改的操作的命令（增，删除，改等），把他们保存在aof_rewrite_buf_blocks中，这是一个链表，每个block都可以保存命令，存不下时，新申请block，然后放入链表后面即可，当子进程通知完成保存后，父进程将aof_rewrite_buf_blocks的命令append 进aof文件就可以了。多么优美的设计，想一想自己当初还考虑用进程间通信，别人直接用最简单的方法就完美的解决了问题，有句话说得真对，越优秀的设计越趋于简单，而复杂的东西往往都是靠不住的。
至于aof文件的载入，也就是一条一条的执行aof文件里面的命令而已。不过考虑到这些命令就是客户端发送给redis的命令，所以redis干脆生成了一个假的客户端，它没有和redis建立网络连接，而是直接执行命令即可。首先搞清楚，这里的假的客户端，并不是真正的客户端，而是存储在redis里面的客户端的信息，里面有写和读的缓冲区，它是存在于redis服务器中的。所以，如下图，直接读入aof的命令，放入客户端的读缓冲区中，然后执行这个客户端的命令即可。这样就完成了aof文件的载入。
// 创建伪客户端
fakeClient = createFakeClient();
while(命令不为空) {
// 获取一条命令的参数信息 argc， argv
...
// 执行
fakeClient->argc = argc;
fakeClient->argv = argv;
cmd->proc(fakeClient);
}整个aof持久化的设计，个人认为相当精彩。其中有很多地方，值得膜拜。
redis另一个比memcached强大的地方，是它支持简单的事务。事务简单说就是把几个命令合并，一次性执行全部命令。对于关系型数据库来说，事务还有回滚机制，即事务命令要么全部执行成功，只要有一条失败就回滚，回到事务执行前的状态。redis不支持回滚，它的事务只保证命令依次被执行，即使中间一条命令出错也会继续往下执行，所以说它只支持简单的事务。
首先看redis事务的执行过程。首先执行multi命令，表示开始事务，然后输入需要执行的命令，最后输入exec执行事务。 redis服务器收到multi命令后，会将对应的client的状态设置为REDIS_MULTI，表示client处于事务阶段，并在client的multiState结构体里面保持事务的命令具体信息（当然首先也会检查命令是否能否识别，错误的命令不会保存），即命令的个数和具体的各个命令，当收到exec命令后，redis会顺序执行multiState里面保存的命令，然后保存每个命令的返回值，当有命令发生错误的时候，redis不会停止事务，而是保存错误信息，然后继续往下执行，当所有的命令都执行完后，将所有命令的返回值一起返回给客户。redis为什么不支持回滚呢？网上看到的解释出现问题是由于客户程序的问题，所以没必要服务器回滚，同时，不支持回滚，redis服务器的运行高效很多。在我看来，redis的事务不是传统关系型数据库的事务，要求CIAD那么非常严格，或者说redis的事务都不是事务，只是提供了一种方式，使得客户端可以一次性执行多条命令而已，就把事务当做普通命令就行了，支持回滚也就没必要了。
我们知道redis是单event loop的，在真正执行一个事物的时候（即redis收到exec命令后），事物的执行过程是不会被打断的，所有命令都会在一个event loop中执行完。但是在用户逐个输入事务的命令的时候，这期间，可能已经有别的客户修改了事务里面用到的数据，这就可能产生问题。所以redis还提供了watch命令，用户可以在输入multi之前，执行watch命令，指定需要观察的数据，这样如果在exec之前，有其他的客户端修改了这些被watch的数据，则exec的时候，执行到处理被修改的数据的命令的时候，会执行失败，提示数据已经dirty。 这是如何是实现的呢？ 原来在每一个redisDb中还有一个dict watched_keys，watched_kesy中dictentry的key是被watch的数据库的key，而value则是一个list，里面存储的是watch它的client。同时，每个client也有一个watched_keys，里面保存的是这个client当前watch的key。在执行watch的时候，redis在对应的数据库的watched_keys中找到这个key（如果没有，则新建一个dictentry），然后在它的客户列表中加入这个client，同时，往这个client的watched_keys中加入这个key。当有客户执行一个命令修改数据的时候，redis首先在watched_keys中找这个key，如果发现有它，证明有client在watch它，则遍历所有watch它的client，将这些client设置为REDIS_DIRTY_CAS，表面有watch的key被dirty了。当客户执行的事务的时候，首先会检查是否被设置了REDIS_DIRTY_CAS，如果是，则表明数据dirty了，事务无法执行，会立即返回错误，只有client没有被设置REDIS_DIRTY_CAS的时候才能够执行事务。 需要指出的是，执行exec后，该client的所有watch的key都会被清除，同时db中该key的client列表也会清除该client，即执行exec后，该client不再watch任何key（即使exec没有执行成功也是一样）。所以说redis的事务是简单的事务，算不上真正的事务。
以上就是redis的事务，感觉实现很简单，实际用处也不是太大。
redis支持频道，即加入一个频道的用户相当于加入了一个群，客户往频道里面发的信息，频道里的所有client都能收到。
实现也很简单，也watch_keys实现差不多，redis server中保存了一个pubsub_channels的dict，里面的key是频道的名称（显然要唯一了），value则是一个链表，保存加入了该频道的client。同时，每个client都有一个pubsub_channels，保存了自己关注的频道。当用用户往频道发消息的时候，首先在server中的pubsub_channels找到改频道，然后遍历client，给他们发消息。而订阅，取消订阅频道不够都是操作pubsub_channels而已，很好理解。
同时，redis还支持模式频道。即通过正则匹配频道，如有模式频道p, 1, 则向普通频道p1发送消息时，会匹配p，1，除了往普通频道发消息外，还会往p，1模式频道中的client发消息。注意，这里是用发布命令里面的普通频道来匹配已有的模式频道，而不是在发布命令里制定模式频道，然后匹配redis里面保存的频道。实现方式也很简单，在redis server里面有个pubsub_patterns的list（这里为什么不用dict？因为pubsub_patterns的个数一般较少，不需要使用dict，简单的list就好了），它里面存储的是pubsubPattern结构体，里面是模式和client信息，如下所示，一个模式，一个client，所以如果有多个clint监听一个pubsub_patterns的话，在list面会有多个pubsubPattern，保存client和pubsub_patterns的对应关系。 同时，在client里面，也有一个pubsub_patterns list，不过里面存储的就是它监听的pubsub_patterns的列表（就是sds），而不是pubsubPattern结构体。
typedef struct pubsubPattern {
redisClient *client; // 监听的client
robj *pattern; // 模式
} pubsubPattern;当用户往一个频道发送消息的时候，首先会在redis server中的pubsub_channels里面查找该频道，然后往它的客户列表发送消息。然后在redis server里面的pubsub_patterns里面查找匹配的模式，然后往client里面发送消息。 这里并没有去除重复的客户，在pubsub_channels可能已经给某一个client发过message了，然后在pubsub_patterns中可能还会给用户再发一次（甚至更多次）。 估计redis认为这是客户程序自己的问题，所以不处理。
/* Publish a message */
int pubsubPublishMessage(robj *channel, robj *message) {
int receivers = 0;
dictEntry *de;
listNode *ln;
listIter li;
/* Send to clients listening for that channel */
de = dictFind(server.pubsub_channels,channel);
if (de) {
list *list = dictGetVal(de);
listNode *ln;
listIter li;
listRewind(list,&li);
while ((ln = listNext(&li)) != NULL) {
redisClient *c = ln->value;
addReply(c,shared.mbulkhdr[3]);
addReply(c,shared.messagebulk);
addReplyBulk(c,channel);
addReplyBulk(c,message);
receivers++;
}
}
/* Send to clients listening to matching channels */
if (listLength(server.pubsub_patterns)) {
listRewind(server.pubsub_patterns,&li);
channel = getDecodedObject(channel);
while ((ln = listNext(&li)) != NULL) {
pubsubPattern *pat = ln->value;
if (stringmatchlen((char*)pat->pattern->ptr,
sdslen(pat->pattern->ptr),
(char*)channel->ptr,
sdslen(channel->ptr),0)) {
addReply(pat->client,shared.mbulkhdr[4]);
addReply(pat->client,shared.pmessagebulk);
addReplyBulk(pat->client,pat->pattern);
addReplyBulk(pat->client,channel);
addReplyBulk(pat->client,message);
receivers++;
}
}
decrRefCount(channel);
}
return receivers;
}总的来看，redis比memcached的功能多很多，实现也更复杂。 不过memcached更专注于保存key-value数据（这已经能满足大多数使用场景了），而redis提供更丰富的数据结构及其他的一些功能。不能说redis比memcached好，不过从源码阅读的角度来看，redis的价值或许更大一点。 另外，redis3.0里面支持了集群功能，这部分的代码还没有研究，后续再跟进。
위 내용은 memcached와 redis 구현 간의 비교를 소개하는 자세한 그래픽 코드의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!
![[웹 프런트엔드] Node.js 빠른 시작](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
