实习每日记录

主要内容为 Go 在1.24之后所采用的新的 Map 底层数据结构 SwissTable 的原理记录。



Go 在2025年2月11日发布了新版本1.24.0，里面比较重大的更新就是**支持弱指针**和**将 map 的默认底层实现替换为 SwissTable**。后者是这篇记录的主题，前者稍微记录一下：

### 1 弱指针（weak 包）

> 官方文档：https://pkg.go.dev/weak

弱指针（weak pointer），是一个存在了很久的概念。它是一种特殊的指针类型，它可以指向一个对象，但是不会增加该对象的引用计数，也不会阻止 GC 来回收该对象。如果弱指针指向的对象被 GC 回收，那么获取值会得到 nil。它的主要作用，一来是能够**防止指针循环引用**，从而使 GC 无法回收内存，继而导致内存泄漏；二来利用弱指针不会影响 GC 这一点，可以更好地**手动控制对象的生命周期**（个人认为后者作用会更明显）。

### 2 在 SwissTable 之前

map，或者叫哈希表（目标是读写时间复杂度`O(1)`的键值对存储结构），都是由两个部分构成：哈希函数，存储结构。虽然理想中的哈希函数，是应该不存在哈希碰撞，并且哈希值的每一位出现概率都是均等的。但是这毕竟是理想，现实里，存储结构也要面对哈希碰撞的问题。在 SwissTable 之前，解决哈希碰撞的存储结构方案有这么两种（也是八股常客）：

- 开放定址法：如果将存储结构看作一个数组，值存在数组上（权且管这个位置叫 slot），那么在发生哈希碰撞后，就会已存在的值的存储位置向后寻找（按寻找的方式，还有其他的方法。特别地，向后寻找的被称为线性探测法），直到能够找到存储的 slot。
- 链表法：仍然将存储结构看作一个数组。在发生哈希碰撞后，所有发生哈希碰撞的值会以链表的形式存在对应的 slot 上。

> Go 在 SwissTable 之前，我认为 Map 使用的方式算是加强版的，混合了部分链表法思路的开放定址法，详见https://www.misaka19327.cc/post/104

### 3 SwissTable

SwissTable 首次被提出是在2017年的 CppCon 大会上，在2022年被字节提 issue，建议使用它作为 Map 的底层数据结构。

SwissTable 的核心思想仍然是**改进线性探测法**，只是将 slot 的关键信息提取出来作为元数据进行读写，比直接读取整个 slot 更快。

#### 3.1 结构

SwissTable 的结构如图：

![image.png](https://www.misaka19327.cc/static/img/ed26df924e0facc32487813af0ca8e6b.image.png)

（对实际内存进行简化，看个意思）

SwissTable 主要由两部分构成：Control Bytes 和对应的 slots 数组。其中，Control Bytes 的每个字节都对应后面的一个 slot，字节内部存储的值，一个是指示 slot 的状态，另外就是在 slot 有值时，存储其 hash 得来的特征值。

图里没有写出来的有两部分，一个是 Group。它不是一个具体的结构，而是由8（不支持 simd 指令的平台）/16（支持 simd 指令的平台）个连续的控制字节组成。按图中所得，对键进行哈希后得到的哈希值，前57位的值（偏移量）就用来决定 slot 位置，而 slot 对应的控制字节的位置之后的7/15个控制字节就是一个 Group。

另外一个是，按照上面的说明，当决定 slot 位置定到了 Control Bytes 的尾部时，对应的控制字节之后的控制字节们的数量可能不足以支撑一个 Group。所以，Control Bytes 尾部也会复制头部的信息。

:::info{title="simd 指令"}
单指令流多数据流（Single Instruction Multiple Data，SIMD）是一种采用一个控制器来控制多个处理器，同时对一组数据（又称“数据向量”）中的每一个分别执行相同的操作从而实现空间上的并行性的技术。
:::

#### 3.2 查

按照上面对 Group 概念的说明，可知一个键的哈希值是可以落到一个长为8/16的 Group 上的，之后就是怎么找到对应的 slot。如果不存在哈希碰撞，那皆大欢喜，第一个控制字节所对应的 slot 就是要找的值。如果存在哈希碰撞，按照线性探测法，应该是对 Group 中的每个控制字节所对应的 slot 都挨个取出来比较 key。但是 SwissTable 在这里做了优化。它利用了 simd 指令并行计算的特点，将特征值和16个控制字节同时进行比较，得到的16个字节再压缩为 uint32，直接取尾部0的数量，即可得到要找的 slot 的位置。如果当前 Group 没能找到值，那么会顺序移动到下一个 Group，再一次整体比较，直至找到对应值或到结束位。

![image.png](https://www.misaka19327.cc/static/img/12c86be7286e75219533ac875901eddb.image.png)

（H2 即为特征值）

事实上，SwissTable 会首先过滤掉特征值不同的控制字节，再利用上述的方法快速找到要检查的 slot 位置。如果检查完第一个 slot 发现 key 不对，那么就可以将 uint32 的结果的检查完的 slot 所对应的1用位运算置零，再次计算尾随0的数量，即可找到下一个要检查的 slot。

增删的步骤基本上和查是差不多的，都是按这个方法定 Group，如果 Group 已满/没找到就顺延到下一个 Group，直到找到空 slot/目标键值对，写入数据/释放数据，并且修改对应的控制字节。

#### 3.3 结束

我认为，SwissTable 能够和 Go 原来的 Map 拉开差距，主要有几个点：

1. SwissTable 利用这个 simd 指令，使得每次找数据的时候都是同时批量地找，比原来的 Map 在 bucket 里的 tophash 找快。并且用的是位运算，比等值比较快。当然，如果不支持 simd 指令，那么性能也会有所下降。
2. 内存紧凑，比起原来的 Map，同一哈希值下的 bucket 是链表组织（内存松散），能够提高缓存命中率（对 CPU 来说）。

> Go runtime 下，原来的 map.go 变成了 map_swiss.go 和 map_noswiss.go，原来的实现还保留着，应该是可以通过 go build 的参数使用原来的底层结构。只是 map_swiss.go 没看懂，不好看源码了，主要是我找不到它的 linkname 链接的目标是谁。

Go底层/特性解析 | 新Map - 关于 SwissTable

主要内容：该项目的目的，技术选型，表结构啥的。先随便写写，反正也不是很急。



### 1 综述

鉴于我目前算是终于找到实习了，并且按实习的时间来看，如果不加班的话我的空闲时间是固定的，所以我想要先启动这个项目。

该项目的起因是因为我之前每天手动去收集同人帖实在有点顶不住，而且收集的效果也略显不足：没法搜索，没法排序筛选，没法看赞量，没法自动更新。其实我寒假中想要利用 KMP 上线的那个增强版本的 wasm 网页就是这个原因的产物，但是那个框架问题太多、加载太慢、并且没有利用多平台的必要，因此只好放弃。

经过上一次的尝试之后，我决定一方面还是采用稳定的框架来做，另一方面是让用户也有能力去提交同人信息。这次我的目标是搭建一个前后端分离的网站，后端会自动获取新帖和点赞量，前端采用流行的框架，达成搜索筛选排序等等的效果。看看能不能在六月份之前上线。

主要技术栈就是后端的 Ktor，PostgreSQL，redis 三件套。其中两个我都不是很熟悉，原因么一方面是对 Kotlin 的偏向和对其后端方向的发展有所好奇，另一部分是想要通过这个项目来接触更多的技术栈。

前端我想用 react 试一下，主要是对 TypeScript 感兴趣。因为没人帮我，所以只能让 ChatGPT 来完成大部分代码，我再来试着改一改这样。

（这个系列主要记后端部分，前端部分会再开一个新的分类去记录）

### 2 目标功能

1. 针对贴吧，会自动获取新帖，刷新老帖子的点赞量。
2. 得有一个用户注册的系统，以防无限制提交同人信息。
3. 有一个审核的功能，经过管理员的确认信息才能上去。
4. 同人信息大致按表格的形式展现，提供搜索，按点赞量排序，按标签筛选，对同人信息进行标记和记录的功能。
5. 前端我想尽量还是统一风格去做。
6. 防大量请求，我看看能不能在 ngingx 做反向代理的时候加点时间限制。
7. 因为每天都有部分帖子产生，所以需要辨认这些帖子是否为同人帖。用户可以以自愿的形式做这部分任务，记录贡献条目数。
8. 加评论？加评论的话我怕域名申请过不去，这部分先保留吧，日后再看看能不能上。

### 3 表结构设计

首先得有一个同人信息表，它里面存着贴吧主题贴的信息，也存别的来源的同人链接，里面的结构大概是这样：

- 主键id，这个不用多说
- 标题
- 网页链接
- 类型，这个和后面的标签做一对一
- 是否为同人
- 点赞量，这个只针对贴吧主题帖，如果是别的来源的话先置0
- 创建主题帖时间

MakeineFanworksCollections | 记录1

记录开题阶段的想法，链接，数据什么的。



# 1 初步设想

这个毕业设计一共包括两套系统：

1. 针对个人、小型团队、家庭的类NAS系统

该系统的使用目标是在一个局域网内，为多人提供云端文件保存、备份和版本历史管理服务（可以通过 Nginx Proxy Manager等工具使其使用公网ip，使得该服务能够不局限在一个局域网内）。通过

该系统的主要功能：

- 将文件上传到云端，并且可以选择性地应用RAID策略进行备份。
- 可以通过加硬盘或者加服务器的方式进行横向扩展（？）。
- 关于文件管理，可以加tag和说明，可以构建虚拟路径，可以以用户手动上传的方式，进行文件的版本管理。
    - 特别的，针对视频、音频、图片，提供在线预览。
    - 针对markdown文档，提供在线编辑功能和查看文件版本详细改动的功能。
    - 针对图片，提供做为图床的功能。
 - 可以选择某些文件进行实时同步（网页端肯定是不能支持这个）

该系统的用户只分为两类：管理员和普通用户。

> 权限管理还没想好，想的是普通用户上传文件，该文件的所有权来自该用户。管理员可以读写该文件，但是对于其他普通用户的读写权限，只能由该文件的所有者控制。
> 
> 关于虚拟文件夹，目前想的是每个用户有自己的个人文件夹，在该文件夹下可以任意控制文件夹的新建和删除。除了个人文件夹，还有一个共有文件夹，所有用户都可以进行文件夹的新建和删除，管理员可以控制这一权限。


2. 为这个NAS系统提供外网访问能力的管理系统

该系统的主要功能：

- 系统1的所有用户，可以通过选中文件挂在这个系统下的方式，在公网进行访问。注意，这个系统主要的作用是类似生成短链接的功能，能够给用户一个入口，获取被选中的文件的最新版本。
- 该系统下不会保存文件，是通过和系统1通信的方式获取文件。

技术栈：语言是 Go，框架还没想好是单体服务还是微服务，再加上数据库两件套。客户端这边语言是 Kotlin，用的框架是 Kotlin Multiplatform 那一套和 Ktor，本地还会维护一个 SQLite 小数据库。

# 2 审题表

申报课题名称：基于Kotlin的中小型云端存储系统

课题简介和要求：

该系统由两部分组成：
1. 在内网生效的，针对家庭或中小型团队的云端存储系统。该系统的主要功能有：
    - 用户可以选择文件进行上传，系统会自动应用策略进行备份。支持通过增加硬盘或者增加服务器的方式进行横向扩展。
    - 用户可以通过虚拟路径和标签管理文件。每个文件保存其版本历史。
    - 针对Markdown文件，提供在线编辑功能和查看版本变化的功能。针对视频、音频、图片文件，提供在线预览功能。
    - 提供多平台客户端和网页端。针对客户端，用户可以选择一些文件进行实时同步。
    - 基于文件所有权的方式，进行权限管理。
2. 提供针对内网的云端文件的外网访问能力的管理系统。
    - 系统1可以有选择地和该系统进行通信。
    - 用户可以在系统1内选择一部分文件，通过该系统使其具备外网访问能力。

毕业设计 | 开题阶段记录

服务器常用命令速查，还有`docker`的一部分写法收集。



### 1 tmux

- 新建会话：`tmux new -s <session-name>`
- 分离会话：`tmux detach`
- 查看所有会话：`tmux ls`
- 进入会话：`tmux attach -t <session-name>`
- 销毁会话：`tmux kill-session -t <session-name>`
- 切换会话：`tmux switch -t <session-name>`
- 重命名会话：`tmux rename-session -t <old-name> <new-name>`

### 2 docker

- 构建镜像：`docker build -t <镜像名> .`（构建使用工作目录下的`DockerFile`）
- 导出镜像：`docker save -o <导出文件名> <镜像id>`
- 导入镜像：`docker load -i <导入文件名>`
- 删除镜像：`docker rmi <镜像id或镜像名>`
- 查看所有镜像：`docker images`
- 查看所有容器：`docker ps`
- 进入容器内部：`docker exec -it <容器名> <终端路径 一般是/bin/bash>`
- 停止容器：`docker stop <容器名>`
- 删除容器：`docker rm <容器id>`
- 在容器内运行镜像：`docker run -d -p <主机端口>:<容器端口> --name <容器名> <镜像名>`（端口映射可以有多个）
- 查看容器日志：`docker logs -f <容器名>`

### 3 docker 写法示例

``` docker
FROM ubuntu:24.04
LABEL authors="Misaka19327"

ENV LANG C.UTF-8
WORKDIR /usr/local/bin

RUN apt-get update

RUN apt-get -y install python3.12
RUN apt-get -y install python3-pip
RUN apt-get -y install vim wget

RUN pip3 install aiotieba --break-system-packages
RUN pip3 install aiofiles --break-system-packages

ENV LD_LIBRARY_PATH /usr/local/lib:$LD_LIBRARY_PATH

COPY main /usr/local/bin/main
COPY script.py /usr/local/bin/script.py
COPY sum_thread.csv /usr/local/bin/sum_thread.csv

RUN chmod +x /usr/local/bin/main
RUN chmod +x /usr/local/bin/script.py
RUN chmod +x /usr/local/bin/sum_thread.csv

EXPOSE 27945

CMD ["/usr/local/bin/main"]
```