Lifelong Learning

上篇已经聊过 1.24 前的 map，这篇让我们看看 1.24 之后的实现 —— 瑞士表（SwissTable） 1 引 在有一次面试的时候，面试官问了我一个问题，这个问题在我学习 SwissTable 的时候意识到是同一个问题。问题如下： 现在有一百万条数据要做处理，还有一个足够大的内存能放下这一百条数据，现在假设这个数据有两种组织方式，一种是链表，另一种是数组，请问哪一种处理起来效率会更高？ 这个问题我当时是这么回答的（当然这里语言组织的比当时好很多^-^）：数组处理效率更高，因为 cpu 把数据从内存读到寄存器的时候，不是一次拿一条数据，而是一次拿一块连续的内存放进 cache。此时如果是链表的情况，链表两个节点在内存空间中地址不连续，就会导致我一次拿的内存可能不会覆盖到下一个节点，那么拿下一个节点的时候，又需要访问，带来了额外开销。而数组不一样，连续的内存让他有了很好的空间局部性，拿一块内存，那下一次访问的数据也大概率会在 cache 中找到，减少了访存的次数，从而提高了性能。 1.1 拉链法的性能瓶颈 从上面的这个引子也就知道了，拉链法指针地址的离散型，是对 Cache 不友好的，按照现代计算机的设计来看，离 CPU 越远，获取数据的成本就越高。换言之，我们希望有一种方式能尽可能让 Hash 表中的数据紧密起来，让 CPU 能一次访存，多次复用。 回到解决 Hash 冲突问题本身，除了拉链法，还有一种就是线性探测法。线性探测法是在 Hash 碰撞的时候，向后找位置，找到第一个可以放下该元素的槽（slot），接着插入，如果直到链表查完都没有 slot 可用，就触发扩容。查询的时候，会从 Hash 的起始 slot 往后查，直到查到元素或者查到空 slot 或者查完整个表，结束查询。 线性探测法的链表会呈现出如下的形式。（忘记画slot的状态的，简单看看~） 可以看出来如果是线性探测法的 Hash 表，只需要一个数组就能承担责任，而数组是内存连续的地址，妥妥的cache friendly。而且实现起来也相对简单，每个位置只需要存储 kv 对以及当前 slot 的状态（是空还是已删除还是有数据）。固然缓存友好，但是线性探测法的缺点在哪里？ 冲突的 Key 总归是要存储起来的，而其存储会占用其他的 Hash 槽，会导致其扩容频率高于拉链法。 查找过程有大概率会退化到 O(n) 的时间复杂度，而且没法进行像 Java 中的 HashMap 那样将链表转化为红黑树的优化。 1.2 单指令流多数据流（SIMD） 先上结论：SIMD 在 SwissTable 中的应用很大的提高了 Hash 对比的效率。 在具体展开讲 SwissTable 之前，先来回顾一下 SIMD，也就是一条指令操作多个数据。连续内存带来的优势会被 SIMD 进一步放大。与 SIMD 对应的是 SISD，也就是单指令流多数据流。 单指令流多数据流硬件层面的限制，导致了一条指令只能操作一个数据，无法实现数据并行。 而在 SIMD 中，每个ALU 前面都有自己独立的局部寄存器组，当 CU 会把指令下发给所有 ALU，然后 ALU 会从自己的局部寄存器组中获取不同的数据，然后进行一样的操作。举个例子： A = [1, 2, 3, 4]，B = [4, 3, 2, 1] 求 A 中元素和 B 中元素对应位置相加。 首先在访存的时候，会分别将 A 和 B 的数据按地址分为四块，放入四个 ALU 中的局部寄存器，然后，CU 发 ADD 指令给每个 ALU，ALU 会从读出局部寄存器的值，然后独立的进行操作，从而实现单指令流多数据流。 这里就看出了 SIMD 的对数据的基本要求： ...

1.24 前后 map 的世界，在 1.24 后，go 的 map 换了实现方式，让我们来康康 1 追踪 map 的起始点 看下面这段代码，我们来定位一下 make 之后发生了什么？ package main func main() { _ = make(map[string]int, 16) } 使用 go tool compile -S 编译文件，可以发现 map 实际上是定位到了底层的 runtime.makemap 中，这使得我们有了窥探 map 源码的机会。 ❯ go tool compile -S main.go | grep 'make' 0x0034 00052 (.../main.go:4) CALL runtime.makemap(SB) rel 52+4 t=R_CALLARM64 runtime.makemap+0 在进入具体方法之前，我们先了解一下 1.24 之前 go 的 map 的结构 2 1.24 前的世界 本节 go 的代码是基于 1.23.2 版本的 2.1 map 的基本构造 在 1.24 前，go 的 map 实现是基于桶数组 + 溢出桶实现的，具体而言是基于 runtime 下的这两个结构体实现的。 首先是 hmap，他是宏观上的 map，包含了 map 的键值对数量、状态、桶的数量以及桶的指针等等。当我们创建了一个 map 的时候，宏观来看就是创建 hmap。 ...

什么是摘樱桃？ 在分支协作中，出现以下这种情况，假设我的 main 分支只想要 feat 分支的 E 或者 F 的改动，此时就需要用到像摘樱桃一样给那几个提交摘过来（一个个小提交就像小樱桃），也就是 cherry-pick。 理解起来不难，但在实际操作中，还是有一些小问题的。我把目前摘樱桃的情况归为三类： 第一类是无冲突直接摘，例如 E 提交创建了一个新文件，这时 main 直接摘 E 过来是没问题的。 第二类是假设 F 是基于 E 的改动，但是我摘的时候，只摘了 F 过来，没有摘 E，此时摘樱桃操作会卡住。 第三类是你摘过来的提交和你本地的提交产生了冲突，此时需要解决冲突，cherry-pick 操作会卡住。 无冲突直接摘 这个没什么好说的，很简单，所以这里介绍一下几个 cherry-pick 的命令，分别是 git cherry-pick A // 只摘提交 A git cherry-pick A..B // 摘提交(A, B] git cherry-pick A^..B // 摘提交[A, B] git cherry-pick --abort // cherry-pick 操作终止，回滚 git cherry-pick --continue // 解决冲突后，cherry-pick 操作继续执行 所摘提交的依赖提交未摘 现在 feat 分支中有一个 main 分支中不存在的文件 READMEX.md，feat 中分别有两个提交，提交 A 是创建文件并写入一些内容，提交 B 是在文件中追加了一些内容。 ...

老 merge 了，但 rebase 弱的一逼，面试被问到，遂复盘 场景 小 A 在 feat1 分支开发，他肯定不能直接在 main 上做修改（为了保护项目的安全性），此时，为了防止大量的冲突，小 A 每次开发前都要拉去 main 分支的代码来看看，没啥冲突就直接合入，这样能有效避免积压大量的冲突。 此时就有问题了，git 中有两种合入代码的方式，分别是 merge 和 rebase，对应命令如下 git merge origin/main git rebase origin/main 到底用哪一个呢？小 A 挠挠头。 这里先给出一个方案，如果你是 main / master 分支的维护者，尽量使用 Merge，如果你是要维护自己的分支，可以用 Rebase，原因我们娓娓道来。 GitGraph GitGraph 是直观的 Git 多分支提交记录的展示，下面是一张示意图 在 GitGraph 中一条分叉就是一个分支，比如说上图，从 C 这个提交分出了一个 Feat 分支，也就是说，Feat 分支拥有含 C 之前的所有 Main 的提交，从 C 之后，Main 和 Feat 形同陌路。 Merge 合入 OK，我们先简单看看，基于上面这张 GitGraph，如果说在小 A 执行 merge 操作，会发什么？ 很直观，如果执行 merge，会基于 main 分支的最新提交和 feat 分支的最新提交，进行合并，然后形成一个新的提交，非常直观。 ...

在面 MoonShot 的时候被问到了这个，当时我只知道认证和鉴权的区别，第一遍听二者的英文名没听懂啥意思，然后就没答出来，我以为是什么其他的芝士点，可恶捏，我得饿补一下芝士点QAQ。 认证（Authentication） 我们常说的登录，这实际上就是认证：Authentication 的完整定义是身份认证，即系统确认你是谁的过程。其本质是用户提供某种可信凭证来证明自己的身份。 平时我们所说的 Jwt 鉴权、Cookie-Session 鉴权这些很多时候讲的就是认证。下面先简单讲讲两个基础认证的手段，后面后统一讲一些框架，比如说 SSO。 Cookie-Session Cookie 和 Session 算是认证的基本芝士了。众所周知，Http 是一个无状态的协议，想象一下，如果没有一种措施让服务器知道你是谁，就得每次操作都需要输一次账号密码了。虽然 Cookie 和 Session 不是专门为认证所打造的，但是其可以实现简单的认证。 下面是一个简单的 Cookie-Session 的图示： 过程相当的简单，这也正是 Cookie-Session 的优点所在，实现起来相当简单，同时 Session 的鉴权信息是保存在服务器上的，一般来说也比较安全，而缺点也很明显。 缺点： 天然非分布式。我们现在的服务器大多都是负载均衡的，而假设我们认证的信息被保存在了服务器 A 上，而后续请求都打到其他服务器上，其他服务器是没有对应的 SessionId 信息的，从而导致无法正常认证。要解决这个问题需要引入其他组件，比如说 Redis 等，进而增加了系统的复杂性。 前端未防护 XSS 的情况下，Cookie 可能会被盗取，从而导致安全问题。 Session 的生命周期管理复杂。一般来说，我们会给 Session 设置一个过期时间，认证时发现过期会拒绝请求，但这些过期的 Session 会造成一定的服务器压力，需要手动清理。 Jwt-Token JwtToken 全称是 Json-Web-Token，是一种无状态的认证手段。这个相较于 Cookie-Session 会更加符合“潮流”一些。我们来看看用 Jwt 是怎么做认证的。 上面就是一个完整的认证流程，从宏观上来看，似乎只是客户端携带的东西不同了。我认为最重要的不同点是服务器存储的信息粒度的变大，服务器无需再存储每个用户的信息，只需要存储一个服务或者一个业务的密钥，就能解决这个业务上所有用户的认证问题，这一个转变解决了下面这些问题： Cookie-Session 的天然不支持分布式的问题，只要一台服务器上有对应服务的密钥，那就 OK。 解决了 Session 的生命周期管理的问题，因为服务器无存储压力，服务器只需要看这个 Jwt 里包含的过期时间有没有过期。 如此完美的方案是否有问题呢？有的兄弟，有的： ...

前段时间在面试字节的时候，面试官拿着 Sql 问我这个锁和索引之间的联系是什么的时候？人懵住了，这玩意还有联系？之后意识到是自己学习东西太过于肤浅，没有建立体系，导致这么简单的问题没答出来，悔不当初 QAQ。 Mysql 存储数据的方式 Mysql 底层存储数据是通过一个一个数据页所组成的，一页中存储的数据属于同一张表，但同一张表的数据不一定分布在同一页，从粗到细粒度大致是： 表空间 (Tablespace) └── 段 (Segment) └── 区 (Extent) └── 页 (Page, 16KB) └── 行记录 (Row) 我们这里主要分析页和行的结构 数据页（Data Page） 上图展示的就是一页的数据内容，Mysql 的行数据被单向链表的形式组织起来，为了提高页内检索效率，所以有了槽和分组的概念。他们的对应关系是，一个数据页中有多个槽，每个槽中有一个或多个数据行，数据行以单向链表的形式组织起来，然后链表头部和尾部分别是记录中的最小记录和最大记录标识。通过这样的形式组织起来的数据有什么好处呢？答曰提高检索效率。如果只单纯使用单向链表，那就意味着每次查找只能单向搜索。而使用槽，槽指针指向了一个分组内的最大记录，那就意味着在一页内可以用二分查找来提高检索的时间复杂度。 行记录（Data Row） 上面讲述了一页是如何组织的，下面来看看一行是如何组织的。 这就是一行数据，从左到右分别记载了： 变长字段列表：记录行数据中变长字段占用的字节数 Null 值列表：记录行数据中，可以为 Null 的列是否为 Null，也就是说一列对应一个 Bit 位，如果为 Null，在对应的 bit 位为 0 记录头：这里主要包含了一些辅助信息，比如记录的类型（是否是 B+树的叶子）、下一条记录的位置以及是否被删除标记。 RowId：当表设置了主键或者唯一性约束，则这一列隐藏，如果没设置，则 Mysql 会默认生成 RowId 字段。 TrxId：这条记录是由哪行所生成的。 Rollptr：UndoLog 的列表挂载，用于回滚和 MVCC。 上面就是一行记录，也就是说，当你创建一个表，Mysql 底层就是这么组织的。 索引 Mysql 索引分类 按照数据结构：Hash 索引、FullText 索引、B+ 树索引 按照底层存储：聚簇索引、非聚簇索引 按照建立索引的字段类型：主键索引、唯一索引、前缀索引、普通索引 按照字段数量：单列索引、组合索引 我们主要来关注聚簇索引和非聚簇索引，我们知道聚簇索引就是主键索引，其存储了主键和整行的数据，而非聚簇索引的一行第一列是索引值，第二行是主键值。为什么？Why？为什么第存全量数据？这是因为 Mysql 的底层数据组织结构造成的，B+ 树存储索引是要存储全量的数据页的，如果说非聚簇索引也存储全量数据，就等于在建立索引的时候，需要将所有数据页进行一次全量拷贝 + 组织，就意味着底层会出现大量重复的数据，所以 InnoDB 选择第二列存储主键值，这样当检索到索引后，只需要再去聚簇索引中，找到对应的数据即可。 Mysql 索引的数据组织结构 我们知道 InnoDB 的索引底层是基于 B+ 树的，而索引和页的关系是什么呢？答案是索引由数据页组成。 Mysql 的数据是这样存的，当你创建一个表并存入数据时，Mysql 会默认生成一个基于主键的聚簇索引，就是无论你主动创建索引与否，Mysql 都会生成聚簇索引，这不只是为了提高检索速度，而是 InnoDB 的行锁机制是基于索引的。所以这里也就 CallBack 到了开头的，索引和锁的关系。 ...

&&& Golang GC 流程 Go 如何启动 GC Go 触发 GC 有三种情况： 主动调用 runtime.gc() 可能会触发 Gc 当分配对象时可能会触发 Gc 守护协程定时 Gc runtime/mgc.go const ( // 根据堆分配内存情况，判断是否触发 GC gcTriggerHeap gcTriggerKind = iota // 定时触发 GC gcTriggerTime // 手动触发 GC gcTriggerCycle } func (t gcTrigger) test() bool { // ... switch t.kind { case gcTriggerHeap: // ... // 如果是堆内存分配导致的 GC，会 Check 当前堆内存的使用情况 trigger, _ := gcController.trigger() return atomic.Load64(&gcController.heapLive) >= trigger case gcTriggerTime: // 如果是守护协程 GC，则会check当前距离上一次 GC 是否已经达到 2 min if gcController.gcPercent.Load() < 0 { return false } lastgc := int64(atomic.Load64(&memstats.last_gc_nanotime)) return lastgc != 0 && t.now-lastgc > forcegcperiod case gcTriggerCycle: // ... // 如果是手动触发 GC，check 前一轮 GC 有没有结束 return int32(t.n-work.cycles) > 0 } return true } Gc - Start Golang 的标记清扫算法的关键点就是标记这一步，其采用三色标记法，从 Root 对象开始进行可达性分析，关键步骤如下： ...

从流式输出到服务端推送技术再到 Java 的 WebFlux 大模型流式输出 像 ChatGPT 这样的网页，我们不难发现问出问题后，大模型吐字是一段接一段的，但我们传统的 Http 请求，一般是每次获取一段数据就要再次发起请求一次。这是一种耗费资源的方式，简言之就是 Http 轮询（短轮询和长轮询 Comet），所以服务端主动推送数据的计数就应运而生。 服务端主动推送技术 这里抛开 Http 轮询计数，主要涉及到了 SSE 和 WebSocket，其实 SSE 和 WebSocket 都是服务于 “实时” 二字的。 SSE 协议 SSE（Server Send Events），顾名思义，服务端发送事件，是指服务端能够主动给客户端发送消息。其基于 Http 协议，需要按照 SSE 协议规范在消息响应体中填充数据，如果需要 SSE 协议，则需要 Http 长连接（默认），并且将请求中的 content-type 设置为 text/event-stream。 其原理实际上是在建立好的 Http 连接上，于客户端协商，返回的类型不为一次性的数据包，而是返回一个 Stream。而基于这个 Strem，服务器可以不断的往内部填入数据，客户端也可以依次接受数据。 其实 SSE 是比较常见的，因为很多时候，只需要服务器推送给客户端，而客户端不需要给服务器发送内容，比如说在一个常用开源容器监控系统 Dozzle 中，就能看到其身影。可以类比，如果一个系统，类似比赛的看板或者日志的看板，就比较适合用 SSE 协议。 因为 SSE 并非一个完全新的协议，而是使用了 Http 协议的功能，并定义一系列规范，所以 SSE 的优点就是： 轻量级（并非全新协议）（相较于 WebSocket） 基于 Http，基本上所有的浏览器都支持、 支持断开重连 缺点： ...

串讲内容 从 Java 的并发的手段出发： Synchorized Volatile ReentrantLock 原子操作类 再到并发的底层 JMM 内存可见性和有序性 再到常见并发工具类 ConcurrentHashMap & HashTable JUC 并发安全手段 Java 的并发一直是面试的考点，这里并发安全手段主要整理了 Synchorized 关键字、Volatile 关键字、ReentranLock、原子操作类这四个 Synchorized 特性： 支持可重入 支持偏向锁、轻量级锁、重量级锁 非公平 Sync 关键字主要作用于方法，作用是标记某个对象或类的某个方法，在同一时刻只能有一个线程进行操作。其主要用法先了解下： // 1. 作用于代码块 synchorized(lock){ } // 2. 作用于普通方法 public synchorized void xxxx(){ } // 3. 作用于静态方法 public static synchorized void xxxx(){ } 上面的代码块，从上到下，Sync 关键字加锁的粒度也是逐渐增大，对于 1 号，锁的粒度是括号里的 lock；对于 2 号，锁的粒度是调用这个方法的对象；对于 3 号，锁的粒度是这个 Class。 ...

Java 中的 ArrayList 类似 Golang 里的 Slice，都是动态数组 ArrayList 什么是 ArrayList ArrayList 是 Java 中最常见的动态数组之一，他实现了 List 接口，底层基于数组实现，但能自动扩容，可以理解为变长数组的一种。 List<String> list = new ArrayList<>(); list.add("zhangsan"); list.add("lisi"); System.out.println(list); ArrayList 的扩容原理 当创建一个 ArrayList 的时候，默认初始的容量为 10，其内部实现类似 Object[] elementData = new Object[10] 当元素超过容量时，arraylist 就会触发扩容机制，其触发条件为 if(size == elementData.length) 扩容策略如下 newCapacity = oldCapacity + (oldCapacity + 1)，简言之就是扩容为原来的 1.5 倍。 这里涉及到扩容过程的主要函数是 grow() private void grow(int minCapacity) { int oldCapacity = elementData.length; int newCapacity = oldCapacity + (oldCapacity + 1); if(newCapacity - minCapacity < 0) { newCapacity = minCapacity; } // 创建新数组，复制旧数据 elementData = Arrays.copyOf(elementData, newCapacity) } 这里的扩容规则实际上并没有 Go 的复杂，但是要理解 minCapacity ...