大家好！我是 Jishan Bhattacharya，今年夏天我有幸作为 Qdrant 2024 夏日编程活动的一员，在 Qdrant 实习。在 Andrey Vasnetsov 的指导下，我深入研究了性能优化领域，专注于利用 WebAssembly (WASM) 改进向量可视化。在本文中，我将分享我在这次充满学习、实验和编码冒险的旅程中的见解、挑战和成就。
项目概述
Qdrant 是一个强大的向量数据库和搜索引擎，旨在存储向量数据并执行相似性搜索和聚类等任务。其突出特点之一是能够在二维空间中可视化高维向量。然而，现有实现面临性能瓶颈，尤其是在扩展到大型数据集时。我的任务是通过利用基于 WASM 的解决方案进行可视化过程中的降维来解决这一挑战。
学习与挑战
我们选择的工具是 Rust，与 WASM 结合使用，并且我们采用了 t-SNE 算法进行降维。对于不熟悉的人来说，t-SNE (t-Distributed Stochastic Neighbor Embedding) 是一种通过将高维数据投影到二维或三维来帮助可视化高维数据的技术。它主要分为两个步骤
计算成对相似度：此步骤涉及计算原始高维空间中每对数据点之间的相似度。
迭代优化：第二步是迭代的，通过梯度下降来细化嵌入。在此，第一步中的相似度矩阵起着至关重要的作用。
一开始，Andrey 交给我的任务是用 Rust 重写现有的 t-SNE JavaScript 实现，并在过程中引入多线程。使用 Vite 设置 WASM 进行多线程执行并非易事，但努力得到了回报。结果表明，Rust 实现的性能优于单线程的 JavaScript 版本，尽管它在处理大型数据集时仍然存在困难。
接下来是进一步优化算法的挑战。t-SNE 第一步的一个关键方面是找到每个数据点的最近邻，这需要一种高效的数据结构。我选择了一种 Vantage Point Tree（也称为 Ball Tree）来加速此过程。至于第二步，虽然它本质上是顺序执行的，但仍有改进的空间。我引入了 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 增强的向量可视化功能将如何造福全球用户。
感谢您与我一同踏上这次编码冒险。希望我的旅程对您有所启发，期待未来与您分享更多精彩的项目。编程愉快！
感谢您与我一同踏上这次编码冒险。希望我的旅程对您有所启发，期待未来与您分享更多精彩的项目。编程愉快！
此页面有用吗？
是