Redis 데이터 구조 유형 예제 코드 분석-Redis-php.cn

intset

ziplist

quicklist

skiplist

总结

HyperLogLog

pfadd

pfcount

집

데이터 베이스

Redis

Redis 데이터 구조 유형 예제 코드 분석

WBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWB

Jun 01, 2023 pm 02:16 PM

redis

intset

집합 컬렉션이 정수를 저장하는 경우 인코딩은 intset 유형(작은 정수 컬렉션)입니다.

typedef struct intset {
    int32 encoding;
    int32 length;
    int contents[];
}

로그인 후 복사

을 나타냅니다.

Field	Description	Explanation
encoding	정수 비트 너비를 16비트로 결정 , 32비트 또는 64비트	열거형은
길이	요소 수
contents	정수 배열, 요소 값 저장

intset은 다음에서 정렬됩니다. 작은 것에서 큰 것 순서대로 요소를 저장합니다. 요소를 저장할 때 정수 크기를 기준으로 인코딩 업그레이드 여부를 결정하고 요소가 삽입될 위치를 찾아 마지막 위치가 아니면 해당 위치 이후의 요소를 한 위치 이동한 후 마지막으로 삽입한다. 요소. 삽입된 요소가 정수가 아닌 경우 저장 형식은 해시 구조가 됩니다.

ziplist

구성 파일에서 다음 조건이 충족되면 hash 및 zset의 인코딩 유형이 ziplist(압축 목록)가 됩니다.

hash-max-ziplist-entries 512 # 当hash元素个数小于512时
hash-max-ziplist-value 64 # 当hash键或值长度小于64时
zset-max-ziplist-entries 128 # 当zset元素个数小于128时
zset-max-ziplist-value 64 # 当zset值小于64时

로그인 후 복사

typedef struct ziplist {
    int32 zlbytes;
    int32 zltail_offset;
    int16 zllength;
    T[] entries;
    int8 zlend;
}
typedef struct entry {
    int<var> prevlen;
    int<var> encoding;
    byte[] content;
}

로그인 후 복사

zlend 표시 압축된 목록의 끝 항상 FFprevlen첫 번째 항목은 항상 0 및 바이트 문자열 길이가 254보다 작으면 1바이트를 사용하고, 그렇지 않으면 5바이트를 사용합니다.encodingencoding type

field	description	description
zlbytes	ziplist가 차지하는 바이트 수
zltail_offset	압축된 목록의 시작 위치에서 마지막 요소의 오프셋	마지막 노드를 빠르게 찾은 다음 역순으로 탐색하는 데 사용됩니다.

Field	Description	Explanation

요소의 내용에 따라 인코딩 유형이 동적으로 변경됩니다. 이 글에서는 자세히 설명하지 않습니다. ziplist 인코딩 유형content 요소 콘텐츠, 선택사항

에서 검색할 수 있습니다.

下图是一个ziplist的demo

Redis 데이터 구조 유형 예제 코드 분석

第1-4字节，zlbytes为25，说明该压缩列表共占用25个字节
第5-8字节，zltail_offset为22，说明最后一个元素从22开始
第9-10字节，zllength为3，说明共有3个元素
第11-16字节，第一个entry: 其中prevlen=0，因为它前面没有数据项；encoding=4，表示后面4byte按照字符串存储，数据的值为name
第17-21字节，第二个entry: 其中prevlen=6，表示前一个entry共占用6byte；encoding=3，表示后面3byte按照字符串存储，数据的值为why
第22-24字节，第三个entry: 其中prevlen=5，表示前一个entry共占用5byte；encoding=0xFE，表示后面1byte存储整数，数据的值为14
第25字节，zlend为FF，标志压缩列表的结束

当用ziplist存储hash结构时，将key与value分别当作一个entry存储。

可见压缩列表存储非常的紧凑，当某一个entry长度变为254时，下一个entry的prevlen将从1个字节扩展到5个字节，这就是级联更新

quicklist

quicklist（快速列表）用于存储list集合，它是ziplist与linkedlist的混合体，linkedlist与双向列表结构类似。

quicklist内部默认单个ziplist长度为8K，超过这个长度，就会另起一个node，可在配置文件中配置。

# -2表示8k，枚举类型可在配置文件中查看
list-max-ziplist-size -2

로그인 후 복사

quicklist默认的压缩深度为0，也就是不压缩。如果压缩深度为1，那么就是首尾不压缩，如果压缩深度为2，那么就是首2个、尾2个不压缩，可在配置文件中配置。

list-compress-depth 0

로그인 후 복사

skiplist

zset使用dict存储value与score的映射，另一方面还需要按照score提供排序功能，于是就有了skiplist（跳跃列表）

先看skiplist的一个demo

Redis 데이터 구조 유형 예제 코드 분석

typedef struct zsl {
    zslnode* header;
    zslnode* tail;
    int maxLevel;
}

로그인 후 복사

typedef struct zslnode {
    sds value;
    double score;
    zslforward*[] forwards;
    zslnode* backward;
}

로그인 후 복사

typedef struct zslforward {
    zslnode* item;
    int span;
}

로그인 후 복사

字段	描述	说明
header	指向跳跃列表的头指针	value固定为NULL，score固定为0，backward为null
tail	指向跳跃列表的尾指针
maxLevel	当前跳跃表最大层数	最大为64
value	用于存储字符串类型的数据
score	用于存储分值
backward	回退节点	图中的←箭头
forwards	前进节点	图中的→箭头，每一层对应一个
span	跨度，存储一个节点跳到下一个节点中间跳过了多少节点	如score1指向score5，则span值为4，这是排名的实现原理

最小分值的backward固定null，对于每一个新插入的节点，会调用一个随机算法，来给它分配一个合理的层数

level1的概率为1-0.25=0.75，实际为100%，因为跳跃列表的最小层数为1

level2的概率为0.75*0.25=0.1875level3的概率为0.1875*0.25=0.0468 ......

leveln的概率为(1-0.25)*Math.pow(0.25,n-1)

总结

Redis作为单线程内存服务，在响应、数据结构上作出了很多的优化，值得我们学习

对象类型	编码类型
string	int、raw、embstr
list	quicklist
hash	dict、ziplist
set	intset、dict
zset	ziplist、skiplist+dict

HyperLogLog

HyperLogLog的原理为伯努利试验，即丢硬币，根据连续出现反面的次数X，推算出一共丢了2的X次方次硬币，当X很大时，推算出来的总数与实际总数误差就很接近了。具体可查询其他文章。

pfadd

element经过hash算法之后是一个64位的固定值

低14位为桶

查找高50位第一个为1的位数，如果大于当前桶的位数，就将其设置为当前桶的位数

假设hash值是：{此处省略45位}01100 00000000000101

低14位的二进制转为10进制，值为5（regnum），即我们把数据放在第5个桶
高50位第一个1的位置是3，即count值为3
registers[5]取出历史值oldcount
如果count > oldcount，则更新 registers[5] = count
如果count <= oldcount，则不做任何处理

HyperLogLog用了16384个桶，每个桶占用6bit，因此说一个HyperLogLog所占用内存是12K。

调和平均数：

假设我的工资为10_000，马云的工资为1_000_000，那我和马云的平均工资为505_000，我肯定是不认同的。。。

如果使用调和平均数，则为2/(1/10_000+1/1_000_000)=19_801

同理，桶位数的平均数为：n/(1/桶1位数+1/桶2位数+...+1/桶n位数)

桶的平均个数为：Math.pow(2，桶位数的平均数)

总数量：const*桶总数n*桶的平均个数，其中constant为不定值，与桶个数有关，假设m为桶个数，取对数

pfcount

p=log2m
switch (p) {
   case 4:
       constant = 0.673 * m * m;
   case 5:
       constant = 0.697 * m * m;
   case 6:
       constant = 0.709 * m * m;
   default:
       constant = (0.7213 / (1 + 1.079 / m)) * m * m;
}

로그인 후 복사

위 내용은 Redis 데이터 구조 유형 예제 코드 분석의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!

본 웹사이트의 성명

본 글의 내용은 네티즌들의 자발적인 기여로 작성되었으며, 저작권은 원저작자에게 있습니다. 본 사이트는 이에 상응하는 법적 책임을 지지 않습니다. 표절이나 침해가 의심되는 콘텐츠를 발견한 경우 admin@php.cn으로 문의하세요.

핫 AI 도구

Video Face Swap

완전히 무료인 AI 얼굴 교환 도구를 사용하여 모든 비디오의 얼굴을 쉽게 바꾸세요!

뜨거운 도구

뜨거운 주제

Gmail 이메일의 로그인 입구는 어디에 있나요?

7698

자바 튜토리얼

1640

Cakephp 튜토리얼

1393

라라벨 튜토리얼

1287

PHP 튜토리얼

1229

Related knowledge

Redis 클러스터 모드를 구축하는 방법 Apr 10, 2025 pm 10:15 PM

Redis Cluster Mode는 Sharding을 통해 Redis 인스턴스를 여러 서버에 배포하여 확장 성 및 가용성을 향상시킵니다. 시공 단계는 다음과 같습니다. 포트가 다른 홀수 redis 인스턴스를 만듭니다. 3 개의 센티넬 인스턴스를 만들고, Redis 인스턴스 및 장애 조치를 모니터링합니다. Sentinel 구성 파일 구성, Redis 인스턴스 정보 및 장애 조치 설정 모니터링 추가; Redis 인스턴스 구성 파일 구성, 클러스터 모드 활성화 및 클러스터 정보 파일 경로를 지정합니다. 각 redis 인스턴스의 정보를 포함하는 Nodes.conf 파일을 작성합니다. 클러스터를 시작하고 Create 명령을 실행하여 클러스터를 작성하고 복제본 수를 지정하십시오. 클러스터에 로그인하여 클러스터 정보 명령을 실행하여 클러스터 상태를 확인하십시오. 만들다

Redis 데이터를 지우는 방법 Apr 10, 2025 pm 10:06 PM

Redis 데이터를 지우는 방법 : Flushall 명령을 사용하여 모든 키 값을 지우십시오. FlushDB 명령을 사용하여 현재 선택한 데이터베이스의 키 값을 지우십시오. 선택을 사용하여 데이터베이스를 전환 한 다음 FlushDB를 사용하여 여러 데이터베이스를 지우십시오. del 명령을 사용하여 특정 키를 삭제하십시오. Redis-Cli 도구를 사용하여 데이터를 지우십시오.

Redis 대기열을 읽는 방법 Apr 10, 2025 pm 10:12 PM

Redis의 대기열을 읽으려면 대기열 이름을 얻고 LPOP 명령을 사용하여 요소를 읽고 빈 큐를 처리해야합니다. 특정 단계는 다음과 같습니다. 대기열 이름 가져 오기 : "큐 :"와 같은 "대기열 : my-queue"의 접두사로 이름을 지정하십시오. LPOP 명령을 사용하십시오. 빈 대기열 처리 : 대기열이 비어 있으면 LPOP이 NIL을 반환하고 요소를 읽기 전에 대기열이 존재하는지 확인할 수 있습니다.

Redis 명령을 사용하는 방법 Apr 10, 2025 pm 08:45 PM

Redis 지시 사항을 사용하려면 다음 단계가 필요합니다. Redis 클라이언트를 엽니 다. 명령 (동사 키 값)을 입력하십시오. 필요한 매개 변수를 제공합니다 (명령어마다 다름). 명령을 실행하려면 Enter를 누르십시오. Redis는 작업 결과를 나타내는 응답을 반환합니다 (일반적으로 OK 또는 -err).

Redis Lock을 사용하는 방법 Apr 10, 2025 pm 08:39 PM

Redis를 사용하여 잠금 작업을 사용하려면 SetNX 명령을 통해 잠금을 얻은 다음 만료 명령을 사용하여 만료 시간을 설정해야합니다. 특정 단계는 다음과 같습니다. (1) SETNX 명령을 사용하여 키 값 쌍을 설정하십시오. (2) 만료 명령을 사용하여 잠금의 만료 시간을 설정하십시오. (3) DEL 명령을 사용하여 잠금이 더 이상 필요하지 않은 경우 잠금을 삭제하십시오.

Redis의 소스 코드를 읽는 방법 Apr 10, 2025 pm 08:27 PM

Redis 소스 코드를 이해하는 가장 좋은 방법은 단계별로 이동하는 것입니다. Redis의 기본 사항에 익숙해집니다. 특정 모듈을 선택하거나 시작점으로 기능합니다. 모듈 또는 함수의 진입 점으로 시작하여 코드를 한 줄씩 봅니다. 함수 호출 체인을 통해 코드를 봅니다. Redis가 사용하는 기본 데이터 구조에 익숙해 지십시오. Redis가 사용하는 알고리즘을 식별하십시오.

Centos redis에서 lua 스크립트 실행 시간을 구성하는 방법 Apr 14, 2025 pm 02:12 PM

CentOS 시스템에서는 Redis 구성 파일을 수정하거나 Redis 명령을 사용하여 악의적 인 스크립트가 너무 많은 리소스를 소비하지 못하게하여 LUA 스크립트의 실행 시간을 제한 할 수 있습니다. 방법 1 : Redis 구성 파일을 수정하고 Redis 구성 파일을 찾으십시오. Redis 구성 파일은 일반적으로 /etc/redis/redis.conf에 있습니다. 구성 파일 편집 : 텍스트 편집기 (예 : VI 또는 Nano)를 사용하여 구성 파일을 엽니 다. Sudovi/etc/redis/redis.conf LUA 스크립트 실행 시간 제한을 설정 : 구성 파일에서 다음 줄을 추가 또는 수정하여 LUA 스크립트의 최대 실행 시간을 설정하십시오 (Unit : Milliseconds).

Redis 명령 줄을 사용하는 방법 Apr 10, 2025 pm 10:18 PM

Redis Command Line 도구 (Redis-Cli)를 사용하여 다음 단계를 통해 Redis를 관리하고 작동하십시오. 서버에 연결하고 주소와 포트를 지정하십시오. 명령 이름과 매개 변수를 사용하여 서버에 명령을 보냅니다. 도움말 명령을 사용하여 특정 명령에 대한 도움말 정보를 봅니다. 종금 명령을 사용하여 명령 줄 도구를 종료하십시오.

See all articles

Redis 데이터 구조 유형 예제 코드 분석

intset

ziplist

quicklist

skiplist

总结

HyperLogLog

pfadd

pfcount

핫 AI 도구

Undresser.AI Undress

AI Clothes Remover

Undress AI Tool

Clothoff.io

Video Face Swap

인기 기사

뜨거운 도구

메모장++7.3.1

SublimeText3 중국어 버전

스튜디오 13.0.1 보내기

드림위버 CS6

SublimeText3 Mac 버전

뜨거운 주제