barrel_vectordb_diskann (barrel_vectordb v2.1.2)
View SourceDiskANN Vamana Graph Implementation
Implements the Vamana graph algorithm from the DiskANN paper with: - Two-pass construction (alpha=1.0 then alpha>1.0) - RobustPrune for alpha-RNG pruning - GreedySearch for graph traversal - FreshVamana insert/delete for streaming updates - Consolidate deletes for batch cleanup - BeamSearch with PQ for SSD-resident search
The alpha parameter (>1) is critical for maintaining graph quality under streaming updates. It keeps more long-range edges which are essential for fast convergence during search.
Summary
Functions
Build index from a list of {Id, Vector} pairs using two-pass Vamana
Close the index and flush to disk For V2 format: writes header and PQ state, closes RocksDB Does NOT use term_to_binary for the entire index
Trigger manual compaction of hot layer to disk
Consolidate deleted nodes (batch cleanup) This repairs the graph by removing edges to deleted nodes and adding new edges to maintain navigability
Lazy delete - marks node as deleted
Deserialize index from binary
Get vector by ID (uses cache for disk mode)
Core search algorithm - optimized version Uses separate candidate queue and result set for efficiency Returns ({SortedResults, VisitedSet})
Get index info
Insert a new vector (FreshVamana algorithm)
Batch insert multiple vectors efficiently Inserts all vectors first, then builds graph edges in one pass. Much more efficient than calling insert/3 repeatedly.
Check if consolidation is needed (threshold-based) Returns true if deleted count exceeds 10% of active size
Create a new empty DiskANN index Options: - dimension: Vector dimension (required) - r: Max out-degree (default: 64) - l_build: Build search width (default: 100) - l_search: Query search width (default: 100) - alpha: Pruning factor (default: 1.2) - distance_fn: cosine | euclidean (default: cosine) - assume_normalized: Skip norm computation for cosine (default: false) - storage_mode: memory | disk (default: memory) - base_path: Path for disk storage (required if storage_mode=disk) - cache_max_size: Max vectors in LRU cache (default: 10000) - hot_layer: Enable hot memory layer for fast writes (default: false) - hot_max_size: Maximum vectors in hot layer before compaction (default: 10000) - hot_compaction_threshold: Trigger compaction at this % of max (default: 0.8) - quantization: none | pq | turboquant | subspace_turboquant (default: none) - tq_bits: TurboQuant bits per component (default: 3, when quantization=turboquant or subspace_turboquant) - tq_seed: TurboQuant random seed (default: 42) - tq_m: Number of subspaces for subspace_turboquant (default: auto, based on dimension)
Open an existing DiskANN index from disk For V2 format: O(1) startup with lazy graph loading For V1 format: Migrates to V2 or loads from diskann.index
Open with options: crypto => none | #{key := <<_:256>>, env => rocksdb env}. The key encrypts the flat files; the env (or one minted from the key) covers the diskann_ids RocksDB.
RobustPrune: Select R neighbors for node P using alpha-RNG pruning V = candidate neighbors Alpha > 1 keeps more long-range edges Optimized: cache distance computations
Search for K nearest neighbors
Search with options Options: - l_search: Search beam width (default: from config) - rerank_factor: Multiplier for rerank candidates (default: 4)
Serialize index to binary (for barrel_vectordb_index behaviour)
Get index size (excluding deleted)
Force sync to disk
Types
-type diskann_config() :: #diskann_config{r :: pos_integer(), l_build :: pos_integer(), l_search :: pos_integer(), alpha :: float(), dimension :: pos_integer(), distance_fn :: cosine | euclidean, assume_normalized :: boolean()}.
-type diskann_index() :: #diskann_index{config :: #diskann_config{r :: pos_integer(), l_build :: pos_integer(), l_search :: pos_integer(), alpha :: float(), dimension :: pos_integer(), distance_fn :: cosine | euclidean, assume_normalized :: boolean()}, size :: non_neg_integer(), medoid_id :: binary() | undefined, medoid_int_id :: non_neg_integer() | undefined, nodes :: #{binary() => diskann_node()}, nodes_int :: #{non_neg_integer() => [non_neg_integer()]}, id_to_idx :: #{binary() => non_neg_integer()}, idx_to_id :: #{non_neg_integer() => binary()}, id_db :: rocksdb:db_handle() | undefined, id_cf_fwd :: rocksdb:cf_handle() | undefined, id_cf_rev :: rocksdb:cf_handle() | undefined, id_db_standalone :: boolean(), id_db_env :: term() | undefined, next_int_id :: non_neg_integer(), quantization_method :: pq | turboquant | subspace_turboquant | none, pq_state :: term() | undefined, pq_codes :: #{binary() => binary()}, pq_codes_int :: #{non_neg_integer() => binary()}, use_pq :: boolean(), tq_state :: term() | undefined, tq_codes :: #{binary() => binary()}, tq_codes_int :: #{non_neg_integer() => binary()}, deleted_set :: sets:set(binary()), deleted_int_set :: sets:set(non_neg_integer()), storage_mode :: memory | disk, vectors :: #{binary() => [float()]}, file_handle :: term() | undefined, base_path :: binary() | undefined, cache_table :: ets:tid() | undefined, cache_max_size :: pos_integer(), graph_cache_table :: ets:tid() | undefined, graph_cache_max_size :: pos_integer(), hot_enabled :: boolean(), hot_max_size :: non_neg_integer(), hot_compaction_threshold :: float(), hot_vectors :: #{non_neg_integer() => [float()]}, hot_graph :: #{non_neg_integer() => [non_neg_integer()]}, hot_id_to_int :: #{binary() => non_neg_integer()}, hot_int_to_id :: #{non_neg_integer() => binary()}, hot_next_int_id :: non_neg_integer(), hot_deleted :: sets:set(non_neg_integer()), hot_pq_codes :: #{non_neg_integer() => binary()}, hot_tq_codes :: #{non_neg_integer() => binary()}, hot_size :: non_neg_integer(), compaction_in_progress :: boolean()}.
Functions
-spec build(map(), [{binary(), [float()]}]) -> {ok, diskann_index()} | {error, term()}.
Build index from a list of {Id, Vector} pairs using two-pass Vamana
-spec close(diskann_index()) -> ok.
Close the index and flush to disk For V2 format: writes header and PQ state, closes RocksDB Does NOT use term_to_binary for the entire index
-spec close_all_standalone_dbs() -> ok.
-spec compact(diskann_index()) -> {ok, diskann_index()} | {error, term()}.
Trigger manual compaction of hot layer to disk
-spec consolidate_deletes(diskann_index()) -> {ok, diskann_index()}.
Consolidate deleted nodes (batch cleanup) This repairs the graph by removing edges to deleted nodes and adding new edges to maintain navigability
-spec delete(diskann_index(), binary()) -> {ok, diskann_index()}.
Lazy delete - marks node as deleted
-spec deserialize(binary()) -> {ok, diskann_index()} | {error, term()}.
Deserialize index from binary
-spec get_vector(diskann_index(), binary()) -> {ok, [float()]} | not_found.
Get vector by ID (uses cache for disk mode)
Core search algorithm - optimized version Uses separate candidate queue and result set for efficiency Returns ({SortedResults, VisitedSet})
-spec info(diskann_index()) -> map().
Get index info
-spec insert(diskann_index(), binary(), [float()]) -> {ok, diskann_index()} | {error, term()}.
Insert a new vector (FreshVamana algorithm)
-spec insert_batch(diskann_index(), [{binary(), [float()]}], map()) -> {ok, diskann_index()} | {error, term()}.
Batch insert multiple vectors efficiently Inserts all vectors first, then builds graph edges in one pass. Much more efficient than calling insert/3 repeatedly.
-spec needs_consolidation(diskann_index()) -> boolean().
Check if consolidation is needed (threshold-based) Returns true if deleted count exceeds 10% of active size
-spec new(map()) -> {ok, diskann_index()} | {error, term()}.
Create a new empty DiskANN index Options: - dimension: Vector dimension (required) - r: Max out-degree (default: 64) - l_build: Build search width (default: 100) - l_search: Query search width (default: 100) - alpha: Pruning factor (default: 1.2) - distance_fn: cosine | euclidean (default: cosine) - assume_normalized: Skip norm computation for cosine (default: false) - storage_mode: memory | disk (default: memory) - base_path: Path for disk storage (required if storage_mode=disk) - cache_max_size: Max vectors in LRU cache (default: 10000) - hot_layer: Enable hot memory layer for fast writes (default: false) - hot_max_size: Maximum vectors in hot layer before compaction (default: 10000) - hot_compaction_threshold: Trigger compaction at this % of max (default: 0.8) - quantization: none | pq | turboquant | subspace_turboquant (default: none) - tq_bits: TurboQuant bits per component (default: 3, when quantization=turboquant or subspace_turboquant) - tq_seed: TurboQuant random seed (default: 42) - tq_m: Number of subspaces for subspace_turboquant (default: auto, based on dimension)
-spec open(binary() | string()) -> {ok, diskann_index()} | {error, term()}.
Open an existing DiskANN index from disk For V2 format: O(1) startup with lazy graph loading For V1 format: Migrates to V2 or loads from diskann.index
-spec open(binary() | string(), map()) -> {ok, diskann_index()} | {error, term()}.
Open with options: crypto => none | #{key := <<_:256>>, env => rocksdb env}. The key encrypts the flat files; the env (or one minted from the key) covers the diskann_ids RocksDB.
RobustPrune: Select R neighbors for node P using alpha-RNG pruning V = candidate neighbors Alpha > 1 keeps more long-range edges Optimized: cache distance computations
-spec search(diskann_index(), [float()], pos_integer()) -> [{binary(), float()}].
Search for K nearest neighbors
-spec search(diskann_index(), [float()], pos_integer(), map()) -> [{binary(), float()}].
Search with options Options: - l_search: Search beam width (default: from config) - rerank_factor: Multiplier for rerank candidates (default: 4)
-spec serialize(diskann_index()) -> binary().
Serialize index to binary (for barrel_vectordb_index behaviour)
-spec size(diskann_index()) -> non_neg_integer().
Get index size (excluding deleted)
-spec sync(diskann_index()) -> ok.
Force sync to disk