主要内容：

1. WorkFlow 项目期望功能
2. WorkFlow 架构设计
3. WorkFlow 实现计划



### * 一些碎碎念

~~这是去年被搁置的一个项目，我现在想了想，决定把现在它拿出来重新做，作为我简历上的一个已上线的，有实际作用的大型项目。希望我能独自顺利地完成它。~~

~~该项目预期客户端主要技术栈是 Jetpack Compose，后端主要技术栈是 Go Http 三件套。如果有余裕的话倒是想折腾一下 Kotlin.js 看看能不能上前端。~~

### 1 WorkFlow 项目期望功能

一开始我对这个项目的预期是一个更高级的文件管理，为文件附加信息，使其更好地进行管理，版本迭代和云端同步。现在我想要对这个应用有更高的期望：我想要它变成一个工作流管理的应用。我设想中的工作流是这样构成的：

- 项目/任务
- 人员
- 资料

从这三方面进行引申，就有了该项目的大致的期望功能：

1. 项目列表，在这里是对下面三个模块的集成。不仅要对所有的参与的项目管理（增删改查），还能关联相关的要用到的文件和知识库，以及任务中关联到的人。在这里引入一个聊天功能。项目的基本信息由发起者编辑，要用到的文件和知识库可以被参与者编辑等等。
2. TODO 列表，这里就是仅对用户自身有效的，可以标记为关联到某一项目，可以加闹钟。
3. 联系人管理，这个没啥好说的。注意单人聊天的功能就不要加了。
4. 文件管理，包括对文件加 tag，加注释，版本管理等。
5. 知识库管理，主要是以 Json 方式进行可视化编辑，参考思维导图或者 Neo4j。该知识库可以选择是否公开，可公开的部分可以被任意用户查找并且下载为自己的知识库。

### 2 WorkFlow 结构设计

1. 该项目数据库是 SQLite，用 Room 作为 ORM 来读写数据。
2. 该项目的网络相关库是 OkHttp，Json 怎么存暂时还没想好。
3. 该项目设置相关的是放到 DataStore 中的。
4. 统一这些 IO 操作的是 Repository 层，大致是一个模块对应一个 Repository。
5. 在 Repository 层和页面层中间的是 ViewModel 层，它负责和页面进行数据的交互。所有的状态都在 ViewModel 中，并且提供方法给上层的页面的事件（比如点击按钮一类的）。一个页面对应一个 ViewModel。
6. 这些结构统一用 Hilt 进行依赖注入。

示例代码如下：

``` kotlin
// 先是 Repository 层 依赖更下层的 DAO 和 OkHttp 此处仅为示例
class TestRepository @Inject constructor (private val dao: FileEntityDAO) {

    suspend fun UpdateValueTest(value: Int) {
        withContext(Dispatchers.IO) {
            dao.getAllFile()
        }
    }
}

// 再是 ViewModel 层 向上提供状态和接口
@HiltViewModel
class TestViewModel @Inject constructor(private val repository: TestRepository) : ViewModel() {
    private val _data = MutableStateFlow<Int>(1)

    val data : StateFlow<Int> get() = _data

    fun updateTestData (value: Int) {
        _data.value = value

        viewModelScope.launch {
            repository.UpdateValueTest(value)
        }
    }
}

// 最后是视图层 这层把 ViewModel 放在 Activity 还是 单独的 Compose 组件里都行 我认为是放在单独成页面的 Compose 组件中比较好
@Composable
fun Greeting2(name: String, modifier: Modifier = Modifier) {
    val viewModel : TestViewModel = hiltViewModel()

    val data by viewModel.data.collectAsState()
    var editedData by remember { mutableIntStateOf(data) }

    TextField(
        value = editedData.toString(),
        onValueChange = { newValue ->
            editedData = newValue.toInt()
        },
        modifier = modifier
    )

    Button(
        onClick = {
            viewModel.updateTestData(editedData)
        }
    ) {
        Text(
            text = "Update"
        )
    }
}
```

### 3 实现计划

1. 10月，先把 WorkFlow 这个大致的框架搭起来，功能上先以文件管理和 TODO 列表为主，先在本地跑通。
2. 11月，开始实现对应后端功能。客户端这块主要是联调和实现用户登录，如果时间来得及，可以把联系人功能加上。
3. 12月，主要任务是把知识库实现好，这块不太清楚需要怎么实现，所以留足时间。

### * 导入依赖

1. Hilt

在项目级别的`build.gradle.kts`中导入：

``` kotlin
plugins {
    ...
    id("com.google.dagger.hilt.android")version "2.52" apply false
}
```

在 App 级别的`build.gradle.kts`中导入：

``` kotlin
dependencies {
    ...
    val hiltVersion = "2.52"

    implementation("com.google.dagger:hilt-android:$hiltVersion")
    kapt("com.google.dagger:hilt-compiler:$hiltVersion")
    implementation("androidx.hilt:hilt-navigation-compose:1.2.0")
}
```

2. OkHttp

App 级别的`build.gradle.kts`中导入：

``` kotlin
dependencies {
    ...
    implementation("com.squareup.okhttp3:okhttp:4.12.0")
}
```

:::danger{title="警告"}
Gradle 进行编译不成功的时候，一定要检查以下工具的版本是否对应，这里给出一个版本记录。

- Gradle 版本：8.9（在 Project Structure 内查看）
- Gradle 用的 Java 版本：17（在 Settings -> Build, Execution, Deployment -> Build Tools -> Gradle 内指定，也可在 gradle.properties 文件内通过`org.gradle.java.home`强制指定）
- Kotlin 版本：2.0.10（在 lib.versions.toml 文件内指定）
- Compose 组件（也说 Compose Compiler Gradle 插件）版本：依赖 Kotlin 版本（在 lib.versions.toml 文件内指定）
- KSP 版本：2.0.10-1.0.24（在项目级别的 build.gradle.kts 文件内指定）
- Kotlin 编译插件（`kotlinCompilerExtensionVersion`）版本：1.5.5（在 app 级别的 build.gradle.kts 文件内指定）
- Kotlin 编译源码标准和目标 Java 版本，目标 jvm 版本：17（在 app 级别的 build.gradle.kts 文件内指定）
- Android Gradle Plugin（agp）版本：8.7.0（在 Project Structure 内查看，也可在 lib.versions.toml 文件内指定）

如果有编译问题，大概率就是这几个东西版本冲突。
:::

WorkFlow | 记录1

主要内容：

1. 泛型
2. 带泛型的 ART 树的实现
3. String 类型的索引实现



### 1 Go 中的泛型

#### 1.1 泛型函数、泛型类型

泛型作为现代语言的一大重要特性，与 1.18 版本被引入。泛型的引入不仅节省了针对不同类型的代码的代码量，也改变了“接口”这一重要概念的定义。

:::tip{title="提示"}
Go 的泛型说实话实现的有点也不能说是残缺，就是说别扭吧。除了这个`[T]`符号选的贼怪异（与切片声明混合容易造成语义不明）之外，泛型还不支持方法和匿名函数也是虽然可以说无伤大雅，但也可以说是功能残缺。不过我个人就不太想纠结这些事情，我什么水平去直接关心语言的实现（），用就是了。
:::

Go 中的泛型声明使用`[]`这一符号，一个简单的泛型函数示例如下：

``` go
func GenericFuncTest [T comparable] (param1 T) T {
	return param1
}

func t () {
	GenericFuncTest[int](1)
}
```

在上述代码中，引入了泛型`T`，每次调用`GenericFuncTest`函数时，都要指定这个泛型的实际类型。而`T`的后面用`comparable`指定了该泛型的类型范围。这一段话里就引出了三个概念：

- 类型形参：`T`，即每次使用泛型时，可以理解为那个泛型的代指
- 类型实参：`int`，每次使用泛型时，实际要用的类型
- 类型约束：`comparable`，该泛型能够匹配的类型

除了泛型函数，类型也是可以指定泛型的，而且上面三个概念依然沿用。

``` go
type GenericMapTest [Key comparable, Value string | int | []string | []Key] map[Key]Value // 没错 泛型可以一次性指定多个 还能互相嵌套

func t () {
	m := GenericMapTest[int, string]{}
	m[1] = "1"
}
```

但是有些写法是会报错的，比如这样：

``` go
//type GenericSliceTest [Elem *GenericMapTest[int, string]] []Elem
// 会报错 主要原因就在那个 * 上
// 下面这个写法就没问题 如果泛型出了语法问题可以考虑包上一层 interface

type GenericSliceTest [Elem interface{*GenericMapTest[int, string]}] []Elem
```

另外，**匿名结构体和匿名函数是不支持泛型的**。

#### 1.2 泛型方法

既然有了泛型类型和泛型函数，那么泛型方法也有，虽然多少有点功能不全。

``` go
type GenericMapTest [Key comparable, Value any] map[Key]Value

func (receiver GenericMapTest[Key, Value]) DeleteElement(key Key) (deleteValue Value) {
	deleteValue, ok := receiver[key]
	if ok {
		delete(receiver, key)
		return deleteValue
	}
	return
}
```

关于泛型方法，要提的点有这几条：

- 泛型方法是**不支持泛型类型以外的泛型**的，即使是普通方法也是不能加泛型的。比如说要是这么声明函数，是过不了编译的：

``` go
func (receiver GenericMapTest[Key, Value]) DeleteElement[T any](key Key) (deleteValue T)
```

:::tip{title="提示"}
关于为什么方法不能引入除了调用者泛型以外的泛型，最简洁的回答是：可以做，但是为了避免编译器复杂度所以没做。具体点说的话，原因如下：

- Go 会在编译期就确定所有泛型的类型，并且根据调用方的类型实参来编译相对应的泛型函数/类型代码，这事好说，在哪里调用了就在哪开始编译对应类型的函数/类型。就像之前的例子中，编译到`GenericMapTest`的时候先过，到具体的要用到这个类型的时候`m := GenericMapTest[int, string]{}`再编译`int`，`string`对应代码。
- 但是方法就不一样了，得考虑接口的存在了。当一个变量类型断言成一个接口类型并且调用泛型方法的时候，它不能确定该变量的实际类型的接口实现函数的对应类型有没有被编译过，也不好编译对应代码。比如说有个 A 接口，底下有一个泛型方法等着实现，有个 B 类型，实现了该泛型方法。然后在 C 函数下通过类型断言的方法将一个`any`断言为 A 类型，调用泛型方法。此时编译器是不知道 B 类型的那个泛型方法实现有没有被针对实际类型编译过的。最极端的情况下，它得扫描整个包才能确定这件事，那开销就大了。更别提**类型断言是在运行期而不是编译期的事**（我到写这篇文的时候才知道），那更没法编译了。

上面的话多少有点别扭，主要是我理解的也有点别扭。看原文的话详情参见：[Type Parameter Proposal](https://go.googlesource.com/proposal/+/refs/heads/master/design/43651-type-parameters.md#No-parameterized-methods)
:::

- 传进来的泛型类型下的参数，是**不能使用 switch 和类型断言的**。如果要实际的获得参数类型，只能用反射。

#### 1.3 接口新定义

之前在指定类型约束的时候，其实很容易一写就写很长的泛型约束，并且这么长的泛型约束也不好复用。所以 Go 将这个问题交给接口来解决。

``` go
type Int interface {
    int | int8 | int16 | int32 | int64
}

type Uint interface {
    uint | uint8 | uint16 | uint32
}

type Float interface {
    float32 | float64
}

type Slice[T Int | Uint | Float] []T

type SliceElement interface {
    Int | Uint | Float | string
}

type Slice[T SliceElement] []T 
```

如上，接口中可以通过指定类型约束来形成一个新的类型，该类型可以在别的泛型中嵌套，也可以和普通的类型一起用。

类型约束可以通过三个运算符来指定：`|``~`和换行，分别表示类型取并集，类型取底层类型，类型取交集。另外，指定了类型约束的接口仍然可以指定要实现的函数原型。

``` go
type GenericInterfaceTest interface {
	~uint8 | ~uint16 | uint32
	byte
        
        String() string
}
```

如上，该泛型接口所指定的类型约束就是以 uint8 为底层类型的所有类型。首先是上面三个 uint 取并集，之后和下面的 byte 取交集，那么取完之后就剩底层为 uint8 的类型了。

由此可以看到，**从 Go 加入泛型之后，以前的接口定义已经不适用了，毕竟不止有要实现的函数**。来回顾一下以前的接口是如何定义的：

> An interface type specifies a method set called its interface.（**一个声明了方法集的接口类型即为接口**）

再看看 Go 1.18之后接口的定义：

> An interface type defines a type set.（**一个接口定义了一个类型的集合**）

接口从一个**方法集**变成了**类型集**。按照此定义，`GenericInterfaceTest`的定义即为：所有底层类型为 uint8 的，并且持有`String`方法的类型的集合；而`interface{}`类型（Go 1.18后新增其别名`any`）的定义即为：所有的类型的集合。而原来的接口定义依然可以套这个新的定义，即**如果一个类型持有一个接口所定义的所有函数原型的对应方法，那么可以认为该类型属于该接口所定义的类型集**。

:::tip{title="comparable"}
特殊的，Go 定义了一个类型`comparable`，该类型是所有可以用`==``!=`比较的类型的集合。需要注意，它**仅仅是可比较，而不是可以比较大小，它只能比较是否相同**。

另外，`comparable`不能被直接或间接地和其他类型合并。
:::

#### 1.4 泛型接口

接口也可以引入泛型，如下示例：

``` go
// 泛型接口定义
type GenericInterfaceTest [T any] interface {
	int | struct{ testValue string }
	
	GenericInterfaceFuncTest (value T) string
}
// 如果该接口没有指定类型集的话 可以通过类似 GenericInterfaceTest[string] 这样的方式成为一个变量的类型

// 实现接口
type GenericInterfaceImplement struct {
	testValue string
}

func (g *GenericInterfaceImplement) GenericInterfaceFuncTest (value string) string {
	return g.testValue + value
}

// 子接口
type GenericInterfaceImplement2 [T any] interface {
	int
	
	GenericInterfaceFuncTest (value T) string
}
```

#### 1.* 一些注意事项

1. 如果一个接口定义了类型约束，那么它不能被实例化。
2. 类型取交集可以用两个完全没有交集的类型，虽然结果是个空集，没有任何类型是它的成员，没有实际意义，但是它是能过编译的。
3. 类型取并集的时候要求取并集的两个类型不能有交集，但是如果其中一个类型是接口的话，可以无视这一规则。
4. 类型取并集的时候，不能用类型形参来取并集。
5. 接口不能直接或者间接地并入自己。
6. 取底层类型的时候，只能用基本类型，类型别名和别的类型都不行，接口也不行。
7. 如果一个接口带方法，那么该接口不能被取并集。

### 2 ART 树的实现

:::tip{title="提示"}
该实现是在[plar/go-adaptive-radix-tree](https://github.com/plar/go-adaptive-radix-tree)的基础上写的。我阅读了所有源码，对着源码写了自己的代码，并且加入了泛型。
:::

ART 树（adaptive radix tree）是一个在前缀树的基础上进行改进的树，它的主要功能是以字节数组为键，进行键值对的有序存储。相比于一般的前缀树，它可以通过不同的节点大小和压缩前缀来大幅减少内存占用的同时，达到相近的性能。

> 前缀树：一种按字节数组存储的树。假设它要存储的目标只有a到z这26个字节，那么它的每个节点都有一个长度为26的字节数组，每个元素存储指向子节点的指针。从根节点开始，每个节点按顺序使用字节数组的一个元素来指向子节点，所以前缀树的高度取决于存储的最长的字节数组。

ART 树有四种节点类型：`node4`，`node16`，`node48`，`node256`。每种节点能存储对应上限个子节点：`node4`能存储4个子节点，`node16`能存储16个子节点，以此类推。节点之间可以按需互相转换，比如如果有需求要在`node4`节点下新增一个子节点的话，该节点就可以转换为`node16`。

除了可转换的节点以外，ART 树还能重用共有的前缀。举例来说，假如树上存储了以`apple`，`app`为键的两个值，那么共同的前缀`app`就会存储到一个节点中，而不是分成三个节点存储。

该树所能支持的操作如下：

``` go
// New 获取一棵新的树
func New[T Value]() Tree[T] {}

type Node[T Value] interface {
	Kind() Kind
	Key() Key
	Value() T
}

// Iterator 迭代器实例
type Iterator[T Value] interface {
	// HasNext 是否存在下一个节点
	HasNext() bool
	// Next 获取下一个节点 如果下一个节点不存在或者树结构被修改 就返回 NoMoreNodeErr 或者 TreeIsModifiedErr
	Next() (node Node[T], e error)
}

// Tree 树的接口
type Tree[T Value] interface {
	// Insert 根据指定的键插入新值 如果键在树中已经有值 就更新值 返回旧的值 并且返回 true
	Insert(key Key, value T) (oldValue T, isUpdated bool)
	// Delete 根据指定的键删除对应的值 并且返回被删除的旧值 如果键不存在将返回 false
	Delete(key Key) (deleteValue T, isDeleted bool)
	// Search 根据指定的键寻找对应的值
	Search(key Key) (value T, isFound bool)

	// ForEach 对树进行遍历 对于每个被遍历到的 符合条件的节点调用 callback 函数 默认情况下遍历只遍历叶子节点
	ForEach(callback Callback[T], options ...int)
	// ForEachWithPrefix 对树进行遍历 对于每个被遍历到的 前缀和指定的键匹配的 符合条件的节点调用 callback 函数 默认情况下遍历只遍历叶子节点
	ForEachWithPrefix(keyPrefix Key, callback Callback[T], options ...int)
	// Iterator 获取一个新的迭代器 默认只遍历叶子节点
	Iterator(options ...int) Iterator[T]

	// Minimum 获取当前树上字典序最小的键所对应的值
	Minimum() (min T, isFound bool)
	// Maximum 获取当前树上字典序最大的键所对应的值
	Maximum() (max T, isFound bool)

	// Size 获取树上键值对数量
	Size() int
}
```

具体的实现就不说了，就写几个写的过程中出现的问题吧。

*****

原作者的节点实现是这样的：

``` go
type artNode[T Value] struct {
	reference unsafe.Pointer
	kind      Kind
}

type nodePrototype[T Value] struct {
	prefixLen   uint32
	prefix      prefix
	childrenNum uint16
	zeroChild   *artNode[T] // 这东西是给正好断在别的键的中间的键用的 比如说 apple 和 appleWatch apple对应的叶子节点就放在这
}

type node4[T Value] struct {
	nodePrototype[T]
	children [node4Max]*artNode[T]
	keys     [node4Max]byte
	isExist  *bitmap
}

type node16[T Value] struct {
	nodePrototype[T]
	children [node16Max]*artNode[T]
	keys     [node16Max]byte
	isExist  *bitmap
}

type node48[T Value] struct {
	nodePrototype[T]
	children [node48Max]*artNode[T]
	keys     [node256Max]byte
	isExist  *bitmap
}

type node256[T Value] struct {
	nodePrototype[T]
	children [node256Max]*artNode[T]
}

type leaf[T Value] struct {
	key   Key
	value T
}
```

它的结构是这样的：所有的节点首先是一个`artNode`类型的结构体，在该结构体内部另有一个指针指向实际的节点内容`nodePrototype`，该类型是所有节点类型的原型，其他的节点类型（除了叶子节点以外）都将其组合进去了。这一点看它们的工厂方法就很明显了：

``` go
func newNode4[T Value]() *artNode[T] {
	return &artNode[T]{
		reference: unsafe.Pointer(&node4[T]{
			isExist: newBitmap(4),
		}),
		kind: Node4,
	}
}

func newNode16[T Value]() *artNode[T] {
	return &artNode[T]{
		reference: unsafe.Pointer(&node16[T]{
			isExist: newBitmap(16),
		}),
		kind: Node16,
	}
}

func newNode48[T Value]() *artNode[T] {
	return &artNode[T]{
		reference: unsafe.Pointer(&node48[T]{
			isExist: newBitmap(256),
		}),
		kind: Node48,
	}
}

func newNode256[T Value]() *artNode[T] {
	return &artNode[T]{
		reference: unsafe.Pointer(new(node256[T])),
		kind:      Node256,
	}
}

func newLeaf[T Value](key Key, value T) *artNode[T] {
	clonedKey := make(Key, len(key))
	copy(clonedKey, key)
	return &artNode[T]{
		reference: unsafe.Pointer(&leaf[T]{
			key:   clonedKey,
			value: value,
		}),
		kind: Leaf,
	}
}
```

这种设计一方面是为了转型方便：`unsafe.Pointer`可以被毫无限制的转型成想要的指针类型。

``` go
func (a *artNode[T]) node() *nodePrototype[T] {
	return (*nodePrototype[T])(a.reference)
}
```

另一方面是为了便于替换节点，比如下面两个函数：

``` go
func replaceRef[T Value](oldNode **artNode[T], newNode *artNode[T]) {
	*oldNode = newNode
}

func replaceNode[T Value](oldNode *artNode[T], newNode *artNode[T]) {
	*oldNode = *newNode
}
```

第一个是替换指针内容，将原本是指向`oldNode`的指针修改为指向`newNode`；第二个是替换实际的指向内容，将`newNode`的内容拷贝到存储`oldNode`的内存中。这两个的区别是改指向还是该内容，基于这个区别，前者一定是在树这个层面上用，后者一定是在节点这个层面上用，但是这两个操作的前提都是基于相同的类型才可以。

*****

因为字节0也是有实际意义的，所以节点内不仅有字节数组来存储子节点所代表的字节，还需要一个结构来存储哪个字节是有实际意义的。原作者针对不同的节点，用的是不同的位图：`[node4Max]byte`，`uint16`，`[4]uint64`（`node256`是不需要这个结构的，只需要检查子节点是否为空即可）。如果字节数组对应位置有意义，那么对应的位为1，反之则为0。鉴于原作者的位运算实在过于复杂而且感觉还有问题（？），我自己封装了一个统一的位图。

``` go
// bitmap 对位图进行封装 把读写逻辑都封进来
// 其底层为 uint16 的切片
type bitmap struct {
	data            []uint16
	effectiveLength int
}

// newBitmap 获取一个新的 bitmap length 用于指定 bitmap 的有效长度
//
// 如果 length 不足16也是用 uint16 进行存储
func newBitmap(length int) *bitmap {
	arrayLength := length / 16
	if length%16 != 0 {
		arrayLength += 1
	}
	return &bitmap{
		data:            make([]uint16, arrayLength),
		effectiveLength: length,
	}
}

// set1 将指定的数位设置为1 如果指定的数位超过了初始化 bitmap 时指定的长度 将不做任何操作
func (b *bitmap) set1(index int) {
	if index >= b.effectiveLength {
		return
	}
	arrayIndex := index / 16
	i := index % 16
	if i == 0 {
		b.data[arrayIndex] |= 1
		return
	}
	b.data[arrayIndex] |= 1 << i
}

// set0 将指定的数位设置为0 如果指定的数位超过了初始化 bitmap 时指定的长度 将不做任何操作
func (b *bitmap) set0(index int) {
	if index >= b.effectiveLength {
		return
	}
	arrayIndex := index / 16
	i := index % 16
	if i == 0 {
		b.data[arrayIndex] &= 65534 // 655534 = 1111111111111110
		return
	}
	b.data[arrayIndex] &= ^(1 << i)
}

// get 指定数位是否为1 如果指定的数位超过了初始化直接返回 false
func (b *bitmap) get(index int) bool {
	if index >= b.effectiveLength {
		return false
	}
	arrayIndex := index / 16
	i := index % 16
	return (b.data[arrayIndex] & (1 << i)) != 0
}

// getNum 获取当前位图中数位为1的位的数量
func (b *bitmap) getNum() int {
	count := 0
	s := b.string()
	for i := range s {
		if s[i] == 49 {
			count += 1
		}
	}

	return count
}

func (b *bitmap) string() string {
	strBuilder := &strings.Builder{}
	for i := range b.data {
		if b.data[i] == 0 {
			strBuilder.WriteString("0 ")
		} else {
			strBuilder.WriteString(numToBinIncludeLeadingZero(b.data[i]))
			strBuilder.WriteString(" ")
		}
	}

	return strBuilder.String()
}
```

位图是个应用挺广的东西，除了这种代替布尔数组来指示是否的用途以外，也可以用来方便的传递多配置项：

``` go
const (
	TraverseLeaf = 1
	TraverseNode = 2
	TraverseAll  = TraverseLeaf | TraverseNode
)
```

### 3 String 类型的索引实现

目前 String 类型所能支持的操作如下：

1. `set`，不多说。
2. `get`，不多说。
3. `setnx`，只有在键不存在的时候设置值。
4. `getrange`，获取对应的值的在`[start, end]`范围内的字符。
5. `getset`，先按key获取旧的值，然后再设置新的值并且返回旧值。
6. `append`，在key存在的情况下，向其已经存在的value追加一个字符串。
7. `del`，不多说。

这个索引结构也没啥可说的了，就是 ART 树。

~~到这之后，这个类 Redis 数据库也就差不多了，再另加功能的话一个是自动整理存档文件，另外的就涉及分布式了。~~

MisakaDB-kv型小型数据库 | 记录7

主要内容：

1. 有序集合数据结构的索引的实现
2. 列表数据结构的索引的实现



### 1 Zset 有序集合

目前 Zset 支持的操作如下：

1. `ZAdd`，添加元素到指定的有序集合中。如果元素已存在则更新，如果有序列表不存在则创建一个新的有序列表。
2. `ZRem`，从指定的有序集合中删除元素。如果删除后有序集合不再持有元素则自动移除。
3. `ZScore`，按给定的 key 和 member 获取对应的 score。
4. `ZCard`，获取指定的有序列表的元素个数。
5. `ZCount`，获取有序列表中，score 在`[min, max]`之间的元素个数。
6. `ZRange`，获取有序列表中，score 在`[min, max]`之间的元素内容。

除了这些功能之外，有序集合内的元素都支持单独的过期时间。

Zset 有序集合的索引的数据结构，是由跳表和哈希表共同组合而成的。先用一个哈希表来存储所有的 key 和有序集合，有序集合本身是用哈希表和跳表共同存储同一类型的节点，哈希表以 member 为键，负责“集合”的特征；跳表以 score 为键，负责“有序”的特征。

``` go
type zsetNode struct {
	indexNode
	score int
}

// 这个其实不应该这么写 这个应该写成 int 的类型别名比较好
type zsetScore struct {
	score int
}

type zset struct {
	dict      map[string]*zsetNode
	skipList  *skipList.SkipList[*zsetNode]
	expireNum int // 过期计数 计算有过期删除的这个需求的 member 的数量 即 expiredAt 字段不为-1的 member 数量 如果它是0 获取有序集合信息的时候就不需要检查是否过期
}

type ZSetIndex struct {
	index map[string]*zset

	mutex        sync.RWMutex
	activeFile   *storage.RecordFile
	archivedFile map[uint32]*storage.RecordFile

	fileIOMode     storage.FileIOType
	baseFolderPath string
	fileMaxSize    int64
	syncDuration   time.Duration
}
```

单独的过期时间这一点，实现思路上大体和之前的类似，即并不在该元素过期时就立刻删除，而是在再次使用到该元素时再判断是否过期。这样的思路有一个问题，即支持的操作中有一些是需要过滤掉所有过期的元素的，比如`ZCard`，因此我选择额外维护了一个`expireNum`信息，用以存储有序集合中过期元素的数量。如果它是0的话，就不需要针对过期元素进行过滤。

``` go
// refreshZset 对有序集合进行循环 删除过期元素
func (z *zset) refreshZset() {
	// 这块不加锁 因为调用者已经把锁加好了
	var node *zsetNode
	for key := range z.dict {
		node = z.dict[key]
		if node.expiredAt != -1 && node.expiredAt < time.Now().UnixMilli() {
			// 过期
			delete(z.dict, key)
			_ = z.skipList.DeleteNode(zsetScore{score: node.score})
			z.expireNum -= 1
		}
	}
}

// ZRange 获取 score 在 [min, max] 区间内的所有 member
func (zi *ZSetIndex) ZRange(key []byte, min, max int) ([][]byte, error) {
        ...
	if targetZset.expireNum != 0 {
		zi.mutex.RUnlock()
		zi.mutex.Lock()
		targetZset.refreshZset()
		zi.mutex.Unlock()
		zi.mutex.RLock()
	}
	...
	return result, nil
}
```

剩下的别的就没有什么特别要说的了，就是对数据结构的各种操作的封装外加写入文件。

### 2 List 列表

目前 List 支持的操作如下：

1. `LInsert`，向列表中插入元素，插入位置由 index 指定。比如说列表里有`1 2 3 4`这几个元素，如果 index 指定为2插入一个10，那么插入后列表是`1 2 10 3 4`。
2. `LPop`，弹出操作，比如说列表里有`1 2 3 4`这几个元素，弹出后列表是`2 3 4`。此外，该函数也承担删除整个列表的操作。只要列表中只有一个元素或者没有元素，该函数都会从 index 中移除列表。
3. `LPush`，压入操作，比如说列表里有`1 2 3 4`这几个元素，压入10列表是`10 1 2 3 4`。该函数也承担创建一个列表的操作，如果列表不存在，就创建一个列表。
4. `LSet`，修改更新操作。该方法不支持修改更新时间。
5. `LRem`，删除操作，删除的对象由 count 和 value 一起指定。如果`count > 0`就是从列表表头开始搜索，删除 count 个符合条件的元素；如果`count < 0`就是从列表表尾开始搜索，删除 count 个符合条件的元素；如果`count = 0`就是删除列表中所有符合条件的元素。注意，**当 count != 0 时，如果被删除的元素个数不满足 count 就会返回`RemoveCountIsNotEnough`错误，返回该错误时，并不会影响索引中存储的值**。
6. `LIndex`，按 index 进行查询操作。比如说列表里有`1 2 3 4`这几个元素，查询 index 为2的元素，返回的就是3。
7. `LLen`，查询列表长度。
8. `LRange`，按范围查询列表内的元素，查询范围是`[start, end)`。比如说列表里有`1 2 3 4`这几个元素，查询 start 为1 end 为3的元素区间，返回的就是`2 3`。

:::tip{title="提示"}
我知道 Redis 里的列表其实是双端队列，只是我实在懒得写另一头的弹出压入，反正代码上是差不了太多的。
:::

除了这些功能之外，有序集合内的所有元素都支持独立的过期时间。因为 List 是形似队列的，我故意将其设计为删除元素后其他元素补位的形式。也就是说，如果`1 2 3 4`，我删除3后，查询 index 为2的元素，仍然能返回有效值，并且返回的是4。

List 的索引的数据结构为哈希表套切片，这一点无需多说了。但是为了支持元素的过期时间，我加了一些东西。

``` go
type expiredInfo struct {
	key         []byte
	expiredNode *indexNode
}

type ListIndex struct {
	index        map[string][]*indexNode
	mutex        sync.RWMutex
	activeFile   *storage.RecordFile
	archivedFile map[uint32]*storage.RecordFile

	fileIOMode     storage.FileIOType
	baseFolderPath string
	fileMaxSize    int64
	syncDuration   time.Duration

	expiredAtChan chan *expiredInfo
	closeMonitor  chan int
}
```

在维护列表的有序性的同时还维护每个元素的单独过期时间实在是有点挑战。在一开始的时候，我设想的是和别的数据结构差不多的意思，即不单独进行过期删除的操作，只在用到该元素的时候判断是否过期，只不过后来我意识到这事行不通，太容易影响到别的元素。假设列表中有`1 2 3 4`4个元素，其中元素2已经过期。如果我要更新索引为2的元素，理论上我应该更新元素4，但是因为过期的元素还没有被删掉，反而会更新到元素3上面去。

如果只在用到该元素的时候判断是否过期会因为影响别的元素的索引所以行不通，那么我在每次读写列表的时候都扫一遍整个列表如何？这一点也不太能行得通，不仅是因为这一点是挺消耗时间的（在这里提消耗时间，上面的有序集合没提的原因是，有序数组内只有3个命令是需要扫描整个数据结构的，而在这里是所有的命令都得扫一遍，那时间差距可就太大了），并且这个思路本身就有一点行不通，因为问题出在还原列表上。

这个项目的文件存储机制是存储操作的，也就是说我在还原列表的时候，拿到的是一条条的操作记录。还是之前的那个例子，假设列表中有`1 2 3 4`4个元素，其中元素2已经过期，要更新索引为2的元素。这些操作放在底层文件记录上是完全看不出来是元素2先过期还是更新操作先来，也就造成了还原列表不准确。

所以要想设计元素单独过期，要达成的效果有两个：

1. 在文件里必须看出过期和操作的先后顺序
2. 尽量别扫描整个列表

所以我想了想，还是用协程来处理这件事：

``` go
// BuildListIndex 给定当前活跃文件和归档文件 重新构建List类型的索引 该方法只会在数据库启动时被调用 如果不存在旧的文件 则新建一个活跃文件
func BuildListIndex(activeFile *storage.RecordFile, archivedFile map[uint32]*storage.RecordFile, fileIOMode storage.FileIOType, baseFolderPath string, fileMaxSize int64, syncDuration time.Duration) (*ListIndex, error) {
        ...

ReadFileFished:
	result.refreshList()
	result.activeFile.StartSyncRoutine(result.syncDuration)
	go result.expiredChanMonitor()

	return result, nil
}

// expiredChanMonitor 监控 channel 如果有过期消息发过来就处理 具体包括修改 index 向文件中写入过期 entry
func (li *ListIndex) expiredChanMonitor() {
	var expiredNode *expiredInfo
	var e error
	var i int
	for {
		select {
		case expiredNode = <-li.expiredAtChan:
			li.mutex.RLock()

			key := string(expiredNode.key)

			targetList, ok := li.index[key]
			if !ok {
				li.mutex.RUnlock()
				continue
			}

			i = 0
			for ; i < len(targetList); i++ {
				if targetList[i] == expiredNode.expiredNode { // 指针比较总比字节数组循环快吧
					// 找到过期值
					break
				}
			}

			li.mutex.RUnlock()
			li.mutex.Lock()

			// 写入文件
			_, e = li.writeEntry(&storage.Entry{
				Key:       expiredNode.key,
				Value:     expiredNode.expiredNode.value,
				EntryType: storage.TypeListExpired,
				ExpiredAt: 0,
			})
			if e != nil {
				logger.GenerateErrorLog(false, false, e.Error())
				continue
			}

			// 正式开始删除
			for ; i < len(targetList)-1; i++ {
				targetList[i] = targetList[i+1]
			}
			// 写回去
			li.index[key] = targetList[:len(targetList)-1]

			li.mutex.Unlock()
		case <-li.closeMonitor:
			return
		}
	}
}

// delayExpiredMessage 延迟发送过期消息到 channel 中
//
// 比如说列表里有1 2 3 4这几个元素 如果 index 指定为2过期 那么过期处理后列表是1 2 4
func (li *ListIndex) delayExpiredMessage(key []byte, expiredNode *indexNode) {
	time.Sleep(time.Until(time.UnixMilli(expiredNode.expiredAt)))
	li.expiredAtChan <- &expiredInfo{
		key:         key,
		expiredNode: expiredNode,
	}
}

// CloseIndex 关闭 List 索引 同时停止定时Sync 关闭文件 关闭内部 channel
func (li *ListIndex) CloseIndex() (err error) {
	defer func() {
		if e := recover(); e != nil {
			panicString := fmt.Sprintf("%s", e)
			logger.GenerateErrorLog(true, false, panicString)
			err = errors.New(panicString)
		}
	}()

	li.mutex.Lock()
	defer li.mutex.Unlock()
	for _, v := range li.archivedFile {
		if v.IsSyncing {
			v.StopSyncRoutine()
		}
		e := v.Close()
		if e != nil {
			if errors.Is(e, os.ErrClosed) {
				continue
			}
			return e
		}
	}
	li.closeMonitor <- 1
	close(li.closeMonitor)
	close(li.expiredAtChan)
	return nil
}

func (li *ListIndex) LInsert(key []byte, index int, value []byte, expiredAt int64) error {
	...

	if expiredAt != -1 {
		// 有实际的过期时间
		go li.delayExpiredMessage(key, targetSlice[index])
	}

	return nil
}
```

先是启动一个协程来监听并且处理过期元素，在每次插入新的可过期的元素时，延迟到过期发生那一刻向监听协程发送过期消息（当然我传得是地址而不是别的，因为索引和元素值都有可能在过期之前改变）。同时，底层文件存储上，我加了一个新的操作类型`TypeListExpired`，专门用来设置过期消息的。还有一点，还原列表之后我还是需要对所有的元素再遍历一次。因为有些过期是有可能发生在数据库关闭期间的，而且就算是没过期，也需要使其加入上面的过期机制中一并处理。

> 经测量，这套方法的超时误差大概在2ms左右。

``` go
const (
	TypeDelete EntryType = iota + 1 // 标识记录删除信息的entry
	TypeRecord                      // 标识记录信息的entry

	TypeLInsert // 以下为 list 准备的 entry type
	TypeLPop
	TypeLPush

	TypeListExpired // 过期标识 专门问 list 用的
)
```

:::tip{title="提示"}
这里其实还有改进的空间。假设在同一时刻下，有元素过期的同时还有操作请求，势必会抢锁，我得确保**必须**优先处理元素过期再说操作请求的事，但是目前的代码并没有实现这一点。

要实现这一点，可以引入`sync.Cond`来解决协程抢锁优先级的问题。
:::

:::tip{title="提示"}
还有一个 Set 集合我没写，有点不想写了，它的索引数据结构很 Hash 一模一样，都是哈希表嵌套，差别不是很大。
:::

MisakaDB-kv型小型数据库 | 记录6

MisakaDB-kv型小型数据库 | 记录5

对 map 的使用方法和底层机制进行记录，以下内容基于 go1.22.1 版本。



Go 中的 map 就是哈希表，比较类似的就是 python 的dict。

### 1 使用方法

增删改查示例代码：

``` go
testMap := make(map[string]string, 10) // 初始化
testMap["test1"] = "test1" // 增
testMap["test1"] = "test2" // 改
delete(testMap, "test1") // 删 删除的键不存在也不会报错
if value, ok := testMap["test1"]; ok { // 查
        fmt.Println(value)
}
```

有几个注意点:

1. 向一个没有 make 初始化过的，实质为 nil 的 map 写入数据会引发 panic，但是查找和删除并不会引发 panic，访问其长度会返回0。
2. 即使 map 中没有对应的键，delete 也不会报错，查询也会返回对应类型的零值。
3. make 一个新的 map 时，可以顺带指定其容量，当然不指定也行，但是在有数据预期的情况下，指定容量会减少 map 扩容的次数，加快速度。
4. 查数据的时候，建议带上 ok，方便很多。
5. map 并不支持并发读写，如果底层检测到了读写冲突，会直接引发 panic。

### 2 底层实现

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

~~偷一张现成的图~~

map 相关的底层数据结构如下：

``` go
// src/runtime/map.go
// A header for a Go map.
type hmap struct {
	// Note: the format of the hmap is also encoded in cmd/compile/internal/reflectdata/reflect.go.
	// Make sure this stays in sync with the compiler's definition.
	count     int // # live cells == size of map.  Must be first (used by len() builtin)
        // map 保存的键值对数量
	flags     uint8
	B         uint8  // log_2 of # of buckets (can hold up to loadFactor * 2^B items)
        // bucket 数组长度为2的 B 次方
	noverflow uint16 // approximate number of overflow buckets; see incrnoverflow for details
	hash0     uint32 // hash seed

	buckets    unsafe.Pointer // array of 2^B Buckets. may be nil if count==0.
        // 当前使用的 bucket 数组
	oldbuckets unsafe.Pointer // previous bucket array of half the size, non-nil only when growing
        // 扩容后的旧的等待数组迁移的 bucket 数组
	nevacuate  uintptr        // progress counter for evacuation (buckets less than this have been evacuated)

	extra *mapextra // optional fields
}

// mapextra holds fields that are not present on all maps.
type mapextra struct {
	// If both key and elem do not contain pointers and are inline, then we mark bucket
	// type as containing no pointers. This avoids scanning such maps.
	// However, bmap.overflow is a pointer. In order to keep overflow buckets
	// alive, we store pointers to all overflow buckets in hmap.extra.overflow and hmap.extra.oldoverflow.
	// overflow and oldoverflow are only used if key and elem do not contain pointers.
	// overflow contains overflow buckets for hmap.buckets.
	// oldoverflow contains overflow buckets for hmap.oldbuckets.
	// The indirection allows to store a pointer to the slice in hiter.
        // 如果键值都不是指针 那么这个 map 会被标记为没有指针 以避免 gc 扫描整个 map
        // 但是 bmap.overflow 是一个指针
        // 为了保证其存活 将所有的 overflow 指向的 bucket 全部存储到 hmap.extra.overflow 和 hmap.extra.oldoverflow
        // 这间接地允许在 hiter 里存储指向切片的指针
        // 注 hiter 是针对 map 的迭代器 不是这里的讨论重点
	overflow    *[]*bmap
	oldoverflow *[]*bmap

	// nextOverflow holds a pointer to a free overflow bucket.
	nextOverflow *bmap
}
```

``` go
// src/cmd/compile/reflectdata/reflect.go
// Builds a type representing a Bucket structure for
// the given map type. This type is not visible to users -
// we include only enough information to generate a correct GC
// program for it.
// Make sure this stays in sync with runtime/map.go.
//
// 该类型对用户不可见 只确保在 gc 里面正确即可
//
//	A "bucket" is a "struct" {
//	      tophash [BUCKETSIZE]uint8 // bucket 存储的键的 hash 值的高8位
//	      keys [BUCKETSIZE]keyType // 键
//	      elems [BUCKETSIZE]elemType // 值
//	      overflow *bucket // 指向下一个 bucket 的指针
//	    }

// src/runtime/map.go
// A bucket for a Go map.
// 这个就是 bucket 的对用户可见的版本
type bmap struct {
	// tophash generally contains the top byte of the hash value
	// for each key in this bucket. If tophash[0] < minTopHash,
	// tophash[0] is a bucket evacuation state instead.
	tophash [bucketCnt]uint8
	// Followed by bucketCnt keys and then bucketCnt elems.
	// NOTE: packing all the keys together and then all the elems together makes the
	// code a bit more complicated than alternating key/elem/key/elem/... but it allows
	// us to eliminate padding which would be needed for, e.g., map[int64]int8.
	// Followed by an overflow pointer.
        // 这段注释解释了为什么 bucket 里面键和值是分开存储的
        // 注释说 虽然这样会加重代码复杂性 但是利于消除间隔
        // 我认为 这个 “消除间隔”（eliminate padding）指的是内存对齐
}
```

> 后两个成员变量实质上并不存在，在访问时是通过指针偏移来访问。

1. 总结一下，map 的底层结构是这样的：hmap 用数组存储一系列 bucket，**每个 bucket 代表着一种 hash 匹配结果，并且存储着 hash 低位值相同的键值对（实质上就是发生了哈希冲突的键值对）**。当一个 bucket 存储的冲突的键值对太多，一个bucket存储不过来，那么会创建一个新的 bucket，老的 bucket 的 overflow 指向新的 bucket，形成一个 **bucket 链表结构**。
2. 引入一个新的概念：**负载因子**，它通过计算 map 存储的键值对数量和底层的 bucket 数量得到。如果负载因子过大，说明哈希冲突严重；如果负载因子过小，说明键值对过于分散，没有有效利用内存。而后者这个情况一般会出现在 map 被大量删除键值对后出现。

> 负载因子这个概念，在采用了相同方法实现的哈希表中是通用的，比如 redis。

4. 当负载因子超过6.5时，说明平均一个 bucket 里面存储了超过6.5个键值对，会触发 rehash，包括对 bucket 数组进行扩容，申请更多的 bucket 并且重新组织所有的键值对。
5. 除了负载因子过高这种情况外，如果通过 overflow 组织的 bucket 数量达到$$2^{min(15, B)}$$时，也会触发 bucket 数组的扩容。因为这种情况说明哈希冲突非常严重，bucket 链表长度过长，可能影响读写效率。
6. 扩容分为两种：增量扩容和等量扩容。

    - 增量扩容是这样的：oldbuckets 指针指向即将要替换的那个老 bucket 数组，创建一个长度等于老 bucket 数组的两倍的新 bucket 数组。如果 map 存储的数据量极其大，那么这次扩容并不会将所有 bucket 全部写入新的数组，而是在每次读写的时候向新的数组写入两个 bucket，直到旧的数组的 bucket 的数据全部搬到新的数组里面之后 释放旧数组的内存空间。
    - 等量扩容是为了应对负载因子过低这种情况的，它会重新组织 bucket，回收没有用到的 bucket，加快查询速度。

> 注意，如果旧数组内还有 bucket，查询的时候都会优先进旧的 bucket 进行查询。

9. 对于增删改查来说，本质都是根据键值找到正确的 bucket 和对应的 value。第一步是计算键值的哈希值，得到的哈希值的低位与 `hmap.B` 取模得到 bucket 在 buckets 数组内的位置，哈希值的高位用于在 bucket 内的 tophash 数组查找对应的下标（一个 bucket 找不到的话会继续沿着 bucket 链表继续找下去）。

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

10. 注意，如果 map 处于 bucket 搬迁的过程中，添加/更新键值对也会和查询一样，从旧的 bucket 数组开始查，但是最终如果是添加而不是更新键值对的话，添加一定是添加到新的 bucket 数组中。
11. 以上的内容都没有提到的是 hmap 的 extra 字段。它是一个可选字段，当 map 的键值对全部不是指针类型时启用，以避免触发 gc 时扫描整个 map 降低 gc 的速度。这些在注释中都说了，但是有一点没有说全：如何解决`bmap.overflow`是个指针？

``` go
// src/cmd/compile/reflectdata/reflect.go
// MapBucketType 为 map 创建一个给定类型的 bucket
// MapBucketType makes the map bucket type given the type of the map.
func MapBucketType(t *types.Type) *types.Type {
	if t.MapType().Bucket != nil { // 复用
		return t.MapType().Bucket
	}
	
	...
	
	// If keys and elems have no pointers, the map implementation
	// can keep a list of overflow pointers on the side so that
	// buckets can be marked as having no pointers.
	// Arrange for the bucket to have no pointers by changing
	// the type of the overflow field to uintptr in this case.
	// See comment on hmap.overflow in runtime/map.go.
	otyp := types.Types[types.TUNSAFEPTR]
	if !elemtype.HasPointers() && !keytype.HasPointers() {
		otyp = types.Types[types.TUINTPTR]
	}
	overflow := makefield("overflow", otyp)
	field = append(field, overflow)
	
	...
	return bucket
}
```

看注释，在 map 的键值都不是指针的情况下，`hmap.overflow`就是 uintptr 类型（一个数值类型而不是指针类型）而不是指针类型。

> 关于 gc（垃圾回收）机制，以后会写。

### * 参考链接

[CSDN | golang map 底层实现源码解析](https://blog.csdn.net/Jeff_fei/article/details/134052696)