Merge Operations Deep Dive

// IDMapToIVFMerger workflow
class IDMapToIVFMerger {
  void merge(IDMapShard* source, IVFShard* target) {
    // 1. Sample vectors for training
    auto sample = source->sample(training_sample_size);

    // 2. Train centroids using k-means
    auto centroids = train_kmeans(sample, nlist);
    target->set_centroids(centroids);

    // 3. Assign vectors to clusters
    auto assignments = assign_to_clusters(
      source->get_all_vectors(),
      centroids
    );

    // 4. Build inverted lists
    for (size_t i = 0; i < source->size(); i++) {
      auto cluster_id = assignments[i];
      target->add_to_list(cluster_id, source->get(i));
    }

    // 5. Verify and swap
    verify_integrity(target);
    swap_shard(source, target);
  }
};

// IVFToOnDiskMerger workflow
class IVFToOnDiskMerger {
  void merge(IVFShard* source, OnDiskShard* target) {
    // 1. Copy centroids (stay in RAM)
    target->set_centroids(source->get_centroids());

    // 2. Open disk file for writing
    auto file = open_mmapped_file(target->path());

    // 3. Write inverted lists to disk
    for (size_t list_id = 0; list_id < nlist; list_id++) {
      auto entries = source->get_list(list_id);
      auto offset = file.write(entries);
      target->set_list_offset(list_id, offset);
    }

    // 4. Sync and swap
    file.sync();
    swap_shard(source, target);

    // 5. Free memory from in-memory lists
    source->clear_lists();
  }
};

Configuration Options