更换数据库这个事儿，是一个非常大的技术挑战，因为我们需要保证整个迁移过程中，既不能长时间停服，也不能丢数据。

实际上，无论是新版本的程序，还是新的数据库，即使我们做了严格的验证测试，做了高可用方案，刚刚上线的系统，它的稳定性总是没有那么好的，需要一个磨合的过程，才能逐步达到一个稳定的状态，这是一个客观规律。这个过程中一旦出现故障，如果不能及时恢复，造成的损失往往是我们承担不起的。

所以我们在设计迁移方案的时候，一定要做到，每一步都是可逆的。要保证，每执行一个步骤后，一旦出现问题，能快速地回滚到上一个步骤。这是很多同学在设计这种升级类技术方案的时候，容易忽略的问题。

第一步-复制旧库数据

首先要做的就是，把旧库的数据复制到新库中。对于大规模数据可以使用自增字段（自增主键/创建时间）作为复制的区间，在业务低谷期分批复制数据到新库中。

第二步-同步数据

因为旧库还在服务线上业务，所以不断会有数据写入旧库，我们不仅要往新库复制数据，还要保证新旧两个库的数据是实时同步的。所以，我们需要用一个同步程序来实现新旧两个数据库实时同步。

我们可以使用 Binlog 实时同步数据。如果源库不是 MySQL 的话，就麻烦一点儿，但也可以参考复制状态机理论来实现。这一步不需要回滚，原因是，只增加了一个新库和一个同步程序，对系统的旧库和程序都没有任何改变。即使新上线的同步程序影响到了旧库，只要停掉同步程序就可以了。

第三步-双写

然后，我们需要改造一下业务，业务逻辑部分不需要变，DAO 层需要做如下改造：

1. 支持双写新旧两个库，并且预留热切换开关，能通过开关控制三种写状态：只写旧库、只写新库和同步双写。
2. 支持读新旧两个库，同样预留热切换开关，控制读旧库还是新库。

然后上线新版的业务服务，这个时候业务服务仍然是只读写旧库，不读写新库。让这个新版的服务需要稳定运行至少一到二周的时间，期间除了验证新版服务的稳定性以外，还要验证新旧两个库中的数据是否是一致的。这个过程中，如果新版服务有问题，可以立即下线新版服务，回滚到旧版本的服务。

稳定一段时间之后，就可以开启服务的双写开关了。开启双写开关的同时，需要停掉同步程序。这里面有一个问题需要注意一下，就是这个双写的业务逻辑，一定是先写旧库，再写新库，并且以写旧库的结果为准。旧库写成功，新库写失败，返回写成功，但这个时候要记录日志，后续我们会用到这个日志来验证新库是否还有问题。旧库写失败，直接返回失败，就不写新库了。这么做的原因是，不能让新库影响到现有业务的可用性和数据准确性。上面这个过程如果出现问题，可以关闭双写，回滚到只读写旧库的状态。

第四步-对比补偿

切换到双写之后，新库与旧库的数据可能会存在不一致的情况，原因有两个：一是停止同步程序和开启双写，这两个过程很难做到无缝衔接，二是双写的策略也不保证新旧库强一致，这时候我们需要上线一个对比和补偿的程序，这个程序对比旧库最近的数据变更，然后检查新库中的数据是否一致，如果不一致，还要进行补偿。

开启双写后，还需要至少稳定运行至少几周的时间，并且期间我们要不断地检查，确保不能有旧库写成功，新库写失败的情况出现。对比程序也没有发现新旧两个库的数据有不一致的情况，这个时候，我们就可以认为，新旧两个库的数据是一直保持同步的。

第五步-流量切换

接下来就可以用类似灰度发布的方式，把读请求一点儿一点儿地切到新库上。同样，期间如果出问题的话，可以再切回旧库。全部读请求都切换到新库上之后，这个时候其实读写请求就已经都切换到新库上了，实际的切换已经完成了，但还有后续的收尾步骤。

第六步-下线历史逻辑

再稳定一段时间之后，就可以停掉对比程序，把服务的写状态改为只写新库。到这里，旧库就可以下线了。注意，整个迁移过程中，只有这个步骤是不可逆的。但是，这步的主要操作就是摘掉已经不再使用的旧库，对于在用的新库并没有什么改变，实际出问题的可能性已经非常小了。

到这里，我们就完成了在线更换数据库的全部流程。双写版本的服务也就完成了它的历史使命，可以在下一次升级服务版本的时候，下线双写功能。

如何实现对比和补偿程序？

在上面的整个切换过程中，如何实现这个对比和补偿程序，是整个这个切换设计方案中的一个难点。这个对比和补偿程序的难度在于，我们要对比的是两个都在随时变换的数据库中的数据。这种情况下，我们没有类似复制状态机这样理论上严谨实际操作还很简单的方法，来实现对比和补偿。但还是可以根据业务数据的实际情况，来针对性地实现对比和补偿，经过一段时间，把新旧两个数据库的差异，逐渐收敛到一致。

像订单这类时效性强的数据，是比较好对比和补偿的。因为订单一旦完成之后，就几乎不会再变了，那我们的对比和补偿程序，就可以依据订单完成时间，每次只对比这个时间窗口内完成的订单。补偿的逻辑也很简单，发现不一致的情况后，直接用旧库的订单数据覆盖新库的订单数据就可以了。

这样，切换双写期间，少量不一致的订单数据，等到订单完成之后，会被补偿程序修正。后续只要不是双写的时候，新库频繁写入失败，就可以保证两个库的数据完全一致。

比较麻烦的是更一般的情况，比如像商品信息这类数据，随时都有可能会变化。如果说数据上有更新时间，那我们的对比程序可以利用这个更新时间，每次在旧库取一个更新时间窗口内的数据，去新库上找相同主键的数据进行对比，发现数据不一致，还要对比一下更新时间。如果新库数据的更新时间晚于旧库数据，那可能是对比期间数据发生了变化，这种情况暂时不要补偿，放到下个时间窗口去继续对比。另外，时间窗口的结束时间，不要选取当前时间，而是要比当前时间早一点儿，比如 1 分钟前，避免去对比正在写入的数据。如果数据连时间戳也没有，那只能去旧库读取 Binlog，获取数据变化，然后去新库对比和补偿。

有一点需要说明的是，上面这些方法，如果严格推敲，都不是百分之百严谨的，都不能保证在任何情况下，经过对比和补偿后，新库的数据和旧库就是完全一样的。但是，在大多数情况下，这些实践方法还是可以有效地收敛新旧两个库的数据差异，你可以酌情采用。

小结

设计在线切换数据库的技术方案，首先要保证安全性，确保每一个步骤一旦失败，都可以快速回滚。此外，还要确保迁移过程中不丢数据，这主要是依靠实时同步程序和对比补偿程序来实现。

我把这个复杂的切换过程的要点，按照顺序总结成下面这个列表：

1. 上线同步程序，从旧库中复制数据到新库中，并实时保持同步；
2. 上线双写服务，只读写旧库；
3. 开启双写，同时停止同步程序；
4. 开启对比和补偿程序，确保新旧数据库数据完全一样；
5. 逐步切量读请求到新库上；
6. 下线对比补偿程序，关闭双写，读写都切换到新库上；
7. 下线旧库和服务的双写功能。

Hash冲突主要有两种解决办法，开放寻址法和链表法。这两种冲突解决办法在实际的软件开发中都非常常用。比如，Java 中 LinkedHashMap 就采用了链表法解决冲突，ThreadLocalMap 是通过线性探测的开放寻址法来解决冲突。那么这两种冲突解决方法各有什么优势和劣势，又各自适用哪些场景吗？

开放寻址法

我们先来看看，开放寻址法的优点有哪些。

开放寻址法不像链表法，需要拉很多链表。散列表中的数据都存储在数组中，可以有效地利用 CPU 缓存加快查询速度。而且，这种方法实现的散列表，序列化起来比较简单。链表法包含指针，序列化起来就没那么容易。你可不要小看序列化，很多场合都会用到的。我们后面就有一节会讲什么是数据结构序列化、如何序列化，以及为什么要序列化。

我们再来看下，开放寻址法有哪些缺点。

上一节我们讲到，用开放寻址法解决冲突的散列表，删除数据的时候比较麻烦，需要特殊标记已经删除掉的数据。而且，在开放寻址法中，所有的数据都存储在一个数组中，比起链表法来说，冲突的代价更高。所以，使用开放寻址法解决冲突的散列表，装载因子的上限不能太大。这也导致这种方法比链表法更浪费内存空间。

所以，我总结一下，当数据量比较小、装载因子小的时候，适合采用开放寻址法。这也是 Java 中的ThreadLocalMap使用开放寻址法解决散列冲突的原因。

链表法

首先，链表法对内存的利用率比开放寻址法要高。因为链表结点可以在需要的时候再创建，并不需要像开放寻址法那样事先申请好。实际上，这一点也是链表优于数组的地方。

链表法比起开放寻址法，对大装载因子的容忍度更高。开放寻址法只能适用装载因子小于 1 的情况。接近 1 时，就可能会有大量的散列冲突，导致大量的探测、再散列等，性能会下降很多。但是对于链表法来说，只要散列函数的值随机均匀，即便装载因子变成 10，也就是链表的长度变长了而已，虽然查找效率有所下降，但是比起顺序查找还是快很多。

链表因为要存储指针，所以对于比较小的对象的存储，是比较消耗内存的，还有可能会让内存的消耗翻倍。而且，因为链表中的结点是零散分布在内存中的，不是连续的，所以对 CPU 缓存是不友好的，这方面对于执行效率也有一定的影响。

当然，如果我们存储的是大对象，也就是说要存储的对象的大小远远大于一个指针的大小（4 个字节或者 8 个字节），那链表中指针的内存消耗在大对象面前就可以忽略了。

实际上，我们对链表法稍加改造，可以实现一个更加高效的散列表。那就是，我们将链表法中的链表改造为其他高效的动态数据结构，比如跳表、红黑树。这样，即便出现散列冲突，极端情况下，所有的数据都散列到同一个桶内，那最终退化成的散列表的查找时间也只不过是 O(logn)。这样也就有效避免了前面讲到的散列碰撞攻击。

所以，我总结一下，基于链表的散列冲突处理方法比较适合存储大对象、大数据量的散列表，而且，比起开放寻址法，它更加灵活，支持更多的优化策略，比如用红黑树代替链表。

年前docker oomkilled 问题一直在困扰我们项目组，大致现象为java堆Xmx配置了6G，但运行一段时间后常驻内存RSS从5G逐渐增长到8G容器阈值，最后报出om killed 之后重启。因为我们业务对内存需求不是很迫切，所以占用8G内存明显不合理，所以之后有了一场漫长的排查问题之旅。

基础中的基础-JVM内存模型

开始逐步对堆外内存进行排查，首先了解一下JVM内存模型。根据JVM规范，JVM运行时数据区共分为虚拟机栈、堆、方法区、程序计数器、本地方法栈五个部分。


• PC 寄存器，也叫程序计数器。可以看成是当前线程所执行的字节码的行号指示器。不是重点。

• 虚拟机栈，描述Java方法执行的内存区域，它是线程私有的，栈帧在整个JVM体系中的地位颇高,包括局部变量表、操作栈、动态连接、方法返回地址等。当申请不到空间时，会抛出 OutOfMemoryError。

• 本地方法栈，和虚拟机栈实现的功能与抛出异常几乎相同。

• 堆内存。堆内存是 JVM 所有线程共享的部分，在虚拟机启动的时候就已经创建。所有的对象和数组都在堆上进行分配。这部分空间可通过 GC 进行回收。当申请不到空间时会抛出 OutOfMemoryError。

• Metaspace（元空间）在JDK 1.8开始，方法区实现采用Metaspace代替，这些元数据信息直接使用本地内存来分配。元空间与永久代之间最大的区别在于：元空间不属于JVM使用的内存，而是使用（进程中的）直接内存。当申请不到空间时会抛出 OutOfMemoryError。

直接内存

java 8下是指除了Xmx设置的java堆外，java进程使用的其他内存。主要包括：DirectByteBuffer分配的内存，JNI里分配的内存，线程栈分配占用的系统内存，jvm本身运行过程分配的内存，codeCache，metaspace元数据空间。

JVM监控分析

可以看到重启前堆内存、栈内存、元空间、直接内存占用空间都没有异常，多数问题通过监控就能定位大致方向，可惜这次监控大法没有生效，怀疑是JVM问题转向JVM原生内存使用方向排查。

使用NMT排查JVM原生内存使用

Native Memory Tracking（NMT）使用

NMT是Java7U40引入的HotSpot新特性，可用于监控JVM原生内存的使用，但比较可惜的是，目前的NMT不能监控到JVM之外或原生库分配的内存。java进程启动时指定开启NMT（有一定的性能损耗），输出级别可以设置为“summary”或“detail”级别。如：

1
2

-XX:NativeMemoryTracking=summary 或者 
-XX:NativeMemoryTracking=detail

开启后，通过jcmd可以访问收集到的数据。

1

jcmd <pid> VM.native_memory [summary | detail | baseline | summary.diff | detail.diff 

如：jcmd 1 VM.native_memory，输出如下：

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

Native Memory Tracking:

Total: reserved=12259645KB（保留内存）, committed=11036265KB （提交内存）
堆内存使用情况，保留内存和提交内存和Xms、Xmx一致，都是8G。
-                 Java Heap (reserved=8388608KB, committed=8388608KB)
                            (mmap: reserved=8388608KB, committed=8388608KB)
用于存储类元数据信息使用到的原生内存，总共12045个类，整体实际使用了79M内存。
-                     Class (reserved=1119963KB, committed=79751KB)
                            (classes #12045)
                            (malloc=1755KB #29277)
                            (mmap: reserved=1118208KB, committed=77996KB)
总共2064个线程，提交内存是2.1G左右，一个线程1M，和设置Xss1m相符。
-                    Thread (reserved=2130294KB, committed=2130294KB)
                            (thread #2064)
                            (stack: reserved=2120764KB, committed=2120764KB)
                            (malloc=6824KB #10341)
                            (arena=2706KB #4127)
JIT的代码缓存，12045个类JIT编译后代码缓存整体使用79M内存。
-                      Code (reserved=263071KB, committed=79903KB)
                            (malloc=13471KB #15191)
                            (mmap: reserved=249600KB, committed=66432KB)
GC相关使用到的一些堆外内存，比如GC算法的处理锁会使用一些堆外空间。118M左右。
-                        GC (reserved=118432KB, committed=118432KB)
                            (malloc=93848KB #453)
                            (mmap: reserved=24584KB, committed=24584KB)
JAVA编译器自身操作使用到的一些堆外内存，很少。
-                  Compiler (reserved=975KB, committed=975KB)
                            (malloc=844KB #1074)
                            (arena=131KB #3)
Internal：memory used by the command line parser, JVMTI, properties等。
-                  Internal (reserved=117158KB, committed=117158KB)
                            (malloc=117126KB #44857)
                            (mmap: reserved=32KB, committed=32KB)
Symbol：保留字符串（Interned String）的引用与符号表引用放在这里，17M左右
-                    Symbol (reserved=17133KB, committed=17133KB)
                            (malloc=13354KB #145640)
                            (arena=3780KB #1)
NMT本身占用的堆外内存，4M左右
-    Native Memory Tracking (reserved=4402KB, committed=4402KB)
                            (malloc=396KB #5287)
                            (tracking overhead=4006KB)
不知道啥，用的很少。
-               Arena Chunk (reserved=272KB, committed=272KB)
                            (malloc=272KB)
其他未分类的堆外内存占用，100M左右。
-                   Unknown (reserved=99336KB, committed=99336KB)
                            (mmap: reserved=99336KB, committed=99336KB)

• 保留内存（reserved）：reserved memory 是指JVM 通过mmaped PROT_NONE 申请的虚拟地址空间，在页表中已经存在了记录（entries），保证了其他进程不会被占用，且保证了逻辑地址的连续性，能简化指针运算。
• 提交内存（commited）：committed memory 是JVM向操做系统实际分配的内存（malloc/mmap）,mmaped PROT_READ | PROT_WRITE,仍然会page faults，但是跟 reserved 不同，完全内核处理像什么也没发生一样。

这里需要注意的是：由于malloc/mmap的lazy allocation and paging机制，即使是commited的内存，也不一定会真正分配物理内存。

malloc/mmap is lazy unless told otherwise. Pages are only backed by physical memory once they’re accessed.

Tips：由于内存是一直在缓慢增长，因此在使用NMT跟踪堆外内存时，一个比较好的办法是，先建立一个内存使用基线，一段时间后再用当时数据和基线进行差别比较，这样比较容易定位问题。

1

jcmd 1 VM.native_memory baseline

同时pmap看一下物理内存的分配，RSS占用了10G。

1

pmap -x 1 | sort -n -k3



运行一段时间后，做一下summary级别的diff，看下内存变化，同时再次pmap看下RSS增长情况。

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

jcmd 1 VM.native_memory summary.diff
Native Memory Tracking:

Total: reserved=13089769KB +112323KB, committed=11877285KB +117915KB

-                 Java Heap (reserved=8388608KB, committed=8388608KB)
                            (mmap: reserved=8388608KB, committed=8388608KB)

-                     Class (reserved=1126527KB +2161KB, committed=85771KB +2033KB)
                            (classes #12682 +154)
                            (malloc=2175KB +113KB #37289 +2205)
                            (mmap: reserved=1124352KB +2048KB, committed=83596KB +1920KB)

-                    Thread (reserved=2861485KB +94989KB, committed=2861485KB +94989KB)
                            (thread #2772 +92)
                            (stack: reserved=2848588KB +94576KB, committed=2848588KB +94576KB)
                            (malloc=9169KB +305KB #13881 +460)
                            (arena=3728KB +108 #5543 +184)

-                      Code (reserved=265858KB +1146KB, committed=94130KB +6866KB)
                            (malloc=16258KB +1146KB #18187 +1146)
                            (mmap: reserved=249600KB, committed=77872KB +5720KB)

-                        GC (reserved=118433KB +1KB, committed=118433KB +1KB)
                            (malloc=93849KB +1KB #487 +24)
                            (mmap: reserved=24584KB, committed=24584KB)

-                  Compiler (reserved=1956KB +253KB, committed=1956KB +253KB)
                            (malloc=1826KB +253KB #2098 +271)
                            (arena=131KB #3)

-                  Internal (reserved=203932KB +13143KB, committed=203932KB +13143KB)
                            (malloc=203900KB +13143KB #62342 +3942)
                            (mmap: reserved=32KB, committed=32KB)

-                    Symbol (reserved=17820KB +108KB, committed=17820KB +108KB)
                            (malloc=13977KB +76KB #152204 +257)
                            (arena=3844KB +32 #1)

-    Native Memory Tracking (reserved=5519KB +517KB, committed=5519KB +517KB)
                            (malloc=797KB +325KB #9992 +3789)
                            (tracking overhead=4722KB +192KB)

-               Arena Chunk (reserved=294KB +5KB, committed=294KB +5KB)
                            (malloc=294KB +5KB)

-                   Unknown (reserved=99336KB, committed=99336KB)
                            (mmap: reserved=99336KB, committed=99336KB



发现这段时间pmap看到的RSS增长了3G多，但NMT观察到的内存增长了不到120M，还有大概2G多常驻内存不知去向，因此也基本排除了由于JVM自身管理的堆外内存的嫌疑。

gdb分析内存块内容

上面提到使用pmap来查看进程的内存映射，pmap命令实际是读取了/proc/pid/maps和/porc/pid/smaps文件来输出。发现一个细节，pmap取出的内存映射发现很多64M大小的内存块。这种内存块逐渐变多且占用的RSS常驻内存也逐渐增长到reserved保留内存大小，内存增长的2G多基本上也是由于这些64M的内存块导致的，因此看一下这些内存块里具体内容。

pmap -x 1看一下实际内存分配情况：


找一块内存块进行dump：

1

gdb --batch --pid 1 -ex "dump memory a.dump 0x7fd488000000 0x7fd488000000+56124000"

简单分析一下内容，发现绝大部分是乱码的二进制内容，看不出什么问题。
strings a.dump | less
或者： hexdump -C a.dump | less
或者： view a.dump

没啥思路的时候，随便搜了一下发现貌似很多人碰到这种64M内存块的问题，了解到glibc的内存分配策略在高版本有较大调整：

从glibc 2.11（为应用系统在多核心CPU和多Sockets环境中高伸缩性提供了一个动态内存分配的特性增强）版本开始引入了per thread arena内存池，Native Heap区被打散为sub-pools ，这部分内存池叫做Arena内存池。也就是说，以前只有一个main arena，目前是一个main arena（还是位于Native Heap区） + 多个per thread arena，多个线程之间不再共用一个arena内存区域了，保证每个线程都有一个堆，这样避免内存分配时需要额外的锁来降低性能。main arena主要通过brk/sbrk系统调用去管理，per thread arena主要通过mmap系统调用去分配和管理。

一个32位的应用程序进程，最大可创建 2 CPU总核数个arena内存池（MALLOC_ARENA_MAX），每个arena内存池大小为1MB，一个64位的应用程序进程，最大可创建 8 CPU总核数个arena内存池（MALLOC_ARENA_MAX），每个arena内存池大小为64MB

ptmalloc2内存分配和释放

当某一线程需要调用 malloc()分配内存空间时， 该线程先查看线程私有变量中是否已经存在一个分配区，如果存在， 尝试对该分配区加锁，如果加锁成功，使用该分配区分配内存，如果失败， 该线程搜索循环链表试图获得一个没有加锁的分配区。如果所有的分配区都已经加锁，那么 malloc()会开辟一个新的分配区，把该分配区加入到全局分配区循环链表并加锁，然后使用该分配区进行分配内存操作。在释放操作中，线程同样试图获得待释放内存块所在分配区的锁，如果该分配区正在被别的线程使用，则需要等待直到其他线程释放该分配区的互斥锁之后才可以进行释放操作。用户 free 掉的内存并不是都会马上归还给系统，ptmalloc2 会统一管理 heap 和 mmap 映射区域中的空闲的chunk，当用户进行下一次分配请求时， ptmalloc2 会首先试图在空闲的chunk 中挑选一块给用户，这样就避免了频繁的系统调用，降低了内存分配的开销。

ptmalloc2的内存收缩机制

业务层调用free方法释放内存时，ptmalloc2先判断 top chunk 的大小是否大于 mmap 收缩阈值(默认为 128KB)，如果是的话，对于主分配区，则会试图归还 top chunk 中的一部分给操作系统。但是最先分配的 128KB 空间是不会归还的，ptmalloc 会一直管理这部分内存，用于响应用户的分配 请求;如果为非主分配区，会进行 sub-heap 收缩，将 top chunk 的一部分返回给操 作系统，如果 top chunk 为整个 sub-heap，会把整个 sub-heap 还回给操作系统。做 完这一步之后，释放结束，从 free() 函数退出。可以看出，收缩堆的条件是当前 free 的 chunk 大小加上前后能合并 chunk 的大小大于 64k，并且要 top chunk 的大 小要达到 mmap 收缩阈值，才有可能收缩堆。

ptmalloc2的mmap分配阈值动态调整

M_MMAP_THRESHOLD 用于设置 mmap 分配阈值，默认值为 128KB，ptmalloc 默认开启 动态调整 mmap 分配阈值和 mmap 收缩阈值。当用户需要分配的内存大于 mmap 分配阈值，ptmalloc 的 malloc()函数其实相当于 mmap() 的简单封装，free 函数相当于 munmap()的简单封装。相当于直接通过系统调用分配内存， 回收的内存就直接返回给操作系统了。因为这些大块内存不能被 ptmalloc 缓存管理，不能重用，所以 ptmalloc 也只有在万不得已的情况下才使用该方式分配内存。

如何优化解决

三种方案：

第一种：控制分配区的总数上限。默认64位系统分配区数为：cpu核数*8，如当前环境40核系统分配区数为320个，每个64M上限的话最多可达20G，限制上限后，后续不够的申请会直接走mmap分配和munmap回收，不会进入ptmalloc2的buffer池。
所以第一种方案调整一下分配池上限个数到4：

1

export MALLOC_ARENA_MAX=4

第二种：之前降到ptmalloc2默认会动态调整mmap分配阈值，因此对于较大的内存请求也会进入ptmalloc2的内存buffer池里，这里可以去掉ptmalloc的动态调整功能。可以设置 M_TRIM_THRESHOLD，M_MMAP_THRESHOLD，M_TOP_PAD 和 M_MMAP_MAX 中的任意一个。这里可以固定分配阈值为128K，这样超过128K的内存分配请求都不会进入ptmalloc的buffer池而是直接走mmap分配和munmap回收（性能上会有损耗）：

1
2
3
4

export MALLOC_MMAP_THRESHOLD_=131072
export MALLOC_TRIM_THRESHOLD_=131072
export MALLOC_TOP_PAD_=131072
export MALLOC_MMAP_MAX_=65536   

第三种：使用tcmalloc来替代默认的ptmalloc2。google的tcmalloc提供更优的内存分配效率，性能更好，ThreadCache会阶段性的回收内存到CentralCache里。 解决了ptmalloc2中arena之间不能迁移导致内存浪费的问题。

总结收获

• 定位问题，一定要了解问题的领域范围，在这次排查中，定位OOM问题领域顺序就是 jvm内存 -> jvm内部内存 -> 进程内存。

• 操作系统知识不能丢，扎实的基础知识可以节省非常多百度的时间和推理问题的时间

• 知识领域是相同的，比如这次的ptmalloc内存分配基本原理和metaspace内存分配、netty的内存分配原理非常相似

• 当时排查问题时因为已经定位到是内存分配问题，所以没有留下问题排查中间过程的相关数据。最近偶然看到一篇博客的记录和我的经历极为相似，于是我参考博客和自己的排查经验整合了这篇排查问题记录。结果和过程都很重要，只有结果，没有过程容易招致他人的不理解，能被人理解也是一门学问～

因为字符比较是从右往左比较的，所以第一层循环 needle.length + 1 <= i < haystack.length。

1
2
3
4
5
6
7
8
9
10
11
12
13

                  start=needle.length - 1                                             end=haystack.length - 1
                          +                                                                   +
                          |                                                                   |
                          |                                                                   |
                          v-------------------------------------------------------------------v->
  0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15  16  17  18  19  20  21  22  23
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
| t | h | i | s |   | i | s |   | a |   | s | i | m | p | l | e |   | e | x | a | m | p | l | e |
+-------------------------------+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
+---------------------------+
| e | x | a | m | p | l | e |
+---+---+---+---+---+---+---+

第二层循环中i变量表示坏字符的位置、j表示搜索坏字符开始位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

                          i
                          +
                          |
                          v
  0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15  16  17  18  19  20  21  22  23
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
| t | h | i | s |   | i | s |   | a |   | s | i | m | p | l | e |   | e | x | a | m | p | l | e |
+-------------------------------+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
+---------------------------+
| e | x | a | m | p | l | e |
+---+---+---+---+---+---+-+-+
                          ^
                          |
                          +
                          j

i,j指针向左搜索,如果完全匹配直接返回i即可

1
2
3
4
5

for (j = needle.length - 1; needle[j] == haystack[i]; --i, --j) {
    if (j == 0) {
        return i;
    }
}

坏字符规则和好字符规则

坏字符:从右向左第一个不匹配的字符
好字符:从坏字符下一个字符直到最后的字符

可以认为字符移动有两种策略：坏字符对齐和好字符对齐，然后选择字符移动距离大的策略即可

wiki实现

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

/**
 * Returns the index within this string of the first occurrence of the
 * specified substring. If it is not a substring, return -1.
 *
 * There is no Galil because it only generates one match.
 *
 * @param haystack The string to be scanned
 * @param needle The target string to search
 * @return The start index of the substring
 */
public static int indexOf(char[] haystack, char[] needle) {
    if (needle.length == 0) {
        return 0;
    }
    int charTable[] = makeCharTable(needle);
    int offsetTable[] = makeOffsetTable(needle);
    for (int i = needle.length - 1, j; i < haystack.length;) {
        for (j = needle.length - 1; needle[j] == haystack[i]; --i, --j) {
            if (j == 0) {
                return i;
            }
        }
        // i += needle.length - j; // For naive method
        i += Math.max(offsetTable[needle.length - 1 - j], charTable[haystack[i]]);
    }
    return -1;
}

/**
 * Makes the jump table based on the mismatched character information.
 */
private static int[] makeCharTable(char[] needle) {
    final int ALPHABET_SIZE = Character.MAX_VALUE + 1; // 65536
    int[] table = new int[ALPHABET_SIZE];
    for (int i = 0; i < table.length; ++i) {
        table[i] = needle.length;
    }
    for (int i = 0; i < needle.length - 2; ++i) {
        table[needle[i]] = needle.length - 1 - i;
    }
    return table;
}

/**
 * Makes the jump table based on the scan offset which mismatch occurs.
 * (bad character rule).
 */
private static int[] makeOffsetTable(char[] needle) {
    int[] table = new int[needle.length];
    int lastPrefixPosition = needle.length;
    for (int i = needle.length; i > 0; --i) {
        if (isPrefix(needle, i)) {
            lastPrefixPosition = i;
        }
        table[needle.length - i] = lastPrefixPosition - i + needle.length;
    }
    for (int i = 0; i < needle.length - 1; ++i) {
        int slen = suffixLength(needle, i);
        table[slen] = needle.length - 1 - i + slen;
    }
    return table;
}

/**
 * Is needle[p:end] a prefix of needle?
 */
private static boolean isPrefix(char[] needle, int p) {
    for (int i = p, j = 0; i < needle.length; ++i, ++j) {
        if (needle[i] != needle[j]) {
            return false;
        }
    }
    return true;
}

/**
 * Returns the maximum length of the substring ends at p and is a suffix.
 * (good suffix rule)
 */
private static int suffixLength(char[] needle, int p) {
    int len = 0;
    for (int i = p, j = needle.length - 1;
             i >= 0 && needle[i] == needle[j]; --i, --j) {
        len += 1;
    }
    return len;
}

什么是幂等

幂等是一个数学上的概念，它的含义是多次执行同一个操作和执行一次操作，最终得到的结果是相同的。

如果我们消费一条消息的时候，要给现有的库存数量减 1，那么如果消费两条相同的消息就会给库存数量减 2，这就不是幂等的。而如果消费一条消息后，处理逻辑是将库存的数量设置为 0，或者是如果当前库存数量是 10 时则减 1，这样在消费多条消息时，所得到的结果就是相同的，这就是幂等的。

说白了，你可以这么理解“幂等”：一件事儿无论做多少次都和做一次产生的结果是一样的，那么这件事儿就具有幂等性。

在生产、消费过程中增加消息幂等性的保证

消息在生产和消费的过程中都可能会产生重复，所以你要做的是，在生产过程和消费过程中增加消息幂等性的保证，这样就可以认为从最终结果上来看，消息实际上是只被消费了一次的。

在消息生产过程中，在 Kafka0.11 版本和 Pulsar 中都支持“producer idempotency”的特性，翻译过来就是生产过程的幂等性，这种特性保证消息虽然可能在生产端产生重复，但是最终在消息队列存储时只会存储一份。

它的做法是给每一个生产者一个唯一的 ID，并且为生产的每一条消息赋予一个唯一 ID，消息队列的服务端会存储 < 生产者 ID，最后一条消息 ID> 的映射。当某一个生产者产生新的消息时，消息队列服务端会比对消息 ID 是否与存储的最后一条 ID 一致，如果一致，就认为是重复的消息，服务端会自动丢弃。

而在消费端，幂等性的保证会稍微复杂一些，你可以从通用层和业务层两个层面来考虑。

在通用层面，你可以在消息被生产的时候，使用发号器给它生成一个全局唯一的消息 ID，消息被处理之后，把这个 ID 存储在数据库中，在处理下一条消息之前，先从数据库里面查询这个全局 ID 是否被消费过，如果被消费过就放弃消费。

你可以看到，无论是生产端的幂等性保证方式，还是消费端通用的幂等性保证方式，它们的共同特点都是为每一个消息生成一个唯一的 ID，然后在使用这个消息的时候，先比对这个 ID 是否已经存在，如果存在，则认为消息已经被使用过。所以这种方式是一种标准的实现幂等的方式，你在项目之中可以拿来直接使用，它在逻辑上的伪代码就像下面这样：

1
2
3
4
5
6
7
8
9
10
11
12
13

boolean isIDExisted = selectByID(ID); // 判断 ID 是否存在

if(isIDExisted) {

  return; // 存在则直接返回

} else {

  process(message); // 不存在，则处理消息

  saveID(ID);   // 存储 ID

}

不过这样会有一个问题：如果消息在处理之后，还没有来得及写入数据库，消费者宕机了重启之后发现数据库中并没有这条消息，还是会重复执行两次消费逻辑，这时你就需要引入事务机制，保证消息处理和写入数据库必须同时成功或者同时失败，但是这样消息处理的成本就更高了，所以，如果对于消息重复没有特别严格的要求，可以直接使用这种通用的方案，而不考虑引入事务。

在业务层面怎么处理呢？这里有很多种处理方式，其中有一种是增加乐观锁的方式。比如，你的消息处理程序需要给一个人的账号加钱，那么你可以通过乐观锁的方式来解决。

具体的操作方式是这样的：你给每个人的账号数据中增加一个版本号的字段，在生产消息时先查询这个账户的版本号，并且将版本号连同消息一起发送给消息队列。消费端在拿到消息和版本号后，在执行更新账户金额 SQL 的时候带上版本号，类似于执行：

1

update user set amount = amount + 20, version=version+1 where userId=1 and version=1;

你看，我们在更新数据时给数据加了乐观锁，这样在消费第一条消息时，version 值为 1，SQL 可以执行成功，并且同时把 version 值改为了 2；在执行第二条相同的消息时，由于 version 值不再是 1，所以这条 SQL 不能执行成功，也就保证了消息的幂等性。

消息会丢失的环节

消息从被写入到消息队列，到被消费者消费完成，这个链路上会有哪些地方存在丢失消息的可能呢？其实，主要存在三个场景：

• 消息从生产者写入到消息队列的过程。

• 消息在消息队列中的存储场景。

• 消息被消费者消费的过程。

1. 在消息生产的过程中丢失消息

消息的生产者一般是我们的业务服务器，消息队列是独立部署在单独的服务器上的。两者之间的网络虽然是内网，但是也会存在抖动的可能，而一旦发生抖动，消息就有可能因为网络的错误而丢失。

针对这种情况，我建议你采用的方案是消息重传：也就是当你发现发送超时后你就将消息重新发一次，但是你也不能无限制地重传消息。一般来说，如果不是消息队列发生故障，或者是到消息队列的网络断开了，重试 2～3 次就可以了。

不过，这种方案可能会造成消息的重复，从而导致在消费的时候会重复消费同样的消息。比方说，消息生产时由于消息队列处理慢或者网络的抖动，导致虽然最终写入消息队列成功，但在生产端却超时了，生产者重传这条消息就会形成重复的消息。

2. 在消息队列中丢失消息

拿 Kafka 举例，消息在 Kafka 中是存储在本地磁盘上的，而为了减少消息存储时对磁盘的随机 I/O，我们一般会将消息先写入到操作系统的 Page Cache 中，然后再找合适的时机刷新到磁盘上。

比如，Kafka 可以配置当达到某一时间间隔，或者累积一定的消息数量的时候再刷盘，也就是所说的异步刷盘。

不过，如果发生机器掉电或者机器异常重启，那么 Page Cache 中还没有来得及刷盘的消息就会丢失了。那么怎么解决呢？

你可能会把刷盘的间隔设置很短，或者设置累积一条消息就就刷盘，但这样频繁刷盘会对性能有比较大的影响，而且从经验来看，出现机器宕机或者掉电的几率也不高，所以我不建议你这样做。

如果你的系统对消息丢失的容忍度很低，那么你可以考虑以集群方式部署 Kafka 服务，通过部署多个副本备份数据，保证消息尽量不丢失。

那么它是怎么实现的呢？

Kafka 集群中有一个 Leader 负责消息的写入和消费，可以有多个 Follower 负责数据的备份。Follower 中有一个特殊的集合叫做 ISR（in-sync replicas），当 Leader 故障时，新选举出来的 Leader 会从 ISR 中选择，默认 Leader 的数据会异步地复制给 Follower，这样在 Leader 发生掉电或者宕机时，Kafka 会从 Follower 中消费消息，减少消息丢失的可能。

由于默认消息是异步地从 Leader 复制到 Follower 的，所以一旦 Leader 宕机，那些还没有来得及复制到 Follower 的消息还是会丢失。为了解决这个问题，Kafka 为生产者提供一个选项叫做“acks”，当这个选项被设置为“all”时，生产者发送的每一条消息除了发给 Leader 外还会发给所有的 ISR，并且必须得到 Leader 和所有 ISR 的确认后才被认为发送成功。这样，只有 Leader 和所有的 ISR 都挂了，消息才会丢失。

从上面这张图来看，当设置“acks=all”时，需要同步执行 1，3，4 三个步骤，对于消息生产的性能来说也是有比较大的影响的，所以你在实际应用中需要仔细地权衡考量。我给你的建议是：

1. 如果你需要确保消息一条都不能丢失，那么建议不要开启消息队列的同步刷盘，而是需要使用集群的方式来解决，可以配置当所有 ISR Follower 都接收到消息才返回成功。

2. 如果对消息的丢失有一定的容忍度，那么建议不部署集群，即使以集群方式部署，也建议配置只发送给一个 Follower 就可以返回成功了。

3. 我们的业务系统一般对于消息的丢失有一定的容忍度，比如说以上面的红包系统为例，如果红包消息丢失了，我们只要后续给没有发送红包的用户补发红包就好了。

3. 在消费的过程中存在消息丢失的可能

我还是以 Kafka 为例来说明。一个消费者消费消息的进度是记录在消息队列集群中的，而消费的过程分为三步：接收消息、处理消息、更新消费进度。

这里面接收消息和处理消息的过程都可能会发生异常或者失败，比如说，消息接收时网络发生抖动，导致消息并没有被正确的接收到；处理消息时可能发生一些业务的异常导致处理流程未执行完成，这时如果更新消费进度，那么这条失败的消息就永远不会被处理了，也可以认为是丢失了。

所以，在这里你需要注意的是，一定要等到消息接收和处理完成后才能更新消费进度，但是这也会造成消息重复的问题，比方说某一条消息在处理之后，消费者恰好宕机了，那么因为没有更新消费进度，所以当这个消费者重启之后，还会重复地消费这条消息。

4. 最佳实践

1. 不要使用 producer.send(msg)，而要使用 producer.send(msg, callback)。记住，一定要使用带有回调通知的 send 方法。
2. 设置 acks = all。acks 是 Producer 的一个参数，代表了你对“已提交”消息的定义。如果设置成 all，则表明所有副本 Broker 都要接收到消息，该消息才算是“已提交”。这是最高等级的“已提交”定义。
3. 设置 retries 为一个较大的值。这里的 retries 同样是 Producer 的参数，对应前面提到的 Producer 自动重试。当出现网络的瞬时抖动时，消息发送可能会失败，此时配置了 retries > 0 的 Producer 能够自动重试消息发送，避免消息丢失。
4. 设置 unclean.leader.election.enable = false。这是 Broker 端的参数，它控制的是哪些 Broker 有资格竞选分区的 Leader。如果一个 Broker 落后原先的 Leader 太多，那么它一旦成为新的 Leader，必然会造成消息的丢失。故一般都要将该参数设置成 false，即不允许这种情况的发生。
5. 设置 replication.factor >= 3。这也是 Broker 端的参数。其实这里想表述的是，最好将消息多保存几份，毕竟目前防止消息丢失的主要机制就是冗余。
6. 设置 min.insync.replicas > 1。这依然是 Broker 端参数，控制的是消息至少要被写入到多少个副本才算是“已提交”。设置成大于 1 可以提升消息持久性。在实际环境中千万不要使用默认值 1。
7. 确保 replication.factor > min.insync.replicas。如果两者相等，那么只要有一个副本挂机，整个分区就无法正常工作了。我们不仅要改善消息的持久性，防止数据丢失，还要在不降低可用性的基础上完成。推荐设置成 replication.factor = min.insync.replicas + 1。
8. 确保消息消费完成再提交。Consumer 端有个参数 enable.auto.commit，最好把它设置成 false，并采用手动提交位移的方式。就像前面说的，这对于单 Consumer 多线程处理的场景而言是至关重要的。

什么是缓存穿透

缓存穿透其实是指从缓存中没有查到数据，而不得不从后端系统（比如数据库）中查询的情况。你可以把数据库比喻为手机，它是经受不了太多的划痕和磕碰的，所以你需要给它贴个膜再套个保护壳，就能对手机起到一定的保护作用了。

不过，少量的缓存穿透不可避免，对系统也是没有损害的，主要有几点原因：

• 一方面，互联网系统通常会面临极大数据量的考验，而缓存系统在容量上是有限的，不可能存储系统所有的数据，那么在查询未缓存数据的时候就会发生缓存穿透。
• 另一方面，互联网系统的数据访问模型一般会遵从“80/20 原则”。“80/20 原则”又称为帕累托法则，是意大利经济学家帕累托提出的一个经济学的理论。它是指在一组事物中，最重要的事物通常只占 20%，而剩余的 80% 的事物确实不重要的。把它应用到数据访问的领域，就是我们会经常访问 20% 的热点数据，而另外的 80% 的数据则不会被经常访问。比如你买了很多衣服，很多书，但是其实经常穿的，经常看的，可能也就是其中很小的一部分。

既然缓存的容量有限，并且大部分的访问只会请求 20% 的热点数据，那么理论上说，我们只需要在有限的缓存空间里存储 20% 的热点数据就可以有效地保护脆弱的后端系统了，也就可以放弃缓存另外 80% 的非热点数据了。所以，这种少量的缓存穿透是不可避免的，但是对系统是没有损害的。

那么什么样的缓存穿透对系统有害呢？答案是大量的穿透请求超过了后端系统的承受范围，造成了后端系统的崩溃。如果把少量的请求比作毛毛细雨，那么一旦变成倾盆大雨，引发洪水，冲倒房屋，肯定就不行了。

产生这种大量穿透请求的场景有很多，接下来，我就带你解析这几种场景以及相应的解决方案。

缓存穿透的解决方案

先来考虑这样一种场景：在你的电商系统的用户表中，我们需要通过用户 ID 查询用户的信息，缓存的读写策略采用 Cache Aside 策略。

那么，如果要读取一个用户表中未注册的用户，会发生什么情况呢？按照这个策略，我们会先读缓存，再穿透读数据库。由于用户并不存在，所以缓存和数据库中都没有查询到数据，因此也就不会向缓存中回种数据（也就是向缓存中设置值的意思），这样当再次请求这个用户数据的时候还是会再次穿透到数据库。在这种场景下，缓存并不能有效地阻挡请求穿透到数据库上，它的作用就微乎其微了。

那如何解决缓存穿透呢？一般来说我们会有两种解决方案：回种空值以及使用布隆过滤器。

我们先来看看第一种方案。

回种空值

回顾上面提到的场景，你会发现最大的问题在于数据库中并不存在用户的数据，这就造成无论查询多少次，数据库中永远都不会存在这个用户的数据，穿透永远都会发生。

类似的场景还有一些：比如由于代码的 bug 导致查询数据库的时候抛出了异常，这样可以认为从数据库查询出来的数据为空，同样不会回种缓存。

那么，当我们从数据库中查询到空值或者发生异常时，我们可以向缓存中回种一个空值。但是因为空值并不是准确的业务数据，并且会占用缓存的空间，所以我们会给这个空值加一个比较短的过期时间，让空值在短时间之内能够快速过期淘汰。下面是这个流程的伪代码：

1
2
3
4
5
6
7
8
9
10
11

Object nullValue = new Object();
try {
  Object valueFromDB = getFromDB(uid); // 从数据库中查询数据
  if (valueFromDB == null) {
    cache.set(uid, nullValue, 10);   // 如果从数据库中查询到空值，就把空值写入缓存，设置较短的超时时间
  } else {
    cache.set(uid, valueFromDB, 1000);
  }
} catch(Exception e) {
  cache.set(uid, nullValue, 10);
}

回种空值虽然能够阻挡大量穿透的请求，但如果有大量获取未注册用户信息的请求，缓存内就会有有大量的空值缓存，也就会浪费缓存的存储空间，如果缓存空间被占满了，还会剔除掉一些已经被缓存的用户信息反而会造成缓存命中率的下降。

所以这个方案，我建议你在使用的时候应该评估一下缓存容量是否能够支撑。如果需要大量的缓存节点来支持，那么就无法通过通过回种空值的方式来解决，这时你可以考虑使用布隆过滤器。

使用布隆过滤器

1970 年布隆提出了一种布隆过滤器的算法，用来判断一个元素是否在一个集合中。这种算法由一个二进制数组和一个 Hash 算法组成。它的基本思路如下：

我们把集合中的每一个值按照提供的 Hash 算法算出对应的 Hash 值，然后将 Hash 值对数组长度取模后得到需要计入数组的索引值，并且将数组这个位置的值从 0 改成 1。在判断一个元素是否存在于这个集合中时，你只需要将这个元素按照相同的算法计算出索引值，如果这个位置的值为 1 就认为这个元素在集合中，否则则认为不在集合中。

下图是布隆过滤器示意图，我来带你分析一下图内的信息。

A、B、C 等元素组成了一个集合，元素 D 计算出的 Hash 值所对应的的数组中值是 1，所以可以认为 D 也在集合中。而 F 在数组中的值是 0，所以 F 不在数组中。

那么我们如何使用布隆过滤器来解决缓存穿透的问题呢？

还是以存储用户信息的表为例进行讲解。首先，我们初始化一个很大的数组，比方说长度为 20 亿的数组，接下来我们选择一个 Hash 算法，然后我们将目前现有的所有用户的 ID 计算出 Hash 值并且映射到这个大数组中，映射位置的值设置为 1，其它值设置为 0。

新注册的用户除了需要写入到数据库中之外，它也需要依照同样的算法更新布隆过滤器的数组中，相应位置的值。那么当我们需要查询某一个用户的信息时，我们首先查询这个 ID 在布隆过滤器中是否存在，如果不存在就直接返回空值，而不需要继续查询数据库和缓存，这样就可以极大地减少异常查询带来的缓存穿透。

布隆过滤器拥有极高的性能，无论是写入操作还是读取操作，时间复杂度都是 O(1)，是常量值。在空间上，相对于其他数据结构它也有很大的优势，比如，20 亿的数组需要 2000000000/8/1024/1024 = 238M 的空间，而如果使用数组来存储，假设每个用户 ID 占用 4 个字节的空间，那么存储 20 亿用户需要 2000000000 * 4 / 1024 / 1024 = 7600M 的空间，是布隆过滤器的 32 倍。

不过，任何事物都有两面性，布隆过滤器也不例外，它主要有两个缺陷：

1. 它在判断元素是否在集合中时是有一定错误几率的，比如它会把不是集合中的元素判断为处在集合中；

2. 不支持删除元素。

关于第一个缺陷，主要是 Hash 算法的问题。因为布隆过滤器是由一个二进制数组和一个 Hash 算法组成的，Hash 算法存在着一定的碰撞几率。Hash 碰撞的含义是不同的输入值经过 Hash 运算后得到了相同的 Hash 结果。

本来，Hash 的含义是不同的输入，依据不同的算法映射成独一无二的固定长度的值，也就是我输入字符串“1”，根据 CRC32 算法，值是 2212294583。但是现实中 Hash 算法的输入值是无限的，输出值的值空间却是固定的，比如 16 位的 Hash 值的值空间是 65535，那么它的碰撞几率就是 1/65535，即如果输入值的个数超过 65535 就一定会发生碰撞。

那么你可能会问为什么不映射成更长的 Hash 值呢？

因为更长的 Hash 值会带来更高的存储成本和计算成本。即使使用 32 位的 Hash 算法，它的值空间长度是 2 的 32 次幂减一，约等于 42 亿，用来映射 20 亿的用户数据，碰撞几率依然有接近 50%。

Hash 的碰撞就造成了两个用户 ID ，A 和 B 会计算出相同的 Hash 值，那么如果 A 是注册的用户，它的 Hash 值对应的数组中的值是 1，那么 B 即使不是注册用户，它在数组中的位置和 A 是相同的，对应的值也是 1，这就产生了误判。

布隆过滤器的误判有一个特点，就是它只会出现“false positive”的情况。这是什么意思呢？当布隆过滤器判断元素在集合中时，这个元素可能不在集合中。但是一旦布隆过滤器判断这个元素不在集合中时，它一定不在集合中。这一点非常适合解决缓存穿透的问题。为什么呢？

你想，如果布隆过滤器会将集合中的元素判定为不在集合中，那么我们就不确定，被布隆过滤器判定为不在集合中的元素，是不是在集合中。假设在刚才的场景中，如果有大量查询未注册的用户信息的请求存在，那么这些请求到达布隆过滤器之后，即使布隆过滤器判断为不是注册用户，那么我们也不确定它是不是真的不是注册用户，那么就还是需要去数据库和缓存中查询，这就使布隆过滤器失去了价值。

所以你看，布隆过滤器虽然存在误判的情况，但是还是会减少缓存穿透的情况发生，只是我们需要尽量减少误判的几率，这样布隆过滤器的判断正确的几率更高，对缓存的穿透也更少。一个解决方案是：

使用多个 Hash 算法为元素计算出多个 Hash 值，只有所有 Hash 值对应的数组中的值都为 1 时，才会认为这个元素在集合中。

布隆过滤器不支持删除元素的缺陷也和 Hash 碰撞有关。给你举一个例子，假如两个元素 A 和 B 都是集合中的元素，它们有相同的 Hash 值，它们就会映射到数组的同一个位置。这时我们删除了 A，数组中对应位置的值也从 1 变成 0，那么在判断 B 的时候发现值是 0，也会判断 B 是不在集合中的元素，就会得到错误的结论。

那么我是怎么解决这个问题的呢？我会让数组中不再只有 0 和 1 两个值，而是存储一个计数。比如如果 A 和 B 同时命中了一个数组的索引，那么这个位置的值就是 2，如果 A 被删除了就把这个值从 2 改为 1。这个方案中的数组不再存储 bit 位，而是存储数值，也就会增加空间的消耗。所以，你要依据业务场景来选择是否能够使用布隆过滤器，比如像是注册用户的场景下，因为用户删除的情况基本不存在，所以还是可以使用布隆过滤器来解决缓存穿透的问题的。

讲了这么多，关于布隆过滤器的使用上，我也给你几个建议：

1. 选择多个 Hash 函数计算多个 Hash 值，这样可以减少误判的几率；

2. 布隆过滤器会消耗一定的内存空间，所以在使用时需要评估你的业务场景下需要多大的内存，存储的成本是否可以接受。

总的来说，回种空值和布隆过滤器是解决缓存穿透问题的两种最主要的解决方案，但是它们也有各自的适用场景，并不能解决所有问题。比方说当有一个极热点的缓存项，它一旦失效会有大量请求穿透到数据库，这会对数据库造成瞬时极大的压力，我们把这个场景叫做“dog-pile effect”（狗桩效应），

这是典型的缓存并发穿透的问题，那么，我们如何来解决这个问题呢？解决狗桩效应的思路是尽量地减少缓存穿透后的并发，方案也比较简单：

1. 在代码中，控制在某一个热点缓存项失效之后启动一个后台线程，穿透到数据库，将数据加载到缓存中，在缓存未加载之前，所有访问这个缓存的请求都不再穿透而直接返回。

2. 通过在 Memcached 或者 Redis 中设置分布式锁，只有获取到锁的请求才能够穿透到数据库。

分布式锁的方式也比较简单，比方说 ID 为 1 的用户是一个热点用户，当他的用户信息缓存失效后，我们需要从数据库中重新加载数据时，先向 Memcached 中写入一个 Key 为”lock.1”的缓存项，然后去数据库里面加载数据，当数据加载完成后再把这个 Key 删掉。这时，如果另外一个线程也要请求这个用户的数据，它发现缓存中有 Key 为“lock.1”的缓存，就认为目前已经有线程在加载数据库中的值到缓存中了，它就可以重新去缓存中查询数据，不再穿透数据库了。

分布式缓存的高可用方案主要选择的方案有客户端方案、中间代理层方案和服务端方案三大类：

• 客户端方案就是在客户端配置多个缓存的节点，通过缓存写入和读取算法策略来实现分布式，从而提高缓存的可用性。
• 中间代理层方案是在应用代码和缓存节点之间增加代理层，客户端所有的写入和读取的请求都通过代理层，而代理层中会内置高可用策略，帮助提升缓存系统的高可用。
• 服务端方案就是 Redis 2.4 版本后提出的 Redis Sentinel 方案。

掌握这些方案可以帮助你，抵御部分缓存节点故障导致的，缓存命中率下降的影响，增强你的系统的鲁棒性。

客户端方案

在客户端方案中，你需要关注缓存的写和读两个方面：

• 写入数据时，需要把被写入缓存的数据分散到多个节点中，即进行数据分片；
• 读数据时，可以利用多组的缓存来做容错，提升缓存系统的可用性。关于读数据，这里可以使用主从和多副本两种策略，两种策略是为了解决不同的问题而提出的。

下面我就带你一起详细地看一下到底要怎么做。

1. 缓存数据如何分片

单一的缓存节点受到机器内存、网卡带宽和单节点请求量的限制，不能承担比较高的并发，因此我们考虑将数据分片，依照分片算法将数据打散到多个不同的节点上，每个节点上存储部分数据。

这样在某个节点故障的情况下，其他节点也可以提供服务，保证了一定的可用性。这就好比不要把鸡蛋放在同一个篮子里，这样一旦一个篮子掉在地上，摔碎了，别的篮子里还有没摔碎的鸡蛋，不至于一个不剩。

一般来讲，分片算法常见的就是 Hash 分片算法和一致性 Hash 分片算法两种。

Hash 分片的算法就是对缓存的 Key 做哈希计算，然后对总的缓存节点个数取余。你可以这么理解：

比如说，我们部署了三个缓存节点组成一个缓存的集群，当有新的数据要写入时，我们先对这个缓存的 Key 做比如 crc32 等 Hash 算法生成 Hash 值，然后对 Hash 值模 3，得出的结果就是要存入缓存节点的序号。

这个算法最大的优点就是简单易理解，缺点是当增加或者减少缓存节点时，缓存总的节点个数变化造成计算出来的节点发生变化，从而造成缓存失效不可用。所以我建议你，如果采用这种方法，最好建立在你对于这组缓存命中率下降不敏感，比如下面还有另外一层缓存来兜底的情况下。

当然了，用一致性 Hash 算法可以很好地解决增加和删减节点时，命中率下降的问题。在这个算法中，我们将整个 Hash 值空间组织成一个虚拟的圆环，然后将缓存节点的 IP 地址或者主机名做 Hash 取值后，放置在这个圆环上。当我们需要确定某一个 Key 需要存取到哪个节点上的时候，先对这个 Key 做同样的 Hash 取值，确定在环上的位置，然后按照顺时针方向在环上“行走”，遇到的第一个缓存节点就是要访问的节点。比方说下面这张图里面，Key 1 和 Key 2 会落入到 Node 1 中，Key 3、Key 4 会落入到 Node 2 中，Key 5 落入到 Node 3 中，Key 6 落入到 Node 4 中。

这时如果在 Node 1 和 Node 2 之间增加一个 Node 5，你可以看到原本命中 Node 2 的 Key 3 现在命中到 Node 5，而其它的 Key 都没有变化；同样的道理，如果我们把 Node 3 从集群中移除，那么只会影响到 Key 5 。所以你看，在增加和删除节点时，只有少量的 Key 会“漂移”到其它节点上，而大部分的 Key 命中的节点还是会保持不变，从而可以保证命中率不会大幅下降。

不过，事物总有两面性。虽然这个算法对命中率的影响比较小，但它还是存在问题：

• 缓存节点在圆环上分布不平均，会造成部分缓存节点的压力较大；当某个节点故障时，这个节点所要承担的所有访问都会被顺移到另一个节点上，会对后面这个节点造成压力。
• 一致性 Hash 算法的脏数据问题。

极端情况下，比如一个有三个节点 A、B、C 承担整体的访问，每个节点的访问量平均，A 故障后，B 将承担双倍的压力（A 和 B 的全部请求），当 B 承担不了流量 Crash 后，C 也将因为要承担原先三倍的流量而 Crash，这就造成了整体缓存系统的雪崩。

说到这儿，你可能觉得很可怕，但也不要太担心，我们程序员就是要能够创造性地解决各种问题，所以你可以在一致性 Hash 算法中引入虚拟节点的概念。

它将一个缓存节点计算多个 Hash 值分散到圆环的不同位置，这样既实现了数据的平均，而且当某一个节点故障或者退出的时候，它原先承担的 Key 将以更加平均的方式分配到其他节点上，从而避免雪崩的发生。

其次，就是一致性 Hash 算法的脏数据问题。为什么会产生脏数据呢？比方说，在集群中有两个节点 A 和 B，客户端初始写入一个 Key 为 k，值为 3 的缓存数据到 Cache A 中。这时如果要更新 k 的值为 4，但是缓存 A 恰好和客户端连接出现了问题，那这次写入请求会写入到 Cache B 中。接下来缓存 A 和客户端的连接恢复，当客户端要获取 k 的值时，就会获取到存在 Cache A 中的脏数据 3，而不是 Cache B 中的 4。

所以，在使用一致性 Hash 算法时一定要设置缓存的过期时间，这样当发生漂移时，之前存储的脏数据可能已经过期，就可以减少存在脏数据的几率。

很显然，数据分片最大的优势就是缓解缓存节点的存储和访问压力，但同时它也让缓存的使用更加复杂。在 MultiGet（批量获取）场景下，单个节点的访问量并没有减少，同时节点数太多会造成缓存访问的 SLA（即“服务等级协议”，SLA 代表了网站服务可用性）得不到很好的保证，因为根据木桶原则，SLA 取决于最慢、最坏的节点的情况，节点数过多也会增加出问题的概率，因此我推荐 4 到 6 个节点为佳。

中间代理层方案

虽然客户端方案已经能解决大部分的问题，但是只能在单一语言系统之间复用。例如微博使用 Java 语言实现了这么一套逻辑，我使用 PHP 就难以复用，需要重新写一套，很麻烦。而中间代理层的方案就可以解决这个问题。你可以将客户端解决方案的经验移植到代理层中，通过通用的协议（如 Redis 协议）来实现在其他语言中的复用。

如果你来自研缓存代理层，你就可以将客户端方案中的高可用逻辑封装在代理层代码里面，这样用户在使用你的代理层的时候就不需要关心缓存的高可用是如何做的，只需要依赖你的代理层就好了。

除此以外，业界也有很多中间代理层方案，比如 Facebook 的Mcrouter，Twitter 的Twemproxy，豌豆荚的Codis。它们的原理基本上可以由一张图来概括：

看这张图你有什么发现吗？ 所有缓存的读写请求都是经过代理层完成的。代理层是无状态的，主要负责读写请求的路由功能，并且在其中内置了一些高可用的逻辑，不同的开源中间代理层方案中使用的高可用策略各有不同。比如在 Twemproxy 中，Proxy 保证在某一个 Redis 节点挂掉之后会把它从集群中移除，后续的请求将由其他节点来完成；而 Codis 的实现略复杂，它提供了一个叫 Codis Ha 的工具来实现自动从节点提主节点，在 3.2 版本之后换做了 Redis Sentinel 方式，从而实现 Redis 节点的高可用。

服务端方案

Redis 在 2.4 版本中提出了 Redis Sentinel 模式来解决主从 Redis 部署时的高可用问题，它可以在主节点挂了以后自动将从节点提升为主节点，保证整体集群的可用性，整体的架构如下图所示：

Redis Sentinel 也是集群部署的，这样可以避免 Sentinel 节点挂掉造成无法自动故障恢复的问题，每一个 Sentinel 节点都是无状态的。在 Sentinel 中会配置 Master 的地址，Sentinel 会时刻监控 Master 的状态，当发现 Master 在配置的时间间隔内无响应，就认为 Master 已经挂了，Sentinel 会从从节点中选取一个提升为主节点，并且把所有其他的从节点作为新主的从节点。Sentinel 集群内部在仲裁的时候，会根据配置的值来决定当有几个 Sentinel 节点认为主挂掉可以做主从切换的操作，也就是集群内部需要对缓存节点的状态达成一致才行。

Redis Sentinel 不属于代理层模式，因为对于缓存的写入和读取请求不会经过 Sentinel 节点。Sentinel 节点在架构上和主从是平级的，是作为管理者存在的，所以可以认为是在服务端提供的一种高可用方案。

使用 NoSQL 提升写入性能

数据库系统大多使用的是传统的机械磁盘，对于机械磁盘的访问方式有两种：一种是随机 IO；另一种是顺序 IO。随机 IO 就需要花费时间做昂贵的磁盘寻道，一般来说，它的读写效率要比顺序 IO 小两到三个数量级，所以我们想要提升写入的性能就要尽量减少随机 IO。

以 MySQL 的 InnoDB 存储引擎来说，更新 binlog、redolog、undolog 都是在做顺序 IO，而更新 datafile 和索引文件则是在做随机 IO，而为了减少随机 IO 的发生，关系数据库已经做了很多的优化，比如说写入时先写入内存，然后批量刷新到磁盘上，但是随机 IO 还是会发生。

索引在 InnoDB 引擎中是以 B+ 树方式来组织的，而 MySQL 主键是聚簇索引（一种索引类型，数据与索引数据放在一起），既然数据和索引数据放在一起，那么在数据插入或者更新的时候，我们需要找到要插入的位置，再把数据写到特定的位置上，这就产生了随机的 IO。而且一旦发生了页分裂，就不可避免会做数据的移动，也会极大地损耗写入性能。

NoSQL 数据库是怎么解决这个问题的呢？

它们有多种的解决方式，这里我给你讲一种最常见的方案，就是很多 NoSQL 数据库都在使用的基于 LSM 树的存储引擎，这种算法使用最多，所以在这里着重剖析一下。

LSM 树（Log-Structured Merge Tree）牺牲了一定的读性能来换取写入数据的高性能，Hbase、Cassandra、LevelDB 都是用这种算法作为存储的引擎。

它的思想很简单，数据首先会写入到一个叫做 MemTable 的内存结构中，在 MemTable 中数据是按照写入的 Key 来排序的。为了防止 MemTable 里面的数据因为机器掉电或者重启而丢失，一般会通过写 Write Ahead Log 的方式将数据备份在磁盘上。

MemTable 在累积到一定规模时，它会被刷新生成一个新的文件，我们把这个文件叫做 SSTable（Sorted String Table）。当 SSTable 达到一定数量时，我们会将这些 SSTable 合并，减少文件的数量，因为 SSTable 都是有序的，所以合并的速度也很快。

当从 LSM 树里面读数据时，我们首先从 MemTable 中查找数据，如果数据没有找到，再从 SSTable 中查找数据。因为存储的数据都是有序的，所以查找的效率是很高的，只是因为数据被拆分成多个 SSTable，所以读取的效率会低于 B+ 树索引。

和 LSM 树类似的算法有很多，比如说 TokuDB 使用的名为 Fractal tree 的索引结构，它们的核心思想就是将随机 IO 变成顺序的 IO，从而提升写入的性能。

提升扩展性

另外，在扩展性方面，很多 NoSQL 数据库也有着先天的优势。还是以你的垂直电商系统为例，你已经为你的电商系统增加了评论系统，开始你的评估比较乐观，觉得电商系统的评论量级不会增长很快，所以就为它分了 8 个库，每个库拆分成 16 张表。

但是评论系统上线之后，存储量级增长的异常迅猛，你不得不将数据库拆分成更多的库表，而数据也要重新迁移到新的库表中，过程非常痛苦，而且数据迁移的过程也非常容易出错。

这时，你考虑是否可以考虑使用 NoSQL 数据库来彻底解决扩展性的问题，经过调研你发现它们在设计之初就考虑到了分布式和大数据存储的场景，比如像 MongoDB 就有三个扩展性方面的特性。

• 其一是 Replica，也叫做副本集，你可以理解为主从分离，也就是通过将数据拷贝成多份来保证当主挂掉后数据不会丢失。同时呢，Replica 还可以分担读请求。Replica 中有主节点来承担写请求，并且把对数据变动记录到 oplog 里（类似于 binlog）；从节点接收到 oplog 后就会修改自身的数据以保持和主节点的一致。一旦主节点挂掉，MongoDB 会从从节点中选取一个节点成为主节点，可以继续提供写数据服务。
• 其二是 Shard，也叫做分片，你可以理解为分库分表，即将数据按照某种规则拆分成多份，存储在不同的机器上。MongoDB 的 Sharding 特性一般需要三个角色来支持，一个是 Shard Server，它是实际存储数据的节点，是一个独立的 Mongod 进程；二是 Config Server，也是一组 Mongod 进程，主要存储一些元信息，比如说哪些分片存储了哪些数据等；最后是 Route Server，它不实际存储数据，仅仅作为路由使用，它从 Config Server 中获取元信息后，将请求路由到正确的 Shard Server 中。

• 其三是负载均衡，就是当 MongoDB 发现 Shard 之间数据分布不均匀，会启动 Balancer 进程对数据做重新的分配，最终让不同 Shard Server 的数据可以尽量的均衡。当我们的 Shard Server 存储空间不足需要扩容时，数据会自动被移动到新的 Shard Server 上，减少了数据迁移和验证的成本。

你可以看到，NoSQL 数据库中内置的扩展性方面的特性可以让我们不再需要对数据库做分库分表和主从分离，也是对传统数据库一个良好的补充。

这个策略的核心原则是用户只与缓存打交道，由缓存和数据库通信，写入或者读取数据。这就好比你在汇报工作的时候只对你的直接上级汇报，再由你的直接上级汇报给他的上级，你是不能越级汇报的。

Write Through 的策略是这样的：先查询要写入的数据在缓存中是否已经存在，如果已经存在，则更新缓存中的数据，并且由缓存组件同步更新到数据库中，如果缓存中数据不存在，我们把这种情况叫做“Write Miss（写失效）”。

一般来说，我们可以选择两种“Write Miss”方式：一个是“Write Allocate（按写分配）”，做法是写入缓存相应位置，再由缓存组件同步更新到数据库中；另一个是“No-write allocate（不按写分配）”，做法是不写入缓存中，而是直接更新到数据库中。

在 Write Through 策略中，我们一般选择“No-write allocate”方式，原因是无论采用哪种“Write Miss”方式，我们都需要同步将数据更新到数据库中，而“No-write allocate”方式相比“Write Allocate”还减少了一次缓存的写入，能够提升写入的性能。

Read Through 策略就简单一些，它的步骤是这样的：先查询缓存中数据是否存在，如果存在则直接返回，如果不存在，则由缓存组件负责从数据库中同步加载数据。

下面是 Read Through/Write Through 策略的示意图：

Read Through/Write Through 策略的特点是由缓存节点而非用户来和数据库打交道，在我们开发过程中相比 Cache Aside 策略要少见一些，原因是我们经常使用的分布式缓存组件，无论是 Memcached 还是 Redis 都不提供写入数据库，或者自动加载数据库中的数据的功能。而我们在使用本地缓存的时候可以考虑使用这种策略，比如说在上一节中提到的本地缓存 Guava Cache 中的 Loading Cache 就有 Read Through 策略的影子。

我们看到 Write Through 策略中写数据库是同步的，这对于性能来说会有比较大的影响，因为相比于写缓存，同步写数据库的延迟就要高很多了。那么我们可否异步地更新数据库？这就是我们接下来要提到的“Write Back”策略。

Write Back（写回）策略

这个策略的核心思想是在写入数据时只写入缓存，并且把缓存块儿标记为“脏”的。而脏块儿只有被再次使用时才会将其中的数据写入到后端存储中。

需要注意的是，在“Write Miss”的情况下，我们采用的是“Write Allocate”的方式，也就是在写入后端存储的同时要写入缓存，这样我们在之后的写请求中都只需要更新缓存即可，而无需更新后端存储了，我将 Write back 策略的示意图放在了下面：

发现了吗？其实这种策略不能被应用到我们常用的数据库和缓存的场景中，它是计算机体系结构中的设计，比如我们在向磁盘中写数据时采用的就是这种策略。无论是操作系统层面的 Page Cache，还是日志的异步刷盘，亦或是消息队列中消息的异步写入磁盘，大多采用了这种策略。因为这个策略在性能上的优势毋庸置疑，它避免了直接写磁盘造成的随机写问题，毕竟写内存和写磁盘的随机 I/O 的延迟相差了几个数量级呢。

但因为缓存一般使用内存，而内存是非持久化的，所以一旦缓存机器掉电，就会造成原本缓存中的脏块儿数据丢失。所以你会发现系统在掉电之后，之前写入的文件会有部分丢失，就是因为 Page Cache 还没有来得及刷盘造成的。

当然，你依然可以在一些场景下使用这个策略，在使用时，我想给你的落地建议是：你在向低速设备写入数据的时候，可以在内存里先暂存一段时间的数据，甚至做一些统计汇总，然后定时地刷新到低速设备上。比如说，你在统计你的接口响应时间的时候，需要将每次请求的响应时间打印到日志中，然后监控系统收集日志后再做统计。但是如果每次请求都打印日志无疑会增加磁盘 I/O，那么不如把一段时间的响应时间暂存起来，经过简单的统计平均耗时，每个耗时区间的请求数量等等，然后定时地，批量地打印到日志中。

我们来考虑一种最简单的业务场景，比方说在你的电商系统中有一个用户表，表中只有 ID 和年龄两个字段，缓存中我们以 ID 为 Key 存储用户的年龄信息。那么当我们要把 ID 为 1 的用户的年龄从 19 变更为 20，要如何做呢？

你可能会产生这样的思路：先更新数据库中 ID 为 1 的记录，再更新缓存中 Key 为 1 的数据。

这个思路会造成缓存和数据库中的数据不一致。比如，A 请求将数据库中 ID 为 1 的用户年龄从 19 变更为 20，与此同时，请求 B 也开始更新 ID 为 1 的用户数据，它把数据库中记录的年龄变更为 21，然后变更缓存中的用户年龄为 21。紧接着，A 请求开始更新缓存数据，它会把缓存中的年龄变更为 20。此时，数据库中用户年龄是 21，而缓存中的用户年龄却是 20。

为什么产生这个问题呢？因为变更数据库和变更缓存是两个独立的操作，而我们并没有对操作做任何的并发控制。那么当两个线程并发更新它们的时候，就会因为写入顺序的不同造成数据的不一致。

另外，直接更新缓存还存在另外一个问题就是丢失更新。还是以我们的电商系统为例，假如电商系统中的账户表有三个字段：ID、户名和金额，这个时候缓存中存储的就不只是金额信息，而是完整的账户信息了。当更新缓存中账户金额时，你需要从缓存中查询完整的账户数据，把金额变更后再写入到缓存中。

这个过程中也会有并发的问题，比如说原有金额是 20，A 请求从缓存中读到数据，并且把金额加 1，变更成 21，在未写入缓存之前又有请求 B 也读到缓存的数据后把金额也加 1，也变更成 21，两个请求同时把金额写回缓存，这时缓存里面的金额是 21，但是我们实际上预期是金额数加 2，这也是一个比较大的问题。

那我们要如何解决这个问题呢？其实，我们可以在更新数据时不更新缓存，而是删除缓存中的数据，在读取数据时，发现缓存中没了数据之后，再从数据库中读取数据，更新到缓存中。

这个策略就是我们使用缓存最常见的策略，Cache Aside 策略（也叫旁路缓存策略），这个策略数据以数据库中的数据为准，缓存中的数据是按需加载的。它可以分为读策略和写策略，其中读策略的步骤是：

• 从缓存中读取数据；
• 如果缓存命中，则直接返回数据；
• 如果缓存不命中，则从数据库中查询数据；
• 查询到数据后，将数据写入到缓存中，并且返回给用户。

写策略的步骤是：

• 更新数据库中的记录；
• 删除缓存记录。

你也许会问了，在写策略中，能否先删除缓存，后更新数据库呢？答案是不行的，因为这样也有可能出现缓存数据不一致的问题，我以用户表的场景为例解释一下。

假设某个用户的年龄是 20，请求 A 要更新用户年龄为 21，所以它会删除缓存中的内容。这时，另一个请求 B 要读取这个用户的年龄，它查询缓存发现未命中后，会从数据库中读取到年龄为 20，并且写入到缓存中，然后请求 A 继续更改数据库，将用户的年龄更新为 21，这就造成了缓存和数据库的不一致。

那么像 Cache Aside 策略这样先更新数据库，后删除缓存就没有问题了吗？其实在理论上还是有缺陷的。假如某个用户数据在缓存中不存在，请求 A 读取数据时从数据库中查询到年龄为 20，在未写入缓存中时另一个请求 B 更新数据。它更新数据库中的年龄为 21，并且清空缓存。这时请求 A 把从数据库中读到的年龄为 20 的数据写入到缓存中，造成缓存和数据库数据不一致。

不过这种问题出现的几率并不高，原因是缓存的写入通常远远快于数据库的写入，所以在实际中很难出现请求 B 已经更新了数据库并且清空了缓存，请求 A 才更新完缓存的情况。而一旦请求 A 早于请求 B 清空缓存之前更新了缓存，那么接下来的请求就会因为缓存为空而从数据库中重新加载数据，所以不会出现这种不一致的情况。

Cache Aside 策略是我们日常开发中最经常使用的缓存策略，不过我们在使用时也要学会依情况而变。比如说当新注册一个用户，按照这个更新策略，你要写数据库，然后清理缓存（当然缓存中没有数据给你清理）。可当我注册用户后立即读取用户信息，并且数据库主从分离时，会出现因为主从延迟所以读不到用户信息的情况。

而解决这个问题的办法恰恰是在插入新数据到数据库之后写入缓存，这样后续的读请求就会从缓存中读到数据了。并且因为是新注册的用户，所以不会出现并发更新用户信息的情况。

Cache Aside 存在的最大的问题是当写入比较频繁时，缓存中的数据会被频繁地清理，这样会对缓存的命中率有一些影响。如果你的业务对缓存命中率有严格的要求，那么可以考虑两种解决方案：

1. 一种做法是在更新数据时也更新缓存，只是在更新缓存前先加一个分布式锁，因为这样在同一时间只允许一个线程更新缓存，就不会产生并发问题了。当然这么做对于写入的性能会有一些影响；

2. 另一种做法同样也是在更新数据时更新缓存，只是给缓存加一个较短的过期时间，这样即使出现缓存不一致的情况，缓存的数据也会很快地过期，对业务的影响也是可以接受。

缓存分类

在我们日常开发中，常见的缓存主要就是静态缓存、分布式缓存和热点本地缓存这三种。

静态缓存在 Web 1.0 时期是非常著名的，它一般通过生成 Velocity 模板或者静态 HTML 文件来实现静态缓存，在 Nginx 上部署静态缓存可以减少对于后台应用服务器的压力。例如，我们在做一些内容管理系统的时候，后台会录入很多的文章，前台在网站上展示文章内容，就像新浪，网易这种门户网站一样。

当然，我们也可以把文章录入到数据库里面，然后前端展示的时候穿透查询数据库来获取数据，但是这样会对数据库造成很大的压力。即使我们使用分布式缓存来挡读请求，但是对于像日均 PV 几十亿的大型门户网站来说，基于成本考虑仍然是不划算的。

所以我们的解决思路是每篇文章在录入的时候渲染成静态页面，放置在所有的前端 Nginx 或者 Squid 等 Web 服务器上，这样用户在访问的时候会优先访问 Web 服务器上的静态页面，在对旧的文章执行一定的清理策略后，依然可以保证 99% 以上的缓存命中率。

这种缓存只能针对静态数据来缓存，对于动态请求就无能为力了。那么我们如何针对动态请求做缓存呢？这时你就需要分布式缓存了。

分布式缓存的大名可谓是如雷贯耳了，我们平时耳熟能详的 Memcached、Redis 就是分布式缓存的典型例子。它们性能强劲，通过一些分布式的方案组成集群可以突破单机的限制。所以在整体架构中，分布式缓存承担着非常重要的角色。

对于静态的资源的缓存你可以选择静态缓存，对于动态的请求你可以选择分布式缓存，那么什么时候要考虑热点本地缓存呢？

答案是当我们遇到极端的热点数据查询的时候。热点本地缓存主要部署在应用服务器的代码中，用于阻挡热点查询对于分布式缓存节点或者数据库的压力。

比如某一位明星在微博上有了热点话题，“吃瓜群众”会到他 (她) 的微博首页围观，这就会引发这个用户信息的热点查询。这些查询通常会命中某一个缓存节点或者某一个数据库分区，短时间内会形成极高的热点查询。

那么我们会在代码中使用一些本地缓存方案，如 HashMap，Guava Cache 或者是 Ehcache 等，它们和应用程序部署在同一个进程中，优势是不需要跨网络调度，速度极快，所以可以来阻挡短时间内的热点查询。来看个例子。

比方说你的垂直电商系统的首页有一些推荐的商品，这些商品信息是由编辑在后台录入和变更。你分析编辑录入新的商品或者变更某个商品的信息后，在页面的展示是允许有一些延迟的，比如说 30 秒的延迟，并且首页请求量最大，即使使用分布式缓存也很难抗住，所以你决定使用 Guava Cache 来将所有的推荐商品的信息缓存起来，并且设置每隔 30 秒重新从数据库中加载最新的所有商品。

首先，我们初始化 Guava 的 Loading Cache：

1
2
3
4
5
6
7
8
9

CacheBuilder<String, List<Product>> cacheBuilder = CacheBuilder.newBuilder().maximumSize(maxSize).recordStats(); // 设置缓存最大值
cacheBuilder = cacheBuilder.refreshAfterWrite(30, TimeUnit.Seconds); // 设置刷新间隔
 
LoadingCache<String, List<Product>> cache = cacheBuilder.build(new CacheLoader<String, List<Product>>() {
    @Override
    public List<Product> load(String k) throws Exception {
        return productService.loadAll(); // 获取所有商品
    }
});

这样，你在获取所有商品信息的时候可以调用 Loading Cache 的 get 方法，就可以优先从本地缓存中获取商品信息，如果本地缓存不存在，会使用 CacheLoader 中的逻辑从数据库中加载所有的商品。

由于本地缓存是部署在应用服务器中，而我们应用服务器通常会部署多台，当数据更新时，我们不能确定哪台服务器本地中了缓存，更新或者删除所有服务器的缓存不是一个好的选择，所以我们通常会等待缓存过期。因此，这种缓存的有效期很短，通常为分钟或者秒级别，以避免返回前端脏数据。

缓存的不足

通过了解上面的内容，你不难发现，缓存的主要作用是提升访问速度，从而能够抗住更高的并发。那么，缓存是不是能够解决一切问题？显然不是。事物都是具有两面性的，缓存也不例外，我们要了解它的优势的同时也需要了解它有哪些不足，从而扬长避短，将它的作用发挥到最大。

首先，缓存比较适合于读多写少的业务场景，并且数据最好带有一定的热点属性。这是因为缓存毕竟会受限于存储介质不可能缓存所有数据，那么当数据有热点属性的时候才能保证一定的缓存命中率。比如说类似微博、朋友圈这种 20% 的内容会占到 80% 的流量。所以，一旦当业务场景读少写多时或者没有明显热点时，比如在搜索的场景下，每个人搜索的词都会不同，没有明显的热点，那么这时缓存的作用就不明显了。

其次，缓存会给整体系统带来复杂度，并且会有数据不一致的风险。当更新数据库成功，更新缓存失败的场景下，缓存中就会存在脏数据。对于这种场景，我们可以考虑使用较短的过期时间或者手动清理的方式来解决。

再次，之前提到缓存通常使用内存作为存储介质，但是内存并不是无限的。因此，我们在使用缓存的时候要做数据存储量级的评估，对于可预见的需要消耗极大存储成本的数据，要慎用缓存方案。同时，缓存一定要设置过期时间，这样可以保证缓存中的会是热点数据。

最后，缓存会给运维也带来一定的成本，运维需要对缓存组件有一定的了解，在排查问题的时候也多了一个组件需要考虑在内。

虽然有这么多的不足，但是缓存对于性能的提升是毋庸置疑的，我们在做架构设计的时候也需要把它考虑在内，只是在做具体方案的时候需要对缓存的设计有更细致的思考，才能最大化的发挥缓存的优势。

LeetCode两个经典的排序算法

这回是标题党， 记录下两个分而治之的排序算法（手写），分而治之的算法很容易改造成并行算法，肯定是未来的潮流， leetcode已通过， 两个算法都使用了原地(inplace)更新。

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

class Solution {
    public List<Integer> sortArray(int[] nums) {
        // merge(nums, 0, nums.length - 1);
        sort(nums, 0, nums.length - 1);
        return IntStream.of(nums).boxed().collect(Collectors.toList());
    }

	//-------------------归并排序-------------------//
    private void merge(int[] nums, int start, int end) {
        if (start >= end) return;
        int midIdx = start + (end - start) / 2;
        merge(nums, start, midIdx);
        merge(nums, midIdx+1, end);
        concat(nums, start, midIdx, end);
    }

    private void concat(int[] nums, int start, int midIdx, int end) {
        int[] tmp = new int[end - start + 1];
        int lp = start, rp = midIdx + 1, i = 0;

        while (lp <= midIdx && rp <= end) {
            tmp[i++] = nums[lp] < nums[rp] ? nums[lp++] : nums[rp++];
        }

        while (lp <= midIdx) {
            tmp[i++] = nums[lp++];
        }

        while (rp <= end) {
            tmp[i++] = nums[rp++];
        }

        System.arraycopy(tmp, 0, nums, start, tmp.length);
    }

    // -------------------  归并排序 链表 ---------------------//

    class Solution {
        public ListNode mergeKLists(ListNode[] lists) {
            if (lists.length == 0) return null;
            return merge(lists, 0 , lists.length - 1);
        }

        private ListNode merge(ListNode[] lists, int low, int high) {
            if (low == high) return lists[low];

            int mid = (high - low) / 2 + low;

            return mergeLists( merge(lists, low, mid), merge(lists, mid+1, high));
        }

        public ListNode mergeLists(ListNode node1, ListNode node2) {
            if (node1 == null) return node2;
            if (node2 == null) return node1;

            if (node1.val < node2.val) {
                node1.next = mergeLists(node1.next, node2);
                return node1;
                
            } else {
                node2.next = mergeLists(node1, node2.next);
                return node2;
            }
        }
    }
    
    //-------------------快速排序-------------------//

    private void sort(int[] nums, int start, int end) {
        if (start >= end) return;

        int bIdx = partition(nums, start, end);
        sort(nums, start, bIdx - 1);
        sort(nums, bIdx + 1, end);
    }

    private int partition(int[] nums, int start, int end) {
        int idx = start, base = nums[end];

        for (int i = start; i < end; i++) {
            if (nums[i] < base) {
                swap(nums, idx++, i);
            }
        }
        swap(nums, idx, end);
        return idx;
    }

    private void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}

最近这个季度

最近比较忙，算了下自己可以利用的空闲时间，忙时一天可能只有1到3个小时空闲时间，甚至一天没有空余时间。一周大约只有30小时时间是可以利用的，如果算上玩手机时间只会更短，如果再把这些时间再浪费掉，可能最近半年的成长就只有一些项目经验而已了。所幸平常关注的博客和《软技能》这本书里有提及一些关于自我时间管理相关内容，我简单实践了2个月，分享下这方面的心得感悟。

计划和休息

《软技能》中作者是如何做计划的？

• 季度计划 明确宏观目标，以及如何实现
• 月计划 估算当月能完成多少工作量
• 周计划 为每周安排必须完成的强制性任务
• 日计划 排除干扰，按需调整
• 休息 每隔一段时间休息，只做强制性任务

很惭愧，工作刚开始一两年我少有计划，单纯凭借好奇心学习到了不少东西。大约从去年写年度总结开始才刚刚做一些计划。目前我使用微软to-do跟踪自己的计划进度和deadline效果显著，治好了我的拖延症。

简单来说《软技能》中阐述的几个观点我感觉十分受益：

1. 要有计划
2. 完成计划时保持专注
3. 使用番茄工作法可以保证保证一段时间的专注， 同时还可以确定自己的工作效率， 总结不足提高自身效率，从而帮助自己精确且高效的指定计划
4. 只有你完成了计划的工作，接下来的休息时间才能安心

这边年读书情况

这半年看的书比较少，但是刷题和博客总结写的多了些

技术类：
《sql反模式》推荐， 应该叫数据库结构设计的最佳实践
《软技能，代码之外的生存指南》 有很多事比代码更重要的多，推荐

心理类：
《你的灯亮着吗》 解决问题前，先要搞清楚问题的本质。 一般般

Manacher 算法 容易理解，实现起来也没什么大坑，复杂度还是 O(n)的， 花半个小时实现下很有意思

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

class Solution {
    public String longestPalindrome(String s) {        
        StringBuilder sb = new StringBuilder(2 + 2 * s.length());
        sb.append("^");
        for (int i = 0; i < s.length(); i++) {
            sb.append("#").append(s.charAt(i));
        }
        sb.append("#$");
        
        String s2 = sb.toString();
        
        int maxStart = 1, max = 0, rC = 1, rR = 1;
        int[] p = new int[s2.length()];
        
        for (int i = 1; i < s2.length() - 1; i++ ) {
            
            p[i] = i < rR ? Math.min(p[2 * rC - i], rR - i) : 0;
            
            while (s2.charAt(i+p[i]+1) == s2.charAt(i - p[i] - 1)) {
                p[i] = p[i]+1;
            }
            
            if (i + p[i] > rR) {
                rC = i;
                rR = i + p[i];
            }
            
            if (p[i] > max) {
                maxStart = i - p[i];
                max = p[i];
            }
        }
        

        return s2.substring(maxStart,maxStart + 2*max+1).replace("#", "");
    }
}

多角色权限如果遇到不同角色能看到不同的列可以怎么做

• 逐行读取

最简单的解决方法，实现简单。但是在微服务中调用接口次数太多，性能很差。

• 批量读取

实现较复杂，但是性能好很多，下面主要介绍这种方法的思路

批量读取

以分页读取数据为例：

1. 读取第一页数据，包含需要展示数据的id和所属权限（多个）

为什么需要所属权限这个字段呢？ 因为决定能否看到这行是有你所拥有的所有权限决定的，而决定能否看到哪个列是由这行所拥有的权限决定的。

如何获取该行所拥有的权限呢，我的做法是分不同的权限查询结果通过union 组合起来

2. 将第一页数据原始顺序保存， 然后按行拥有权限分组

记录原始顺序是因为后面分组后会打乱， 为什么要分组？分组后同样的查询才能聚合在一起，可以简化代码

3. 根据权限分组多次查询所需要的字段，然后将查询结果合并

这里我使用的graphql来选择需要查询的字段

4. 最后还原成原来的顺序

可以使用guava Ordering工具类方便生成Compartor

[]: https://blog.yamato.moe/2018/11/06/2018-11-06-biz/ “根据权限查询时避免角色切换的一种思路”
[]: https://blog.yamato.moe/2019/04/04/Mybatis%20ResultSetHandler_2019-04-04%20%E7%BB%AD/ “【片段】 Mybatis ResultSetHandler 实践-续”
[]: https://blog.yamato.moe/2019/01/09/Mybatis%20ResultSetHandler_2019-01-09/ “【片段】 Mybatis ResultSetHandler 实践”

树的高度

104. Maximum Depth of Binary Tree (Easy)

递归计算二叉树左右两边深度，取最大值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

/**

 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) return 0;
        int left = maxDepth(root.left);
        int right = maxDepth(root.right);
        return Math.max(left, right) + 1;
    }
}

平衡树

110. Balanced Binary Tree (Easy)

递归遍历二叉树左右子树深度

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

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    
    private boolean balance = true;
    
    public boolean isBalanced(TreeNode root) {
        visitTree(root);
        return balance;
    }
    
    private int visitTree(TreeNode root) {
        if (root == null) return 0;
        int left = visitTree(root.left);
        int right = visitTree(root.right);
        if (Math.abs(left - right) > 1 ) this.balance = false;
        return Math.max(left, right) + 1;
    }
}

两节点的最长路径

543. Diameter of Binary Tree (Easy)

递归遍历二叉树左右子树深度， 路径就是两边子树深度之和

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

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    
    private int max;
        
    public int diameterOfBinaryTree(TreeNode root) {
        deep(root);
        return max;
    }
    
    private int deep(TreeNode root) {
        if (root == null) return 0;
        int left = deep(root.left);
        int right = deep(root.right);
        max = Math.max(max,left+right);
        return Math.max(left, right) + 1;
    }
}

翻转树

226. Invert Binary Tree (Easy)

递归交换左右子树的引用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) return root;
        TreeNode right =root.right;
        root.right = invertTree(root.left);
        root.left = invertTree(right);
        return root;
    }
}

归并两棵树

617. Merge Two Binary Trees (Easy)

递归时如果其中一个节点是空，可以直接复用该节点。如果新建节点，需要拷贝节点的左右子树引用，递归时会用到。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
        if (t1 == null && t2 == null ) return null;
        if (t1 == null) return t2;
        if (t2 == null) return t1;
        TreeNode root =  new TreeNode(t1.val + t2.val);
        root.left = mergeTrees(t1.left, t2.left);
        root.right = mergeTrees(t1.right, t2.right);
        return root;
    }
}

判断路径和是否等于一个数

Leetcode : 112. Path Sum (Easy)

递归查询子树和是否等于目标和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean hasPathSum(TreeNode root, int sum) {
        if (root == null) return false;
        if (root.val == sum && root.left == null && root.right == null) return true;
        return  hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
    }
}

统计路径和等于一个数的路径数量

437. Path Sum III (Easy)

双层递归

1. 以当前节点为起点统计路径和
2. 当前节点以下节点为起点统计路径和

以root为根节点的路径数量= 以root为起点统计路径和+root左节点为起点统计路径和+root右节点为起点统计路径和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int pathSum(TreeNode root, int sum) {
        if (root == null) return 0;
        //结果数 等于 以当前root为父节点和 root以下为父节点结果数之和
        return sum(root, sum) + pathSum(root.left, sum) + pathSum(root.right, sum);
    }
    // 计算以当前node为父节点能都多少路径数
    private int sum(TreeNode node, int sum) {
        if (node == null) return 0;
        int count = 0;
        if (node.val == sum) count++;
        count += sum(node.left, sum - node.val) + sum(node.right, sum - node.val);
        return count;
    }
}

子树

572. Subtree of Another Tree (Easy)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isSubtree(TreeNode s, TreeNode t) {
        if (s == null) return false;
        return isSubRoot(s, t) || isSubtree(s.left, t) || isSubtree(s.right, t);
    }
    
    public boolean isSubRoot(TreeNode node, TreeNode t) {
        if (node == null && t == null) return true;
        if (node == null || t == null) return false;
        if (node.val != t.val) return false;
        return isSubRoot(node.left, t.left) && isSubRoot(node.right, t.right); 
    }
}

树的对称

101. Symmetric Tree (Easy)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) return true;
        return isSymmetric(root.left, root.right);
    }
    
    public boolean isSymmetric(TreeNode left, TreeNode right) {
        if (left == null && right == null) return true;
        if (left == null || right == null) return false;
        if (left.val != right.val) return false;
        return isSymmetric(left.left, right.right) && isSymmetric(left.right, right.left);
    }
}

最小路径

111. Minimum Depth of Binary Tree (Easy)

和最大路径类似

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int minDepth(TreeNode root) {
        if (root == null) return 0;
        int left = minDepth(root.left);
        int right = minDepth(root.right);
        if (left == 0 || right == 0) return left + right + 1;
        return Math.min(left, right) + 1;
    }
}

统计左叶子节点的和

404. Sum of Left Leaves (Easy)

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

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {

    public int sumOfLeftLeaves(TreeNode root) {
        if (root == null) return 0;
        if (root.left != null && root.left.left == null && root.left.right == null) return root.left.val + sumOfLeftLeaves(root.right);
        return sumOfLeftLeaves(root.left) + sumOfLeftLeaves(root.right);
    }
}
````

#### 相同节点值的最大路径长度

[687. Longest Univalue Path (Easy)](https://leetcode.com/problems/longest-univalue-path/)

递归查找左右子树相同节点值最大路径，最大路径的计算：如果相等路径+1，如果不相等置为0。

```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private int path = 0;
    
    public int longestUnivaluePath(TreeNode root) {
        visit(root);
       return path; 
    }
    
    private int visit(TreeNode root) {
        if  (root == null) return 0;
        int left = visit(root.left);
        int right = visit(root.right);
        
        left =  (root.left != null && root.val == root.left.val) ? left + 1 : 0;
        right = (root.right != null && root.val == root.right.val)? right + 1 : 0;
        path = Math.max(path, left+right);
        return Math.max(left, right );
    }
}

间隔遍历

337. House Robber III (Medium)

递归查询两种情况

1. 如果从当前节点开始
2. 从当前节点的子节点开始

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int rob(TreeNode root) {
        if (root == null) return 0;
        int val1 = root.val, val2 = 0;
        if (root.left != null) val1+= rob(root.left.left) + rob(root.left.right);
        if (root.right != null) val1+= rob(root.right.left) + rob(root.right.right);
        
        val2 = rob(root.left) + rob(root.right);
        return Math.max(val1, val2);
    }
}

找出二叉树中第二小的节点

Second Minimum Node In a Binary Tree (Easy)

第二小节点在子树节点上，如果子树值与根节点相等，继续向下查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int findSecondMinimumValue(TreeNode root) {
        if (root == null) return -1;
        if (root.left == null) return -1;
        int left = root.left.val, right = root.right.val;
        if (root.val == root.left.val) left = findSecondMinimumValue(root.left);
        if (root.val == root.right.val) right = findSecondMinimumValue(root.right);
        if (left != -1 && right != -1) return Math.min(left, right);
        if (left > -1) return left;
        return right;
    }
}

二叉树的层平均值

637. Average of Levels in Binary Tree (Easy)

BFS

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

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<Double> averageOfLevels(TreeNode root) {
        List<Double> ret = new ArrayList<>();
        if (root == null) return ret;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty()) {
            int count = queue.size();
            double sum = 0d;
            
            for(int i = 0; i < count; i++) {
                TreeNode node = queue.poll();
                sum+= node.val;
                if (node.left != null) queue.add(node.left);
                if (node.right != null) queue.add(node.right);
            }
            ret.add(sum/count);
        }
        return ret;
    }
}

找树左下角的值

513. Find Bottom Left Tree Value (Easy)

DFS

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

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private int val = 0;
    
    public int findBottomLeftValue(TreeNode root) {
        if (root == null) return val;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty()) {
            // 这一行的数量
            int count = queue.size();
            
            for (int i = 0; i < count; i++) {
                TreeNode node = queue.poll();
                if(i == 0) val = node.val;
                if (node.left != null) queue.add(node.left);
                if (node.right != null) queue.add(node.right);
            }
        }
        return val;
    }
}

非递归实现二叉树的后序遍历

入栈条件： 未访问过该节点
出栈条件： 访问过该节点

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

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    
    private List<Integer> res = new LinkedList<>();
    private Stack<TreeNode> stack = new Stack<>();
    private Set<TreeNode> visited = new HashSet<>();
    
    public List<Integer> postorderTraversal(TreeNode root) {
        if (root == null) return res;
        stack.push(root);
        
        while (!stack.isEmpty()) {
            TreeNode node = stack.peek();
            
            if ((node.left == null && node.right == null) || visited.contains(node)) {
                TreeNode i = stack.pop();
                res.add(i.val);
            } else {
                visited.add(node);
                if (node.right != null)
                    stack.push(node.right);
                if (node.left != null) 
                    stack.push(node.left);
            }
        }
        return res;
    }
    
    private void visit(TreeNode root) {
        if(root == null) return;
        visit(root.left);
        visit(root.right);
        res.add(root.val);
    }
}

非递归实现二叉树的前序遍历

入栈条件： 无
出栈条件： 直接出栈

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

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private List<Integer> res = new LinkedList<>();
    private Stack<TreeNode> stack = new Stack<>();
    
    public List<Integer> preorderTraversal(TreeNode root) {
        if (root == null) return res;
        stack.push(root);
        
        while (!stack.isEmpty()) {
                TreeNode node = stack.pop();
                res.add(node.val);
                if (node.right != null) stack.push(node.right);
                if (node.left != null)  stack.push(node.left);
        }
        return res;
    }
}

非递归实现二叉树的中序遍历

入栈条件： 未访问过该节点
出栈条件： 访问过该节点
入栈顺序: right -> middle -> left

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

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private List<Integer> res = new LinkedList<>();
    private Stack<TreeNode> stack = new Stack<>();
    private Set<TreeNode> visited = new HashSet<>();
    
    public List<Integer> inorderTraversal(TreeNode root) {
        if (root == null) return res;
        push(root);
        
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            if ((node.left == null && node.right == null) || visited.contains(node)) {
                res.add(node.val);
            } else {
                push(node);
            }
        }
        return res;
    }
    
    private void push(TreeNode root) {
        if (root == null) return;
        visited.add(root);
        if (root.right != null) stack.push(root.right);
        stack.push(root);
        if (root.left != null) stack.push(root.left);
    }
}

修剪二叉搜索树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode trimBST(TreeNode root, int L, int R) {
        if (root == null) return null;
        if (root.val < L) return trimBST(root.right, L, R);
        if (root.val > R) return trimBST(root.left, L, R);
        root.left = trimBST(root.left, L, R);
        root.right = trimBST(root.right, L, R);
        return root;
    }
}

二叉搜索树中第K小的元素

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

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private int cnt;
    private int val;
    
    public int kthSmallest(TreeNode root, int k) {
        search(root, k);
        return val;
    
    }
    
    private void search(TreeNode root, int k) {
        if (root == null) return;
        // 
        kthSmallest(root.left, k);
        cnt++;
        if (cnt == k) {
            val =  root.val;
            return;
        }
        kthSmallest(root.right, k);
    }
}

把二叉搜索树转换为累加树

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

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    
    private int sum;
    
    public TreeNode convertBST(TreeNode root) {
        // 中序遍历 但是是从右往左遍历
        // 
        visit(root);
        return root;
    }
    
    
    private void visit(TreeNode root) {
        if (root == null) return;
        
        visit(root.right);
         sum += root.val;
    
        root.val = sum;
        
        visit(root.left);
    }
}

二叉搜索树的最近公共祖先

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // 公共祖先在左边
        if (root.val > p.val && root.val > q.val) return lowestCommonAncestor(root.left, p, q);
        // 公共祖先在右边
        if (root.val < p.val && root.val < q.val) return lowestCommonAncestor(root.right, p, q);
        // 公共祖先在这
        return root;
    }
}

二叉树的最近公共祖先

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || p == root || q == root) return root;
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        
        // 左右都是父节点， 上一级就是公共父节点
        if(left != null && right != null) return root;
        if (left == null && right == null) return null;
        if (left != null) return left;
        return right;
    }
}

将有序数组转换为二叉搜索树

二叉树中序遍历

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

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        return build(nums, 0, nums.length -1);
    }
    
    
    private TreeNode build(int[] nums, int start, int end) {
        
        if(start> end) return null;
        
        TreeNode node = new TreeNode(nums[(start+end)/2]);
        
        node.left = build(nums, start, (start+end)/2 -1);
        node.right = build(nums, (start+end)/2+1, end);
        return node;
    }
}

有序链表转换二叉搜索树

链表转数组

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

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode sortedListToBST(ListNode head) {
        List<Integer> list = new LinkedList();
        ListNode now = head;
        while (now != null) {
            list.add(now.val);
            now = now.next;
        }
        
        return build(list, 0, list.size() - 1);
    }
    
    
    private TreeNode build(List<Integer> nums, int start, int end) {
        
        if(start> end) return null;
        
        TreeNode node = new TreeNode(nums.get((start+end)/2));
        
        node.left = build(nums, start, (start+end)/2 -1);
        node.right = build(nums, (start+end)/2+1, end);
        return node;
    }
}

还可以使用双指针找到链表中间节点，缺点是重复遍历节点

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

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode sortedListToBST(ListNode head) {
//         List<Integer> list = new LinkedList();
//         ListNode now = head;
//         while (now != null) {
//             list.add(now.val);
//             now = now.next;
//         }
        
//         return build(list, 0, list.size() - 1);
        
        return sortedListToBST(head, null);
        
        

    }
    
    private TreeNode sortedListToBST(ListNode head, ListNode tail) {
        if (head == tail) return null;
        
        ListNode mid = head, end = head;
        while (end != tail && end.next != tail) {
            mid = mid.next;
            end = end.next.next;
        }
        
        TreeNode root = new TreeNode(mid.val);
        root.right = sortedListToBST(mid.next, tail);
        root.left = sortedListToBST(head, mid);
        return root;
    }
    
    
    private TreeNode build(List<Integer> nums, int start, int end) {
        
        if(start> end) return null;
        
        TreeNode node = new TreeNode(nums.get((start+end)/2));
        
        node.left = build(nums, start, (start+end)/2 -1);
        node.right = build(nums, (start+end)/2+1, end);
        return node;
    }
    
}

两数之和 IV - 输入 BST

自己写两次遍历搜索二叉树，注意要排除自身节点

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

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private boolean res;
    private TreeNode r;
    private TreeNode current;
    
    
    public boolean findTarget(TreeNode root, int k) {
        r = root;
        visit(root, k);
        return res;
    }
    
    private void visit(TreeNode root, int val) {
        if (root == null) return;
        visit(root.left, val);
        current = root;
        if (find(r, val - root.val)) {res = true; return;}
        visit(root.right, val);
    }
    
    private boolean find(TreeNode root, int value) {
        if (root == null) return false;
        if (root == current) return false;
        if (root.val == value ) return true;
        return  (value > root.val) ? find(root.right, value): find(root.left, value);
    }
}

正经思路， 中序遍历转化为排序数组， 使用双指针查找

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

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {

    private List<Integer> res = new ArrayList<>(64);
    
    public boolean findTarget(TreeNode root, int k) {

        visitTree(root);
        
        int low = 0, high = res.size() - 1;
        while (low < high) {
            int sum = res.get(low) + res.get(high);
            if (sum == k) return true;
            if (sum < k) low++;
            else high--;
        }
        return false;
        
    }
    

    
    private void visitTree(TreeNode root) {
        if (root == null) return;
        visitTree(root.left);
        res.add(root.val);
        visitTree(root.right);        
    }

}

前情概要

1. 问题背景

使用多个角色查询列表时，会遇到两个维度的不同点：

• 行维度：多个角色能够看到行的并集，sql需要多次查询取并集，之后还要去重分页排序
• 列维度：如果不同角色可见列不同，计算出当前行能看到列的并集

举一个例子：

假设存在一个登录员工拥有两个角色：

1. 长期激励负责人：能看到拥有长期激励的人（行维度），能看到基本信息和长期激励信息（列维度）
2. 薪酬负责人：能看到低职级的人（行维度），能看到基本信息和薪酬信息（列维度）

那么，在列表中他能看见：

2. 实际遇到的问题（困难重重）

基本思路已经在前期概要里介绍，本人已经实践了一段时间，挖了两个深坑正在解决中。

性能问题（已解决）

最开始的实现中数据是一条一条读取的，同时薪酬字段属于加密信息，使用了第三方微服务提供解密，读取字段多+解密字段多 导致了在百条分页的情况下接口在超时的边缘不断试探。。。

解决方案：

• 合并查询sql,批量查询数据
• 合并解密请求,批量调用解密微服务

因为之前为了方便我们解密使用了mybatis的TypeHandler做到字段隐式加解密，目前我们的做法是对于单条数据的加解密，还是保持原来的typeHandler做法，而对批量数据处理，重新写一套数据实体，同时使用mybatis的拦截器对查询的批量数据做批量解密的处理。具体做法可以参见我的另一片文章：【片段】 Mybatis ResultSetHandler 实践-续

批量查询带来的问题

批量查询返回的列表中列字段都是一致的，而我们的需求是不同的行能看见不同的列字段，把批量查询出来的列表直接返回是有问题的，这个问题因为疏忽导致了线上的一次故障。

所以目前的思路是先做一次数据批量预取，之后在对列字段做处理，隐藏掉不能看见的字段。

3. 总结

没有想到当时想解决权限查询时避免角色切换这个问题时会遇到这么多困难，想法是正确的，在实际执行时还是困难重重。值得欣慰的在最开始的时候思路和方向都是正确的，同时也把其中遇到的各种问题和心得记录了下来，经过层层积累，才到达现在的高度。

[]: https://blog.yamato.moe/2018/11/06/2018-11-06-biz/ “根据权限查询时避免角色切换的一种思路”
[]: https://blog.yamato.moe/2019/04/04/Mybatis%20ResultSetHandler_2019-04-04%20%E7%BB%AD/ “【片段】 Mybatis ResultSetHandler 实践-续”
[]: https://blog.yamato.moe/2019/01/09/Mybatis%20ResultSetHandler_2019-01-09/ “【片段】 Mybatis ResultSetHandler 实践”

本人本身不太喜欢方法论，感觉都是套路，生搬硬套不适合自己，敏捷开发就是其中让我保持谨慎态度的方法论之一。

敏捷开发与Scrum

对于一个项目来说，能够即快又好地完成当然是非常棒的，但是众所周知，受限于项目管理三要素：时间、质量、成本，只能折衷选择。因此「敏捷」作为一种方法论（虽然Agile自称为Culture）被提出，其中Scrum(/skrʌm/，一种球类比赛)是比较知名的实现类之一。

在Scum中，它主要强调将瀑布式开发流程转为多阶段小迭代，可以理解为CPU的多级流水线(Instruction pipeline)设计，流水线设计将CPU的计算逻辑拆分，实现了复用计算模块，进而提高了时钟频率，同时也引入了寄存器/分支预测等管理模块增加了复杂度。

类似于CPU流水线机制，敏捷开发本质是在保持时间、质量不变的情况下，通过投入管理成本降低开发过程的空转成本，进而提高时钟周期的方法。

用白话来说，可以把软件开放比作流水车间，把PM，SE比作流水线工人。

我见过的的假敏捷

然而到了现实，由于各种原因，却很容易成为假敏捷

• 将工位的隔栏拆开变成网吧“敏捷岛”
• 强行将Release计划拆成一个月一版，将Sprint拆成2周就看作快速迭代，照着人月神话反着搞
• 招聘一堆无责任心的开发让你去“敏捷”，永远无法实现“全功能部队”
• 客户难沟通，PO低估工作量，SE设计缺陷，编码质量低等原因，最终导致延期
  上述任何一个问题，都可能导致最终项目一锅粥，导致高层焦虑，中层跑路，底层混日子的结果。

敏捷能够提供强大高效的方法论，但是前提是需要本身基础过硬的团队，敏捷只能帮助存在进步瓶颈的团队。如果项目已经空心化，债务多，这不是敏捷方法论应该解决的问题。