简介
大家好！我是 Jishan Bhattacharya，今年夏天我很荣幸作为 Qdrant 2024编程之夏项目的一部分，在 Qdrant 实习。在 Andrey Vasnetsov 的指导下，我深入性能优化领域，专注于使用 WebAssembly (WASM) 增强向量可视化。在这篇文章中，我将分享我这段充满学习、实验和大量编码冒险旅程中的见解、挑战和成就。
项目概述
Qdrant 是一个强大的向量数据库和搜索引擎，旨在存储向量数据并执行相似性搜索和聚类等任务。其突出特点之一是能够在二维空间中可视化高维向量。然而，现有的实现面临性能瓶颈，尤其是在扩展到大型数据集时。我的任务是通过利用基于 WASM 的解决方案进行可视化过程中的降维来解决这个挑战。
学习与挑战
我们选择的工具是 Rust，搭配 WASM，并采用 t-SNE 算法进行降维。对于不熟悉的人来说，t-SNE（t-分布随机近邻嵌入）是一种通过将高维数据投影到二维或三维空间来帮助可视化高维数据的技术。它主要分两步操作：
计算成对相似度：这一步涉及计算原始高维空间中每对数据点之间的相似度。
迭代优化：第二步是迭代的，通过梯度下降来优化嵌入。在这里，第一步中的相似度矩阵起着至关重要的作用。
一开始，Andrey 交给我的任务是用 Rust 重写 t-SNE 现有的 JavaScript 实现，并在其中引入多线程。使用 Vite 为多线程执行设置 WASM 并非易事，但努力得到了回报。最终的 Rust 实现优于单线程的 JavaScript 版本，尽管它在处理大型数据集时仍然存在问题。
接下来是进一步优化算法的挑战。t-SNE 第一步的一个关键方面是为每个数据点找到最近邻居，这需要高效的数据结构。我选择使用视点树（也称为球树）来加速这个过程。至于第二步，虽然它本质上是顺序的，但仍有改进的空间。我结合了 Barnes-Hut 近似来加速梯度计算。这种方法近似计算低维空间中点之间的力，使过程更高效。
举例来说，想象将一个二维空间分成多个象限，每个象限包含多个点。每个象限再次被细分为四个象限。如此循环，直到每个点都属于一个单元格。
Barnes-Hut 近似
然后我们计算每个单元格的质心，如图中蓝色圆圈所示。现在假设我们想要找出作用在红点上的所有力，由虚线表示。Barnes Hut 的近似法指出，对于足够远的点，我们不是计算每个单独点的力，而是使用质心作为代理，显著减少计算量。这在图中由蓝色虚线表示。
这些优化带来了显著的差异——Barnes-Hut t-SNE 对于 10,000 个向量来说比精确 t-SNE 快了八倍。
精确 t-SNE - 总耗时：884.728 秒
Barnes-Hut t-SNE - 总耗时：104.191 秒
尽管取得了这些改进，算法的第一步仍然是瓶颈，导致明显的延迟和空白屏幕。我尝试了近似最近邻算法，但性能提升微乎其微。在与我的导师商议后，我们决定在服务器端计算最近邻，将距离矩阵直接传递给可视化过程，而不是原始向量。
在等待距离矩阵 API 准备就绪的同时，我探索了进一步的优化。我观察到工作线程以特定间隔向主线程发送结果进行渲染，由于序列化和反序列化导致不必要的延迟。
序列化和反序列化开销
为了解决这个问题，我实现了一个 SharedArrayBuffer，允许主线程即时访问工作线程所做的更改。这一改变带来了显著的改进。
此外，之前的架构由于工作线程发送结果的固定间隔而导致动画卡顿。
以前采用固定间隔的架构
我引入了“按需渲染”的方法，即当主线程准备好渲染下一个结果时，它会向工作线程发送信号。这创建了更流畅、响应更快的动画。
当前采用按需渲染的架构
完成这些优化后，最后一步是通过创建一个 Node.js 包来结束项目。这个包暴露了必要的接口，用于接收距离矩阵、执行计算并返回结果，使解决方案易于集成到各种项目中。
改进空间
在回顾这段变革之旅时，仍有一些领域可以改进和进一步增强：
有效负载解析：当请求大量向量时，在主线程上解析有效负载可能会导致用户界面无响应。实现更快的解析器可以缓解此问题。
直接数据请求：允许工作线程直接请求数据可以消除主线程的初始数据传输，从而加快整个过程。
图表库优化：分析表明，近 80% 的时间都花在了 Chart.js 的更新函数上。切换到 WebGL 加速的图表库可以显著提高性能，特别是对于大型数据集。
分析结果
结论
参加 Qdrant 2024编程之夏是一次非常有意义的经历。我借此机会拓展了我的编码技能边界，同时探索了 Rust 和 WebAssembly 等新技术。我非常感谢我的导师和整个 Qdrant 团队的指导和支持，他们让这段旅程既有教育意义又充满乐趣。
这次经历不仅磨练了我的技术技能，也点燃了我对优化实际应用性能的更深热情。我很高兴能将我所学到的知识和技能应用于未来的项目，并期待看到 Qdrant 增强的向量可视化功能将如何造福全球用户。
这次经历不仅磨练了我的技术技能，也点燃了我对优化实际应用性能的更深热情。我很高兴能将我所学到的知识和技能应用于未来的项目，并期待看到 Qdrant 增强的向量可视化功能将如何造福全球用户。
感谢您与我一起踏上这段编码冒险之旅。希望您在我的旅程中有所收获，我期待着未来与您分享更多激动人心的项目。祝您编码愉快！