-
Notifications
You must be signed in to change notification settings - Fork 2
/
Copy pathsummary
4560 lines (4331 loc) · 341 KB
/
summary
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
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
################
Redis 引发的问题:
1、缓存雪崩
如果缓存数据设置的过期时间是相同的,并且Redis恰好将这部分数据全部删光了。这就会导致在这段时间内,这些缓存同时失效,全部请求到数据库中。
采用的是惰性删除+定期删除两种策略对过期键删除。
缓存的时候给过期时间加上一个随机值。
如何解决缓存雪崩:
事发前:实现Redis的高可用(主从架构+Sentinel 或者Redis Cluster),尽量避免Redis挂掉这种情况发生。
主从架构+Sentinel:
https://www.cnblogs.com/kevingrace/p/9004460.html
Redis Cluster:
事发中:万一Redis真的挂了,我们可以设置本地缓存(ehcache) + 限流(hystrix),尽量避免我们的数据库被干掉(起码能保证我们的服务还是能正常工作的)。
本地缓存(ehcache,一般 Redis作为一级缓存, ehcache作为二级缓存): https://blog.csdn.net/qq_34898847/article/details/89762974
缓存数据有两级:内存和磁盘,因此无需担心容量问题
缓存数据会在虚拟机重启的过程中写入磁盘。
其核心是CacheManager,一切Ehcache的应用都是从CacheManager开始的。它是用来管理Cache(缓存)的,一个应用可以有多个CacheManager,而一个CacheManager下又可以有多个Cache。Cache内部保存的是一个个的Element,而一个Element中保存的是一个key和value的配对,相当于Map里面的一个Entry。
Ehcache缓存过期策略:
FIFO、LRU、LFU
限流(hystrix):
事发后:redis持久化,重启后自动从磁盘上加载数据,快速恢复缓存数据。
如何快速恢复缓存数据:
RDB和AOF持久化机制
2、缓存穿透
查询一个一定不存在的数据。由于缓存不命中,并且出于容错考虑,如果从数据库查不到数据则不写入缓存,这将导致这个不存在的数据每次请求都要到数据库去查询,失去了缓存的意义。
解决缓存穿透也有两种方案:
a、由于请求的参数是不合法的(每次都请求不存在的参数),于是我们可以使用布隆过滤器(BloomFilter)或者压缩filter提前拦截,不合法就不让这个请求到数据库层!
布隆过滤器实现(布隆过滤器是哈希表和位图的结合):
将所有可能存在的数据缓存放到布隆过滤器中,当黑客访问不存在的缓存时迅速返回避免缓存及DB挂掉。
guava实现:com.google.guava-guava
b、当我们从数据库找不到的时候,我们也将这个空对象设置到缓存里边去。下次再请求的时候,就可以从缓存里边获取了。一般会将空对象设置一个较短的过期时间。
但这样会把所有key都存下来,浪费大量内存空间,最后触发redis的缓存淘汰策略。
3、缓存与数据库双写一致
a、为什么是先删除缓存再更新数据库,而不是反过来?
b、https://blog.51cto.com/14230003/2363051
################
Object类(7个native方法、3个wait()方法、个一个静态方法块、一个equals、一个finalize):
public class Object {
private static native void registerNatives();
static {
registerNatives();
}
public final native Class<?> getClass();
public native int hashCode();
public boolean equals(Object obj) {
return (this == obj);
}
/**
* 浅拷贝 和 深拷贝
*/
protected native Object clone() throws CloneNotSupportedException;
/**
* 该字符串由类名(对象是该类的一个实例)、标记符“@”和此对象哈希码的无符号十六进制表示组成。
*/
public String toString() {
return getClass().getName() + "@" + Integer.toHexString(hashCode());
}
/*唤醒在此对象监视器上等待的单个线程。*/
public final native void notify();
/*唤醒在此对象监视器上等待的所有线程。*/
public final native void notifyAll();
public final native void wait(long timeout) throws InterruptedException;
public final void wait(long timeout, int nanos) throws InterruptedException {
if (timeout < 0) {
throw new IllegalArgumentException("timeout value is negative");
}
if (nanos < 0 || nanos > 999999) {
throw new IllegalArgumentException(
"nanosecond timeout value out of range");
}
if (nanos > 0) {
timeout++;
}
wait(timeout);
}
public final void wait() throws InterruptedException {
wait(0);
}
/**
* 垃圾回收器准备释放内存的时候,会先调用finalize()。
*/
protected void finalize() throws Throwable { }
}
################
map: merge、compute、computeIfAbsent、computeIfPresent、getOrDefault
################
一致性哈希(常用于负载均衡)
具体实现:
一致性哈希将整个哈希值空间组织成一个虚拟的圆环,可以选择服务器的ip或主机名作为关键字进行哈希,这样每台机器就能确定其在哈希环上的位置,将数据key使用相同的函数H计算出哈希值h确定此数据在环上的位置,
从此位置沿环顺时针“行走”,第一台遇到的服务器就是其应该定位到的服务器。
容错性和可扩展性:
容错性-如果一台服务器不可用,则受影响的数据仅仅是此服务器到其环空间中前一台服务器(即顺着逆时针方向行走遇到的第一台服务器)之间数据,其它不会受到影响。
可扩展性-如果增加一台服务器,则受影响的数据仅仅是新服务器到其环空间中前一台服务器(即顺着逆时针方向行走遇到的第一台服务器)之间数据,其它不会受到影响。
虚拟节点:
一致性哈希算法在服务节点太少时,容易因为节点分部不均匀而造成数据倾斜问题。一致性哈希算法引入了虚拟节点机制,即对每一个服务节点计算多个哈希,每个计算结果位置都放置一个此服务节点,称为虚拟节点。
具体做法可以在服务器ip或主机名的后面增加编号来实现。
代码实现:
import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;
import java.util.Collection;
import java.util.SortedMap;
import java.util.TreeMap;
public class ConsistentHash<T> {
HashFunc hashFunc; // Hash计算对象,用于自定义hash算法
private final int numberOfReplicas; // 复制的节点个数
private final SortedMap<Long, T> circle = new TreeMap<>(); // 一致性Hash环
/**
* 构造,使用Java默认的Hash算法
* @param numberOfReplicas 复制的节点个数,增加每个节点的复制节点有利于负载均衡
* @param nodes 节点对象
*/
public ConsistentHash(int numberOfReplicas, Collection<T> nodes) {
this.numberOfReplicas = numberOfReplicas;
this.hashFunc = new HashFunc() {
@Override
public Long hash(Object key) {
// return fnv1HashingAlg(key.toString());
return md5HashingAlg(key.toString());
}
};
//初始化节点
for (T node : nodes) {
add(node);
}
}
/**
* 构造
* @param hashFunc hash算法对象
* @param numberOfReplicas 复制的节点个数,增加每个节点的复制节点有利于负载均衡
* @param nodes 节点对象
*/
public ConsistentHash(HashFunc hashFunc, int numberOfReplicas, Collection<T> nodes) {
this.numberOfReplicas = numberOfReplicas;
this.hashFunc = hashFunc;
//初始化节点
for (T node : nodes) {
add(node);
}
}
/**
* 增加节点<br>
* 每增加一个节点,就会在闭环上增加给定复制节点数<br>
* 例如复制节点数是2,则每调用此方法一次,增加两个虚拟节点,这两个节点指向同一Node
* 由于hash算法会调用node的toString方法,故按照toString去重
*
* @param node 节点对象
*/
public void add(T node) {
for (int i = 0; i < numberOfReplicas; i++) {
circle.put(hashFunc.hash(node.toString() + i), node);
}
}
/**
* 移除节点的同时移除相应的虚拟节点
*
* @param node 节点对象
*/
public void remove(T node) {
for (int i = 0; i < numberOfReplicas; i++) {
circle.remove(hashFunc.hash(node.toString() + i));
}
}
/**
* 获得一个最近的顺时针节点
*
* @param key 为给定键取Hash,取得顺时针方向上最近的一个虚拟节点对应的实际节点
* @return 节点对象
*/
public T get(Object key) {
if (circle.isEmpty()) {
return null;
}
long hash = hashFunc.hash(key);
if (!circle.containsKey(hash)) {
SortedMap<Long, T> tailMap = circle.tailMap(hash); //返回此映射的部分视图,其键大于等于 hash
hash = tailMap.isEmpty() ? circle.firstKey() : tailMap.firstKey();
}
//正好命中
return circle.get(hash);
}
/**
* 使用MD5算法
* @param key
* @return
*/
private static long md5HashingAlg(String key) {
MessageDigest md5 = null;
try {
md5 = MessageDigest.getInstance("MD5");
md5.reset();
md5.update(key.getBytes());
byte[] bKey = md5.digest();
long res = ((long) (bKey[3] & 0xFF) << 24) | ((long) (bKey[2] & 0xFF) << 16) | ((long) (bKey[1] & 0xFF) << 8)| (long) (bKey[0] & 0xFF);
return res;
} catch (NoSuchAlgorithmException e) {
e.printStackTrace();
}
return 0l;
}
/**
* 使用FNV1hash算法
* @param key
* @return
*/
private static long fnv1HashingAlg(String key) {
final int p = 16777619;
int hash = (int) 2166136261L;
for (int i = 0; i < key.length(); i++)
hash = (hash ^ key.charAt(i)) * p;
hash += hash << 13;
hash ^= hash >> 7;
hash += hash << 3;
hash ^= hash >> 17;
hash += hash << 5;
return hash;
}
/**
* Hash算法对象,用于自定义hash算法
*/
public interface HashFunc {
public Long hash(Object key);
}
}
################
排序:Collections.sort(consumeDetialList, Comparator.comparing(ConsumeDetialVO::getParse));
################
重复数据合并:Map<String,List<ActMarketTagKeyDTO>> collect = tagKeyDTOS.stream().collect(Collectors.groupingBy(ActMarketTagKeyDTO::getActKey));
################
InnoDB存储引擎中有页(Page)的概念,页是其磁盘管理的最小单位。InnoDB存储引擎中默认每个页的大小为16KB, 可通过参数innodb_page_size将页的大小设置为4K、8K、16K,在MySQL中可通过如下命令查看页的大小:
show variables like 'innodb_page_size';
################
<? extends E>
<? super E>
################
zookeeper 都有哪些应用场景?
分布式协调:
这个其实是 zookeeper 很经典的一个用法,简单来说,就好比,你 A 系统发送个请求到 mq,然后 B 系统消息消费之后处理了。那 A 系统如何知道 B 系统的处理结果?用 zookeeper
就可以实现分布式系统之间的协调工作。A 系统发送请求之后可以在 zookeeper 上对某个节点的值注册个监听器,一旦 B 系统处理完了就修改 zookeeper 那个节点的值,A 系统立马就可以收到通知,完美解决。
分布式锁
元数据/配置信息管理
zookeeper 可以用作很多系统的配置信息的管理,比如 kafka、storm 等等很多分布式系统都会选用 zookeeper 来做一些元数据、配置信息的管理,包括 dubbo 注册中心不也支持 zookeeper 么?
HA高可用性
这个应该是很常见的,比如 hadoop、hdfs、yarn 等很多大数据系统,都选择基于 zookeeper 来开发 HA 高可用机制,就是一个重要进程一般会做主备两个,主进程挂了立马通过 zookeeper 感知到切换到备用进程。
################
豆瓣书单:
https://book.douban.com/subject/26792439/
https://book.douban.com/subject/26912767/
https://book.douban.com/subject/26941639/
https://book.douban.com/subject/30335935/comments/
https://book.douban.com/subject/30231515/comments/hot?p=3
################
https://mp.weixin.qq.com/s?__biz=MzI4Njc5NjM1NQ==&mid=2247489683&idx=1&sn=8c1833a1c8a64c9230de772243dc472c&chksm=ebd627bfdca1aea9119ee327099531ce88108104ba78e0db27b8a9f4012fd249484a0f95bb4d&mpshare=1&scene=1&srcid=&sharer_sharetime=1568603345220&sharer_shareid=db798041d94b69fbcc5d91e179481c7a&key=2609303a4cd567e303c9e7373854b44df9fa8058e59174ff3f07b9c1a952964db45da9c296652b2ef135737e3da2f8458028dd9c67cdc927bdb4b67513f497ecab72c90a1f50c94b98f696ae2b784401&ascene=1&uin=MTE3MjAzNzc0MA%3D%3D&devicetype=Windows+7&version=62060833&lang=zh_CN&pass_ticket=IUGc8tYF7PU53RkiZq1d9qoUuuO%2F0R48igsSkF8y%2BWbYguRbUW7Q101rcvOXUYVo
SpringBoot 启动过程
SpringBoot 自动配置原理
ApplicationContextAware: 当一个类实现了这个接口(ApplicationContextAware)之后,这个类就可以方便获得ApplicationContext中的所有bean。换句话说,就是这个类可以直接获取spring配置文件中,所有有引用到的bean对象·
################
零内存拷贝(https://juejin.im/post/5c1b285de51d452f6028a98d)
零拷贝就是一种避免 CPU 将数据从一块存储拷贝到另外一块存储的技术。
零拷贝技术通过减少数据拷贝次数,简化协议处理的层次,在应用程序和网络之间提供更快的数据传输方法,从而可以有效地降低通信延迟,提高网络吞吐率。零拷贝技术是实现主机或者路由器等设备高速网络接口的主要技术之一。
硬件和软件之间的数据传输可以通过使用 DMA 来进行,DMA 进行数据传输的过程中几乎不需要 CPU 参与。
1).避免数据拷贝:
a).避免操作系统内核缓冲区之间进行数据拷贝操作。
b).避免操作系统内核和用户应用程序地址空间这两者之间进行数据拷贝操作。
c).用户应用程序可以避开操作系统直接访问硬件存储。
d).数据传输尽量让 DMA 来做。
2).Linux 中的零拷贝技术主要有下面这几种:
a).直接 I/O:
对于这种数据传输方式来说,应用程序可以直接访问硬件存储,操作系统内核只是辅助数据传输:这类零拷贝技术针对的是操作系统内核并不需要对数据进行直接处理的情况,
数据可以在应用程序地址空间的缓冲区和磁盘之间直接进行传输,完全不需要 Linux 操作系统内核提供的页缓存的支持。
b).在数据传输的过程中,避免数据在操作系统内核地址空间的缓冲区和用户应用程序地址空间的缓冲区之间进行拷贝:
有的时候,应用程序在数据进行传输的过程中不需要对数据进行访问,那么,将数据从 Linux 的页缓存拷贝到用户进程的缓冲区中就可以完全避免,传输的数据在页缓存中就可以得到处理。在某些特殊的情况下,
这种零拷贝技术可以获得较好的性能。Linux 中提供类似的系统调用主要有 mmap(),sendfile() 以及 splice()。
c).对数据在 Linux 的页缓存和用户进程的缓冲区之间的传输过程进行优化:
该零拷贝技术侧重于灵活地处理数据在用户进程的缓冲区和操作系统的页缓存之间的拷贝操作。这种方法延续了传统的通信方式,但是更加灵活。在Linux中,该方法主要利用了写时复制技术。
###############################面试题###############################
1、生产环境中的redis是怎么部署的?
面试官心里分析
看看你了解不了解你们公司的redis生产集群的部署架构,如果你不了解,那么确实你就很失职了,你的redis是主从架构?集群架构?用了哪种集群方案?有没有做高可用保证?有没有开启持久化机制确保可以进行数据恢复?
线上redis给几个G的内存?设置了哪些参数?压测后你们redis集群承载多少QPS?
兄弟,这些你必须是门儿清的,否则你确实是没好好思考过
面试题剖析
redis cluster,10台机器,5台机器部署了redis主实例,另外5台机器部署了redis的从实例,每个主实例挂了一个从实例,5个节点对外提供读写服务,每个节点的读写高峰qps可能可以达到每秒5万,5台机器最多是25万读写请求/s。
机器是什么配置?
32G内存+8核CPU+1T磁盘,但是分配给redis进程的是10g内存,一般线上生产环境,redis的内存尽量不要超过10g,超过10g可能会有问题。5台机器对外提供读写,一共有50g内存。
因为每个主实例都挂了一个从实例,所以是高可用的,任何一个主实例宕机,都会自动故障迁移,redis从实例会自动变成主实例继续提供读写服务
你往内存里写的是什么数据?每条数据的大小是多少?
商品数据,每条数据是10kb。100条数据是1mb,10万条数据是1g。常驻内存的是200万条商品数据,占用内存是20g,仅仅不到总内存的50%。目前高峰期每秒就是3500左右的请求量。
2、redis 集群模式的工作原理能说一下么?在集群模式下,redis 的 key 是如何寻址的?分布式寻址都有哪些算法?了解一致性 hash 算法吗?
1).redis cluster 集群模式:
a).Redis Cluster 是 Redis 的分布式解决方案。
当遇到单机内存、并发、流量等瓶颈时,可以采用Cluster架构达到负载均衡的目的。
分布式集群首要解决把整个数据集按照分区规则映射到多个节点的问题,即把数据集划分到多个节点上,每个节点负责整个数据的一个子集。
数据自动分片:
aa).redis 的 key 是如何寻址的 ——> hash slot算法:
redis cluster 有固定的 16384(2的14次方) 个 hash slot,对每个 key 计算 CRC16 值,然后对 16384 取模,可以获取 key 对应的 hash slot。redis cluster 中每个 master 都会持有部分 slot
任何一台机器宕机,另外两个节点,不影响的。因为 key 找的是 hash slot,不是机器。
bb).分布式寻址都有哪些算法:
hash 算法(大量缓存重建)
一致性 hash 算法(自动缓存迁移)+ 虚拟节点(自动负载均衡)
具体实现:
一致性哈希将整个哈希值空间组织成一个虚拟的圆环,可以选择服务器的ip或主机名作为关键字进行哈希,这样每台机器就能确定其在哈希环上的位置,将数据key使用相同的函数H计算出哈希值h确定此数据在环上的位置,
从此位置沿环顺时针“行走”,第一台遇到的服务器就是其应该定位到的服务器。
容错性和可扩展性:
容错性-如果一台服务器不可用,则受影响的数据仅仅是此服务器到其环空间中前一台服务器(即顺着逆时针方向行走遇到的第一台服务器)之间数据,其它不会受到影响。
可扩展性-如果增加一台服务器,则受影响的数据仅仅是新服务器到其环空间中前一台服务器(即顺着逆时针方向行走遇到的第一台服务器)之间数据,其它不会受到影响。
虚拟节点:
一致性哈希算法在服务节点太少时,容易因为节点分部不均匀而造成数据倾斜问题。一致性哈希算法引入了虚拟节点机制,即对每一个服务节点计算多个哈希,每个计算结果位置都放置一个此服务节点,称为虚拟节点。
具体做法可以在服务器ip或主机名的后面增加编号来实现。
redis cluster 的 hash slot 算法
b).hash tags 功能:
通过hash tag功能可以将多个不同key映射到同一个slot上,这样就能够提供 multi-key 操作
c).通过 gossip 协议来进行节点之间通信:
aa).所有节点都持有一份元数据,不同的节点如果出现了元数据的变更,就不断将元数据发送给其它的节点,让其它节点也进行元数据的变更。
bb).gossip 协议好处在于,元数据的更新比较分散,不是集中在一个地方,更新请求会陆陆续续打到所有节点上去更新,降低了压力;不好在于,元数据的更新有延时,可能导致集群中的一些操作会有一些滞后。
cc).每个节点都有一个专门用于节点间通信的端口,就是自己提供服务的端口号+10000,比如 7001,那么用于节点间通信的就是 17001 端口。
dd).每个节点每隔一段时间都会往另外几个节点发送 ping 消息,同时其它几个节点接收到 ping 之后返回 pong。
ee).交换的信息:
信息包括故障信息,节点的增加和删除,hash slot 信息等等。
ff).gossip 协议:
gossip 协议包含多种消息,包含 ping,pong,meet,fail 等等:
meet:某个节点发送 meet 给新加入的节点,让新节点加入集群中,然后新节点就会开始与其它节点进行通信。其实内部就是发送了一个 gossip meet 消息给新加入的节点,通知那个节点去加入我们的集群。
ping:每个节点都会频繁给其它节点发送 ping,其中包含自己的状态还有自己维护的集群元数据,互相通过 ping 交换元数据。
每个节点每秒会执行 10 次 ping,每次会选择 5 个最久没有通信的其它节点。当然如果发现某个节点通信延时达到了 cluster_node_timeout / 2,那么立即发送 ping,避免数据交换延时过长,落后的时间太长了。
pong:返回 ping 和 meeet,包含自己的状态和其它信息,也用于信息广播和更新。
fail:某个节点判断另一个节点 fail 之后,就发送 fail 给其它节点,通知其它节点说,某个节点宕机啦。
2).redis cluster 的高可用与主备切换原理:
redis cluster 功能强大,直接集成了 replication 和 sentinel 的功能。
判断节点宕机:
如果一个节点认为另外一个节点宕机,那么就是 pfail,主观宕机。如果多个节点都认为另外一个节点宕机了,那么就是 fail,客观宕机,跟哨兵的原理几乎一样,sdown,odown。
在 cluster-node-timeout 内,某个节点一直没有返回 pong,那么就被认为 pfail。
如果一个节点认为某个节点 pfail 了,那么会在 gossip ping 消息中,ping 给其他节点,如果超过半数的节点都认为 pfail 了,那么就会变成 fail。
从节点过滤:
对宕机的 master node,从其所有的 slave node 中,选择一个切换成 master node。
检查每个 slave node 与 master node 断开连接的时间,如果超过了 cluster-node-timeout * cluster-slave-validity-factor,那么就没有资格切换成 master。
从节点选举:
每个从节点,都根据自己对 master 复制数据的 offset,来设置一个选举时间,offset 越大(复制数据越多)的从节点,选举时间越靠前,优先进行选举。
所有的 master node 开始 slave 选举投票,给要进行选举的 slave 进行投票,如果大部分 master node(N/2 + 1)都投票给了某个从节点,那么选举通过,那个从节点可以切换成 master。
3).为什么Redis集群有16384个槽:
https://www.cnblogs.com/rjzheng/p/11430592.html
3、redis 的持久化有哪几种方式?不同的持久化机制都有什么优缺点?持久化机制具体底层是如何实现的?什么是多路复用,原理是什么?
首先,为什么要持久化:
宕机后重启保证数据不丢失,也就是灾难恢复、数据恢复,如果丢失会出现什么问题?大量的请求过来,缓存全部无法命中,在 redis 里根本找不到数据,这个时候就死定了,出现缓存雪崩问题。一下 mysql 承接高并发,然后就挂了...
1).持久化有哪几种方式:
持久化机制有两种,第一种是快照(DDB snapshot),第二种是 AOF 日志,以 append-only 的模式写入一个日志文件中。快照是一次全量备份,AOF 日志是连续的增量备份。快照是内存数据的二进制序列化形式,在存储上非常紧凑,
而 AOF 日志记录的是内存数据修改的指令记录文本。 AOF 日志在长期的运行过程中会变的无比庞大,数据库重启时需要加载 AOF 日志进行指令重放,这个时间就会无比漫长。所以需要定期进行 AOF 重写,给 AOF 日志进行瘦身。
2).不同的持久化机制都有什么优缺点:
RDB 快照:
a).通过开启子进程的方式进行的,它是一个比较耗资源的操作。遍历整个内存,大块写磁盘会加重系统负载。
b).RDB 会生成多个数据文件,每个数据文件都代表了某一个时刻中 redis 的数据,这种多个数据文件的方式,非常适合做冷备,可以将这种完整的数据文件发送到一些远程的安全存储上去,
比如说 Amazon 的 S3 云服务上去,在国内可以是阿里云的 ODPS 分布式存储上,以预定好的备份策略来定期备份 redis 中的数据。
c).RDB 对 redis 对外提供的读写服务,影响非常小,可以让 redis 保持高性能,因为 redis 主进程只需要 fork 一个子进程,让子进程执行磁盘 IO 操作来进行 RDB 持久化即可。
d).相对于 AOF 持久化机制来说,直接基于 RDB 数据文件来重启和恢复 redis 进程,更加快速。
e).如果想要在 redis 故障时,尽可能少的丢失数据,那么 RDB 没有 AOF 好。一般来说,RDB 数据快照文件,都是每隔 5 分钟,或者更长时间生成一次,这个时候就得接受一旦 redis 进程宕机,
那么会丢失最近 5 分钟的数据。
f).RDB 每次在 fork 子进程来执行 RDB 快照数据文件生成的时候,如果数据文件特别大,可能会导致对客户端提供的服务暂停数毫秒,或者甚至数秒。
AOF:
fsync 是一个耗时的 IO 操作,它会降低 Redis 性能,同时也会增加系统 IO 负担。
a).AOF 可以更好的保护数据不丢失,一般 AOF 会每隔 1 秒,通过一个后台线程执行一次fsync操作,最多丢失 1 秒钟的数据。
b).AOF 日志文件以 append-only 模式写入,所以没有任何磁盘寻址的开销,写入性能非常高,而且文件不容易破损,即使文件尾部破损,也很容易修复。
c).AOF 日志文件即使过大的时候,出现后台重写操作,也不会影响客户端的读写。因为在 rewrite log 的时候,会对其中的指令进行压缩,创建出一份需要恢复数据的最小日志出来。
在创建新日志文件的时候,老的日志文件还是照常写入。当新的 merge 后的日志文件 ready 的时候,再交换新老日志文件即可。
d).AOF 日志文件的命令通过非常可读的方式进行记录,这个特性非常适合做灾难性的误删除的紧急恢复。比如某人不小心用 flushall 命令清空了所有数据,只要这个时候后台 rewrite 还没有发生,
那么就可以立即拷贝 AOF 文件,将最后一条 flushall 命令给删了,然后再将该 AOF 文件放回去,就可以通过恢复机制,自动恢复所有数据。
e).对于同一份数据来说,AOF 日志文件通常比 RDB 数据快照文件更大。
f).AOF 开启后,支持的写 QPS 会比 RDB 支持的写 QPS 低,因为 AOF 一般会配置成每秒 fsync 一次日志文件,当然,每秒一次 fsync,性能也还是很高的。(如果实时写入,那么 QPS 会大降,redis 性能会大大降低)
g).以前 AOF 发生过 bug,就是通过 AOF 记录的日志,进行数据恢复的时候,没有恢复一模一样的数据出来。所以说,类似 AOF 这种较为复杂的基于命令日志 / merge / 回放的方式,
比基于 RDB 每次持久化一份完整的数据快照文件的方式,更加脆弱一些,容易有 bug。不过 AOF 就是为了避免 rewrite 过程导致的 bug,因此每次 rewrite 并不是基于旧的指令日志进行 merge 的,
而是基于当时内存中的数据进行指令的重新构建,这样健壮性会好很多。
通常 Redis 的主节点是不会进行持久化操作,持久化操作主要在从节点进行。从节点是备份节点,没有来自客户端请求的压力,它的操作系统资源往往比较充沛。
但是如果出现网络分区,从节点长期连不上主节点,就会出现数据不一致的问题,特别是在网络分区出现的情况下又不小心主节点宕机了,那么数据就会丢失,所以在生产环境要
做好实时监控工作,保证网络畅通或者能快速修复。另外还应该再增加一个从节点以降低网络分区的概率,只要有一个从节点数据同步正常,数据也就不会轻易丢失。
混合持久化:
重启 Redis 时,我们很少使用 rdb 来恢复内存状态,因为会丢失大量数据。我们通常使用 AOF 日志重放,但是重放 AOF 日志性能相对 rdb 来说要慢很多,这样在 Redis 实例很大的情况下,启动需要花费很长的时间。
混合持久化将 rdb 文件的内容和增量的 AOF 日志文件存在一起。这里的 AOF 日志不再是全量的日志,而是自持久化开始到持久化结束的这段时间发生的增量 AOF 日志,通常这部分 AOF 日志很小。
于是在 Redis 重启的时候,可以先加载 rdb 的内容,然后再重放增量 AOF 日志就可以完全替代之前的 AOF 全量文件重放,重启效率因此大幅得到提升。
3).持久化机制具体底层是如何实现的:
RDB 实现原理:
在服务线上请求的同时, Redis 还需要进行内存快照,内存快照要求 Redis 必须进行文件 IO 操作,可文件 IO 操作是不能使用多路复用 API。
这意味着单线程同时在服务线上的请求还要进行文件 IO 操作,文件 IO 操作会严重拖垮服务器请求的性能。还有个重要的问题是为了不阻塞线上的业务,就需要边持久化边响应客户端请求。
持久化的同时,内存数据结构还在改变,比如一个大型的 hash 字典正在持久化,结果一个请求过来把它给删掉了,还没持久化完呢,这尼玛要怎么搞?
Redis 使用操作系统的多进程 COW(Copy On Write) 机制来实现快照持久化。
fork(多进程):
持久化时会调用 glibc 的函数 fork 产生一个子进程,快照持久化完全交给子进程来处理,父进程继续处理客户端请求。子进程刚刚产生时,它和父进程共享内存里面的代码段和数据段。
这时可以将父子进程想像成一个连体婴儿,共享身体。这是 Linux 操作系统的机制,为了节约内存资源,所以尽可能让它们共享起来。在进程分离的一瞬间,内存的增长几乎没有明显变化。
子进程做数据持久化,它不会修改现有的内存数据结构,它只是对数据结构进行遍历读取,然后序列化写到磁盘中。但是父进程不一样,它必须持续服务客户端请求,然后对内存数据结构进行不间断的修改。
这个时候就会使用操作系统的 COW 机制来进行数据段页面的分离。数据段是由很多操作系统的页面组合而成,当父进程对其中一个页面的数据进行修改时,会将被共享的页面复制一份分离出来,然后对这个复制的页面进行修改。
这时子进程相应的页面是没有变化的,还是进程产生时那一瞬间的数据。
随着父进程修改操作的持续进行,越来越多的共享页面被分离出来,内存就会持续增长。但是也不会超过原有数据内存的 2 倍大小。另外一个 Redis 实例里冷数据占的比例往往是比较高的,
所以很少会出现所有的页面都会被分离,被分离的往往只有其中一部分页面。每个页面的大小只有 4K,一个 Redis 实例里面一般都会有成千上万的页面。子进程因为数据没有变化,
它能看到的内存里的数据在进程产生的一瞬间就凝固了,再也不会改变,这也是为什么 Redis 的持久化叫「快照」的原因。接下来子进程就可以非常安心的遍历数据了进行序列化写磁盘了。
AOF 实现原理:
AOF 日志存储的是 Redis 服务器的顺序指令序列, AOF 日志只记录对内存进行修改的指令记录。(重放)
Redis 会在收到客户端修改指令后,先进行参数校验,如果没问题,就立即将该指令文本存储到 AOF 日志中,也就是先存到磁盘,然后再执行指令。这样即使遇到突发宕机,已经存储到 AOF 日志的指令进行重放一下就可以恢复到宕机前的状态。
长期运行——>AOF 日志文件增长——>宕机重启——>重放耗时——>长时无法对外提供服务,所以需要对 AOF 日志瘦身。
AOF 重写:
Redis 提供了 bgrewriteaof 指令用于对 AOF 日志进行瘦身。其原理就是开辟一个子进程对内存进行遍历转换成一系列 Redis 的操作指令,序列化到一个新的 AOF 日志文件中。
序列化完毕后再将操作期间发生的增量 AOF 日志追加到这个新的 AOF 日志文件中,追加完毕后就立即替代旧的 AOF 日志文件了,瘦身工作就完成了。
fsync:
AOF 日志是以文件的形式存在的,当程序对 AOF 日志文件进行写操作时,实际上是将内容写到了内核为文件描述符分配的一个内存缓存中,然后内核会异步将脏数据刷回到磁盘
的。这就意味着如果机器突然宕机, AOF 日志内容可能还没有来得及完全刷到磁盘中,这个时候就会出现日志丢失。
Linux 的 glibc 提供了 fsync(int fd)函数可以将指定文件的内容强制从内核缓存刷到磁盘。只要 Redis 进程实时调用 fsync 函数就可以保证 aof 日志不丢失。但是 fsync 是一个
磁盘 IO 操作,它很慢!如果 Redis 执行一条指令就要 fsync 一次,那么 Redis 高性能的地位就不保了。所以在生产环境的服务器中, Redis 通常是每隔 1s 左右执行一次 fsync 操作,周期 1s 是可以配置的。
这是在数据安全性和性能之间做了一个折中,在保持高性能的同时,尽可能使得数据少丢失。
4).什么是多路复用,原理是什么:
https://www.jianshu.com/p/dfd940e7fca2
4.Redis的同步机制了解么?
主从复制是 Redis 分布式的基础, Redis 的高可用离开了主从复制将无从进行。Redis 的集群模式,都依赖于主从复制。不过复制功能也不是必须的,如果你将 Redis 只用来做缓存,跟 memcache 一样来对
待,也就无需要从库做备份,挂掉了重新启动一下就行。但是只要你使用了 Redis 的持久化功能,就必须认真对待主从复制,它是系统数据安全的基础保障。很多企业都没有使用到 Redis 的集群,但是至少都做了主从。
分布式系统的理论基石——CAP 原理:
C - Consistent, 一致性
A - Availability, 可用性
P - Partition tolerance,分区容忍性
分布式系统的节点往往都是分布在不同的机器上进行网络隔离开的,这意味着必然会有网络断开的风险,这个网络断开的场景的专业词汇叫着「网络分区」。
在网络分区发生时,两个分布式节点之间无法进行通信,我们对一个节点进行的修改操作将无法同步到另外一个节点,所以数据的「一致性」将无法满足,因为两个分布式节点的
数据不再保持一致。除非我们牺牲「可用性」,也就是暂停分布式节点服务,在网络分区发生时,不再提供修改数据的功能,直到网络状况完全恢复正常再继续对外提供服务。
一句话概括 CAP 原理就是——网络分区发生时,一致性和可用性两难全。
最终一致:
Redis 的主从数据是异步同步的,所以分布式的 Redis 系统并不满足「一致性」要求。当客户端在 Redis 的主节点修改了数据后,立即返回,即使在主从网络断开的情况下,主节
点依旧可以正常对外提供修改服务,所以 Redis 满足「可用性」。Redis 保证「最终一致性」,从节点会努力追赶主节点,最终从节点的状态会和主节点
的状态将保持一致。如果网络断开了,主从节点的数据将会出现大量不一致,一旦网络恢复,从节点会采用多种策略努力追赶上落后的数据,继续尽力保持和主节点一致。
主从同步:
增量同步:
Redis 同步的是指令流,主节点会将那些对自己的状态产生修改性影响的指令记录在本地的内存 buffer 中,然后异步将 buffer 中的指令同步到从节点,从节点一边执行同步的指令流来达到和主节点一样的状态,
一边向主节点反馈自己同步到哪里了 (偏移量)。
因为内存的 buffer 是有限的,所以 Redis 主库不能将所有的指令都记录在内存 buffer中。 Redis 的复制内存 buffer 是一个定长的环形数组,如果数组内容满了,就会从头开始覆盖前面的内容。
如果因为网络状况不好,从节点在短时间内无法和主节点进行同步,那么当网络状况恢复时, Redis 的主节点中那些没有同步的指令在 buffer 中有可能已经被后续的指令覆盖掉了,
从节点将无法直接通过指令流来进行同步,这个时候就需要用到更加复杂的同步机制 —— 快照同步。
快照同步:
快照同步是一个非常耗费资源的操作,它首先需要在主库上进行一次 bgsave 将当前内存的数据全部快照到磁盘文件中,然后再将快照文件的内容全部传送到从节点。从节点将快
照文件接受完毕后,立即执行一次全量加载,加载之前先要将当前内存的数据清空。加载完毕后通知主节点继续进行增量同步。
在整个快照同步进行的过程中,主节点的复制 buffer 还在不停的往前移动,如果快照同步的时间过长或者复制 buffer 太小,都会导致同步期间的增量指令在复制 buffer 中被覆
盖,这样就会导致快照同步完成后无法进行增量复制,然后会再次发起快照同步,如此极有可能会陷入快照同步的死循环。所以务必配置一个合适的复制 buffer 大小参数,避免快照复制的死循环。
从从同步:
从从同步功能是 Redis 后续版本增加的功能,为了减轻主库的同步负担。
增加从节点:
当从节点刚刚加入到集群时,它必须先要进行一次快照同步,同步完成后再继续进行增量同步。
无盘复制:
主节点在进行快照同步时,会进行很重的文件 IO 操作,所谓无盘复制是指主服务器直接通过套接字将快照内容发送到从节点,生成快照是一个遍历的过程,主节点会一边遍历内存,一遍将序
列化的内容发送到从节点,从节点还是跟之前一样,先将接收到的内容存储到磁盘文件中,再进行一次性加载。
Wait 指令:
Redis 的复制是异步进行的, wait 指令可以让异步复制变身同步复制,确保系统的强一致性 (不严格)。 wait 指令是 Redis3.0 版本以后才出现的。
5.Pipeline有什么好处,为什么要用pipeline?
使用 pipeline, 可以使多个连续的写操作和多个连续的读操作总共只会花费一次网络来回,就好比连续的 write(request)操作合并了,连续的 read(response) 操作也合并了一样。
服务器根本没有任何区别对待,还是收到一条消息,执行一条消息,回复一条消息的正常的流程。客户端通过对管道中的指令列表改变读写顺序就可以大幅节省 IO 时间。
> redis-benchmark -t set -P 2 -q # 管道压力测试。选项 -P 参数(可选),它表示单个管道内并行的请求数量,如果继续增 -P 参数QPS不再提升,说明 Redis 的单线程 CPU 已经飙到了 100%。
连续的 write 操作根本就没有耗时,之后第一个 read 操作会等待一个网络的来回开销,然后所有的响应消息就都已经回送到内核的读缓冲了,后续的 read 操作直接就可以从缓冲拿到结果,瞬间就返回了
6.redis特点?
线程 IO 模型:
Redis 是个单线程程序!Nginx 也是单线程。因为它所有的数据都在内存中,所有的运算都是内存级别的运算。
Redis 单线程如何处理那么多的并发客户端连接?
非阻塞 IO:
当我们调用套接字的读写方法,默认它们是阻塞的,比如 read 方法要传递进去一个参数n,表示读取这么多字节后再返回,如果没有读够线程就会卡在那里,直到新的数据到来或者
连接关闭了, read 方法才可以返回,线程才能继续处理。而 write 方法一般来说不会阻塞,除非内核为套接字分配的写缓冲区已经满了, write 方法就会阻塞,直到缓存区中有空闲空间挪出来了。
非阻塞 IO 在套接字对象上提供了一个选项 Non_Blocking,当这个选项打开时,读写方法不会阻塞,而是能读多少读多少,能写多少写多少。能读多少取决于内核为套接字分配的
读缓冲区内部的数据字节数,能写多少取决于内核为套接字分配的写缓冲区的空闲空间字节数。读方法和写方法都会通过返回值来告知程序实际读写了多少字节。
有了非阻塞 IO 意味着线程在读写 IO 时可以不必再阻塞了,读写可以瞬间完成然后线程可以继续干别的事了。
事件轮询 (多路复用):
Redis 是一个事件驱动的内存数据库,服务器需要处理两种类型的事件:文件事件、时间事件。
Redis 基于 Reactor 模式开发了自己的事件处理器。
如: (fd、fd、fd、fd、fd、fd...)——> I/O 多路复用模块 ——> 事件分发器 ——> (链接应答处理器、命令请求处理器、命令回复处理器...)
“I/O 多路复用模块”会监听多个 FD ,当这些FD产生 accept,read,write 或 close 的文件事件。会向“文件事件分发器(dispatcher)”传送事件。
文件事件分发器(dispatcher)在收到事件之后,会根据事件的类型将事件分发给对应的 handler。
I/O 多路复用模块:
Redis 的 I/O 多路复用模块,其实是封装了操作系统提供的 select,epoll,avport 和 kqueue 这些基础函数。向上层提供了一个统一的接口,屏蔽了底层实现的细节。
一般而言 Redis 都是部署到 Linux 系统上,所以我们就看看使用 Redis 是怎么利用 linux 提供的 epoll 实现I/O 多路复用。
事件分发器(dispatcher):
根据不同的事件类型调用不同的事件处理器,将不同的事件分别分发给了读事件和写事件。
文件事件处理器的类型:
Redis 有大量的事件处理器类型,我们就讲解处理一个简单命令涉及到的三个处理器:
acceptTcpHandler 连接应答处理器,负责处理连接相关的事件,当有client 连接到Redis的时候们就会产生 AE_READABLE 事件。引发它执行。
readQueryFromClinet 命令请求处理器,负责读取通过 sokect 发送来的命令。
sendReplyToClient 命令回复处理器,当Redis处理完命令,就会产生 AE_WRITEABLE 事件,将数据回复给 client。
通信协议:
Redis 的作者认为数据库系统的瓶颈一般不在于网络流量,而是数据库自身内部逻辑处理上。所以即使 Redis 使用了浪费流量的文本协议,依然可以取得极高的访问性能。 Redis
将所有数据都放在内存,用一个单线程对外提供服务,单个节点在跑满一个 CPU 核心的情况下可以达到了 10w/s 的超高 QPS。
RESP(Redis Serialization Protocol),RESP 是 Redis 序列化协议的简写。它是一种直观的文本协议,优势在于实现异常简单,解析性能极好。
Redis 协议将传输的结构数据分为 5 种最小单元类型,单元结束时统一加上回车换行符号\r\n。
a、 单行字符串 以 + 符号开头。
b、 多行字符串 以 $ 符号开头,后跟字符串长度。
c、 整数值 以 : 符号开头,后跟整数的字符串形式。
d、 错误消息 以 - 符号开头。
e、 数组 以 * 号开头,后跟数组的长度。
如:
单行字符串 hello world > +hello world\r\n
多行字符串 hello world > $11\r\nhello world\r\n # 多行字符串当然也可以表示单行字符串。
整数 1024 > :1024\r\n
错误 参数类型错误 > -WRONGTYPE Operation against a key holding the wrong kind of value
数组 [1,2,3] > *3\r\n:1\r\n:2\r\n:3\r\n
NULL 用多行字符串表示,不过长度要写成-1 > $-1\r\n
空串 用多行字符串表示,长度填 0 > $0\r\n\r\n # 注意这里有两个\r\n。为什么是两个? 因为两个\r\n 之间,隔的是空串。
客户端 -> 服务器:
客户端向服务器发送的指令只有一种格式,多行字符串数组。比如一个简单的 set 指令set author codehole 会被序列化成下面的字符串。
> *3\r\n$3\r\nset\r\n$6\r\nauthor\r\n$8\r\ncodehole\r\n
服务器 -> 客户端:
服务器向客户端回复的响应要支持多种数据结构,所以消息响应在结构上要复杂不少。不过再复杂的响应消息也是以上 5 中基本类型的组合。
内存回收机制:
惰性删除和定时任务删除:
惰性删除:
当客户端进行某个 key 的get 访问,该key被设置了过期时间,如果此时 get 操作的时候 key 过期了,此时 Redis 将会针对该 key 占用的空间进行回收。
优点:该方式采用用户访问的方式进行空间回收,无需维护 key 的 TTL 链表数据。
缺点:如果存在大量已过期的 key 但是长时间内用户一直没有进行 get 方法,会导致过期 key 堆积在内存中,产生内存泄漏。
定时任务删除:
Redis 内部维护一个定时任务,每秒执行10次。定时随机的进行过期key的内存回收。
当你删除了 1GB 的 key 后,再去观察内存,你会发现内存变化不会太大。原因是操作系统回收内存是以页为单位,如果这个页上只要有一个 key
还在使用,那么它就不能被回收。 Redis 虽然删除了 1GB 的 key,但是这些 key 分散到了很多页面中,每个页面都还有其它 key 存在,这就导致了内存不会立即被回收。
Sentinel:
6.5.scan 的用法?
复杂度虽然也是 O(n),但是它是通过游标分步进行的,不会阻塞线程;
服务器不需要为游标保存状态,游标的唯一状态就是 scan 返回给客户端的游标整数;
返回的结果可能会有重复,需要客户端去重复,这点非常重要;
遍历的过程中如果有数据修改,改动后的数据能不能遍历到是不确定的;
单次返回的结果是空的并不意味着遍历结束,而要看返回的游标值是否为零;
基本用法:
> scan 0 match key99* count 1000 # scan 参数提供了三个参数,第一个是 cursor 整数值,第二个是 key 的正则模式,第三个是遍历的 limit hint。
第一次遍历时, cursor 值为 0,然后将返回结果中第一个整数值作为下一次遍历的 cursor。一直遍历到返回的 cursor 值为 0 时结束。
scan 指令返回的游标就是第一维数组的位置索引,我们将这个位置索引称为槽 (slot)。
scan 遍历顺序:
它不是从第一维数组的第 0 位一直遍历到末尾,而是采用了高位进位加法来遍历。之所以使用这样特殊的方式进行遍历,是考虑到字典的扩容和缩容时避免槽位的遍历重复和遗漏。
普通加法和高位进位加法的区别:高位进位法从左边加,进位往右边移动,同普通加法正好相反。但是最终它们都会遍历所有的槽位并且没有重复。
rehash 就是将元素的hash 值对数组长度进行取模运算,因为长度变了,所以每个元素挂接的槽位可能也发生了变化。又因为数组的长度是 2^n 次方,所以取模运算等价于位与操作。
a mod 8 = a & (8-1) = a & 7
a mod 16 = a & (16-1) = a & 15
a mod 32 = a & (32-1) = a & 31
这里的 7, 15, 31 称之为字典的 mask 值, mask 的作用就是保留 hash 值的低位,高位都被设置为 0。
假设当前的字典的数组长度由 8 位扩容到 16 位,那么 3 号槽位 011 将会被 rehash到 3 号槽位和 11 号槽位,也就是说该槽位链表中大约有一半的元素还是 3 号槽位,其它
的元素会放到 11 号槽位, 11 这个数字的二进制是 1011,就是对 3 的二进制 011 增加了一个高位。
scan 指令是一系列指令,除了可以遍历所有的 key 之外,还可以对指定的容器集合进行遍历。比如 zscan 遍历 zset 集合元素, hscan 遍历 hash 字典的元素、 sscan 遍历 set 集合的元素。
大 key 扫描:
一个很大的hash,一个很大的 zset 经常会形成很大的对象。这样的对象对 Redis 的集群数据迁移带来了很大的问题,因为在集群环境下,如果某个 key 太大,会数据导致迁移卡顿。另外在内存分配
上,如果一个 key 太大,那么当它需要扩容时,会一次性申请更大的一块内存,这也会导致卡顿。如果这个大 key 被删除,内存会一次性回收,卡顿现象会再一次产生。
如果你观察到 Redis 的内存大起大落,这极有可能是因为大 key 导致的。
> redis-cli -h 127.0.0.1 -p 7001 --bigkeys -i 0.1 # 上面这个指令每隔 100 条 scan 指令就会休眠 0.1s, ops 就不会剧烈抬升,但是扫描的时间会变长。
7.Redis 能用来做什么?
分布式锁
缓存
延迟队列 zset (消息序列化为 value,处理时间置为 score,多个线程轮询取 value 进行业务处理)
每个人的每天签到记录 位图(setbit、getbit),如一年 365 天,每天的签到记录只占据一个位,365 天就是 365 个位, 46 个字节 (一个稍长一点的字符串) 就可以完全容纳下
位图统计指令 bitcount 和位图查找指令 bitpos, bitcount 用来统计指定位置范围内 1 的个数, bitpos 用来查找指定范围内出现的第一个 0 或 1。
bitfield:可以一次进行多个位的操作,> bitfield w get u4 0 # 从第一个位开始取 4 个位,结果是无符号数 (u)
解决统计问题 (HyperLogLog)
HyperLogLog 提供不精确的去重计数方案,虽然不精确但是也不是非常不精确,标准误差是 0.81%,这样的精确度已经可以满足 UV 统计需求。
三个指令 pfadd、 pfcount 和 pfmerge,一个是增加计数,一个是获取计数,再一个是将多个 pf 计数值累加在一起形成一个新的 pf 值,比如在网站中我们有两个内容差不多的页面,运营说需要这两个页面的数据进行合并。
其中页面的 UV 访问量也需要合并,那这个时候 pfmerge 就可以派上用场了。
> pfadd codehole user1
> pfcount codehole
允许有稍微误差的去重 (布隆过滤器)
当布隆过滤器说某个值存在时,这个值可能不存在;当它说不存在时,那就肯定不存在。
布隆过滤器能准确过滤掉那些已经看过的内容,那些没有看过的新内容,它也会过滤掉极小一部分 (误判),但是绝大多数新内容它都能准确识别。这样就可以完全保证推荐给用户的内容都是无重复的。
基本使用:
有二个基本指令, bf.add 添加元素, bf.exists 查询元素是否存在,它的用法和 set 集合的 sadd 和 sismember 差不多。注意 bf.add 只能一次添加一个元素,如果想要
一次添加多个,就需要用到 bf.madd 指令。同样如果需要一次查询多个元素是否存在,就需要用到 bf.mexists 指令。
error_rate 和 initial_size。错误率越低,需要的空间越大。 initial_size 参数表示预计放入的元素数量,当实际数量超出这个数值时,误判率会上升。
默认的 error_rate 是 0.01,默认的 initial_size 是 100。 error_rate 越小,需要的存储空间就越大。
原理:
每个布隆过滤器对应到 Redis 的数据结构里面就是一个大型的位数组和几个不一样的无偏 hash 函数。所谓无偏就是能够把元素的 hash 值算得比较均匀。
向布隆过滤器中添加 key 时,会使用多个 hash 函数对 key 进行 hash 算得一个整数索引值然后对位数组长度进行取模运算得到一个位置,每个 hash 函数都会算得一个不同的位置。
再把位数组的这几个位置都置为 1 就完成了 add 操作。
当实际元素开始超出初始化大小时,应该对布隆过滤器进行重建,重新分配一个 size 更大的过滤器,再将所有的历史元素批量 add 进
去 (这就要求我们在其它的存储器中记录所有的历史元素)。因为 error_rate 不会因为数量超出就急剧增加,这就给我们重建过滤器提供了较为宽松的时间。
应用场景举例:
在爬虫系统中,我们需要对 URL 进行去重,已经爬过的网页就可以不用爬了。但是URL 太多了,几千万几个亿,如果用一个集合装下这些 URL 地址那是非常浪费空间的。这
时候就可以考虑使用布隆过滤器。它可以大幅降低去重存储消耗,只不过也会使得爬虫系统错过少量的页面。
布隆过滤器在 NoSQL 数据库领域使用非常广泛,我们平时用到的 HBase、 Cassandra还有 LevelDB、 RocksDB 内部都有布隆过滤器结构,布隆过滤器可以显著降低数据库的 IO
请求数量。当用户来查询某个 row 时,可以先通过内存中的布隆过滤器过滤掉大量不存在的 row 请求,然后再去磁盘进行查询。
邮箱系统的垃圾邮件过滤功能也普遍用到了布隆过滤器,因为用了这个过滤器,所以平时也会遇到某些正常的邮件被放进了垃圾邮件目录中,这个就是误判所致,概率很低。
限流:
简单限流:
使用 zset 数据结构的 score 值来表示滑动时间窗口,只需要保留这个时间窗口内的行为数据,窗口之外的数据都可以砍掉。
那这个 zset 的 value 填什么比较合适呢?它只需要保证唯一性即可,用 uuid 会比较浪费空间,那就改用毫秒时间戳吧。
public boolean isActionAllowed(String userId, String actionKey, int period, int maxCount) {
String key = String.format("hist:%s:%s", userId, actionKey);
long nowTs = System.currentTimeMillis();
Pipeline pipe = jedis.pipelined();
pipe.multi();
pipe.zadd(key, nowTs, "" + nowTs);
// 移除时间窗口之前的行为记录,剩下的都是时间窗口内的
pipe.zremrangeByScore(key, 0, nowTs - period * 1000);
Response<Long> count = pipe.zcard(key);
// 设置 zset 过期时间,避免冷用户持续占用内存
// 过期时间应该等于时间窗口的长度,再多宽限 1s
pipe.expire(key, period + 1);
pipe.exec();
pipe.close();
return count.get() <= maxCount;
}
整体思路就是:每一个行为到来时,都维护一次时间窗口。将时间窗口外的记录全部清理掉,只保留窗口内的记录。zset 集合中只有 score 值非常重要, value 值没有特别的意义,只需要保证它是唯一的就可
以了。因为这几个连续的 Redis 操作都是针对同一个 key 的,使用 pipeline 可以显著提升 Redis 存取效率。
漏斗限流:
void makeSpace() {
long nowTs = System.currentTimeMillis();
long deltaTs = nowTs - leakingTs; // 距离上一次漏水过去了多久
int deltaQuota = (int) (deltaTs * leakingRate);
if (deltaQuota < 0) { // 间隔时间太长,整数数字过大溢出
this.remainQuota = capacity;
this.leakingTs = nowTs;
return;
}
if (deltaQuota < 1) { // 腾出空间太小,最小单位是 1
return;
}
this.remainQuota += deltaQuota;
this.leakingTs = nowTs;
if (this.remainQuota > this.capacity) {
this.remainQuota = this.capacity;
}
}
Redis-Cell 限流:
漏斗限流无法保证 redis 操作原子性,Redis 4.0 提供了一个限流 Redis 模块,它叫 redis-cell。该模块也使用了漏斗算法,并提供了原子的限流指令。该模块只有 1 条指令 cl.throttle。
用法:
> cl.throttle userId:actionkey 15 30 60 1 # 15-capacity 漏斗容量;30 60-30 operations / 60 seconds 漏水速率;1-need 1 quota(可选,默认为1)
1) (integer) 0 # 0 表示允许, 1 表示拒绝
2) (integer) 15 # 漏斗容量 capacity
3) (integer) 14 # 漏斗剩余空间 left_quota
4) (integer) -1 # 如果拒绝了,需要多长时间后再试(漏斗有空间了,单位秒)
5) (integer) 2 # 多长时间后,漏斗完全空出来(left_quota==capacity,单位秒)
在执行限流指令时,如果被拒绝了,就需要丢弃或重试。 cl.throttle 指令考虑的非常周到,连重试时间都帮你算好了,直接取返回结果数组的第四个值进行 sleep 即可,如果不想
阻塞线程,也可以异步定时任务来重试。
地理位置距离排序(GeoHash 算法):
GeoHash 算法将二维的经纬度数据映射到一维的整数,这样所有的元素都将在挂载到一条线上,距离靠近的二维坐标映射到一维后的点之间距离也会很接近。
它将整个地球看成一个二维平面,然后划分成了一系列正方形的方格,就好比围棋棋盘。所有的地图元素坐标都将放置于唯一的方格中。方格越
小,坐标越精确。然后对这些方格进行整数编码,越是靠近的方格编码越是接近。那如何编码呢?一个最简单的方案就是切蛋糕法。设想一个正方形的蛋糕摆在你面前,二刀下去均分
分成四块小正方形,这四个小正方形可以分别标记为 00,01,10,11 四个二进制整数。然后对每一个小正方形继续用二刀法切割一下,这时每个小小正方形就可以使用 4bit 的二进制整数
予以表示。然后继续切下去,正方形就会越来越小,二进制整数也会越来越长,精确度就会越来越高。
编码之后,每个地图元素的坐标都将变成一个整数,通过这个整数可以还原出元素的坐标,整数越长,还原出来的坐标值的损失程度就越小。对于「附近的人」这个功能而言,损失的一点精确度可以忽略不计。
GeoHash 算法会继续对这个整数做一次 base32 编码 (0-9,a-z 去掉 a,i,l,o 四个字母) 变成一个字符串。在 Redis 里面,经纬度使用 52 位的整数进行编码,放进了 zset 里面, zset的 value 是元素的 key,
score 是 GeoHash 的 52 位整数值。 zset 的 score 虽然是浮点数,但是对于 52 位的整数值,它可以无损存储。在使用 Redis 进行 Geo 查询时,我们要时刻想到它的内部结构实际上只是一个
zset(skiplist)。通过 zset 的 score 排序就可以得到坐标附近的其它元素 (实际情况要复杂一些,不过这样理解足够了),通过将 score 还原成坐标值就可以得到元素的原始坐标。
> geoadd company 116.48105 39.996794 juejin
> geoadd company 116.562108 39.787602 jd 116.334255 40.027400 xiaomi
> geodist company juejin ireader km # 距离单位可以是 m、 km、 ml、 ft,分别代表米、千米、英里和尺。
> geopos company juejin
> geopos company juejin ireader
> geohash company ireader # 使用这个编码值去 http://geohash.org/${hash}中进行直接定位,它是 geohash 的标准编码值。
> georadiusbymember company ireader 20 km count 3 asc # 范围 20 公里以内最多 3 个元素按距离正排,它不会排除自身
> georadiusbymember company ireader 20 km withcoord withdist withhash count 3 asc # 三个可选参数 withcoord withdist withhash 用来携带附加出参参数
> georadius company 116.514202 39.905409 20 km withdist count 3 asc # 根据坐标值来查询附近的元素,这个指令更加有用,它可以根据用户的定位来计算「附近的车」,「附近的餐馆」等
8.数据结构都有哪些?特点是什么?
存储界限 当集合对象的元素不断增加,或者某个 value 值过大,这种小对象存储也会被升级为标准结构。 Redis 规定在小对象存储结构的限制条件如下:
hash-max-zipmap-entries 512 # hash 的元素个数超过 512 就必须用标准结构存储
hash-max-zipmap-value 64 # hash 的任意元素的 key/value 的长度超过 64 就必须用标准结构存储
list-max-ziplist-entries 512 # list 的元素个数超过 512 就必须用标准结构存储
list-max-ziplist-value 64 # list 的任意元素的长度超过 64 就必须用标准结构存储
zset-max-ziplist-entries 128 # zset 的元素个数超过 128 就必须用标准结构存储
zset-max-ziplist-value 64 # zset 的任意元素的长度超过 64 就必须用标准结构存储
set-max-intset-entries 512 # set 的整数元素个数超过 512 就必须用标准结构存储
string (字符串)、 hash (哈希)、 list (列表)、 set (集合) 和 zset (有序集合)。
RedisObject redis 对象头:
所有的 Redis 对象都有下面的这个结构头:
struct RedisObject {
int4 type; // 4bits
int4 encoding; // 4bits
int24 lru; // 24bits
int32 refcount; // 4bytes
void *ptr; // 8bytes, 64-bit system
} robj;
不同的对象具有不同的类型 type(4bit),同一个类型的 type 会有不同的存储形式 encoding(4bit),为了记录对象的 LRU 信息,使用了 24 个 bit 来记录 LRU 信息。每个对
象都有个引用计数,当引用计数为零时,对象就会被销毁,内存被回收。 ptr 指针将指向对象内容 (body) 的具体存储位置。这样一个 RedisObject 对象头需要占据 16 字节的存储空间。
SDS 字符串结构:
struct SDS {
int8 capacity; // 1byte
int8 len; // 1byte
int8 flags; // 1byte
byte[] content; // 内联数组,长度为 capacity
}
在字符串比较小时,SDS 对象头的大小是 capacity+3,至少是 3。意味着分配一个字符串的最小空间占用为 19 字节 (16+3)。
intset 是紧凑的数组结构:
struct intset<T> {
int32 encoding; // 决定整数位宽是 16 位、 32 位还是 64 位
int32 length; // 元素个数
int<T> contents; // 整数数组,可以是 16 位、 32 位和 64 位
}
当 set 集合容纳的元素都是整数并且元素个数较小时, Redis 会使用 intset 来存储结合元素。 intset 是紧凑的数组结构,同时支持 16 位、 32 位和 64 位整数。
ziplist 压缩列表:
压缩列表是一块连续的内存空间,元素之间紧挨着存储,没有任何冗余空隙。zset 和 hash 容器对象在元素个数较少的时候,采用压缩列表 (ziplist) 进行存储。
struct ziplist<T> {
int32 zlbytes; // 整个压缩列表占用字节数
int32 zltail_offset; // 最后一个元素距离压缩列表起始位置的偏移量,用于快速定位到最后一个
节点
int16 zllength; // 元素个数
T[] entries; // 元素内容列表,挨个挨个紧凑存储
int8 zlend; // 标志压缩列表的结束,值恒为 0xFF
}
压缩列表为了支持双向遍历,所以才会有 ztail_offset 这个字段,用来快速定位到最后一个元素,然后倒着遍历。
struct entry {
int<var> prevlen; // 前一个 entry 的字节长度
int<var> encoding; // 元素类型编码
optional byte[] content; // 元素内容
}
entry 块随着容纳的元素类型不同,也会有不一样的结构。它的 prevlen 字段表示前一个 entry 的字节长度,当压缩列表倒着遍历时,需要通过这
个字段来快速定位到下一个元素的位置。它是一个变长的整数,当字符串长度小于254(0xFE) 时,使用一个字节表示;如果达到或超出 254(0xFE) 那就使用 5 个字节来表示。
第一个字节是 0xFE(254),剩余四个字节表示字符串长度。
级联更新:~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
quicklist 快速列表:
struct quicklist {
quicklistNode* head;
quicklistNode* tail;
long count; // 元素总数
int nodes; // ziplist 节点的个数
int compressDepth; // LZF 算法压缩深度
...
}
struct quicklistNode {
quicklistNode* prev;
quicklistNode* next;
ziplist* zl; // 指向压缩列表
int32 size; // ziplist 的字节总数
int16 count; // ziplist 中的元素数量
int2 encoding; // 存储形式 2bit,原生字节数组还是 LZF 压缩存储
...
}
quicklist 内部默认单个 ziplist 长度为 8k 字节,超出了这个字节数,就会新起一个ziplist。 ziplist 的长度由配置参数 list-max-ziplist-size 决定。
因为普通的链表需要的附加指针空间太大,会比较浪费空间,而且会加重内存的碎片化。比如这个列表里存的只是 int 类型的数据,结构上还需要两个额外的指针 prev 和 next 。所以 Redis 将链表和 ziplist
结合起来组成了 quicklist。也就是将多个ziplist 使用双向指针串起来使用。这样既满足了快速的插入删除性能,又不会出现太大的空间冗余。
a).字符串
字符串是动态字符串,可修改,预分配冗余空间来减少内存的频繁分配,在内存中它是以字节数组的形式存在。
如果 value 值是一个整数,还可以对它进行自增操作。自增是有范围的,它的范围是 signed long 的最大最小值,超过了这个值, Redis 会报错。那么编码是 int。
扩容策略:
当字符串长度小于 1M 时,扩容都是加倍现有的空间,如果超过 1M,扩容时一次只会多扩 1M 的空间。需要注意的是字符串最大长度为 512M。
内部结构实现:
Redis 的字符串有两种存储方式,在长度特别短时,使用 emb 形式存储 (embeded),当长度超过 44 时,使用 raw 形式存储。
可以通过命令:debug object key 查看 key 的 encoding (encoding:embstr)
embstr 存储形式:
RedisObject 对象头和 SDS 对象连续存在一起,使用 malloc 方法一次分配。
raw 存储形式:
需要两次 malloc,RedisObject 和 SDS 两个对象头在内存地址上一般是不连续的。
而内存分配器 jemalloc/tcmalloc 等分配内存大小的单位都是 2、 4、 8、 16、 32、 64 等等,为了能容纳一个完整的 embstr 对象, jemalloc 最少会分配 32 字节的空间,如果字符
串再稍微长一点,那就是 64 字节的空间。如果总体超出了 64 字节, Redis 认为它是一个大字符串,不再使用 emdstr 形式存储,而该用 raw 形式。
SDS 结构体中的 content 中的字符串是以字节\0 结尾的字符串,之所以多出这样一个字节,是为了便于直接使用 glibc 的字符串处理函数,以及为了便于字符串的调试打印输出。留给 content 的长度
最多只有 45(64-19) 字节了。字符串又是以\0 结尾,所以 embstr 最大能容纳的字符串长度就是 44。
b).列表
底层是链表,插入和删除操作非常快,时间复杂度为 O(1),但是索引定位很慢,时间复杂度为O(n)。
> lrange key 0 -1 #获取所有元素, O(n) 慎用。
> ltrim books 1 0 #这其实是清空了整个列表,因为区间范围长度为负,ltrim 跟的两个参数 start_index 和 end_index 定义了一个区间,在这个区间内的值,ltrim 要保留,区间之外统统砍掉。我们可以通过 ltrim 来实现一个定长的链表,这一点非常有用。
> lindex books 1 # O(n) 慎用 index=-1 表示倒数第一个元素,同样 index=-2 表示倒数第二个元素。
列表底层存储的不是一个简单的 linkedlist,而是称之为快速链表 quicklist 的一个结构。首先在列表元素较少的情况下会使用一块连续的内存存储,这个结构是 ziplist,也即是压缩列表。
它将所有的元素紧挨着一起存储,分配的是一块连续的内存。当数据量比较多的时候才会改成 quicklist。
c).字典
Redis 的字典的值只能是字符串,Redis为了高性能,不能堵塞服务,所以采用了渐进式 rehash 策略。
同字符串一样,hash 结构中的单个子 key 也可以进行计数,它对应的指令是 hincrby,和 incr 使用基本一样: > hincrby key age 1
如果数据量很小,key 和 value 会作为两个 entry 相邻存在一起 > object encoding hello # "ziplist"
> hset books java "think in java"
> hset books golang "concurrency in go"
> hset books python "python cookbook"
> hgetall books # key 和 value 间隔出现
> hlen books
> hget books java
> hset books golang "learning go programming" # 因为是更新操作,所以返回 0
> hmset books java "effective java" python "learning python" golang "modern golang programming" # 批量 set
> hdel books java
底层实现:
struct RedisDb {
dict* dict; // 所有 key 和 value 也组成了一个全局字典
dict* expires; // 带过期时间的 key 集合也是一个字典
...
}
dict 内部结构:
struct dict {
...
dictht ht[2]; // 内部包含两个 hashtable,通常情况下只有一个 hashtable 是有值的。但是在dict 扩容缩容时,需要分配新的 hashtable,然后进行渐进式搬迁,
}
dictht 内部结构:
struct dictht {
dictEntry** table; // 二维
long size; // 第一维数组的长度
long used; // hash 表中的元素个数
...
}
hash 函数:Redis 的字典默认的 hash 函数是siphash。
扩容条件:
正常情况下, 当 hash 表中元素的个数等于第一维数组的长度时,就会开始扩容,扩容的新数组是原数组大小的 2 倍。不过如果 Redis 正在做 bgsave,为了减少内存页的过多分离 (Copy On Write),
Redis 尽量不去扩容 (dict_can_resize),但是如果 hash 表已经非常满了,元素的个数已经达到了第一维数组长度的 5 倍 (dict_force_resize_ratio),说明 hash 表已经过于拥挤了,这个时候就会强制扩容。
缩容条件:
缩容的条件是元素个数低于数组长度的 10%。缩容不会考虑 Redis 是否正在做 bgsave。
d).集合
元素个数较少且存放元素都是整数的 set 集合,使用的是 intset 这个紧凑的整数数组结构:
如果整数可以用 uint16 表示,那么 intset 的元素就是 16 位的数组,如果新加入的整数超过了 uint16 的表示范围,那么就使用 uint32 表示,如果新加入的元素超过了 uint32
的表示范围,那么就使用 uint64 表示, Redis 支持 set 集合动态从 uint16 升级到 uint32,再升级到 uint64。
如果 set 里存储的是字符串,那么 sadd 立即升级为 hashtable 结构。
相当于 Java 语言里面的 HashSet,Java 中的 HashSet 继承自 HashMap,且 value 都指向同一个 Object。Redis 中的 set 的 value 都为 null。
set 结构可以用来存储活动中奖的用户 ID,因为有去重功能,可以保证同一个用户不会中奖两次。
Java 中 HashSet 可以保证不存在重复元素的原因:向 HashSet 中添加一个已经存在的元素时,新添加的集合元素将不会被放入 HashMap中,原来的元素也不会有任何改变,这也就满足了 Set 中元素不重复的特性。
> sadd books python # 返回 1
> sadd books python # 返回 0
> sadd books java golang # 返回 2
> smembers books # 注意顺序,和插入的并不一致,因为 set 是无序的
> sismember books java # 查询某个 value 是否存在,返回 1,相当于 contains(o)
> scard books # 获取长度相当于 count()
> spop books # 弹出一个
e).有序集合
如果数据量很小,value 和 score 会作为两个 entry 相邻存在一起 > object encoding world # "ziplist"
类似于 Java 的 SortedSet 和 HashMap 的结合体,一方面它需要一个 hash 结构来存储 value 和 score 的对应关系,另一方面需要提供按照 score 来排序的功能,还需要能够指定 score 的范围来获
取 value 列表的功能,这就需要另外一个结构「跳跃列表」。因为 zset 要支持随机的插入和删除,所以它不好使用数组来表示。
跳跃列表采取一个随机策略来决定新元素可以兼职到第几层:
Redis 的跳跃表共有 64 层,意味着最多可以容纳 2^64 次方个元素。
首先 L0 层肯定是 100% 了, L1 层只有 50% 的概率, L2 层只有 25% 的概率, L3层只有 12.5% 的概率,一直随机到最顶层 L31 层。绝大多数元素都过不了几层,只有极少数元素可以深入到顶层。
列表中的元素越多,能够深入的层次就越深,能进入到顶层的概率就会越大。
每一个 kv 块对应的结构如下面的代码中的 zslnode 结构,kv 之间使用指针串起来形成了双向链表结构,它们是有序排列的,从小到大。不同的 kv 层高可能不一样,层数越高的 kv 越少。
同一层的 kv会使用指针串起来。每一个层元素的遍历都是从 kv header 出发。kv header 也是这个结构,只不过 value 字段是 null 值——无效的, score 是Double.MIN_VALUE,用来垫底的。
struct zslnode {
string value;
double score;
zslnode*[] forwards; // 多层连接指针
zslnode* backward; // 回溯指针
}
struct zsl {
zslnode* header; // 跳跃列表头指针
int maxLevel; // 跳跃列表当前的最高层
map<string, zslnode*> ht; // hash 结构的所有键值对
}
查找过程:O(lg(n))
插入过程
删除过程
更新过程:
redis 的操作是:先删除这个元素,再插入这个元素,需要经过两次路径搜索。
如果 score 值都一样呢?
zset 的排序元素不只看 score 值,如果 score 值相同还需要再比较 value 值 (字符串比较)。
元素排名是怎么算出来的?
Redis 在 skiplist 的 forward 指针上进行了优化,给每一个 forward 指针都增加了 span 属性, span 是「跨度」的意思,表示从前一个节点沿着当前层的 forward 指针跳到当前这个节
点中间会跳过多少个节点。 Redis 在插入删除操作时会小心翼翼地更新 span 值的大小。
这样当我们要计算一个元素的排名时,只需要将「搜索路径」上的经过的所有节点的跨度 span 值进行叠加就可以算出元素的最终 rank 值。
应用场景举例:
zset 可以用来存粉丝列表,value 值是粉丝的用户 ID,score 是关注时间。我们可以对粉丝列表按关注时间进行排序。
zset 还可以用来存储学生的成绩,value 值是学生的 ID,score 是他的考试成绩。我们可以对成绩按分数进行排序就可以得到他的名次。
> zadd books 9.0 "think in java" # 1
> zadd books 8.9 "java concurrency" # 1
> zadd books 8.6 "java cookbook" # 1
> zrange books 0 -1 # 按 score 排序列出,参数区间为排名范围
1) "java cookbook"
2) "java concurrency"
3) "think in java"
> zrevrange books 0 -1 # 按 score 逆序列出,参数区间为排名范围
1) "think in java"
2) "java concurrency"
3) "java cookbook"
> zcard books # 相当于 count() 3
> zscore books "java concurrency" # 获取指定 value 的 score "8.9000000000000004" 内部 score 使用 double 类型进行存储,所以存在小数点精度问题
> zrank books "java concurrency" # 排名 1
> zrangebyscore books 0 8.91 # 根据分值区间遍历 zset
1) "java cookbook"
2) "java concurrency"
> zrangebyscore books -inf 8.91 withscores # 根据分值区间 (-∞, 8.91] 遍历 zset,同时返回分值。 inf 代表 infinite,无穷大的意思。
1) "java cookbook"
2) "8.5999999999999996"
3) "java concurrency"
4) "8.9000000000000004"
> zrem books "java concurrency" # 删除 value 1
> zrange books 0 -1
1) "java cookbook"
2) "think in java"
9.Redis 数据库内存数据满了,会宕机吗?
在使用 Redis 的时候我们要配置 Redis 能使用的最大的内存大小,存到一定容量的时候会触发 Redis 的内存淘汰策略。如果不设置最大内存大小或者设置最大内存大小为0,在64位操作系统下不限制内存大小,在32位操作系统下最多使用3GB内存
通过配置文件配置(redis.conf):
> maxmemory 100mb
通过命令修改:
> config set maxmemory 100mb
淘汰策略(内存用完的时候触发):
noeviction(默认策略):对于写请求不再提供服务,直接返回错误(DEL请求和部分特殊请求除外)
allkeys-random:从所有 key 中随机淘汰数据
volatile-random:从设置了过期时间的 key 中随机淘汰
volatile-ttl:在设置了过期时间的 key 中,根据 key 的过期时间进行淘汰,越早过期的越优先被淘汰
allkeys-lru:从所有 key 中使用 LRU 算法进行淘汰
volatile-lru:从设置了过期时间的 key 中使用 LRU 算法进行淘汰
volatile-lfu(Redis4.0新增):在设置了过期时间的 key中使用 LFU 算法淘汰key
allkeys-lfu(Redis4.0新增):在所有的 key 中使用 LFU 算法淘汰数据
LRU(Least Recently Used):
即最近最少使用,如果一个数据在最近一段时间没有被用到,那么将来被使用到的可能性也很小,所以就可以被淘汰掉。
LFU(Least Frequently Used):
根据 key 的最近被访问的频率进行淘汰,很少被访问的优先被淘汰,被访问的多的则被留下来。
一个 key 很久没有被访问到,只刚刚是偶尔被访问了一次,那么它就被认为是热点数据,不会被淘汰,而有些key将来是很有可能被访问到的则被淘汰了。如果使用LFU算法则不会出现这种情况,
因为使用一次并不会使一个 key 成为热点数据。
Redis为了实现近似LRU算法,给每个key增加了一个额外增加了一个24bit的字段,用来存储该key最后一次被访问的时间。
Redis使用的是近似LRU算法,它跟常规的LRU算法还不太一样。近似LRU算法通过随机采样法淘汰数据,每次随机出5(默认)个key,从里面淘汰掉最近最少使用的key。
Redis3.0对近似LRU算法进行了一些优化。新算法会维护一个候选池(大小为16),池中的数据根据访问时间进行排序,第一次随机选取的key都会放入池中,随后每次随机选取的key只有在访问时间小于池中最小的时间才会放入池中,
直到候选池被放满。当放满后,如果有新的key需要放入,则将池中最后访问时间最大(最近被访问)的移除。当需要淘汰的时候,则直接从池中选取最近访问时间最小(最久没被访问)的key淘汰掉就行。
###############################源码类#############################
1、你看过那些源码吗?
2、那你能讲讲 HashMap的实现原理吗?
3、HashMap什么时候会进行 rehash?
4、结合源码说说 HashMap在高并发场景中为什么会出现死循环?
5、JDK1.8中对 HashMap做了哪些性能优化?
6、HashMap和 HashTable有何不同?
7、HashMap 和 ConcurrentHashMap 的区别?
https://swenfang.github.io/2018/06/03/Java%208%20ConcurrentHashMap%20%E6%BA%90%E7%A0%81%E8%A7%A3%E8%AF%BB/
链表转红黑树的阈值为什么是8,而不是16等其他数量?
8、 ConcurrentHashMap和LinkedHashMap有什么区别?
9、为什么ConcurrentHashMap中的链表转红黑树的阀值是8?
10、还看过其他的源码吗?Spring的源码有了解吗?
11、SpringBoot 的源码呢?知道 starter 是怎么实现的吗?
https://www.cnblogs.com/hjwublog/p/10332042.html
12、happens-before原则?
对volatile域的写入操作happens-before于每一个后续对同一域的读操作。
############################## cookie 和 session ########################
cookie 是浏览器保存在用户电脑上的一小段文本,通俗的来讲就是当一个用户通过 http 访问到服务器时,服务器会将一些 Key/Value 键值对返回给客户端浏览器,并给这些数据加上一些限制条件,
在条件符合时这个用户下次访问这个服务器时,数据通过请求头又被完整地给带回服务器,服务器根据这些信息来判断不同的用户。
Session 是基于 Cookie 来工作的,同一个客户端每次访问服务器时,只要当浏览器在第一次访问服务器时,服务器设置一个id并保存一些信息(例如登陆就保存用户信息,视具体情况),并把这个 id 通过 Cookie 存到客户端,
客户端每次和服务器交互时只传这个 id,就可以实现维持浏览器和服务器的状态,而这个ID通常是 NAME 为 JSESSIONID 的一个 Cookie。
当浏览器第一次访问服务器时,服务器创建 Session 并将 SessionID 通过 Cookie 带给浏览器保存在客户端,同时服务器根据业务逻辑保存相应的客户端信息保存在 session 中;客户端再访问时上传 Cookie,
服务器得到 Cookie 后获取里面的 SessionID,来维持状态。
############################## 在一张表中,查询出一个字段相同,一个字段不同的记录 ###########################
比如表A中
字段1 字段2
2 43
3 65
2 68
1 92
用sql语句实现查询,查询出
2 43
2 68
这样结果
select distinct x.字段一,x.字段二
from a as x,a as Y
where x.字段一=y.字段一 and x.字段二!=y.字段二
############################# 深拷贝 和 浅拷贝 #############################