Nicksxs's Blog

What hurts more, the pain of hard work or the pain of regret?

之前做了个简单的铺垫,作为大模型应用技术领域非常重要的一环,向量数据库我们在前面有做一些引导性的介绍,其中的索引技术,
而在众多向量数据库比较有代表性的 Milvus,这边我们来尝试安装 Milvus 初体验一下
因为只是初体验,不作为生产环境使用,所以就用最简单的方式,Docker单机部署的方式
首先需要需要有Docker环境
确认下 docker 命令可执行
然后拉取启动脚本

1
2
wget https://raw.githubusercontent.com/milvus-io/milvus/master/scripts/standalone_embed.sh
bash standalone_embed.sh start

启动过程中需要注意一些问题,这也是有点想吐槽的,这个官方的启动脚本竟然都不是稳定成功的,最开始就是失败的,后面重新删除拉下来的镜像再启动就好了
并且官方提供的demo python版本的示例也是有问题的
因为主要是java的缘故,就用了java的sdk来尝试
只是我们可以先运行一个ui工具

1
docker run -p 8000:3000 -e MILVUS_URL={milvus server IP}:19530 zilliz/attu:v2.4


这里就能看到运行情况
然后我们运行个简单的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
package MilvusDemo;

import com.google.gson.Gson;
import com.google.gson.JsonObject;
import com.google.gson.JsonParser;
import io.milvus.v2.client.ConnectConfig;
import io.milvus.v2.client.MilvusClientV2;
import io.milvus.v2.common.DataType;
import io.milvus.v2.common.IndexParam;
import io.milvus.v2.service.collection.request.AddFieldReq;
import io.milvus.v2.service.collection.request.CreateCollectionReq;
import io.milvus.v2.service.index.request.CreateIndexReq;
import io.milvus.v2.service.vector.request.InsertReq;

import java.util.ArrayList;
import java.util.List;

/**
* @author shixuesen
* @date 2024/7/21
*/
public class Demo {

public static void main(String[] args) {
ConnectConfig connectConfig = ConnectConfig.builder()
.uri("http://127.0.0.1:19530")
.build();
// 连接配置
MilvusClientV2 clientV2 = new MilvusClientV2(connectConfig);
// define a Collection Schema
CreateCollectionReq.CollectionSchema collectionSchema = clientV2.createSchema();
// add two fileds, id and vector
Integer dim = 5;
// 这里的 CollectionSchema 就类似于mysql的数据库表结构
collectionSchema.addField(AddFieldReq.builder().fieldName("my_id").dataType(DataType.Int64).isPrimaryKey(Boolean.TRUE).autoID(Boolean.FALSE).description("id").build());
collectionSchema.addField(AddFieldReq.builder().fieldName("my_vector").dataType(DataType.FloatVector).dimension(dim).build());

CreateCollectionReq req = CreateCollectionReq
.builder()
.collectionSchema(collectionSchema)
.collectionName("quick_setup")
.dimension(dim).build();
// 通过schema 生成 Collection,就类似于mysql中的表
clientV2.createCollection(req);

// 然后可以对字段创建索引
IndexParam indexParam = IndexParam.builder()
.fieldName("my_id")
.build();
IndexParam vertorIndexParam = IndexParam.builder()
.fieldName("my_vector")
.indexType(IndexParam.IndexType.AUTOINDEX)
.metricType(IndexParam.MetricType.IP)
.build();
List<IndexParam> indexParamList = new ArrayList<>();
indexParamList.add(indexParam);
indexParamList.add(vertorIndexParam);


// 接着创建索引
clientV2.createIndex(CreateIndexReq.builder()
.collectionName("quick_setup")
.indexParams(indexParamList)
.build());
JsonObject jsonObject = JsonParser.parseString("{\"my_id\": 0, \"my_vector\": [0.3580376395471989, -0.6023495712049978, 0.18414012509913835, -0.26286205330961354, 0.9029438446296592], \"color\": \"pink_8682\"}").getAsJsonObject();
List<JsonObject> jsonData = new ArrayList<>();
jsonData.add(jsonObject);
// 然后插入数据
clientV2.insert(InsertReq.builder().collectionName("quick_setup")
.data(jsonData).build());

// 插入之后我们想进行查询,就用向量进行搜索,不过要先加载Collection
clientV2.loadCollection(LoadCollectionReq.builder().collectionName("quick_setup").build());
SearchResp searchResp = clientV2.search(SearchReq.builder()
.collectionName("quick_setup")
.data(Collections.singletonList(new FloatVec(new float[]{0.3580376395471989F, -0.6023495712049978F, 0.18414012509913835F, -0.26286205330961354F, 0.9029438446296592F})))
.topK(10)
.outputFields(Collections.singletonList("*"))
.build()
);
for (List<SearchResp.SearchResult> searchResult : searchResp.getSearchResults()) {
System.out.println(searchResult);
}


}
}

我们用同样的向量进行搜索

1
[SearchResp.SearchResult(entity={my_id=0, $meta={"color":"pink_8682"}, my_vector=[0.35803765, -0.6023496, 0.18414013, -0.26286206, 0.90294385]}, score=1.4093276, id=0)]

得出的score就是很高的,只是做了下尝试,官方的示例代码是少得可怜,也不全,很难想象是目前比较热门的向量数据库

最近在迁移一个自己用的mysql实例,发现用 portainer 安装 mysql 一直失败,还以为是配置了自定义端口映射被系统防火墙限制,但后面不映射端口也是不行,一开始查看 journal日志也没什么发现,因为之前在腾讯云的小机器也是正常的部署,所以没觉得是可能会oom,一时间就有点没头绪,结果也是好奇就看了下dmesg,发现里面都是oom,给了1g的内存的ubuntu虚拟机,安装了一两个docker就不行了,不过这里比较重要的就是记录下dmesg 跟 journal日志的这点区别
dmesg 打印了内核的日志缓冲,所以这个跟journal差别的第一点就是一个是个会被刷掉的缓冲区,另一个是记在文件,但更重要的是dmesg是打印的内核日志,而journal是会通过systemd收集日志,journal可以收集内核日志,但是可以进行配置,并且可能会晚于dmesg

而对于这个oom,如果是系统的oom killer,那的确是有可能dmesg会能查看到,而journal看不到
简单记录下,PS:奶娃是有点累,一天都没啥时间了

最近在学习过程中碰到一个比较有意思的Spring特性,就是 SmartLifecycle ,这个可以很轻松的融合进 Spring 生命周期

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public interface SmartLifecycle extends Lifecycle, Phased {
int DEFAULT_PHASE = Integer.MAX_VALUE;

default boolean isAutoStartup() {
return true;
}

default void stop(Runnable callback) {
this.stop();
callback.run();
}

default int getPhase() {
return Integer.MAX_VALUE;
}
}

接口继承了 org.springframework.context.Lifecycleorg.springframework.context.Phased
其中默认实现了 isAutoStartup , 并且默认是返回 true,所以相对于 Lifecycle 能更智能些自动启动
然后 Lifecycle 这个接口就比较简单,只有几个接口

1
2
3
4
5
6
7
public interface Lifecycle {
void start();

void stop();

boolean isRunning();
}

我们可以是实现下这个接口

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
@Component
public class MySmartLifecycle implements SmartLifecycle {

private volatile boolean isRunning;

@Override
public void start() {
System.out.println("my smart life cycle start");
isRunning = true;
}

@Override
public void stop() {
System.out.println("my smart life cycle end");
isRunning = false;
}

@Override
public boolean isRunning() {
return isRunning;
}
}

这个 bean 会在 Spring 启动后被自动调用 start 方法

这个就是在不深入 bean 的生命周期,并且是在 bean 已经都初始化以后调用
同样会在 spring 容器关闭时调用 stop 方法

如果有此类的需求就可以扩展此接口实现
而这个其实是在 spring 生命周期中的 finishRefresh 方法中进行调用

1
2
3
4
5
6
7
8
9
10
protected void finishRefresh() {
this.clearResourceCaches();
this.initLifecycleProcessor();
this.getLifecycleProcessor().onRefresh();
this.publishEvent((ApplicationEvent)(new ContextRefreshedEvent(this)));
if (!NativeDetector.inNativeImage()) {
LiveBeansView.registerApplicationContext(this);
}

}

调用了 LifecycleProcessoronRefresh 方法

1
2
3
4
public void onRefresh() {
this.startBeans(true);
this.running = true;
}

这其中就会调用 start 方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
private void startBeans(boolean autoStartupOnly) {
// 获取这些bean
Map<String, Lifecycle> lifecycleBeans = this.getLifecycleBeans();
Map<Integer, LifecycleGroup> phases = new TreeMap();
lifecycleBeans.forEach((beanName, bean) -> {
if (!autoStartupOnly || bean instanceof SmartLifecycle && ((SmartLifecycle)bean).isAutoStartup()) {
int phase = this.getPhase(bean);
((LifecycleGroup)phases.computeIfAbsent(phase, (p) -> {
return new LifecycleGroup(phase, this.timeoutPerShutdownPhase, lifecycleBeans, autoStartupOnly);
})).add(beanName, bean);
}

});
if (!phases.isEmpty()) {
phases.values().forEach(LifecycleGroup::start);
}

}

会先判断 isAutoStartup,然后将不同周期加入分组,然后再循环调用start

java的函数式接口是java8引入的很重要的特性,也让日常代码有了比较大的风格转变
这里介绍下BiFunction,
BiFunction的代码很短

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
@FunctionalInterface
public interface BiFunction<T, U, R> {

/**
* Applies this function to the given arguments.
*
* @param t the first function argument
* @param u the second function argument
* @return the function result
*/
R apply(T t, U u);

/**
* Returns a composed function that first applies this function to
* its input, and then applies the {@code after} function to the result.
* If evaluation of either function throws an exception, it is relayed to
* the caller of the composed function.
*
* @param <V> the type of output of the {@code after} function, and of the
* composed function
* @param after the function to apply after this function is applied
* @return a composed function that first applies this function and then
* applies the {@code after} function
* @throws NullPointerException if after is null
*/
default <V> BiFunction<T, U, V> andThen(Function<? super R, ? extends V> after) {
Objects.requireNonNull(after);
return (T t, U u) -> after.apply(apply(t, u));
}
}

默认的方法就跟普通的FunctionalInterface一样,就有一个apply方法,只是这里的特殊点有两个

返回值作为参数

这个BiFunction有三个泛型参数,T,U跟R,而这个R其实是具体方法的返回值
比如我们简单实现一个字符串拼接

1
2
BiFunction<String, String, String> biDemo = (s1, s2) -> s1 + s2;
System.out.println(biDemo.apply("hello ", "world"));

apply返回的就是参数R

andThen

这个方法是可以让结果再调用传入的方法,并返回结果

1
2
Function<String, Integer> funcDemo = String::length;
System.out.println(biDemo.andThen(funcDemo).apply("hello ", "world"));

定义了个函数接口,并且给了实现,就是字符串获取长度
然后传给biDemo,这样就可以输出拼接后的字符串长度

组合使用

1
2
3
public <T1, T2, R1, R2> R2 combination(T1 t1, T2 t2, BiFunction<T1, T2, R1> biFunction, Function<R1, R2> function) {
return biFunction.andThen(function).apply(t1, t2);
}

这样就把前面的两个方法串起来了

结合AI写的一篇HNSW的介绍文章,算是向量数据库中比较核心的算法

1. 引言

向量数据库在当今人工智能和机器学习领域扮演着越来越重要的角色。随着数据规模的不断扩大和应用场景的日益复杂,传统的数据库系统已经难以满足高维向量数据的快速检索需求。在这个背景下,近似最近邻(Approximate Nearest Neighbor, ANN)搜索问题成为了一个热点研究方向。

HNSW(Hierarchical Navigable Small World)算法是解决ANN问题的一种高效方法。它通过构建一个多层次的图结构,结合小世界网络的特性,实现了对高维向量数据的快速、精确检索。本文将深入浅出地介绍HNSW算法的核心思想、工作原理以及实际应用。

2. HNSW算法的核心思想

HNSW算法的核心思想可以概括为三个关键点:分层结构、小世界图和近似搜索。

分层结构

HNSW采用了一种多层次的图结构。想象一下,如果我们要在一个大城市中找到一个特定的地址,我们通常会先看城市地图,然后逐步缩小范围到区、街道,最后定位到具体门牌号。HNSW的分层结构就类似于这种由粗到细的搜索过程。这个就是之前介绍跳表的目的,就是现在稀疏的结构里可以快速定位,然后再往下层进行搜索,提高了搜索效率

小世界图

小世界网络是一种特殊的图结构,它具有较短的平均路径长度和较高的聚类系数。在HNSW中,每一层都是一个小世界图。这种结构使得在图中的任意两点之间都存在一条相对较短的路径,大大提高了搜索效率。

近似搜索

与传统的KNN(K-Nearest Neighbors)算法不同,HNSW通过牺牲一小部分精度来换取显著的速度提升。它不保证一定能找到真正的最近邻,但可以以极高的概率找到足够接近的点,而且搜索速度要快得多。

3. HNSW的工作原理

数据结构:多层图的构建过程

  1. HNSW从底层开始构建,每个数据点都会出现在底层。
  2. 对于每个新插入的点,算法会随机决定它是否应该出现在上一层。这个过程一直持续到某一层,该点不再被选中。
  3. 在每一层,新点会与该层的其他点建立连接,形成小世界图结构。

搜索过程:自顶向下的贪婪搜索

  1. 搜索从最顶层开始,选择一个随机起点。
  2. 在当前层进行贪婪搜索,不断移动到离目标更近的邻居。
  3. 当在当前层无法找到更近的点时,下降到下一层继续搜索。
  4. 重复这个过程直到达到底层,得到最终结果。

插入新向量的过程

  1. 确定新向量应该出现在哪些层。
  2. 从顶层开始,在每一层执行类似于搜索的过程,找到适合连接的邻居点。
  3. 建立连接,同时可能需要删除一些现有连接以维持图的结构特性。

    论文中的算法是这样的
  • 红色节点表示新插入的数据点。在这个例子中,新节点被插入到了层级0和层级1。

  • 红色实线表示新建立的同层连接。新节点与其邻近节点建立了连接。

  • 红色虚线表示新建立的跨层连接。新节点在不同层级之间建立了连接。

  • 绿色虚线箭头表示插入过程的路径。这条路径展示了算法如何从顶层开始,逐层下降,最终确定新节点的插入位置。

  • 其他颜色的节点和灰色的连接线表示原有的HNSW结构。

  • 插入过程从顶层开始,沿着绿色虚线所示的路径向下搜索。

  • 在每一层,算法都会寻找最近的邻居节点,并决定是否在该层插入新节点。

  • 在本例中,新节点被插入到了层级0(基础层)和层级1。这是因为HNSW使用概率方法来决定节点应该出现在哪些层级。

  • 插入后,新节点与其邻近节点建立连接(红色实线),以维持图的小世界特性。

  • 同时,新节点也与其在不同层级的对应节点建立跨层连接(红色虚线),以确保层级之间的快速访问。

4. HNSW的性能分析

时间复杂度分析

  • 搜索时间复杂度: O(log N),其中N是数据点的总数。
  • 插入时间复杂度: 平均情况下为O(log N)。

空间复杂度分析

  • 空间复杂度: O(N log N),因为上层节点数量呈指数衰减。

与其他ANN算法的比较

相比LSH(Locality-Sensitive Hashing)和Annoy等算法,HNSW在大多数场景下都能提供更好的查询性能和更高的准确率。然而,HNSW的内存消耗相对较高,这是它的一个潜在缺点。

5. HNSW的实际应用

在推荐系统中的应用

HNSW可以用于快速检索相似用户或物品,提高推荐系统的响应速度和准确性。例如,在音乐推荐中,可以用HNSW快速找到与用户喜好相似的歌曲。

在图像检索中的应用

在大规模图像数据库中,HNSW可以实现快速的相似图像搜索。这在图像搜索引擎、视觉商品搜索等场景中非常有用。

在自然语言处理中的应用

HNSW可以用于词嵌入或句子嵌入的快速检索,支持语义相似度计算、文本分类等任务。

6. HNSW的优化和变种

参数调优技巧

  • 层数选择:影响搜索速度和内存使用
  • 每层连接数:影响搜索准确度和构建时间
  • 候选集大小:影响搜索质量和速度的平衡

常见的HNSW变种算法介绍

  • NSW-G:改进了图的构建方法,提高了搜索效率
  • HCNNG:结合了层次聚类,提高了在某些数据集上的性能

7. 实现HNSW的挑战与解决方案

大规模数据集的处理

  • 使用外部存储和分批处理
  • 采用压缩技术减少内存占用

并行化和分布式实现

  • 搜索过程的并行化
  • 分布式索引构建和查询

动态更新和删除操作的处理

  • 软删除技术
  • 定期重建索引

8. 总结与展望

HNSW算法通过其独特的分层小世界图结构,在保证高准确率的同时实现了对高维向量数据的快速检索。它在推荐系统、图像检索、自然语言处理等多个领域都有广泛应用。

未来,向量数据库技术可能会朝着以下方向发展:

  1. 更高效的压缩和索引技术
  2. 更好的动态更新支持
  3. 与深度学习模型的更紧密集成
  4. 针对特定领域的优化变体

随着人工智能和大数据技术的不断发展,HNSW等高效的向量检索算法将在更广阔的应用场景中发挥重要作用。

0%