Create Ann Index

Ann Index Manager

• 在 Storage Daemon 中设计一个VectorIndexManager单例对整个 Storaged 中的 Ann Index 进行管理。
• Ann Index 的生命周期：
  • 创建：通过 CreateTagAnnIndex 请求创建 Ann Index。

    除非删除，否则会一直在内存中维护，在退出时需要持久化到磁盘，同时重启系统后需要从磁盘中加载已经存在的 Ann Index。

  • 使用：在查询时使用 Ann Index 进行加速。
  • 删除：通过 DropTagAnnIndex 请求删除 Ann Index。
  • 更新：通过 UpdateTagAnnIndex 请求更新 Ann Index。

class VectorIndexManager final {
 public:
  static VectorIndexManager& getInstance();
  // Initialize the manager with necessary dependencies
  Status init(meta::IndexManager* indexManager, std::string annIndexPath);
  // Start the manager (background tasks, cleanup threads, etc.)
  Status start();
  // Stop the manager gracefully
  Status stop();
  // Wait until the manager stops (similar to StorageServer::waitUntilStop)
  void waitUntilStop();
  // Notify the manager to stop (used for signal handling)
  void notifyStop();
  // Create a vector index for a specific partition and index ID
  Status createOrUpdateIndex(GraphSpaceID spaceId,
                             PartitionID partitionId,
                             IndexID indexId,
                             const std::shared_ptr<meta::cpp2::AnnIndexItem>& indexItem);
  // Get an existing vector index
  StatusOr<std::shared_ptr<AnnIndex>> getIndex(GraphSpaceID spaceId,
                                               PartitionID partitionId,
                                               IndexID indexId);
  // Remove a vector index
  Status removeIndex(GraphSpaceID spaceId, PartitionID partitionId, IndexID indexId);
  // Get all managed indexes for a partition
  std::vector<std::shared_ptr<AnnIndex>> getIndexesByPartition(GraphSpaceID spaceId,
                                                               PartitionID partitionId);
  // Check if an index exists
  bool hasIndex(GraphSpaceID spaceId, PartitionID partitionId, IndexID indexId) const;
  // Rebuild an index (called during BuildVectorIndexTask)
  Status rebuildIndex(GraphSpaceID spaceId,
                      PartitionID partitionId,
                      IndexID indexId,
                      const std::shared_ptr<meta::cpp2::AnnIndexItem>& indexItem);
};

Storage 中 VectorIndexManager 的传递

1. 在 StorageServer::start() 方法创建了 StorageEnv 实例并将 env 传递给 AdminTaskManager
2. 初始化 Ann Index Manager 实例
3. 然后将 Ann Index Manager 实例与 StorageEnv 关联
4. StorageEnv 结构定义
   • 我们增加了一个新的成员变量 annIndexMan_，用于管理 ANN 索引。
   • 需要在 Storaged 启动时初始化

// StorageServer 启动
void StorageServer::start(){
  // 初始化各个组件
  schemaMan_ = meta::ServerBasedSchemaManager::create(metaClient_.get());
  indexMan_ = meta::ServerBasedIndexManager::create(metaClient_.get());
  kvstore_ = getStoreInstance();
 
  // 创建 StorageEnv 并设置各个组件
  env_ = std::make_unique<storage::StorageEnv>();
  env_->kvstore_ = kvstore_.get();
  env_->indexMan_ = indexMan_.get();
  env_->schemaMan_ = schemaMan_.get();
  env_->rebuildIndexGuard_ = std::make_unique<IndexGuard>();
  env_->metaClient_ = metaClient_.get();
  env_->verticesML_ = std::make_unique<VerticesMemLock>();
  env_->edgesML_ = std::make_unique<EdgesMemLock>();
  env_->adminStore_ = getAdminStoreInstance();
  env_->adminSeqId_ = getAdminStoreSeqId();
}
 
// VectorIndexManager 启动
vectorIndexMgr = std::make_unique<VectorIndexManager>();
vectorIndexMgr->init(storageServer->getIndexMgr());
 
// StorageServer 设置 ANN 索引管理器
storageServer->setEnvAnnIndexMgr(vectorIndexMgr.get());

Ann Index Interface

Ann Index Item

• 通用的 Index Item 是对单个 Schema 的多个 field 的索引定义，同时索引参数只有s2_max_level和s2_max_cells，不能满足 Ann Index 对多个 Schema 同名属性进行索引创建的要求，所以我们设计了新的 Ann Index Item。

• Ann Index Item 是对多个 Schema 的同名属性进行索引创建的定义，包含了所有需要索引的 Schema 的信息。同时通过一个list<binary>来存储 ann index 创建的参数。

  ann index params:
  [IVF/*ann type*/, 128 /*dim*/, L2/*metric type*/, 3/*nlist*/, 3/*train size*/]
  [HNSW/*ann type*/, 128 /*dim*/, L2/*metric type*/, 16/*max degree*/, 200/*ef construction*/, 100000/*max elements*/]

struct IndexItem {
    1: common.IndexID       index_id,
    2: binary               index_name,
    3: common.SchemaID      schema_id
    4: binary               schema_name,
    5: list<ColumnDef>      fields,
    6: optional binary      comment,
    7: optional IndexParams index_params,
}
 
struct AnnIndexItem {
    1: common.IndexID           index_id,
    2: binary                   index_name,
    3: binary                   prop_name,
    4: list<common.SchemaID>    schema_ids,
    5: list<binary>             schema_names,
    6: list<ColumnDef>          fields,
    7: optional binary          comment,
    8: optional list<binary>    ann_params,         // ANN specific parameters
}

Ann Index Request & Response

• 之前的 CreateTagIndexReq 只支持单个 Schema 的索引创建，而 Ann Index 需要支持多个 Schema 的同名属性进行索引创建，所以我们设计了新的 CreateTagAnnIndexReq。

struct CreateTagAnnIndexReq {
    1: common.GraphSpaceID      space_id,
    2: binary                   index_name,
    3: list<binary>             tag_names,
    4: IndexFieldDef            field,
    5: bool                     if_not_exists,
    6: optional binary          comment,
    7: optional list<binary>    ann_params,
}

• Storaged 需要通过 meta client 执行listTagAnnIndexes和listEdgeAnnIndexes获取 Ann 索引信息，Ann Index 的条目由 Ann Index Item 存储与之前的 Index Item 结构不同，所以设计新的 Resp。

struct ListTagAnnIndexesResp {
    1: common.ErrorCode         code,
    2: common.HostAddr          leader,
    3: list<AnnIndexItem>	items,
}
struct ListEdgeAnnIndexesResp {
    1: common.ErrorCode         code,
    2: common.HostAddr          leader,
    3: list<AnnIndexItem>    	items,
}

Create Ann Index Syntax Design

CREATE TAG ANNINDEX <index_name> ON <tag_name_list>::(<field_name>) [IF NOT EXISTS] ann_index_params}[COMMENT '<comment>']

ann_index_params:
{ANNINDEX_TYPE: "IVF", DIM:128, METRIC_TYPE:"L2", NLIST:3, TRAINSIZE:3}
{ANNINDEX_TYPE: "HNSW", DIM:128, METRIC_TYPE:"L2", MAXDEGREE:15, EFCONSTRUCTION:200, MAXELEMENTS:10000}

Create Ann Index Plan

1. Graphd 生成 Start->CreateTagAnnIndex->SubmitJob 的计划
2. 执行时，metad 先在内部创建 Ann 索引条目，创建成功后，会进行 AdminJob 的提交
3. Metad 将 Job 的参数打包传给 Storaged 的 AdminTask，Storaged 通过内部的 AdminTaskManager 处理这些任务，完成任务。这里涉及到分布式的时序问题：

   Meta Client 缓存更新机制：Storage 节点的 IndexManager 通过 MetaClient 获取索引信息，但 MetaClient 的缓存是通过心跳周期更新的:

   • 时序问题：Meta 服务创建索引后，Storage 节点需要等待下一个心跳周期才能看到新索引
   • 同步问题：getTagAnnIndex 直接从缓存读取，如果缓存还没更新就会返回 IndexNotFound

• 所以我们在 Storaged 中使用重试机制，如果多次重试失败直接向 meta server 请求数据强制刷新缓存

Storaged BuildTagVectorIndexTask Plan

对每个 Partition 做相同的操作：

1. 扫描 KVStore(RocksDB)中的所有符合 property name 的 vector 属性的数据
2. 将 Vertex ID/Edge Type 与 VectorID 存入 KVStore 的 id-vid column family

   Vertex ID 是 std::string 类型，这里通过 hash 计算 VectorID，所以需要存入两份映射VectorID->VertexID和VertexID->VectorID

3. 通过这些数据构建内存中的 Ann Index