Google | Tony Bai

标签 Google 下的文章

Go map使用Swiss Table重新实现，性能最高提升近50%

十一月 14, 2024
9 条评论

本文永久链接 – https://tonybai.com/2024/11/14/go-map-use-swiss-table

在2024月11月5日的Go compiler and runtime meeting notes中，我们注意到了一段重要内容，如下图红框所示：

这表明，来自字节的一位工程师在两年多前提出的“使用Swiss table重新实现Go map”的建议即将落地，目前该issue已经被纳入Go 1.24里程碑。

Swiss Table是由Google工程师于2017年开发的一种高效哈希表实现，旨在优化内存使用和提升性能，解决Google内部代码库中广泛使用的std::unordered_map所面临的性能问题。Google工程师Matt Kulukundis在2017年CppCon大会上详细介绍了他们在Swiss Table上的工作：

目前，Swiss Table已被应用于多种编程语言，包括C++ Abseil库的flat_hash_map(可替换std::unordered_map)、Rust标准库Hashmap的默认实现等。

Swiss Table的出色表现是字节工程师提出这一问题的直接原因。字节跳动作为国内使用Go语言较为广泛的大厂。据issue描述，Go map的CPU消耗约占服务总体开销的4%。其中，map的插入（mapassign）和访问（mapaccess）操作的CPU消耗几乎是1:1。大家可千万不能小看4%这个数字，以字节、Google这样大厂的体量，减少1%也意味着真金白银的大幅节省。

Swiss Table被视为解决这一问题的潜在方案。字节工程师初版实现的基准测试结果显示，与原实现相比，Swiss Table在查询、插入和删除操作上均提升了20%至50%的性能，尤其是在处理大hashmap时表现尤为突出；迭代性能提升了10%；内存使用减少了0%至25%，并且不再消耗额外内存。

这些显著的性能提升引起了Go编译器和运行时团队的关注，特别是当时负责该子团队的Austin Clements。在经过两年多的实验和评估后，Go团队成员Michael Pratt基于Swiss Table实现的internal/runtime/maps最终成为Go map的底层默认实现。

在本文中，我们将简单介绍Swiss Table这一高效的哈希表实现算法，并提前看一下Go map的Swiss Table实现。

在进入swiss table工作原理介绍之前，我们先来回顾一下当前Go map的实现(Go 1.23.x)。

1. Go map的当前实现

map，也称为映射，或字典，或哈希表，是和数组等一样的最常见的数据结构。实现map有两个关键的考量，一个是哈希函数(hash function)，另一个就是碰撞处理(collision handling)。hash函数是数学家的事情，这里不表。对于碰撞处理，在大学数据结构课程中，老师通常会介绍两种常见的处理方案：

开放寻址法(Open Addressing)

在发生哈希碰撞时，尝试在哈希表中寻找下一个可用的位置，如下图所示k3与k1的哈希值发生碰撞后，算法会尝试从k1的位置开始向后找到一个空闲的位置：

链式哈希法(拉链法, Chaining)

每个哈希桶(bucket)存储一个链表（或其他数据结构），所有哈希值相同的元素(比如k1和k3)都被存储在该链表中。

Go当前的map实现采用的就是链式哈希，当然是经过优化过的了。要了解Go map的实现，关键把握住下面几点：

编译器重写

我们在用户层代码中使用的map操作都会被Go编译器重写为对应的runtime的map操作，就如下面Go团队成员Keith Randall在GopherCon大会上讲解map实现原理的一个截图所示：

链式哈希

前面提过，Go map当前采用的是链式哈希的实现，一个map在内存中的结构大致如下：

来自Keith Randall的ppt截图

我们看到，一个map Header代表了一个map类型的实例，map header中存储了有关map的元数据(图中字段与当前实现可能有少许差异，毕竟那是几年前的一个片子了)，如：

- len: 当前map中键值对的数量。
- bucket array: 存储数据的bucket数组，可以对比前面的链式哈希的原理图进行理解，不过不同的是，Go map中每个bucket本身就可以存储多个键值对，而不是指向一个键值对的链表。
- hash seed: 用于哈希计算的种子，用于分散数据并提高安全性。

通常一个bucket可以存储8个键值对，这些键值对是根据键的哈希值分配到对应的bucket中。

注：在《Go语言第一课》专栏中，有关于Go map工作原理的系统说明，感兴趣的童鞋可以看看。

溢出桶(overflow bucket)

每个bucket后面还会有Overflow Bucket。当一个bucket中的数据超出容量时，会创建overflow bucket来存储多余的数据。这样可以避免直接扩展bucket数组，节省内存空间。但如果出现过多的overflow bucket，性能就会下降。

“蚂蚁搬家”式的扩容

当map中出现过多overflow bucket而导致性能下降时，我们就要考虑map bucket扩容的事儿了，以始终保证map的操作性能在一个合理的范围。是否扩容由一个名为load factor的参数所控制。load factor是元素数量与bucket数量的比值，比值越高，map的读写性能越差。目前Go map采用了一个经验值来确定是否要扩容，即load factor = 6.5。当load factor超过这个值时，就会触发扩容。所谓扩容就是增大bucket数量(当前实现为增大一倍数量)，减少碰撞，让每个bucket中存放的element数量降下来。

扩容需要对存量element做rehash，在元素数量较多的情况下，“一次性”的完成桶的扩容会造成map操作延迟“突增”，无法满足一些业务场景的要求，因此Go map采用“增量”扩容的方式，即在访问和插入数据时，“蚂蚁搬家”式的做点搬移元素的操作，直到所有元素完成搬移。

Go map的当前实现应该可以适合大多数的场合，但依然有一些性能和延迟敏感的业务场景觉得Go map不够快，另外一个常被诟病的就是当前实现的桶扩容后就不再缩容(shrink)了，这会给内存带来压力。

来自issue 20135的截图

下面我们再来看看swiss table的结构和工作原理。

2. Swiss table的工作原理

就像前面提到的，Swiss table并非来自某个大学或研究机构的论文，而是来自Google工程师在工程领域的”最佳实践”，因此关于Swiss table的主要资料都来自Google的开源C++ library Abseil以及开发者的演讲视频。在Abseil库中，它是flat_hash_map、flat_hash_set、node_hash_map以及node_hash_set等数据结构的底层实现，并且Swiss table的实现在2018年9月正式开源。

和Go map当前实现不同，Swiss table使用的不是拉链法，而是开放寻址，但并非传统的方案。下面是根据公开资源画出的一个Swiss table的逻辑结构图(注意：并非真实内存布局)：

如果用一个式子来表示Swiss table，我们可以用：

A swiss table = N * (metdata array + slots array)

我们看到：swiss table将所谓的桶（这里叫slot）分为多个group，每个group中有16个slot，这也是swiss table的创新，即将开放寻址方法中的probing(探测key碰撞后下一个可用的位置(slot))放到一个16个slot的group中进行，这样的好处是可以通过一个SIMD指令并行探测16个slot，这种方法也被称为Group Probing。

在上图中，我们看到一个Group由metadata和16个slot组成。metadata中存储的是元数据，而slot中存储的是元素(key和value)。Group probling主要是基于metadata实现的，Google工程师的演讲有对group probing实现的细节描述。

当我们向swiss table插入一个元素或是查找一个元素时，swiss table会通过hash函数对key进行求值，结果是一个8字节(64bit)的数。和Go map的当前实现一样，这个哈希值的不同bit功用不同，下图是一个来自abseil官网的示例：

哈希值的高57bit被称为H1，低7bit被称为H2。前者用于标识该元素在Group内的索引，查找和插入时都需要它。后者将被用于该元素的元数据，放在metadata中存储，用于快速的group probing之用，也被称为哈希指纹。

每个Group的metadata也是一个16字节数组，每个字节对应一个slot，是该slot的控制字节。这个字节的8个bit位的组成如下：

图来自abseil库官网

metadata中的控制字节有三个状态：

最高位为1，其余全零为空闲状态(Empty)，即对应的slot尚未曾被任何element占据过；
最高位为0，后7位为哈希指纹(H2)，为对应的slot当前已经有element占据的已使用状态；
最高位为1，其他位为1111110的，为对应的slot为已删除状态，后续可以被继续使用。

下面是Abseil开发者演进slide中的一个针对swiss table的迭代逻辑：

通过这幅图可以看出H1的作用。不过这里通过pos = pos + 1进行probing（探测）显然是不高效的！metadata之所以设计为如此，并保存了插入元素的哈希指纹就是为了实现高效的probing，下图演示了基于key的hash值的H2指纹通过SIMD指令从16个位置中快速得到匹配的pos的过程：

虽然有两个匹配项，但这个过程就像“布隆过滤器”一样，快速排除了不可能的匹配项，减少了不必要的内存访问。

由此也可以看到：swiss table的16个条目的分组大小不是随意选择的，而是基于SSE2寄存器长度(128bit, 16bytes)和现代CPU的缓存行大小(64字节)优化的，保证了一个Group的控制字节能被单次SIMD指令处理。

此外swiss table也是通过load factor来判定是否需要对哈希表进行扩容，一旦扩容，swiss table通常是会将group数量增加一倍，然后重新计算当前所有元素在新groups中的新位置(rehash)，这个过程是有一定开销的。如果不做优化，当表中元素数量较多时，这个过程会导致操作延迟增加。

最后，虽然多数情况是在group内做probing，但当元素插入时，如果当前Group已满，就必须探测到下一个Group，并将元素插入到下一个Group。这样，在该元素的查找操作中，probing也会跨group进行。

到这里，我们已经粗略了解了swiss table的工作原理，那么Go tip对swiss table当前的实现又是怎样的呢？我们下面就来看看。

3. Go tip版本当前的实现

Go tip版本基于swiss table的实现在https://github.com/golang/go/blob/master/src/internal/runtime/maps下。

由于Go map是原生类型，且有了第一版实现，考虑到Go1兼容性，新版基于swiss table的实现也要继承已有的语义约束。同时，也要尽量避免swiss table自身的短板，Go团队在swiss table之上做了局部改进。比如为了将扩容带来的开销降到最低，Go引入了多table的设计，以支持渐进式扩容。也就是说一个map实际上是多个swiss table，而不是像上面说的一个map就是一个swiss table。每个table拥有自己的load factor，可以独立扩容(table的扩容是一次性扩容)，这样就可以将扩容的开销从全部数据变为局部少量数据，减少扩容带来的影响。

Go swiss-table based map的逻辑结构大致如下：

我们可以看出与C++ swisstable的最直观不同之处除了有多个table外，每个group包含8个slot和一个control word，而不是16个slot。此外，Go使用了二次探测(quadratic probing), 探测序列必须以空slot结束。

为了实现渐进式扩容，数据分散在多个table中；单个table容量有上限(maxTableCapacity)，超过上限时分裂成两个table；使用可扩展哈希(extendible hashing)根据hash高位选择table，且每个table可以独立增长。

Go使用Directory管理多个table，Directory是Table的数组，大小为2^globalDepth。如果globalDepth=2，那Directory最多有4个表，分为0×00、0×01、0×10、0×11。Go通过key的hash值的前globalDepth个bit来选择table。这是一种“extendible hashing”，这是一种动态哈希技术，其核心特点是通过动态调整使用的哈希位数(比如上面提到的globalDepth)来实现渐进式扩容。比如：初始可能只用1位哈希值来区分，需要时可以扩展到用2位，再需要时可以扩展到用3位，以此类推。

举个例子，假设我们用二进制表示哈希值的高位，来看一个渐进式扩容的过程：

初始状态 (Global Depth = 1):

directory
hash前缀  指向的table
0*** --> table1 (Local Depth = 1)
1*** --> table2 (Local Depth = 1)

当table1满了需要分裂时，增加一位哈希值 (Global Depth = 2):

directory
hash前缀  指向的table
00** --> table3 (Local Depth = 2)  // 由table1扩容而成
01** --> table4 (Local Depth = 2)  // 由table1扩容而成
10** --> table2 (Local Depth = 1)
11** --> table2 (Local Depth = 1)  // 复用table2因为它的Local Depth还是1

如果table2也满了，需要分裂：

directory
hash前缀  指向的table
00** --> table3 (Local Depth = 2)
01** --> table4 (Local Depth = 2)
10** --> table5 (Local Depth = 2) // 由table2扩容而成
11** --> table6 (Local Depth = 2) // 由table2扩容而成

通过extendible hashing实现的渐进式扩容，每次只处理一部分数据，扩容过程对其他操作影响小，空间利用更灵活。

对于新版go map实现而言，单个Table达到负载因子阈值时触发Table扩容。当需要分裂的Table的localDepth等于map的globalDepth时触发Directory扩容，这就好理解了。

除此之外，Go版本对small map也有特定优化，比如少量元素(<=8)时直接使用单个group，避免或尽量降低swiss table天生在少量元素情况下的性能回退问题。

更多实现细节，大家可以自行阅读https://github.com/golang/go/blob/master/src/internal/runtime/maps/下的Go源码进行理解。

注：目前swiss table版的go map依然还未最终定型，并且后续还会有各种优化加入，这里只是对当前的实现(2024.11.10)做概略介绍，不代表以后的map实现与上述思路完全一致。

4. Benchmark

目前gotip版本中GOEXPERIMENT=swissmap默认已经打开，我们直接用gotip版本即可体验基于swiss table实现的map。

字节工程师zhangyunhao的gomapbench repo提供了对map的性能基准测试代码，不过这个基准测试太多，我大幅简化了一下，只使用Int64，并只测试了元素个数分别为12、256和8192时的情况。

注：我基于Centos 7.9，使用Go 1.23.0和gotip(devel go1.24-84e58c8 linux/amd64)跑的benchmark。

// 在experiments/swiss-table-map/mapbenchmark目录下
$go test -run='^$' -timeout=10h -bench=. -count=10 > origin-map.txt
$GOEXPERIMENT=swissmap gotip test -run='^$' -timeout=10h -bench=. -count=10 > swiss-table-map.txt
$benchstat origin-map.txt swiss-table-map.txt > result.txt

注：gotip版本的安装请参考《Go语言第一课》专栏的第3讲。benchstat安装命令为go install golang.org/x/perf/cmd/benchstat@latest

下面是result.txt中的结果：

goos: linux
goarch: amd64
pkg: demo
cpu: Intel(R) Xeon(R) Platinum
                                  │ origin-map.txt │         swiss-table-map.txt          │
                                  │     sec/op     │    sec/op     vs base                │
MapIter/Int/12-8                      179.7n ± 10%   190.6n ±  4%        ~ (p=0.436 n=10)
MapIter/Int/256-8                     4.328µ ±  5%   3.748µ ±  1%  -13.40% (p=0.000 n=10)
MapIter/Int/8192-8                    137.3µ ±  1%   123.6µ ±  1%   -9.95% (p=0.000 n=10)
MapAccessHit/Int64/12-8               10.12n ±  2%   10.68n ± 14%   +5.64% (p=0.000 n=10)
MapAccessHit/Int64/256-8              10.29n ±  3%   11.29n ±  1%   +9.77% (p=0.000 n=10)
MapAccessHit/Int64/8192-8             25.99n ±  1%   14.93n ±  1%  -42.57% (p=0.000 n=10)
MapAccessMiss/Int64/12-8              12.39n ± 88%   20.99n ± 50%        ~ (p=0.669 n=10)
MapAccessMiss/Int64/256-8             13.12n ±  6%   11.34n ±  7%  -13.56% (p=0.000 n=10)
MapAccessMiss/Int64/8192-8            15.71n ±  1%   14.03n ±  1%  -10.66% (p=0.000 n=10)
MapAssignGrow/Int64/12-8              607.1n ±  2%   622.6n ±  2%   +2.54% (p=0.000 n=10)
MapAssignGrow/Int64/256-8             25.98µ ±  3%   23.22µ ±  1%  -10.64% (p=0.000 n=10)
MapAssignGrow/Int64/8192-8            792.3µ ±  1%   844.1µ ±  1%   +6.54% (p=0.000 n=10)
MapAssignPreAllocate/Int64/12-8       450.2n ±  2%   409.2n ±  1%   -9.11% (p=0.000 n=10)
MapAssignPreAllocate/Int64/256-8     10.412µ ±  1%   6.055µ ±  2%  -41.84% (p=0.000 n=10)
MapAssignPreAllocate/Int64/8192-8     342.4µ ±  1%   232.6µ ±  2%  -32.05% (p=0.000 n=10)
MapAssignReuse/Int64/12-8             374.2n ±  1%   235.4n ±  2%  -37.07% (p=0.000 n=10)
MapAssignReuse/Int64/256-8            8.737µ ±  1%   4.716µ ±  4%  -46.03% (p=0.000 n=10)
MapAssignReuse/Int64/8192-8           296.4µ ±  1%   181.0µ ±  1%  -38.93% (p=0.000 n=10)
geomean                               1.159µ         984.2n        -15.11%

我们看到了除了少数测试项有不足外(比如MapAssignGrow以及一些元素数量少的情况下)，大多数测试项中，新版基于swiss table的map的性能都有大幅提升，有些甚至接近50%！

5. 小结

本文探讨了Go语言中的map实现的重塑，即引入Swiss Table这一高效哈希表结构的背景与优势。Swiss Table由Google工程师开发，旨在优化内存使用和提升性能，解决了传统哈希表在高负载情况下的性能瓶颈。通过对比现有的链式哈希实现，Swiss Table展示了在查询、插入和删除操作上显著提高的性能，尤其是在处理大规模数据时。

经过两年多的实验与评估，Go团队决定将Swiss Table作为Go map的底层实现，预计将在Go 1.24中正式落地。新的实现不仅承继了原有的语义约束，还通过引入多表和渐进式扩容的设计，进一步优化了扩容过程的性能。尽管当前实现仍在完善中，但Swiss Table的引入无疑为Go语言的性能提升提供了新的可能性，并为未来进一步优化奠定了基础。

对于那些因Go引入自定义iterator而批评Go团队的Gopher来说，这个Go map的重塑无疑会很对他们的胃口。

本文涉及的源码可以在这里下载。

6. 参考资料

runtime: use SwissTable – https://github.com/golang/go/issues/54766
swiss table benchmark result – https://gist.github.com/aclements/9fb32ac0a287d2ff360f1bc166cdf4b8
Swisstable, a Quick and Dirty Description – https://faultlore.com/blah/hashbrown-tldr/
Swiss Tables Design Notes – https://abseil.io/about/design/swisstables
Designing a Fast, Efficient, Cache-friendly Hash Table, Step by Step – https://www.youtube.com/watch?v=ncHmEUmJZf4
Abseil’s Open Source Hashtables: 2 Years In – https://www.youtube.com/watch?v=JZE3_0qvrMg
Swiss Tables and absl::Hash – https://abseil.io/blog/20180927-swisstables
SwissMap: A smaller, faster Golang Hash Table – https://www.dolthub.com/blog/2023-03-28-swiss-map/
What is a Hash Map? – https://www.freecodecamp.org/news/what-is-a-hash-map/
Inside the Map Implementation – https://www.youtube.com/watch?v=Tl7mi9QmLns

Gopher部落知识星球在2024年将继续致力于打造一个高品质的Go语言学习和交流平台。我们将继续提供优质的Go技术文章首发和阅读体验。同时，我们也会加强代码质量和最佳实践的分享，包括如何编写简洁、可读、可测试的Go代码。此外，我们还会加强星友之间的交流和互动。欢迎大家踊跃提问，分享心得，讨论技术。我会在第一时间进行解答和交流。我衷心希望Gopher部落可以成为大家学习、进步、交流的港湾。让我相聚在Gopher部落，享受coding的快乐! 欢迎大家踊跃加入！

img{512x368}

著名云主机服务厂商DigitalOcean发布最新的主机计划，入门级Droplet配置升级为：1 core CPU、1G内存、25G高速SSD，价格5$/月。有使用DigitalOcean需求的朋友，可以打开这个链接地址：https://m.do.co/c/bff6eed92687 开启你的DO主机之路。

Gopher Daily(Gopher每日新闻) – https://gopherdaily.tonybai.com

我的联系方式：

微博(暂不可用)：https://weibo.com/bigwhite20xx
微博2：https://weibo.com/u/6484441286
博客：tonybai.com
github: https://github.com/bigwhite
Gopher Daily归档 – https://github.com/bigwhite/gopherdaily
Gopher Daily Feed订阅 – https://gopherdaily.tonybai.com/feed

商务合作方式：撰稿、出书、培训、在线课程、合伙创业、咨询、广告合作。

构建无密码认证：passkey入门与Go实现

十一月 1, 2024
0 条评论

本文永久链接 – https://tonybai.com/2024/11/01/introduction-to-passkey

传统的密码认证一直以来都是数字时代的主流身份验证方式。然而，用户常常选择易记的弱密码并重复使用，导致账号易受攻击。密码泄露、钓鱼攻击等安全问题层出不穷，超过80%的数据泄露与密码相关。

截图来自FIDO联盟官网

与此同时，频繁的密码管理和忘记密码情况严重影响用户体验。服务商在安全保存用户密码方面的责任也增加了系统建设和维护的成本。为了应对这些问题，科技行业开始积极探索无密码认证的方法。

无密码认证利用设备生物识别、硬件加密和其他更安全的验证手段，提供了更安全的登录体验。在Thoughtworks最新一期（第31期）技术雷达文档中，一种名为passkey的无密码认证技术被列入“试验” 象限，许多读者可能在github或其他支持passkey的站点和应用中使用过这一技术了。

Passkey是FIDO联盟(Fast IDentity Online)提出的一种无密码认证解决方案。FIDO联盟是一个开放的行业协会，其核心使命是减少世界对密码的依赖。联盟成员包括众多知名的科技公司和组织，如Google、微软、Apple、Amazon等，致力于定义一套开放、可扩展、可互操作的机制，以降低用户和设备身份验证时对密码的依赖。

Passkey是FIDO联盟的首个无密码身份认证凭据方案，支持用户通过与解锁手机、平板或计算机相同的方式（如生物识别(比如屏幕指纹、面部识别等)、PIN码或图案）登录应用程序和网站。目前许多主流设备、操作系统原生应用、浏览器和站点都支持passkey技术(如下图)，这使得passkey技术在未来的无密码认证认证领域展现出巨大的潜力。

图来自passkeys.dev(截至20241026)

在这篇文章中，我将对passkey技术进行入门介绍，并通过Go实现一个简单的示例供大家参考。

1. passkey的工作原理

通过上面的介绍，我们大致知道了passkey是密码的替代品，一旦使用了passkey，我们登录网站时就无需再输入密码，用于网站对你的身份进行验证的passkey存储在你的设备本地，你顶多只需通过本地设备的生物识别(比如指纹、人脸或图案密码等)进行一次解锁即可。

从技术本质来说，paaskey就是“免密登录服务器”方案在Web服务和终端App领域的应用。没错！passkey就是基于非对称加密实现的一种无密码认证技术。下图展示了Bob这个用户登录不同Web服务时使用不同passkey的情景：

如果你熟悉非对称加密的运作原理，你就可以立即get到passkey的工作原理。

注：在《Go语言精进之路：从新手到高手的编程思想、方法和技巧》的第51条“使用net/http包实现安全通信”中有对非对称加密的全面系统讲解以及示例说明。如果你不是很熟悉，可以看一下我的这本书中的内容。

以上图中的Web Service1为例，用户Bob在注册时会在其自己的设备(比如电脑)上创建一对私钥与公钥，比如Bob的bob-ws1-private key和bob-ws1-public key，私钥会保存在Bob的设备上，而并不需要保密的公钥则会发送给Web Service1保存。之后，Web Service1对Bob进行身份验证的时候，只需发送一块数据给Bob设备上的应用(通常是浏览器)，应用会申请使用Bob的私钥，这个过程可能需要bob输入设备的用户密码或使用生物识别（比如指纹）来授权。使用Bob的私钥对这块数据进行签名后，发回Web Service1，后者通过Bob保存在服务器上的公钥对这块签名后的数据进行验签，验签通过，则Bob的身份验证就通过了！当然这只是基本原理，还有很多场景、交互和技术细节，比如支持在网吧等公共计算机上借助个人的其他设备(比如手机)进行基于passkey的的身份验证等，这些需要进一步阅读相关规范。更多原理细节我们也会在接下来的内容中详细说明。

不过，在进一步了解原理之前，我们先来了解一下paaskey与FIDO、webauthn之间的关系。

FIDO2是一个开放的认证标准框架，旨在取代传统密码认证。它包含WebAuthn（由W3C提供的WebAPI规范）和CTAP（客户端到认证器的协议），即客户端设备和外部认证器的通信标准。FIDO2的主要目标是增强网络安全性，支持无需密码的安全登录方式。

WebAuthn是FIDO2的WebAPI组件，定义了应用如何在网页上与浏览器协作，以支持基于公钥的认证方式。它允许浏览器和Web应用访问用户设备上的身份验证器（如指纹传感器或USB密钥），并进行认证交互。WebAuthn作为Web标准，得到了大多数现代浏览器的支持。

Passkey是对FIDO2标准的应用，以实现无密码认证。在技术栈上，Passkey利用WebAuthn和CTAP来构建实际应用体验，从而让用户在支持FIDO2的Web应用中享受无密码登录的便捷。这三者共同实现了现代无密码身份认证的完整生态体系。

下面我们通过一个序列图具体了解一下paaskey的工作原理：

上图展示了Passkey的工作流程，包括注册和认证两个主要流程。

在passkey（即基于WebAuthn的非密码认证机制）中，有三个主要的实体：

浏览器(客户端)：提供 WebAuthn API
服务器(即规范中的依赖方(Relying Party))：验证用户身份
认证器(Authenticator)：生成和存储密钥对（认证器可以是设备内置的，如TouchID、FaceID，或外部硬件如YubiKey）。

我们先来看看注册流程。

用户输入用户名并触发注册流程，浏览器向服务器请求注册选项，服务器生成随机挑战（challenge）并创建注册选项。

浏览器调用WebAuthn API(navigator.credentials.create)，操作系统检查可用的认证器，并根据认证器类型调用相应的系统API。认证器请求用户验证（如需要），系统根据请求的用户验证级别来决定验证方式。验证级别包括无需验证(none)、隐式验证(silent，比如设备已解锁，使用之前的验证结果)以及必须验证（Required）。如果是必须验证，系统会显示验证提示（密码/生物识别/PIN等）。

用户提供身份验证信息后，认证器会生成新的公私钥对，并将私钥安全存储在认证器中，公钥和其他凭证数据(私钥签名后的挑战数据)返回给浏览器。浏览器将公钥和其他凭证发送给服务器，服务器验证凭证(通过公钥验签)并存储公钥，注册完成。

接下来，我们再来看认证流程。

当用户输入用户名并触发登录后，浏览器会向服务器请求认证选项，服务器生成新的挑战并返回认证选项。

浏览器调用WebAuthn API (navigator.credentials.get)，认证器使用私钥对挑战进行签名，并返回签名和其他断言数据给浏览器。

浏览器将断言发送给服务器，服务器使用存储的公钥验证签名，认证完成。

我们看到在整个注册和身份验证流程中，用户都无需记忆复杂的密码，机密信息（比如传统的密码）也无需传递给服务器保存，而公钥本身就是随意公开分发的，服务端甚至都无需对其进行任何加密处理。由此可以看到：passkey既提供了更好的安全性，又提供了更好的用户体验，是传统密码认证的理想替代方案之一。

注：使用另一个设备进行身份验证的流程，大家可以自行阅读passkey相关规范了解。

了解了原理之后，我们再来看一个简单的示例，直观地看看如何实现基于passkey的身份认证。

2. passkey身份认证示例

我们使用Go实现一个最简单的基于passkey进行注册和身份验证的示例。在这个示例里，我们将使用webauthn官方推荐的Go包：go-webauthn/webauthn来实现服务端对passkey登录的支持。

注：本示例的工作环境为Go 1.23.0、macOS和Edge浏览器。

这个示例的文件布局如下：

// intro-to-passkey/demo
$tree -F .
.
├── go.mod
├── go.sum
├── main.go
└── static/
    └── index.html

首先我们通过一个静态文件服务器提供了前端首页，并注册了4个API端点用于处理Passkey注册和认证：

// intro-to-passkey/demo/main.go
func main() {
    // 静态文件服务
    http.Handle("/", http.FileServer(http.Dir("static")))

    // API 路由
    http.HandleFunc("/api/register/begin", handleBeginRegistration)
    http.HandleFunc("/api/register/finish", handleFinishRegistration)
    http.HandleFunc("/api/login/begin", handleBeginLogin)
    http.HandleFunc("/api/login/finish", handleFinishLogin)

    log.Println("Server running on http://localhost:8080")
    log.Fatal(http.ListenAndServe(":8080", nil))
}

关键的passkey配置在init函数中：

func init() {
    var err error
    webAuthn, err = webauthn.New(&webauthn.Config{
        RPDisplayName: "Passkey Demo",                    // Relying Party Display Name
        RPID:          "localhost",                       // Relying Party ID
        RPOrigins:     []string{"http://localhost:8080"}, //允许的源
    })
    if err != nil {
        log.Fatal(err)
    }
    userDB = NewUserDB() // 初始化内存用户数据库
}

运行该go程序后，打开localhost:8080，我们将看到下面页面：

接下来，我们先来注册一个用户的passkey。在注册输入框中输入”tonybai”，点击“注册”，浏览器会弹出下面对话框，提醒用户将为localhost创建密钥：

点击“继续”，本地os会弹出身份验证对话框：

输入你的os登录密码，便可继续注册过程。如果注册ok，页面会显示下面“注册成功”字样：

在服务器后端，上述的注册过程是由两个handler共同完成的，这也是webauthn规范确定的流程，大家可以结合上面的序列图一起看。

首先是处理/api/register/begin的handleBeginRegistration，它的大致逻辑如下：

func handleBeginRegistration(w http.ResponseWriter, r *http.Request) {
    // 1. 验证用户名是否已存在
    if _, exists := userDB.users[data.Username]; exists {
        http.Error(w, "User already exists", http.StatusBadRequest)
        return
    }

    // 2. 创建新用户
    user := &User{
        ID:          []byte(data.Username),
        Name:        data.Username,
        DisplayName: data.Username,
    }
    userDB.users[data.Username] = user

    // 3. 生成注册选项和会话数据
    options, sessionData, err := webAuthn.BeginRegistration(user)

    // 4. 存储会话数据
    sessionID := storeSession(sessionData)
    http.SetCookie(w, &http.Cookie{
        Name:     "registration_session",
        Value:    sessionID,
        Path:     "/",
        MaxAge:   300,
        HttpOnly: true,
    })

    // 5. 返回注册选项给客户端
    json.NewEncoder(w).Encode(options)
}

注意：这段代码中的session与传统Web应用中用于跟踪用户登录状态的session不同。这种session机制是WebAuthn协议的一部分，用于确保认证流程的安全性：

防止重放攻击：每次认证都会生成新的挑战
确保认证操作的完整性：开始认证和完成认证必须使用相同的session数据
时效性控制：认证过程必须在有限时间内完成(上面示例中的有效期为5分钟)

所以这里的session更像是一个”挑战-响应”认证过程中的临时状态存储，而不是用来维持用户登录状态的传统session。用户的登录状态管理应该是在这个认证系统之上另外实现的，比如使用JWT token或传统的session机制。

handleFinishRegistration用于处理客户端发到/api/register/finish的完成注册请求，它的逻辑大致如下：

func handleFinishRegistration(w http.ResponseWriter, r *http.Request) {
    // 1. 获取并验证会话
    sessionData, ok := getSession(cookie.Value)
    if !ok {
        http.Error(w, "Invalid session", http.StatusBadRequest)
        return
    }

    // 2. 获取用户信息
    username := string(sessionData.UserID)
    user := userDB.users[username]

    // 3. 验证并完成注册
    credential, err := webAuthn.FinishRegistration(user, *sessionData, r)

    // 4. 保存凭证
    userDB.Lock()
    user.Credentials = append(user.Credentials, *credential)
    userDB.Unlock()

    // 5. 清理会话
    delete(sessionStore, cookie.Value)
}

注册passkey后，我们就可以来基于passkey进行登录了！服务端会使用passkey对用户进行身份验证。

我们在登录输入框中输入”tonybai”，然后点击”Passkey登录”，本地os会弹出身份验证对话框：

输入os登录密码后，便可继续身份验证过程，如果服务端身份验证ok，页面会显示下面“登录成功”字样：

如果在登录输入框中输入一个未曾注册过的用户名，则服务器会验证失败，页面会显示如下错误：

和注册过程一样，上述的验证过程也是由两个handler共同完成的，这也是webauthn规范确定的流程。

首先是处理/api/login/begin的handleBeginLogin，它的大致逻辑如下：

func handleBeginLogin(w http.ResponseWriter, r *http.Request) {
    // 1. 验证用户是否存在
    user, ok := userDB.users[data.Username]
    if !ok {
        http.Error(w, "User not found", http.StatusNotFound)
        return
    }

    // 2. 生成认证选项和会话数据
    options, sessionData, err := webAuthn.BeginLogin(user)

    // 3. 存储会话数据
    sessionID := storeSession(sessionData)
    http.SetCookie(w, &http.Cookie{
        Name:     "login_session",
        Value:    sessionID,
        Path:     "/",
        MaxAge:   300,
        HttpOnly: true,
    })

    // 4. 返回认证选项给客户端
    json.NewEncoder(w).Encode(options)
}

之后，是handleFinishLogin处理的来自客户端到/api/login/finish的请求，以完成登录流程：

func handleFinishLogin(w http.ResponseWriter, r *http.Request) {
    // 1. 获取并验证会话
    sessionData, ok := getSession(cookie.Value)
    if !ok {
        http.Error(w, "Invalid session", http.StatusBadRequest)
        return
    }

    // 2. 获取用户信息
    username := string(sessionData.UserID)
    user := userDB.users[username]

    // 3. 验证并完成登录
    _, err = webAuthn.FinishLogin(user, *sessionData, r)

    // 4. 清理会话
    delete(sessionStore, cookie.Value)
}

我们看到注册和登录都采用两步验证流程，每个流程都包含开始和完成两个步骤，同时使用会话保持认证状态的连续性。

整个示例的前端基本由js代码完成：

<!DOCTYPE html>
<html>
<head>
    <title>Passkey Demo</title>
    <style>
        .container {
            margin: 20px;
            padding: 20px;
            border: 1px solid #ccc;
        }
        .form-group {
            margin: 10px 0;
        }
        #status {
            margin-top: 20px;
            padding: 10px;
        }
        .error {
            color: red;
        }
        .success {
            color: green;
        }
    </style>
</head>
<body>
    <div class="container">
        <h2>注册</h2>
        <div class="form-group">
            <input type="text" id="registerUsername" placeholder="用户名">
            <button onclick="register()">注册 Passkey</button>
        </div>
    </div>

    <div class="container">
        <h2>登录</h2>
        <div class="form-group">
            <input type="text" id="loginUsername" placeholder="用户名">
            <button onclick="login()">Passkey 登录</button>
        </div>
    </div>

    <div id="status"></div>

    <script>
        // 工具函数：将 ArrayBuffer 转换为 Base64URL 字符串
        function bufferToBase64URL(buffer) {
            const bytes = new Uint8Array(buffer);
            let str = '';
            for (const byte of bytes) {
                str += String.fromCharCode(byte);
            }
            return btoa(str)
                .replace(/\+/g, '-')
                .replace(/\//g, '_')
                .replace(/=/g, '');
        }

        // 工具函数：将 Base64URL 字符串转换为 ArrayBuffer
        function base64URLToBuffer(base64URL) {
            if (!base64URL) {
                throw new Error('Empty base64URL string');
            }
            const base64 = base64URL.replace(/-/g, '+').replace(/_/g, '/');
            const padLen = (4 - (base64.length % 4)) % 4;
            const padded = base64.padEnd(base64.length + padLen, '=');
            const binary = atob(padded);
            const buffer = new ArrayBuffer(binary.length);
            const bytes = new Uint8Array(buffer);
            for (let i = 0; i < binary.length; i++) {
                bytes[i] = binary.charCodeAt(i);
            }
            return buffer;
        }

        function showStatus(message, isError = false) {
            const status = document.getElementById('status');
            status.textContent = message;
            status.className = isError ? 'error' : 'success';
        }

        // 开始注册
        async function startRegistration(username) {
            try {
                // 1. 从服务器获取注册选项
                const response = await fetch('/api/register/begin', {
                    method: 'POST',
                    headers: {
                        'Content-Type': 'application/json',
                    },
                    body: JSON.stringify({ username }),
                });

                if (!response.ok) {
                    throw new Error(`Server error: ${response.status}`);
                }

                const responseData = await response.json();

                // 确保我们使用的是 publicKey 对象
                const options = responseData.publicKey;
                if (!options) {
                    throw new Error('Invalid server response: missing publicKey');
                }

                // 2. 解码 challenge
                options.challenge = base64URLToBuffer(options.challenge);

                // 3. 解码 user.id
                if (options.user && options.user.id) {
                    options.user.id = base64URLToBuffer(options.user.id);
                }

                console.log('Processed options:', options); // 调试输出

                // 4. 创建凭证
                const credential = await navigator.credentials.create({
                    publicKey: options
                });

                // 5. 准备发送到服务器的数据
                const registrationData = {
                    id: credential.id,
                    rawId: bufferToBase64URL(credential.rawId),
                    type: credential.type,
                    response: {
                        attestationObject: bufferToBase64URL(credential.response.attestationObject),
                        clientDataJSON: bufferToBase64URL(credential.response.clientDataJSON)
                    }
                };

                // 6. 发送注册数据到服务器
                const finishResponse = await fetch('/api/register/finish', {
                    method: 'POST',
                    headers: {
                        'Content-Type': 'application/json',
                    },
                    body: JSON.stringify(registrationData)
                });

                if (!finishResponse.ok) {
                    throw new Error(`Server error: ${finishResponse.status}`);
                }

                showStatus('注册成功！');
            } catch (error) {
                console.error('Registration error:', error);
                showStatus(`注册失败: ${error.message}`, true);
            }
        }

        // 开始登录
        async function startLogin(username) {
            try {
                // 1. 从服务器获取登录选项
                const response = await fetch('/api/login/begin', {
                    method: 'POST',
                    headers: {
                        'Content-Type': 'application/json',
                    },
                    body: JSON.stringify({ username }),
                });

                if (!response.ok) {
                    throw new Error(`Server error: ${response.status}`);
                }

                const responseData = await response.json();
                const options = responseData.publicKey;

                if (!options) {
                    throw new Error('Invalid server response: missing publicKey');
                }

                // 2. 解码 challenge
                options.challenge = base64URLToBuffer(options.challenge);

                // 3. 解码 allowCredentials
                if (options.allowCredentials) {
                    options.allowCredentials = options.allowCredentials.map(credential => ({
                        ...credential,
                        id: base64URLToBuffer(credential.id),
                    }));
                }

                // 4. 获取凭证
                const credential = await navigator.credentials.get({
                    publicKey: options
                });

                // 5. 准备发送到服务器的数据
                const loginData = {
                    id: credential.id,
                    rawId: bufferToBase64URL(credential.rawId),
                    type: credential.type,
                    response: {
                        authenticatorData: bufferToBase64URL(credential.response.authenticatorData),
                        clientDataJSON: bufferToBase64URL(credential.response.clientDataJSON),
                        signature: bufferToBase64URL(credential.response.signature),
                        userHandle: credential.response.userHandle ? bufferToBase64URL(credential.response.userHandle) : null
                    }
                };

                // 6. 发送登录数据到服务器
                const finishResponse = await fetch('/api/login/finish', {
                    method: 'POST',
                    headers: {
                        'Content-Type': 'application/json',
                    },
                    body: JSON.stringify(loginData)
                });

                if (!finishResponse.ok) {
                    throw new Error(`Server error: ${finishResponse.status}`);
                }

                showStatus('登录成功！');
            } catch (error) {
                console.error('Login error:', error);
                showStatus(`登录失败: ${error.message}`, true);
            }
        }

        // 注册按钮处理函数
        function register() {
            const username = document.getElementById('registerUsername').value;
            if (!username) {
                showStatus('请输入用户名', true);
                return;
            }
            startRegistration(username);
        }

        // 登录按钮处理函数
        function login() {
            const username = document.getElementById('loginUsername').value;
            if (!username) {
                showStatus('请输入用户名', true);
                return;
            }
            startLogin(username);
        }
    </script>
</body>
</html>

这段代码没有使用任何第三方库或框架，对js略知一二的读者想必也能看个七七八八。

综上，我们看到这个示例实现提供了完整的Passkey认证功能，但需要注意这是一个演示版本。在生产环境中，还需要考虑更多，比如数据的持久化存储、更完善的错误处理等。