Introduzione: i limiti del brute-force search

Un Vector DB naive usa approximate nearest neighbor (ANN) via brute-force: per ogni query, calcola distanza euclidea verso tutti gli N vettori, ordina top-k. Complessità: O(N × d) dove d=numero dimensioni. Con N=100M e d=768:

• Operazioni float: 100M × 768 = 76.8 miliardi operazioni per query.
• Latency single query: ~250ms (CPU bound).
• Throughput 1000 query/sec: impossibile.
• RAM occupato: 100M × 768 × 4 byte = 307 GB (float32).

La soluzione è cambiare paradigma verso hierarchical indexing (HNSW — Hierarchical Navigable Small World) dove search diventa O(log N) con traversal smart del graph.

Strategie di indexing per 100M+ vettori

1. HNSW (Hierarchical Navigable Small World) — Il gold standard moderno

HNSW è algoritmo probabilistico che costruisce multi-layer graph dove layer 0 contiene tutti i vettori, layer 1 il 10%, layer 2 l'1%, ecc. Search inizia dal top layer (pochi nodi) e scende, navigando lokalmente verso nearest neighbor approssimato. Complessità query: O(log N). Propriet chiave:

• Memory-efficient: Circa 3-5 volte RAM del dataset float (non infinito).
• Sublinear latency: 100M vettori ~40ms average (vs 250ms brute-force).
• Tunable accuracy: Parametri M (edges per node) e ef (expansion factor search).

Implementazione parametri:

import hnswlib

# Creare indice HNSW per 100M vettori, dim=768
index = hnswlib.Index(space='cosine', dim=768)
index.init_index(max_elements=100_000_000,
                 ef_construction=200,  # accuracy construction (200-400 comune)
                 M=16)                 # max connections per node (8-64 range)

# Load vettori batch: ogni batch 10K vettori
for batch_idx in range(0, 100_000_000, 10_000):
    vectors = load_batch(batch_idx, batch_idx + 10_000)
    labels = range(batch_idx, batch_idx + 10_000)
    index.add_items(vectors, labels)

# Salva index su disco (persistenza)
index.save_index("vectors_100m.hnsw")

# Query: ritorna top-10 neighbors
query_vector = [0.1, 0.2, ..., 0.8]  # 768 dim
index.set_ef(ef=100)  # ef search trade-off latency/accuracy
labels, distances = index.knn_query(query_vector, k=10)
        

2. IVF (Inverted File Index) — Per estemi di compressione

IVF divide vector space in Voronoi cells (es. 1000 clusters). Ogni vettore è assegnato al cluster + vettori neighbor nel cluster sono codificati. Search: trovi cluster query-nearest e cerca solo dentro top-5 clusters. Latency O(clusters_searched × cluster_size), non O(N).

import faiss

# IVF: creare 1000 clusters (Voronoi)
quantizer = faiss.IndexFlatL2(768)  # quantizer per distanza
index = faiss.IndexIVFFlat(quantizer, 768, 1000)
index.train(training_vectors)

# Add 100M vettori: ogni vector va in uno dei 1000 clusters
index.add(all_vectors)

# Query search: solo nei top 5 clusters (probe=5)
index.nprobe = 5
distances, labels = index.search(query_vector, k=10)
        

3. DiskANN — Per ultra-large scale (1B+ vectors)

Microsoft DiskANN memorizza graph su SSD, non RAM. Ogni node tiene solo K nearest neighbors (non N). Accesso SSD è ~100x più lento di RAM ma consuma 100x meno memoria. Per 1B vettori: memoria ~10GB, latency ~200ms (acceptable per alcuni use case).

Partitioning e sharding di 100M vettori

Oltre un certo threshold (tipicamente 50-200M per cluster singolo), distribuire i vettori su più macchine diventa necessario. Due strategie:

Range Partitioning: Shard per ID ranges

Assegna vettori a shard in base a ID modulo numero shards. Semplice ma riskky per skewed distributions.

# 100M vettori distribuiti su 10 shards (10M per shard)
num_shards = 10

def get_shard(vector_id, num_shards):
    return vector_id % num_shards

# Shard 0: IDs 0, 10, 20, ..., 99999990
# Shard 1: IDs 1, 11, 21, ..., 99999991
# etc.

# Query: invia a TUTTI i shard, merge top-10 results
query_result = []
for shard_id in range(num_shards):
    partial_result = query_shard(shard_id, query_vector, k=100)
    query_result.extend(partial_result)

# Merge: prendi top-10 globali da risultati merged
final_result = sorted(query_result, key=lambda x: x.distance)[:10]
        

Semantic Partitioning: Shard per feature clustering

Esegui K-means su sample dei vettori, assegna cluster membership a ogni vettore. Vettori semanticamente vicini finiscono nello stesso shard. Query: calcola affinity con cluster centroids, interroga solo top-3 shards. Latency inferiore.

from sklearn.cluster import KMeans

# Campionare 1M vettori per clustering
sample_vectors = random_sample(all_vectors, 1_000_000)
kmeans = KMeans(n_clusters=10)
kmeans.fit(sample_vectors)

# Assegna ogni vettore a cluster
def assign_to_shard(vector):
    distances_to_centroids = np.linalg.norm(
        kmeans.cluster_centers_ - vector, axis=1)
    shard_id = np.argmin(distances_to_centroids)
    return shard_id

# Query: trova top-3 cluster-nearest
query_centroid_dist = np.linalg.norm(
    kmeans.cluster_centers_ - query_vector, axis=1)
top_shards = np.argsort(query_centroid_dist)[:3]

result = []
for shard_id in top_shards:
    partial = query_shard(shard_id, query_vector, k=50)
    result.extend(partial)

final = sorted(result, key=lambda x: x.distance)[:10]
        

Quantizzazione: ridurre memoria del 75%

Stai memorizzando float32 (4 byte per componente). Con d=768 e 100M vettori: 307 GB RAM. Quantizzazione uint8 riduce a 77 GB (75% savings). Trade-off: accuracy cala ~2-3% ma latenza migliora.

Quantizzazione uniforme uint8

Mappa range [min_val, max_val] di ogni dimensione a [0, 255].

import numpy as np

def quantize_vector(vector, min_val=None, max_val=None):
    """Quantizza float32 a uint8"""
    if min_val is None:
        min_val = np.percentile(vector, 0.1)
    if max_val is None:
        max_val = np.percentile(vector, 99.9)

    # Normalizza a [0, 1]
    normalized = (vector - min_val) / (max_val - min_val + 1e-8)
    normalized = np.clip(normalized, 0, 1)

    # Scala a [0, 255]
    quantized = (normalized * 255).astype(np.uint8)
    return quantized, min_val, max_val

def dequantize_vector(quantized, min_val, max_val):
    """Dequantizza uint8 a float32"""
    normalized = quantized.astype(np.float32) / 255.0
    vector = normalized * (max_val - min_val) + min_val
    return vector

# Applicare a tutti 100M vettori
quantized_vectors = []
scales = {}

for i in range(0, 100_000_000, 100_000):
    batch = all_vectors[i:i+100_000]
    batch_quantized, min_val, max_val = quantize_vector(batch)
    quantized_vectors.append(batch_quantized)
    scales[i] = (min_val, max_val)

# Indice HNSW su uint8 (memory: 25% dell'originale)
quantized_index = hnswlib.Index(space='l2', dim=768)
quantized_index.add_items(np.vstack(quantized_vectors))
        

Query optimization e batch processing

Batch query: ridurre latency per mille query

Inviare query una alla volta è inefficiente. Batch processing sfrutta SIMD parallelization:

# MALE: query seriali
latency_total = 0
for query_vec in query_batch:
    start = time.time()
    result = index.search(query_vec, k=10)
    latency_total += time.time() - start
# 1000 query × 40ms = 40 secondi

# BENE: batch query con vectorization
start = time.time()
query_matrix = np.vstack(query_batch)  # [1000, 768]
results = index.batch_search(query_matrix, k=10)
elapsed = time.time() - start
# 1000 query × 0.8ms = 0.8 secondi (50x miglioramento!)
        

Caching query results

Queries ripetute colpiscono spesso gli stessi vettori. Cache LRU su Redis:

import redis
import hashlib

redis_cache = redis.Redis(host='localhost', port=6379)

def search_with_cache(query_vector, k=10):
    # Hash della query
    query_hash = hashlib.md5(query_vector.tobytes()).hexdigest()
    cache_key = f"vector_search:{query_hash}:k{k}"

    # Prova cache
    cached_result = redis_cache.get(cache_key)
    if cached_result:
        return json.loads(cached_result)

    # Cache miss: query l'indice
    result = index.search(query_vector, k=k)

    # Salva in cache per 1 ora
    redis_cache.setex(cache_key, 3600, json.dumps(result))
    return result
        

Memory management per 100M+ vectors

Monitoraggio RAM real-time

import psutil

def monitor_memory():
    process = psutil.Process()
    memory_info = process.memory_info()

    rss_mb = memory_info.rss / 1024 / 1024  # Resident set size
    vms_mb = memory_info.vms / 1024 / 1024  # Virtual memory size

    print(f"RSS: {rss_mb:.0f} MB | VMS: {vms_mb:.0f} MB")

    # Alert se RSS > 80GB
    if rss_mb > 80_000:
        trigger_scale_out()  # Spinup nuovo shard

# Chiamare ogni 5 minuti
schedule.every(5).minutes.do(monitor_memory)
        

Eviction policy per cache overflow

Quando RAM è piena, implementare LRU eviction: rimuovere vettori meno usati da RAM, tenere su SSD warm cache.

Monitoring e alerting in production

KPI critici per 100M+ setup

• Query latency (p50, p95, p99): Target p95 < 100ms, alert se > 200ms per 5 min.
• RAM usage: Alert se > 85% per prevenire OOM.
• Index freshness: Time tra insert e queryable. Target < 10 secondi.
• Recall accuracy: Top-10 returned match top-10 brute-force. Target > 95%.

from prometheus_client import Histogram, Gauge

# Prometheus metrics
query_latency = Histogram('vector_search_latency_ms', 'Query latency')
ram_usage = Gauge('ram_usage_gb', 'RAM usage')
index_freshness = Gauge('index_freshness_seconds', 'Time to index')

def record_query_latency(duration_ms):
    query_latency.observe(duration_ms)

def record_ram():
    usage_gb = psutil.virtual_memory().used / 1024**3
    ram_usage.set(usage_gb)

# Setup alerts in Grafana
# p95 latency > 200ms per 5 min → page oncall
# ram > 85% → scale out shard
        

Case study: scaling a 200M vectors in production

Sistema RAG per enterprise, 200M vettori articoli interni (d=768). Challenge: 5000 query/sec, p95 latency budget 100ms.

Soluzione implementata

• Sharding: 4 shards geografici (EU-West, EU-Central, US-East, Asia-Pacific), 50M vettori ciascuno.
• Indexing: HNSW + quantizzazione uint8 (ridotto da 307GB a 77GB per globale).
• Query routing: Load balancer invia query al shard più vicino geograficamente + hot-standby.
• Batch processing: Applicazione batch-accumula query, invia ogni 50ms in batch da 100.
• Cache: Redis cluster (3 nodi) cache top-100 query (80% hit rate).

Risultato: 100ms p95 consistently. Costo infra: €2K/mese su Hetzner (vs €50K cloud managed service).

FAQ: domande comuni su Vector DB scaling

Q1: A che punto devo migrare da single-instance a cluster?

Risposta: Soglia raccomandata: 50-100M vettori. A 100M+ il costo single-instance (RAM + CPU) diventa insostenibile e latency degrada. Cluster di 4-8 nodi è sweet-spot costo/performance.

Q2: Quantizzazione uint8 cala accuracy troppo?

Risposta: Dipende da use case. Per information retrieval (top-10 neighbors) accuracy cala ~1-2%. Per clustering/anomaly detection può calare più. Best practice: test su tuo dataset con recall metric (confronta top-10 quantizzato vs float32).

Q3: Quando usare HNSW vs IVF?

Risposta: HNSW è default moderno (sub-100ms, 95%+ recall). IVF se necessita estrema compression (1B+ vectors) e puoi tollerare 150-300ms latency. DiskANN se stack budget molto limitato.

Q4: Come evitare hotspots in sharding?

Risposta: Range partition causa skew se ID distribution è sbilenciato. Usa semantic partitioning (K-means clustering) o consistent hashing per distribuire query load uniformemente. Monitor query/sec per shard e ribilancia automaticamente ogni 24h.

Q5: Costo infrastrutturale 100M vector cluster?

Risposta: Stima: 4 nodi r7i.2xlarge (768 GB RAM totale), SSD NVMe per durability. AWS: ~€8K/mese. Hetzner: ~€2K/mese. Self-hosted datacenter: €300/mese (hardware) + ops (€3K/mese). Pinecone managed: €12K/mese.

Conclusioni e prossimi step

Scalare Vector Database oltre 100 milioni di vettori non richiede innovazione nuova, bensì selezione accurata di 4 tecniche consolidate: HNSW hierarchical indexing, semantic sharding, quantizzazione, batch processing. Implementando in modo disciplinato, production systems moderni mantengono latency sub-100ms e costi sostenibili anche a scala massive.

Action items: (1) Benchmark HNSW vs IVF sul tuo dataset con recall metric. (2) Plan sharding strategy (semantic o range) basato su query distribution. (3) Setup monitoring latency/recall in staging prima di produzione. (4) Quantize e test accuracy impact.