-
Notifications
You must be signed in to change notification settings - Fork 0
/
redisxi-lie-yi.html
539 lines (473 loc) · 35.9 KB
/
redisxi-lie-yi.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="utf-8">
<meta http-equiv="X-UA-Compatible" content="IE=edge">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<meta name="author" content="CatsAction" />
<meta property="og:type" content="article" />
<meta name="twitter:card" content="summary">
<meta name="keywords" content="Redis, Redis, " />
<meta property="og:title" content="Redis系列一 - 概念和数据类型"/>
<meta property="og:url" content="./redisxi-lie-yi.html" />
<meta property="og:description" content="前述 本篇讲述的内容主要是一些概念性的东西，彼此之间没有太多关联性，也不打算太深入，写的时候觉得是个知识点都会把它记录下来，后续会针对某些内容单独写篇文章，可以关注Redis系列的其它内容。 本篇的最后，泛概讲解了下Redis常见数据类型String，List， Hash，Set，ZSet的C语言结构。相关内容参考了Redis设计与实现 Redis特点 是一个单线程应用。 是一个内存中的数据结构存储系统，支持丰富数据类型。 常用作缓存，可以持久化数据到硬盘。 支持简单的消息队列协议，可用作普通的消息队列中间件。 内置Lua脚本支持。 支持事务和LRU事件。 Pub/Sub（分发和订阅） Publisher（生产者）不将消息发送给特定的Consumer（消费者），而是发送到channel（频道）。订阅相应channel的Consumer都将收到消息，Publisher往channel分发消息，它不需要知道都有哪些Consumer订阅了消息。 GeoHash原理 下面是Pub/Sub最简单的使用。 首先客户端订阅了两个channel。分别是first，second。 127.0.0.1:6379[1]> SUBSCRIBE …" />
<meta property="og:site_name" content="CatsAction's blog" />
<meta property="og:article:author" content="CatsAction" />
<meta property="og:article:published_time" content="2019-09-12T00:00:00+08:00" />
<meta name="twitter:title" content="Redis系列一 - 概念和数据类型">
<meta name="twitter:description" content="前述 本篇讲述的内容主要是一些概念性的东西，彼此之间没有太多关联性，也不打算太深入，写的时候觉得是个知识点都会把它记录下来，后续会针对某些内容单独写篇文章，可以关注Redis系列的其它内容。 本篇的最后，泛概讲解了下Redis常见数据类型String，List， Hash，Set，ZSet的C语言结构。相关内容参考了Redis设计与实现 Redis特点 是一个单线程应用。 是一个内存中的数据结构存储系统，支持丰富数据类型。 常用作缓存，可以持久化数据到硬盘。 支持简单的消息队列协议，可用作普通的消息队列中间件。 内置Lua脚本支持。 支持事务和LRU事件。 Pub/Sub（分发和订阅） Publisher（生产者）不将消息发送给特定的Consumer（消费者），而是发送到channel（频道）。订阅相应channel的Consumer都将收到消息，Publisher往channel分发消息，它不需要知道都有哪些Consumer订阅了消息。 GeoHash原理 下面是Pub/Sub最简单的使用。 首先客户端订阅了两个channel。分别是first，second。 127.0.0.1:6379[1]> SUBSCRIBE …">
<title>Redis系列一 - 概念和数据类型 ·
CatsAction's blog
</title>
<link href="//netdna.bootstrapcdn.com/twitter-bootstrap/2.3.2/css/bootstrap-combined.min.css" rel="stylesheet">
<link rel="icon" type="image/x-icon" href="./theme/image/logo.ico" />
<link rel="stylesheet" type="text/css" href="./theme/css/elegant.prod.css" media="screen">
<link rel="stylesheet" type="text/css" href="./theme/css/custom.css" media="screen">
</head>
<body>
<div id="content">
<div class="navbar navbar-static-top">
<div class="navbar-inner">
<div class="container-fluid">
<a class="btn btn-navbar" data-toggle="collapse" data-target=".nav-collapse">
<span class="icon-bar"></span>
<span class="icon-bar"></span>
<span class="icon-bar"></span>
</a>
<a class="brand" href="./"><span class=site-name>CatsAction's blog</span></a>
<div class="nav-collapse collapse">
<ul class="nav pull-right top-menu">
<li >
<a href=
.
>Home</a>
</li>
<li ><a href="./categories.html">Categories</a></li>
<li ><a href="./tags.html">Tags</a></li>
<li ><a href="./archives.html">Archives</a></li>
<li><form class="navbar-search" action="./search.html" onsubmit="return validateForm(this.elements['q'].value);"> <input type="text" class="search-query" placeholder="Search" name="q" id="tipue_search_input"></form></li>
</ul>
</div>
</div>
</div>
</div>
<div class="container-fluid">
<div class="row-fluid">
<div class="span1"></div>
<div class="span10">
<article itemscope>
<div class="row-fluid">
<header class="page-header span10 offset2">
<h1>
<a href="./redisxi-lie-yi.html">
Redis系列一
<small class="subtitle">
概念和数据类型
</small>
</a>
</h1>
</header>
</div>
<div class="row-fluid">
<div class="span8 offset2 article-content">
<h2>前述</h2>
<p>本篇讲述的内容主要是一些概念性的东西，彼此之间没有太多关联性，也不打算太深入，写的时候觉得是个知识点都会把它记录下来，后续会针对某些内容单独写篇文章，可以关注Redis系列的其它内容。</p>
<p>本篇的最后，泛概讲解了下Redis常见数据类型String，List， Hash，Set，ZSet的C语言结构。相关内容参考了<a href="https://book.douban.com/subject/25900156/">Redis设计与实现</a></p>
<h2>Redis特点</h2>
<ul>
<li>
<p>是一个单线程应用。</p>
</li>
<li>
<p>是一个内存中的数据结构存储系统，支持丰富数据类型。</p>
</li>
<li>
<p>常用作缓存，可以持久化数据到硬盘。</p>
</li>
<li>
<p>支持简单的消息队列协议，可用作普通的消息队列中间件。</p>
</li>
<li>
<p>内置Lua脚本支持。</p>
</li>
<li>
<p>支持事务和LRU事件。</p>
</li>
</ul>
<h2>Pub/Sub（分发和订阅）</h2>
<p>Publisher（生产者）不将消息发送给特定的Consumer（消费者），而是发送到channel（频道）。订阅相应channel的Consumer都将收到消息，Publisher往channel分发消息，它不需要知道都有哪些Consumer订阅了消息。</p>
<p><img alt="Redis Pub/Sub模式" src="./images/redis-pub-sub.png"></p>
<p><a href="https://zhuanlan.zhihu.com/p/35940647">GeoHash原理</a></p>
<p>下面是Pub/Sub最简单的使用。<br>
首先客户端订阅了两个channel。分别是first，second。</p>
<div class="highlight"><pre><span></span><span class="err">127.0.0.1:6379[1]> SUBSCRIBE first second</span>
<span class="err">Reading messages... (press Ctrl-C to quit)</span>
<span class="err">1) "subscribe"</span>
<span class="err">2) "first"</span>
<span class="err">3) (integer) 1</span>
<span class="err">1) "subscribe"</span>
<span class="err">2) "second"</span>
<span class="err">3) (integer) 2</span>
</pre></div>
<p>服务端Publisher分发消息</p>
<div class="highlight"><pre><span></span><span class="err">127.0.0.1:6379> PUBLISH first hello</span>
<span class="err">(integer) 1</span>
<span class="err">127.0.0.1:6379> PUBLISH second "hello redis"</span>
<span class="err">(integer) 1</span>
</pre></div>
<p>客户端将收到如下消息</p>
<div class="highlight"><pre><span></span><span class="err">1) "message"</span>
<span class="err">2) "first"</span>
<span class="err">3) "hello"</span>
<span class="err">1) "message"</span>
<span class="err">2) "second"</span>
<span class="err">3) "hello redis"</span>
</pre></div>
<h2>Pipelining模式</h2>
<p>Pipelining即管道。使用Pipelining，我们可以一次向Redis发送多个命令请求，并一次获得请求结果。Pipelining有如下优点。</p>
<ul>
<li>
<p>避免单个命令发送多次阻塞。Redis每一个命令请求，Client都会阻塞等待结果。Pipelining一次向Redis Server发送多个命令，减少了阻塞次数。</p>
</li>
<li>
<p>减少了网络RTT。Pipelining将请求和回复一次传输，减少了网络传输次数和总时间。</p>
</li>
<li>
<p>降低了Socket IO时间。对于Redis命令，请求和产生结果相对较快，而读写IO相对较慢。一次Pipelining请求只读写一次IO，这比多个命令分开请求减少了IO读写次数。<br></p>
</li>
</ul>
<h2>数据持久化</h2>
<p>Redis提供快照RDB和AOF两种持久化方式。RDB持久化方式会在一个特定的间隔保存那个时间点的一个数据快照。AOF持久化方式则会记录服务器收到的每一个写操作。在服务启动时，
重新执行这些日志重建原来的数据。</p>
<h6>RDB工作方式</h6>
<ul>
<li>
<p>Redis调用fork()，产生一个子进程。</p>
</li>
<li>
<p>子进程把数据写到一个临时的RDB文件。</p>
</li>
<li>
<p>当子进程写完新的RDB文件后，把旧的RDB文件替换掉。</p>
</li>
</ul>
<h6>RDB和AOF优缺点对比</h6>
<p>参加<a href="https://segmentfault.com/a/1190000002906345">Redis持久化</a>和官网<a href="https://redis.io/topics/persistence">Redis Persistence</a><br></p>
<h2>内存优化</h2>
<ul>
<li>
<p>Redis string数据结构没有采用C预约的string，而是自己设计了数据结构，保持了字符串长度和预分配空间。由于预分配空间的存在，会造成内存浪费，因此不要频繁的使用字符串append操作。</p>
</li>
<li>
<p>共享内存。Redis存储整数时会共享内存。但是设置maxmemory和LRU时失效，应注意相关数据和设置的优化。</p>
</li>
<li>
<p>编码优化。当对象数量和体积比较小时，Redis会使用压缩列表或整数集合存储。使用OBJECT ENCODING key查看存结构。</p>
</li>
<li>
<p>控制key数量。过多的key会造成内存浪费，可以将多个key整合到hash类型里，并保证value不超过hash-max-ziplist-value限制，这样可以利用ziplist编码。</p>
</li>
</ul>
<p>参考<a href="https://cachecloud.github.io/2017/02/16/Redis%E5%86%85%E5%AD%98%E4%BC%98%E5%8C%96/">Redis的内存优化</a>和官网<a href="https://redis.io/topics/memory-optimization">memory-optimization</a><br></p>
<p><a href="https://www.jianshu.com/p/8677603d3865">Redis内存优化</a></p>
<h2>缓存更新策略</h2>
<ul>
<li>
<p>被动删除：当读/写一个已经过期的key时，会触发惰性删除策略，直接删除掉这个过期key</p>
</li>
<li>
<p>主动删除：由于惰性删除策略无法保证冷数据被及时删掉，所以Redis会定期主动淘汰一批已过期的key</p>
</li>
<li>
<p>当前已用内存超过maxmemory限定时，触发主动清理策略</p>
</li>
</ul>
<h2>事务</h2>
<p>Redis通过MULTI、DISCARD、EXEC和WATCH四个命令来实现事务功能。Redis事务并不保证严格的事务特性，当执行错误时，并不能回滚到之前的操作。下面是Redis事务和严格事务的特性对比。</p>
<ul>
<li>
<p>原子性（Atomicity），Redis单个命令是原子性的，但是Redis事务并不保证原子性，因为执行发生错误它并不回滚。</p>
</li>
<li>
<p>一致性（Consistency），入队错误，执行错误保证一致性。</p>
</li>
<li>
<p>隔离性（Isolation），Redis是单线程，事务总是满足隔离性的。</p>
</li>
<li>
<p>持久性（Durability），持久性和是内存模式还是硬盘模式有关。内存模式重启数据丢失。<br></p>
</li>
</ul>
<h2>数据类型</h2>
<h5><em>1: string</em></h5>
<p>Redis的string类型未复用C，自定义类型SDS。类型定义如下。</p>
<div class="highlight"><pre><span></span><span class="k">struct</span> <span class="n">sdshdr</span> <span class="p">{</span>
<span class="kt">int</span> <span class="n">len</span><span class="p">;</span> <span class="c1">// 长度</span>
<span class="kt">int</span> <span class="n">free</span><span class="p">;</span> <span class="c1">// 剩余可用空间</span>
<span class="kt">char</span> <span class="n">buf</span><span class="p">[];</span> <span class="c1">// 保存字符串的数组</span>
<span class="p">};</span>
</pre></div>
<p>使用SDS有如下优点。</p>
<ul>
<li>保存了字符串长度，获取长度的时间复杂度为O(1)。</li>
<li>SDS的free可以减少字符串扩展和收索时的内存再分配次数，也可以用来避免数组溢出。</li>
<li>二进制安全，不靠'\0'判断字符串是否结束，而是字符串长度。</li>
</ul>
<h5><em>2: list</em></h5>
<p>Redis list中每个节点是一个<code>listNode</code>结构，多个<code>listNode</code>组成一个双向链表。而list结构本身保存链表的长度，头尾指针，以及三个操作函数。</p>
<div class="highlight"><pre><span></span><span class="k">typedef</span> <span class="k">struct</span> <span class="n">listNode</span> <span class="p">{</span>
<span class="k">struct</span> <span class="n">listNode</span> <span class="o">*</span><span class="n">prev</span><span class="p">;</span>
<span class="k">struct</span> <span class="n">listNode</span> <span class="o">*</span><span class="n">next</span><span class="p">;</span>
<span class="kt">void</span> <span class="o">*</span><span class="n">value</span><span class="p">;</span> <span class="c1">// 节点值保存指针</span>
<span class="p">}</span> <span class="n">listNode</span><span class="p">;</span>
<span class="k">typedef</span> <span class="k">struct</span> <span class="n">list</span> <span class="p">{</span>
<span class="n">listNode</span> <span class="o">*</span><span class="n">head</span><span class="p">;</span>
<span class="n">listNode</span> <span class="o">*</span><span class="n">tail</span><span class="p">;</span>
<span class="kt">unsigned</span> <span class="kt">long</span> <span class="n">len</span><span class="p">;</span>
<span class="kt">void</span> <span class="o">*</span><span class="p">(</span><span class="o">*</span><span class="n">dup</span><span class="p">)(</span><span class="kt">void</span> <span class="o">*</span><span class="n">ptr</span><span class="p">);</span> <span class="c1">// 节点复制函数</span>
<span class="kt">void</span> <span class="p">(</span><span class="o">*</span><span class="n">free</span><span class="p">)(</span><span class="kt">void</span> <span class="o">*</span><span class="n">ptr</span><span class="p">);</span> <span class="c1">// 节点释放函数</span>
<span class="kt">int</span> <span class="p">(</span><span class="o">*</span><span class="n">match</span><span class="p">)(</span><span class="kt">void</span> <span class="o">*</span><span class="n">ptr</span><span class="p">,</span> <span class="kt">void</span> <span class="o">*</span><span class="n">key</span><span class="p">);</span> <span class="c1">// 节点对比函数</span>
<span class="p">}</span> <span class="n">list</span><span class="p">;</span>
</pre></div>
<p>基于list结构，读取list头尾节点元素的时间复杂度为O(1)，读取list长度的时间复杂度也是O(1)。</p>
<h5><em>3: hash</em></h5>
<div class="highlight"><pre><span></span><span class="k">typedef</span> <span class="k">struct</span> <span class="n">dictht</span> <span class="p">{</span>
<span class="n">dictEntry</span> <span class="o">**</span><span class="n">table</span><span class="p">;</span> <span class="c1">// hash表数组</span>
<span class="kt">unsigned</span> <span class="kt">long</span> <span class="n">size</span><span class="p">;</span> <span class="c1">// 哈希表容量大小</span>
<span class="kt">unsigned</span> <span class="kt">long</span> <span class="n">sizemask</span><span class="p">;</span> <span class="c1">// 哈希表大小掩码，用于计算索引值</span>
<span class="kt">unsigned</span> <span class="kt">long</span> <span class="n">used</span><span class="p">;</span> <span class="c1">// 元素个数</span>
<span class="p">};</span>
<span class="n">typeof</span> <span class="k">struct</span> <span class="n">dictEntry</span><span class="p">{</span>
<span class="kt">void</span> <span class="o">*</span><span class="n">key</span><span class="p">;</span> <span class="c1">// 键</span>
<span class="k">union</span><span class="p">{</span> <span class="c1">// 值</span>
<span class="kt">void</span> <span class="o">*</span><span class="n">val</span><span class="p">;</span>
<span class="n">uint64_tu64</span><span class="p">;</span>
<span class="n">int64_ts64</span><span class="p">;</span>
<span class="p">}</span>
<span class="k">struct</span> <span class="n">dictEntry</span> <span class="o">*</span><span class="n">next</span><span class="p">;</span>
<span class="p">};</span>
</pre></div>
<p>上面是Redis hash表的定义，每个hash表元素类型为<code>dictEntry</code>，如果hash值冲突，会用next指针指向下一个<code>dictEntry</code>节点（链地址法）。</p>
<p>Redis又在dictht的基础上，又抽象了一层字典dict。</p>
<div class="highlight"><pre><span></span><span class="k">typedef</span> <span class="k">struct</span> <span class="n">dictType</span> <span class="p">{</span>
<span class="kt">uint64_t</span> <span class="p">(</span><span class="o">*</span><span class="n">hashFunction</span><span class="p">)(</span><span class="k">const</span> <span class="kt">void</span> <span class="o">*</span><span class="n">key</span><span class="p">);</span>
<span class="kt">void</span> <span class="o">*</span><span class="p">(</span><span class="o">*</span><span class="n">keyDup</span><span class="p">)(</span><span class="kt">void</span> <span class="o">*</span><span class="n">privdata</span><span class="p">,</span> <span class="k">const</span> <span class="kt">void</span> <span class="o">*</span><span class="n">key</span><span class="p">);</span>
<span class="kt">void</span> <span class="o">*</span><span class="p">(</span><span class="o">*</span><span class="n">valDup</span><span class="p">)(</span><span class="kt">void</span> <span class="o">*</span><span class="n">privdata</span><span class="p">,</span> <span class="k">const</span> <span class="kt">void</span> <span class="o">*</span><span class="n">obj</span><span class="p">);</span>
<span class="kt">int</span> <span class="p">(</span><span class="o">*</span><span class="n">keyCompare</span><span class="p">)(</span><span class="kt">void</span> <span class="o">*</span><span class="n">privdata</span><span class="p">,</span> <span class="k">const</span> <span class="kt">void</span> <span class="o">*</span><span class="n">key1</span><span class="p">,</span> <span class="k">const</span> <span class="kt">void</span> <span class="o">*</span><span class="n">key2</span><span class="p">);</span>
<span class="kt">void</span> <span class="p">(</span><span class="o">*</span><span class="n">keyDestructor</span><span class="p">)(</span><span class="kt">void</span> <span class="o">*</span><span class="n">privdata</span><span class="p">,</span> <span class="kt">void</span> <span class="o">*</span><span class="n">key</span><span class="p">);</span>
<span class="kt">void</span> <span class="p">(</span><span class="o">*</span><span class="n">valDestructor</span><span class="p">)(</span><span class="kt">void</span> <span class="o">*</span><span class="n">privdata</span><span class="p">,</span> <span class="kt">void</span> <span class="o">*</span><span class="n">obj</span><span class="p">);</span>
<span class="p">}</span> <span class="n">dictType</span><span class="p">;</span>
<span class="k">typedef</span> <span class="k">struct</span> <span class="n">dict</span> <span class="p">{</span>
<span class="n">dictType</span> <span class="o">*</span><span class="n">type</span><span class="p">;</span>
<span class="kt">void</span> <span class="o">*</span><span class="n">privdata</span><span class="p">;</span>
<span class="n">dictht</span> <span class="n">ht</span><span class="p">[</span><span class="mi">2</span><span class="p">];</span>
<span class="kt">long</span> <span class="n">rehashidx</span><span class="p">;</span> <span class="cm">/* rehashing not in progress if rehashidx == -1 */</span>
<span class="kt">unsigned</span> <span class="kt">long</span> <span class="n">iterators</span><span class="p">;</span> <span class="cm">/* number of iterators currently running */</span>
<span class="p">}</span> <span class="n">dict</span><span class="p">;</span>
</pre></div>
<p>type和privdata是针对不同类型键值对，为创建多态字典而设置的。type指向<code>dictType</code>的指针，而privdata则是传给那些类型特定函数的可选参数。</p>
<p>ht属性包含两个<code>dictht</code>元素的数组，其中ht[1]只用字rehash（hash重构）时才使用。</p>
<h5><em>4: set</em></h5>
<p>下面是整数集合的结构。如果集合包含的元素足够少，且所有成员都能表示为平台有符号范围之内的十进制整数，那么Redis会采用整数集合这种有序数组来存储集合。</p>
<div class="highlight"><pre><span></span><span class="k">typedef</span> <span class="k">struct</span> <span class="n">intset</span><span class="p">{</span>
<span class="kt">uint32_t</span> <span class="n">encoding</span><span class="p">;</span> <span class="c1">//编码方式</span>
<span class="kt">uint32_t</span> <span class="n">length</span><span class="p">;</span> <span class="c1">// 集合包含的元素数量</span>
<span class="kt">int8_t</span> <span class="n">contents</span><span class="p">[];</span> <span class="c1">//保存元素的数组 </span>
<span class="p">};</span>
</pre></div>
<p>上面的intset contents虽然定义成int8类型，但它实际存储类型根据encoding而定，可能是int16，int32，int64等。</p>
<p>对于原先所有元素都用int16表示的intset，如果新插入的元素需要int32或者int64表示，就需要对contents进行升级（重新分配更大的空间），然后将原有的元素复制到新分配的空间，再插入新元素，仍需保持intset的有序。</p>
<p>关于更多intset升级的内容，可以查看黄健宏的《Redis设计与实现》<a href="http://redisbook.com/preview/ziplist/cascade_update.html">升级</a></p>
<h5><em>5: sorted set</em></h5>
<p>有序集合的底层实现是跳跃表（skiplist），是一种有序数据结构，它通过在每个节点中维持多个指向其他节点的指针，从而达到快速查找访问节点的目的。</p>
<div class="highlight"><pre><span></span><span class="k">typedef</span> <span class="k">struct</span> <span class="n">zskiplistNode</span><span class="p">{</span>
<span class="c1">//层</span>
<span class="k">struct</span> <span class="n">zskiplistLevel</span><span class="p">{</span>
<span class="c1">//前进指针</span>
<span class="k">struct</span> <span class="n">zskiplistNode</span> <span class="o">*</span><span class="n">forward</span><span class="p">;</span>
<span class="c1">//跨度</span>
<span class="kt">unsigned</span> <span class="kt">int</span> <span class="n">span</span><span class="p">;</span>
<span class="p">}</span> <span class="n">level</span><span class="p">[];</span>
<span class="c1">//后退指针, 用于从表尾向表头方向访问节点</span>
<span class="k">struct</span> <span class="n">zskiplistNode</span> <span class="o">*</span><span class="n">backward</span><span class="p">;</span>
<span class="c1">//分值, 用于排序</span>
<span class="kt">double</span> <span class="n">score</span><span class="p">;</span>
<span class="c1">//成员对象</span>
<span class="n">robj</span> <span class="o">*</span><span class="n">obj</span><span class="p">;</span>
<span class="p">};</span>
</pre></div>
<p>跳跃表是链表的扩展，是一种快速查找结构。相比B树，红黑树等平衡二叉树，跳跃表实现简单。</p>
<p>下图是一个简单的跳跃表</p>
<p><center>
<img alt="跳跃表" src="./images/skiplist3.jpeg">
</center></p>
<p>相对于普通链表，跳跃表随机化给节点分层，增加前向指针，从而利用二分查找的优势。
跳表具有如下性质：</p>
<p>(1) 由很多层结构组成</p>
<p>(2) 每一层都是一个有序的链表</p>
<p>(3) 最底层(Level 1)的链表包含所有元素</p>
<p>(4) 如果一个元素出现在 Level i 的链表中，则它在 Level i 之下的链表也都会出现。</p>
<p>(5) 每个节点包含两个指针，一个指向同一链表中的下一个元素，一个指向下面一层的元素。</p>
<p><em>参考资料：</em></p>
<p><em><a href="https://blog.csdn.net/qpzkobe/article/details/80056807">跳跃表原理</a></em></p>
<p><em><a href="https://subetter.com/algorithm/skip-list.html">跳跃表</a></em></p>
<h5><em>6: 压缩列表（ziplist）</em></h5>
<p>在列表，散列，有序集合长度比较短或者体积比较小时，Redis可以选择用ziplist这种紧凑结构来存储这些类型。对于大小和体积，可以通过配置项修改。下面是list使用ziplist的默认配置项，hash和zset把开头的list更换也有对应的配置。</p>
<div class="highlight"><pre><span></span><span class="err">list-max-ziplist-entries 512</span>
<span class="err">list-max-ziplist-value 512</span>
</pre></div>
<p><strong>ziplist的连锁更新</strong></p>
<p>下面是压缩列表每个节点元素的构成结构。</p>
<div class="highlight"><pre><span></span><span class="p">|</span> previous_entry_length <span class="p">|</span> encoding <span class="p">|</span> content <span class="p">|</span>
</pre></div>
<p>其中previous_entry_length存储前一个元素的长度，encoding存储当前节点元素类型和长度，content存储当前节点元素内容。</p>
<p>对于previous_entry_length，当前一个元素长度小于254字节，需要1个字节来存储长度。当前一个元素长度大于等于254时，需要5字节来存储长度。</p>
<p>如上所述，Redis为了节省内存，previous_entry_length所占空间长度是根据前一个元素的长度变动的。因此，当插入一个长度大于254的元素时，就可能造成当前节点的previous_entry_length空间无法存储其长度，因此需要扩展，而这样的扩展，就可能造成下一个节点的扩展，这种现象叫ziplist的连锁更新。</p>
<p>连锁更新时间复杂度为O(N^2) ，但是触碰的几率很低。</p>
<p>关于连锁更新更详细介绍，可以查看黄健宏的《Redis设计与实现》<a href="http://redisbook.com/preview/ziplist/cascade_update.html">连锁更新</a></p>
<p>上面的配置中，entries项指定在ziplist下允许包含的元素最大数量，value指定ziplist下每个节点的最大体积。如果超过这个限制，Redis会将ziplist存储转换为对应类型通常的存储结构。</p>
<p><em>参考资料：</em></p>
<p><em><a href="https://blog.csdn.net/u013679744/article/details/79195563">Redis原理</a></em></p>
<h2>quiklist</h2>
<p>在用<code>DEBUG OBJECT</code>查看list和hash的encoding时，我们看到有一种存储类型是quiklist。它是zipList和linkedList（双向链表）的混合体，它将linkedList按段切分，每一段使用zipList来紧凑存储，多个zipList之间使用双向指针串接起来。</p>
<p>下面是一个简单的quiklist示例图。
<center>
<img alt="quicklist" src="./images/quiklist.png">
</center></p>
<p>下面是quiklist的Redis C定义。</p>
<div class="highlight"><pre><span></span><span class="k">struct</span> <span class="n">quicklist</span> <span class="p">{</span>
<span class="n">quicklistNode</span><span class="o">*</span> <span class="n">head</span><span class="p">;</span>
<span class="n">quicklistNode</span><span class="o">*</span> <span class="n">tail</span><span class="p">;</span>
<span class="kt">long</span> <span class="n">count</span><span class="p">;</span> <span class="c1">// 元素总数</span>
<span class="kt">int</span> <span class="n">nodes</span><span class="p">;</span> <span class="c1">// ziplist 节点的个数</span>
<span class="kt">int</span> <span class="n">compressDepth</span><span class="p">;</span> <span class="c1">// LZF 算法压缩深度</span>
<span class="p">...</span>
<span class="p">}</span>
<span class="k">struct</span> <span class="n">quicklistNode</span> <span class="p">{</span>
<span class="n">quicklistNode</span><span class="o">*</span> <span class="n">prev</span><span class="p">;</span>
<span class="n">quicklistNode</span><span class="o">*</span> <span class="n">next</span><span class="p">;</span>
<span class="n">ziplist</span><span class="o">*</span> <span class="n">zl</span><span class="p">;</span> <span class="c1">// 指向压缩列表</span>
<span class="n">int32</span> <span class="n">size</span><span class="p">;</span> <span class="c1">// ziplist 的字节总数</span>
<span class="n">int16</span> <span class="n">count</span><span class="p">;</span> <span class="c1">// ziplist 中的元素数量</span>
<span class="n">int2</span> <span class="n">encoding</span><span class="p">;</span> <span class="c1">// 存储形式2bit，原生字节数组还是LZF压缩存储</span>
<span class="p">...</span>
<span class="p">}</span>
</pre></div>
<p><em>参考资料</em></p>
<p><em><a href="https://www.cnblogs.com/virgosnail/p/9542470.html">quiklist</a></em></p>
<h2>后述</h2>
<p>本篇大体讲解了Redis一些常见概念和数据类型，Redis的其它系列会扩展和讲解其它知识点，下面是一些内容。</p>
<p><em><a href="./redisxi-lie-zhi.html">Redis Sentinel模式</a></em></p>
<p><em><a href="./redisxi-lie-er.html">Redis内存淘汰机制</a></em></p>
<hr />
<aside>
<nav>
<ul class="articles-timeline">
<li class="previous-article">« <a href="./mysqlxi-lie-wu.html"
title="Previous: MySQL系列五 - 分布式事务">MySQL系列五 <small class="subtitle">分布式事务</small></a></li>
<li class="next-article"><a href="./redisxi-lie-er.html"
title="Next: Redis系列二 - 内存淘汰机制">Redis系列二 <small class="subtitle">内存淘汰机制</small></a> »</li>
</ul>
</nav>
</aside>
</div>
<section id="article-sidebar" class="span2">
<h4>Published</h4>
<time itemprop="dateCreated" datetime="2019-09-12T00:00:00+08:00"> 9
12, 2019</time>
<!---->
<h4>Category</h4>
<a class="category-link"
href="./categories.html#redis-ref">Redis</a>
<h4>Tags</h4>
<ul class="list-of-tags tags-in-article">
<li><a href="./tags.html#redis-ref">Redis
<span>11</span>
</a></li>
</ul>
<h4>Stay in Touch</h4>
<div id="sidebar-social-link">
<a href="mailto:[email protected]" title="My Email Address" target="_blank" rel="nofollow noopener noreferrer">
<svg xmlns="http://www.w3.org/2000/svg" aria-label="Mail" role="img" viewBox="0 0 512 512"><rect width="512" height="512" rx="15%" fill="#328cff"/><path d="m250 186c-46 0-69 35-69 74 0 44 29 72 68 72 43 0 73-32 73-75 0-44-34-71-72-71zm-1-37c30 0 57 13 77 33 0-22 35-22 35 1v150c-1 10 10 16 16 9 25-25 54-128-14-187-64-56-149-47-195-15-48 33-79 107-49 175 33 76 126 99 182 76 28-12 41 26 12 39-45 19-168 17-225-82-38-68-36-185 67-248 78-46 182-33 244 32 66 69 62 197-2 246-28 23-71 1-71-32v-11c-20 20-47 32-77 32-57 0-108-51-108-108 0-58 51-110 108-110" fill="#fff"/></svg>
</a>
<a href="https://github.com/boyaziqi" title="catsaction Github Repository" target="_blank" rel="nofollow noopener noreferrer">
<svg xmlns="http://www.w3.org/2000/svg" aria-label="GitHub" role="img" viewBox="0 0 512 512"><rect width="512" height="512" rx="15%" fill="#1B1817"/><path fill="#fff" d="M335 499c14 0 12 17 12 17H165s-2-17 12-17c13 0 16-6 16-12l-1-50c-71 16-86-28-86-28-12-30-28-37-28-37-24-16 1-16 1-16 26 2 40 26 40 26 22 39 59 28 74 22 2-17 9-28 16-35-57-6-116-28-116-126 0-28 10-51 26-69-3-6-11-32 3-67 0 0 21-7 70 26 42-12 86-12 128 0 49-33 70-26 70-26 14 35 6 61 3 67 16 18 26 41 26 69 0 98-60 120-117 126 10 8 18 24 18 48l-1 70c0 6 3 12 16 12z"/></svg>
</a>
<a href="https://www.linkedin.com/feed/" title="My LinkedIn" target="_blank" rel="nofollow noopener noreferrer">
<svg xmlns="http://www.w3.org/2000/svg" aria-label="LinkedIn" role="img" viewBox="0 0 512 512" fill="#fff"><rect width="512" height="512" rx="15%" fill="#0077b5"/><circle cx="142" cy="138" r="37"/><path stroke="#fff" stroke-width="66" d="M244 194v198M142 194v198"/><path d="M276 282c0-20 13-40 36-40 24 0 33 18 33 45v105h66V279c0-61-32-89-76-89-34 0-51 19-59 32"/></svg>
</a>
</div>
<h4>Friendship Links</h4>
<ul class="list-of-tags tags-in-article">
<li>
<a href="https://leetcode-cn.com/" title="力扣中国站点" target="_blank" rel="nofollow noopener noreferrer">
LeetCode
</a>
</li>
<li>
<a href="https://coolshell.cn/about" title="陈皓酷壳" target="_blank" rel="nofollow noopener noreferrer">
CoolShell
</a>
</li>
<li>
<a href="https://yikun.github.io/" title="姜毅坤博客" target="_blank" rel="nofollow noopener noreferrer">
Yikun
</a>
</li>
<li>
<a href="https://www.nowcoder.com/" title="牛客网" target="_blank" rel="nofollow noopener noreferrer">
牛客网
</a>
</li>
</ul>
</section>
</div>
</article>
</div>
<div class="span1"></div>
</div>
</div>
</div>
<footer>
<div>
<span class="site-name">CatsAction's blog</span> - It's a wonderful world
</div>
<div id="fpowered">
Powered by: <a href="http://getpelican.com/" title="Pelican Home Page" target="_blank" rel="nofollow noopener noreferrer">Pelican</a>
Theme: <a href="https://elegant.oncrashreboot.com/" title="Theme Elegant Home Page" target="_blank" rel="nofollow noopener noreferrer">Elegant</a>
</div>
</footer> <script src="//code.jquery.com/jquery.min.js"></script>
<script src="//netdna.bootstrapcdn.com/twitter-bootstrap/2.3.2/js/bootstrap.min.js"></script>
<script>
function validateForm(query)
{
return (query.length > 0);
}
</script>
<script>
(function () {
if (window.location.hash.match(/^#comment-\d+$/)) {
$('#comment_thread').collapse('show');
}
})();
window.onhashchange=function(){
if (window.location.hash.match(/^#comment-\d+$/))
window.location.reload(true);
}
$('#comment_thread').on('shown', function () {
var link = document.getElementById('comment-accordion-toggle');
var old_innerHTML = link.innerHTML;
$(link).fadeOut(200, function() {
$(this).text('Click here to hide comments').fadeIn(200);
});
$('#comment_thread').on('hidden', function () {
$(link).fadeOut(200, function() {
$(this).text(old_innerHTML).fadeIn(200);
});
})
})
</script>
</body>
<!-- Theme: Elegant built for Pelican
License : MIT -->
</html>