讲解十种性能优化手段
那些手段？
第一类 通用的“时间”和“空间”互换取舍的手段
- 索引术
- 压缩术
- 缓存术
- 预取术
- 削峰填谷术
- 批量处理术
第二类 大多与提升并行能力有关
- 榨干计算机资源
- 水平扩容
- 分片术
- 无锁术
索引术
索引的原理：就是拿额外的“空间”换取查询的“时间”，增加写入的开销，但是读取数据的时间复杂度一般从O(n)降低到O(logn)甚至O(1)
在生活中，一本字典从一本没有目录而且内容乱序的新华字典查询一个字时，需要一页一页查找到；用索引之后，就像用拼音先在目录中先找到要查到字在哪一页，直接翻过去就行了。
书籍的目录是典型的树状结构，那么软件世界常见的索引有哪些数据结构，分别在什么场景使用呢？
哈希表（Hash Table）：哈希表的原理可以类比银行办业务取号，给每个人一个号（计算出的 Hash 值），叫某个号直接对应了某个人，索引效率是最高的 O(1)，消耗的存储空间也相对更大。K-V 存储组件以及各种编程语言提供的 Map/Dict 等数据结构，多数底层实现是用的哈希表。
二叉搜索树（Binary Search Tree）：有序存储的二叉树结构，在编程语言中广泛使用的红黑树属于二叉搜索树，确切的说是“不完全平衡的”二叉搜索树。从 C++、Java 的 TreeSet、TreeMap，到 Linux 的 CPU 调度，都能看到红黑树的影子。Java 的 HashMap 在发现某个 Hash 槽的链表长度大于 8 时也会将链表升级为红黑树，而相比于红黑树“更加平衡”的 AVL 树反而实际用的更少。
平衡多路搜索树（B-Tree）：这里的 B 指的是 Balance 而不是 Binary，二叉树在大量数据场景会导致查找深度很深，解决办法就是变成多叉树，MongoDB 的索引用的就是 B-Tree。
叶节点相连的平衡多路搜索树（B+ Tree）：B+ Tree 是 B-Tree 的变体，只有叶子节点存数据，叶子与相邻叶子相连，MySQL 的索引用的就是 B+树，Linux 的一些文件系统也使用的 B+树索引 inode。其实 B+树还有一种在枝桠上再加链表的变体：B*树，暂时没想到实际应用。
日志结构合并树（LSM Tree）：Log Structured Merge Tree，简单理解就是像日志一样顺序写下去，多层多块的结构，上层写满压缩合并到下层。LSM Tree 其实本身是为了优化写性能牺牲读性能的数据结构，并不能算是索引，但在大数据存储和一些 NoSQL 数据库中用的很广泛，因此这里也列进去了。
字典树（Trie Tree）：又叫前缀树，从树根串到树叶就是数据本身，因此树根到枝桠就是前缀，枝桠下面的所有数据都是匹配该前缀的。这种结构能非常方便的做前缀查找或词频统计，典型的应用有：自动补全、URL 路由。其变体基数树（Radix Tree）在 Nginx 的 Geo 模块处理子网掩码前缀用了；Redis 的 Stream、Cluster 等功能的实现也用到了基数树（Redis 中叫 Rax）。
跳表（Skip List）：是一种多层结构的有序链表，插入一个值时有一定概率“晋升”到上层形成间接的索引。跳表更适合大量并发写的场景，不存在红黑树的再平衡问题，Redis 强大的 ZSet 底层数据结构就是哈希加跳表。
倒排索引（Inverted index）：这样翻译不太直观，可以叫“关键词索引”，比如书籍末页列出的术语表就是倒排索引，标识出了每个术语出现在哪些页，这样我们要查某个术语在哪用的，从术语表一查，翻到所在的页数即可。倒排索引在全文索引存储中经常用到，比如 ElasticSearch 非常核心的机制就是倒排索引；Prometheus 的时序数据库按标签查询也是在用倒排索引
数据库主键之争：自增长 vs UUID。主键是很多数据库非常重要的索引，尤其是 MySQL 这样的 RDBMS 会经常面临这个难题：是用自增长的 ID 还是随机的 UUID 做主键？
自增长 ID 的性能最高，但不好做分库分表后的全局唯一 ID，自增长的规律可能泄露业务信息；而 UUID 不具有可读性且太占存储空间。
争执的结果就是找一个兼具二者的优点的折衷方案：
用雪花算法生成分布式环境全局唯一的 ID 作为业务表主键，性能尚可、不那么占存储、又能保证全局单调递增，但引入了额外的复杂性，再次体现了取舍之道。
再回到数据库中的索引，建索引要注意哪些点呢？
定义好主键并尽量使用主键，多数数据库中，主键是效率最高的聚簇索引；
在 Where 或 Group By、Order By、Join On 条件中用到的字段也要按需建索引或联合索引，MySQL 中搭配 explain 命令可以查询 DML 是否利用了索引；
类似枚举值这样重复度太高的字段不适合建索引（如果有位图索引可以建），频繁更新的列不太适合建索引；
单列索引可以根据实际查询的字段升级为联合索引，通过部分冗余达到索引覆盖，以避免回表的开销；
尽量减少索引冗余，比如建 A、B、C 三个字段的联合索引，Where 条件查询 A、A and B、A and B and C
都可以利用该联合索引，就无需再给 A 单独建索引了；根据数据库特有的索引特性选择适合的方案，比如像 MongoDB，还可以建自动删除数据的 TTL 索引、不索引空值的稀疏索引、地理位置信息的 Geo 索引等等。
数据库之外，在代码中也能应用索引的思维，比如对于集合中大量数据的查找，使用 Set、Map、Tree 这样的数据结构，其实也是在用哈希索引或树状索引，比直接遍历列表或数组查找的性能高很多。
缓存术
缓存优化性能原理：就是拿额外的“空间”换取查询的“时间”
计算机科学中只有两件困难的事情：缓存失效和命名规范。
缓存的使用除了带来额外的复杂度以外，还面临如何处理缓存失效的问题。
- 多线程并发编程需要用各种手段（比如 Java 中的 synchronized volatile）防止并发更新数据，一部分原因就是防止线程本地缓存的不一致；
- 缓存失效衍生的问题还有：缓存穿透、缓存击穿、缓存雪崩。解决用不存在的 Key 来穿透攻击，需要用空值缓存或布隆过滤器；解决单个缓存过期后，瞬间被大量恶意查询击穿的问题需要做查询互斥；解决某个时间点大量缓存同时过期的雪崩问题需要添加随机 TTL；
- 热点数据如果是多级缓存，在发生修改时需要清除或修改各级缓存，这些操作往往不是原子操作，又会涉及各种不一致问题。
除了通常意义上的缓存外，对象重用的池化技术，也可以看作是一种缓存的变体。
常见的诸如 JVM，V8 这类运行时的常量池、数据库连接池、HTTP 连接池、线程池、Golang 的 sync.Pool 对象池等等。
在需要某个资源时从现有的池子里直接拿一个，稍作修改或直接用于另外的用途，池化重用也是性能优化常见手段。
压缩术
缓存优化性能原理：时间换空间
压缩的原理消耗计算的时间，换一种更紧凑的编码方式来表示数据。
为什么要拿时间换空间？时间不是最宝贵的资源吗？
举一个视频网站的例子，如果不对视频做任何压缩编码，因为带宽有限，巨大的数据量在网络传输的耗时会比编码压缩的耗时多得多。
对数据的压缩虽然消耗了时间来换取更小的空间存储，但更小的存储空间会在另一个维度带来更大的时间收益。
这个例子本质上是：“操作系统内核与网络设备处理负担 vs 压缩解压的 CPU/GPU 负担”的权衡和取舍。
我们在代码中通常用的是无损压缩，比如下面这些场景:
- HTTP 协议中 Accept-Encoding 添加 Gzip/deflate，服务端对接受压缩的文本（JS/CSS/HTML）请求做压缩，大部分图片格式本身已经是压缩的无需压缩；
- HTTP2 协议的头部 HPACK 压缩；
- JS/CSS 文件的混淆和压缩（Uglify/Minify）；
- 一些 RPC 协议和消息队列传输的消息中，采用二进制编码和压缩（Gzip、Snappy、LZ4 等等）；
- 缓存服务存过大的数据，通常也会事先压缩一下再存，取的时候解压；
- 一些大文件的存储，或者不常用的历史数据存储，采用更高压缩比的算法存储；
- JVM 的对象指针压缩，JVM 在 32G 以下的堆内存情况下默认开启“UseCompressedOops”，用 4 个 byte 就可以表示一个对象的指针，这也是 JVM 尽量不要把堆内存设置到 32G 以上的原因；
- MongoDB 的二进制存储的 BSON 相对于纯文本的 JSON 也是一种压缩，或者说更紧凑的编码。但更紧凑的编码也意味着更差的可读性，这一点也是需要取舍的。纯文本的 JSON 比二进制编码要更占存储空间但却是 REST API 的主流，因为数据交换的场景下的可读性是非常重要的。
信息论告诉我们，无损压缩的极限是信息熵。进一步减小体积只能以损失部分信息为代价，也就是有损压缩。
那么，有损压缩有哪些应用呢？
- 预览和缩略图，低速网络下视频降帧、降清晰度，都是对信息的有损压缩；
- 音视频等多媒体数据的采样和编码大多是有损的，比如 MP3 是利用傅里叶变换，有损地存储音频文件；jpeg 等图片编码也是有损的。虽然有像 WAV/PCM 这类无损的音频编码方式，但多媒体数据的采样本身就是有损的，相当于只截取了真实世界的极小一部分数据；
- 散列化，比如 K-V 存储时 Key 过长，先对 Key 执行一次“傻”系列（SHA-1、SHA-256）哈希算法变成固定长度的短 Key。另外，散列化在文件和数据验证（MD5、CRC、HMAC）场景用的也非常多，无需耗费大量算力对比完整的数据。
能减少的就减少：
- JS 打包过程“摇树”，去掉没有使用的文件、函数、变量；
- 开启 HTTP/2 和高版本的 TLS，减少了 Round Trip，节省了 TCP 连接，自带大量性能优化；
- 减少不必要的信息，比如 Cookie 的数量，去掉不必要的 HTTP 请求头；
- 更新采用增量更新，比如 HTTP 的 PATCH，只传输变化的属性而不是整条数据；
- 缩短单行日志的长度、缩短 URL、在具有可读性情况下用短的属性名等等；
- 使用位图和位操作，用风骚的位操作最小化存取的数据。典型的例子有：用 Redis 的位图来记录统计海量用户登录状态；布隆过滤器用位图排除不可能存在的数据；大量开关型的设置的存储等等。
能删除的就删除：
- 删掉不用的数据；
- 删掉不用的索引；
- 删掉不该打的日志；
- 删掉不必要的通信代码，不去发不必要的 HTTP、RPC 请求或调用，轮询改发布订阅；
预取术
削峰填谷
削峰填谷的原理也是“时间换时间”，谷时换峰时。
常见的有这几类问题，我们分别来看每种对应的解决方案：
- 针对前端、客户端的启动优化或首屏优化：代码和数据等资源的延时加载、分批加载、后台异步加载、或按需懒加载等等。
- 背压控制 - 限流、节流、去抖等等。一夫当关，万夫莫开，从入口处削峰，防止一些恶意重复请求以及请求过于频繁的爬虫，甚至是一些 DDoS 攻击。简单做法有网关层根据单个 IP 或用户用漏桶控制请求速率和上限；前端做按钮的节流去抖防止重复点击；网络层开启 TCP SYN Cookie 防止恶意的 SYN 洪水攻击等等。彻底杜绝爬虫、黑客手段的恶意洪水攻击是很难的，DDoS 这类属于网络安全范畴了。
- 针对正常的业务请求洪峰，用消息队列暂存再异步化处理：常见的后端消息队列 Kafka、RocketMQ 甚至 Redis 等等都可以做缓冲层，第一层业务处理直接校验后丢到消息队列中，在洪峰过去后慢慢消费消息队列中的消息，执行具体的业务。另外执行过程中的耗时和耗计算资源的操作，也可以丢到消息队列或数据库中，等到谷时处理。
- 捋平毛刺：有时候洪峰不一定来自外界，如果系统内部大量定时任务在同一时间执行，或与业务高峰期重合，很容易在监控中看到“毛刺”——短时间负载极高。一般解决方案就是错峰执行定时任务，或者分配到其他非核心业务系统中，把“毛刺”摊平。比如很多数据分析型任务都放在业务低谷期去执行，大量定时任务在创建时尽量加一些随机性来分散执行时间。
- 避免错误风暴带来的次生洪峰：有时候网络抖动或短暂宕机，业务会出现各种异常或错误。这时处理不好很容易带来次生灾害，比如：很多代码都会做错误重试，不加控制的大量重试甚至会导致网络抖动恢复后的瞬间，积压的大量请求再次冲垮整个系统；还有一些代码没有做超时、降级等处理，可能导致大量的等待耗尽 TCP 连接，进而导致整个系统被冲垮。解决之道就是做限定次数、间隔指数级增长的 Back-Off 重试，设定超时、降级策略。