扇贝的自我述说

索引的原理是拿额外的存储空间换取查询时间，增加了写入数据的开销，但使读取数据的时间复杂度一般从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这样的数据结构，其实也是在用哈希索引或树状索引，比直接遍历列表或数组查找的性能高很多。

软件设计开发某种意义上是“取”与“舍”的艺术。你无法获取无限的资源去完成无限膨胀的需求。只能在有限的条件内去完成限定范围内的事情。

在性能方面，高性能软件系统也意味着更高的实现成本，有时候与其他质量属性甚至会冲突，比如安全性、可扩展性、可观测性等等。

性能优化总结下来有两个方向：

• 资源置换——也就是“时间”和“空间”的互换取舍。
• 并行处理。

下面来分别说明这两个方向。

资源置换

在“时间”和“空间”的互换舍取有常见的6种方法：

• 索引
• 压缩
• 缓存
• 预取
• 削峰填谷
• 批量处理

索引

索引的原理是拿额外的存储空间换取查询时间，增加了写入数据的开销，但使读取数据的时间复杂度一般从O(n)降低到O(logn)甚至O(1)。

有很多种索引的类型，根据不同的场景需要使用不同的索引类型。索引还涉及到主键和分库分表的处理。

缓存

缓存优化性能的原理和索引一样，是拿额外的存储空间换取查询时间。

缓存的形式同样多种多样。从廉价的磁盘到昂贵的CPU高速缓存，最终目的都是用来换取宝贵的时间。

Phil Karlton 曾说过：There are only two hard things in Computer Science: cache invalidation and naming things.

计算机科学中只有两件困难的事情：缓存失效和命名规范。

缓存的使用除了带来额外的复杂度以外，还面临如何处理缓存失效的问题。

压缩

压缩是一个“时间换空间”的办法。

压缩的原理消耗计算的时间，换一种更紧凑的编码方式来表示数据。

为什么要拿时间换空间？时间不是最宝贵的资源吗？

举一个视频网站的例子，如果不对视频做任何压缩编码，因为带宽有限，巨大的数据量在网络传输的耗时会比编码压缩的耗时多得多。

对数据的压缩虽然消耗了时间来换取更小的空间存储，但更小的存储空间会在另一个维度带来更大的时间收益。

这个例子本质上是：“操作系统内核与网络设备处理负担 vs 压缩解压的CPU/GPU负担”的权衡和取舍。

预取

预取通常搭配缓存一起用，其原理是在缓存空间换时间基础上更进一步，再加上一次“时间换时间”，也就是：用事先预取的耗时，换取第一次加载的时间。

当可以猜测出以后的某个时间很有可能会用到某种数据时，把数据预先取到需要用的地方，能大幅度提升用户体验或服务端响应速度。

是否用预取模式就像自助餐餐厅与厨师现做的区别，在自助餐餐厅可以直接拿做好的菜品，一般餐厅需要坐下来等菜品现做。

削峰填谷

削峰填谷的原理也是“时间换时间”，谷时换峰时。

削峰填谷与预取是反过来的：预取是事先花时间做，削峰填谷是事后花时间做。就像三峡大坝可以抗住短期巨量洪水，事后雨停再慢慢开闸防水。软件世界的“削峰填谷”是类似的，只是不是用三峡大坝实现，而是用消息队列、异步化等方式。

针对不同的场景同样会使用不同的应用手段。

批量处理

批量处理同样可以看成“时间换时间”，其原理是减少了重复的事情，是一种对执行流程的压缩。以个别批量操作更长的耗时为代价，在整体上换取了更多的时间。

并行处理

并行处理也有为4种常见手段：

• 榨干计算资源。
• 水平扩容
• 分片
• 无锁

榨干计算资源

让硬件资源都在处理真正有用的逻辑计算，而不是做无关的事情或空转。

从晶体管到集成电路、驱动程序、操作系统、直到高级编程语言的层层抽象，每一层抽象带来的更强的通用性、更高的开发效率，多是以损失运行效率为代价的。

水平扩容

本节的水平扩容以及下面一节的分片，可以算整体的性能提升而不是单点的性能优化，会因为引入额外组件反而降低了处理单个请求的性能。

但当业务规模大到一定程度时，再好的单机硬件也无法承受流量的洪峰，就得水平扩容了，毕竟”众人拾柴火焰高”。

在这背后的理论基础是，硅基半导体已经接近物理极限，随着摩尔定律的减弱，阿姆达尔定律的作用显现出来。

分片

水平扩容针对无状态组件，分片针对有状态组件。二者原理都是提升并行度，但分片的难度更大。

负载均衡也不再是简单的加权轮询了，而是进化成了各个分片的协调器

无锁

有些业务场景，比如库存业务，按照正常的逻辑去实现，水平扩容带来的提升非常有限，因为需要锁住库存，扣减，再解锁库存。

票务系统也类似，为了避免超卖，需要有一把锁禁锢了横向扩展的能力。

不管是单机还是分布式微服务，锁都是制约并行度的一大因素。比如上篇提到的秒杀场景，库存就那么多，系统超卖了可能导致非常大的经济损失，但用分布式锁会导致即使服务扩容了成千上万个实例，最终无数请求仍然阻塞在分布式锁这个串行组件上了，再多水平扩展的实例也无用武之地。

避免竞争Race Condition 是最完美的解决办法。

什么是页？为什么要有页

假设没有页，mysql和磁盘间交互时，每当有⼀条数据改动，都要进⾏磁盘IO。如果修改的数据很多，那么要访问多次磁盘，性能急剧下降。
此时就会有⼀个想法“那么如果在访问磁盘时，能⼀次性修改多条数据就好了”。 所以有了页。在⼀页中可以存储多条数据。
有了页之后，mysql和磁盘间的交互是以页为单位的。⽽不是⼀条数据为单位。那么就能提升性能。

Java一开始就有接口，但到Java8才引入了接口的默认方法。

在Java 8之前，接口只能定义抽象方法和常量。实现接口的类必须实现接口中定义的所有抽象方法。如果在接口中添加新的方法，那么所有实现该接口的类都必须修改代码以实现新的方法。

Java 8引入了接口的默认方法和静态方法，使得接口的定义更加灵活和易于使用。通过默认方法，接口可以提供一些默认的实现，而不需要强制实现这些方法。这种改进使得接口在Java中的应用更加广泛，也为Java 8中的函数式编程提供了更好的支持。

有下面这样一个叫MyInterface的接口，里面有个默认方法myDefaultMethod：

interface MyInterface {
  default void myDefaultMethod() {
    System.out.println("This is a default method in MyInterface.");
  }
}

class MyClass implements MyInterface {
  // no need to implement myDefaultMethod() in MyClass
}

public class Main {
  public static void main(String[] args) {
    MyClass obj = new MyClass();
    obj.myDefaultMethod(); // output: This is a default method in MyInterface.
  }
}

继承MyInterface接口的类就不需要去实现接口中的默认方法了。在主程序中也可以直接使用默认方法。

当然，实现类也可以对默认方法进行重写。

默认方法的主要目的是为了使现有的接口能够被修改而不破坏现有的实现。

接口中的静态方法。

接口中的静态方法是指在接口中声明的带有static关键字的方法，这些方法可以通过接口名称直接调用，而无需实例化接口的实现类。

静态方法可以直接通过接口名称调用，而默认方法则必须通过实现类的实例调用。静态方法通常用于提供实用工具或服务，而默认方法用于为现有的接口提供新的功能或行为。

在Java中有两种字符串的处理方式：

• 第一种是不可变的方式：String
• 第二种是可变的方式：StringBuffer、StringBuilder

String对象一旦被创建，就不可修改，任何的字符串操作都会返回一个新的String对象，这可能导致频繁的对象创建和销毁，影响性能。

StringBuffer和StringBuilder允许进行修改操作，提供了一种更高效的字符串处理方式。

由于String的不可变性，因此天生具备线程安全，可以在多个线程中安全使用。

而StringBuffer和StringBuilder的主要区别在于线程安全性和性能方面。

StringBuffer是线程安全的，所有方法都是同步的（底层实现加了synchronize关键字），因此可以被多个线程同时访问和修改。

StringBuilder是线程不安全的，适用于单线程环境下的字符串处理，但性能比StringBuffer更高。

因此当字符串处理不需要修改时，可以使用String；当字符串需要频繁修改时，建议使用StringBuffer或Stringbuilder

String类型是存储在字符串常量空间里的。

StringBuffer存储在堆内存里。

StringBuilder存储在堆内存里。

假设一个教室50个人，但只有一个厕所。

当你想上厕所的时候也有其它人想上厕所，这种情况叫冲突。

肯定不能说有内急的人一块上厕所。

如何保证在发生冲突的时候，在同一时间只有一个人可以上厕所呢？

可以制定某种规则，只有符合规则的人才能上厕所。

可以有以下规定：

• 都想上厕所的人打一架、打赢了的人才能上厕所。
• 剪刀石头布，赢的人上厕所。
• 先到先得，谁先来谁上厕所。

先上厕所的人把门关上，上完厕所再把门打开。

但如果这个人一直上厕所，永远不出来也不行。因为他可能在厕所里晕倒了。因此需要在厕所设置一个闹钟，一旦超时规定时间，闹钟就会响。之后破门而入把他从厕所里面救出来。

但如果这个人确实是因为肚子不舒服需要很长的上厕所时间，但这个闹钟超过了预设的超时时间响了怎么办？强行破门后，发现对方真的是肚子不舒服，而不是晕倒在厕所。

实现分布式锁的方式

那在程序种如何实现这整套厕所的分配规则呢？

比如在数据库中有个字段为lock master，当有数据访问时设置为唯一标识，当不访问时设置为null，那其它的程序来访问时候就知道了，这个数据有人正在用。当然这个数据库可以是mysql可以是redis。

而redis的分布式也是这样的，是多个服务器去访问另一个集中的服务器，这个集中的服务器上有redis。

注意事项：用完要释放锁、锁一定要设置过期时间。（如果不加后面，如果服务器执行到一半挂了，后面的所有服务器都用不了）。如果方法执行过长，可能会释放别人的锁，可以使用续期（续期的别名叫看门狗）

实现分布式锁的工具

MySQL数据库：select for update 行级锁（最简单）（但比较吃性能），这里涉及到乐观锁和悲观锁。

redis来存储标识。（性能比较好，读写更快）支持setnx，支持lua脚本，也方便实现分布式锁

Zookeeper（不推荐，企业用的少）

实现分布式锁的实现

Redisson实现分布式锁，上面那些都不要自己写。

官网：Redisson PRO – Redis Java client with features of In-Memory Data Grid

github：redisson / redisson

给Redisson下定义（当别人问你Redisson是什么的时候，你怎么回答？）：Redisson是一个用Java操作Redis的客户端。提供了大量的分布式数据集，用来简化对Redis的操作和使用。可以让开发者像使用本地集合一样使用Redis，让开发者完全感受不到Redis的存在。

补充：Redisson是Java客户端，而Java客户端就是用来操作Java的。用了Redisson可以往Redis里面增删改查。并且Redisson实现了很多Java里支持的接口和数据结构。

分布式锁的优缺点

优点：

• 可以避免分布式系统中的资源竞争问题：在分布式系统中，多个进程或者节点可能同时对同一个资源进行访问，导致竞争和冲突。分布式锁可以通过协调进程或者节点之间的访问，避免这种竞争和冲突。
• 提高系统可用性、降低运营和维护成本：可以不用显式配置服务器，可以部署多个服务器。
• 可以保证数据的一致性和可靠性：分布式锁可以确保在任何时刻只有一个进程或者节点可以访问共享资源，从而保证数据的一致性和可靠性。

缺点：

• 增加开发成本，增加系统复杂度：使用分布式锁需要引入一些新的组件或者服务，比如 ZooKeeper 等，这会增加系统的复杂度。
• 会增加系统的延迟：由于需要通过网络进行通信，分布式锁会增加系统的延迟。在高并发的情况下，这个延迟可能会很大。
• 可能会出现死锁：由于分布式锁涉及多个节点或者进程之间的协调，如果协调不当，就可能会出现死锁问题。