Nicksxs's Blog

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

最近在学习过程中碰到一个比较有意思的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等高效的向量检索算法将在更广阔的应用场景中发挥重要作用。

因为买了两个NX30Pro,主要是奔着可以刷Openwrt,然后把两个都刷成了ImmortalWrt,结果发现要作为有线中继的话设置还有点麻烦,所以记录下
首先要设置个与主路由相同网段的静态地址,方便管理
在网络-LAN-基本设置-协议设置成“静态地址”
然后IPv4地址就是刚才说的静态地址,可以设个好记的
子网掩码就默认的,255.255.255.0,
IPv4网关就是主路由地址,DNS也设置成主路由地址
基础设置改成忽略此接口-不提供DHCP服务,由主路由提供
然后在高级设置中将IPv6的 路由通告服务和DHCPv6服务跟NDP代理禁用掉,
物理设置中勾选桥接接口
目前我是这样设置可以作为有线中继连通网络了,后续有变化继续更新

在学习向量数据库的时候,发现检索的算法 HNSW 是个比较重要且核心的概念,直接学习(面向小白)可能有一定的门槛,所以我们先通过常见算法的跳表来做个引入
跳表的前置基础就是最常见的序列结构之一的链表,链表的特点是添加插入元素效率非常高,查询检索则需要线性复杂度,比如Java中的hashmap,在jdk1.8以后就把
单纯链表的结构改成了链表和红黑树结合的方式,因为当链表比较长的时候,线性时间复杂度也是个比较慢的方法相比对数时间复杂度,而对于链表,也有直接在它基础
优化而来的跳表结构,跳表是在链表的基础上引入了分层的概念,通过投硬币概率来决定是否生成新层,先用比较通俗的话来讲一下我的理解
因为链表查找只能从前往后一个一个找(单向链表),那么有没有办法可以跳过一些,加速我的查找,那么引入了分层的结构,在更上层以更稀疏的数据链表来索引数据,
举个例子,我原来是一个

1
1 --> 2 --> 3 --> 4 --> 5 --> 6 --> 7 --> 8 --> 9 

这样的链表,我要查找8个元素是否存在,那我需要查找八次才能找到
如果我把结构改成

1
2
3
1 --------------> 4 --------------> 7 ---------> null 
| | |
1 --> 2 --> 3 --> 4 --> 5 --> 6 --> 7 --> 8 --> 9 --> null

变成这样的结构,我现在第一层找最后一个比8小的元素,就是7,然后再到下一层查找,这样我的查找路径就是 1 --> 4 --> 7 --> 8 速度加快了一倍
直观来说这样是能够提升很多查询效率,但是具体怎么实现我们也来看一下
首先定义个简单的Node

1
2
3
4
5
6
7
8
9
public class Node {
public int data = -1;

public Node[] forwards;

public Node(int level) {
forwards = new Node[level];
}
}

接下去是SkipList的主体结构

1
2
3
4
5
6
7
8
public class SkipList {
private static final int MAX_LEVEL = 16;

private int currentLevel = 0;

private Node head = new Node(MAX_LEVEL);

private Random random = new Random();

包含最大层数,当前层数,头结点,跟随机值
生成随机层数参考了redis的zset实现方法

1
2
3
4
5
6
7
private int generateRandomLevel() {
// 参考redis sorted set 实现
int level = 1;
while ((random.nextInt() & 0xFFFF) < (0.25 * 0xFFFF))
level += 1;
return Math.min(level, MAX_LEVEL);
}

接下去先看下

插入元素

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
public void insert(int value) {
int level = generateRandomLevel();
if (level >= currentLevel) {
currentLevel = level;
}

Node newNode = new Node(level);
newNode.setData(value);
Node[] update = new Node[level];

Arrays.fill(update, head);

Node p = head;

for (int i = level - 1; i >= 0; --i) {
// 找到应该处在的位置,把前一元素记录为待更新
while (p.forwards[i] != null && p.forwards[i].data < value) {
p = p.forwards[i];
}
// 对应这一层,更新新的位置p
update[i] = p;
}

// 每一层都处理前后链接
for (int i = 0; i < level; i++) {
newNode.forwards[i] = update[i].forwards[i];
update[i].forwards[i] = newNode;
}
}

看下图片演示,类似于链表的插入,但是需要处理每一层的前后链接

查找元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public Node search(int value) {
Node p = head;
// 逐层找到比目标元素小的最后一个元素
// 然后再往下一层找
for (int i = currentLevel - 1; i >= 0 ; i--) {
while (p.forwards[i] != null && p.forwards[i].data < value) {
p = p.forwards[i];
}
}
// 此时如果前一元素就是目标元素就返回该元素
if (p.forwards[0] != null && p.forwards[0].data == value) {
return p.forwards[0];
} else {
return null;
}
}

也可以看下图里的演示,按红色的线寻找元素

删除元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public void delete(int value) {
Node[] update = new Node[currentLevel];
Node p = head;
// 找到待删除元素的前一元素
for (int i = currentLevel - 1; i >= 0; i--) {
while (p.forwards[i] != null && p.forwards[i].data < value) {
p = p.forwards[i];
}
update[i] = p;
}
// 判断如果该层有这个元素就更新链接
if (p.forwards[0] != null && p.forwards[0].data == value) {
for (int i = currentLevel - 1; i >= 0; i--) {
if (update[i].forwards[i] != null && update[i].forwards[i].data == value) {
update[i].forwards[i] = update[i].forwards[i].forwards[i];
}
}
}
}

删除操作就类似于插入操作。了解了跳表原理以后其实HNSW就是个在空间层面的跳表

0%