#include "scann/scann_ops/cc/scann.h"
#include <fcntl.h>
#include <sys/mman.h>
#include <unistd.h>
#include <algorithm>
#include <atomic>
#include <cerrno>
#include <cmath>
#include <cstdint>
#include <cstring>
#include <filesystem>
#include <fstream>
#include <limits>
#include <memory>
#include <random>
#include <string>
#include <system_error>
#include <utility>
#include "absl/algorithm/container.h"
#include "absl/container/flat_hash_map.h"
#include "absl/container/flat_hash_set.h"
#include "absl/container/node_hash_set.h"
#include "absl/strings/match.h"
#include "absl/strings/str_cat.h"
#include "absl/strings/string_view.h"
#include "absl/synchronization/mutex.h"
#include "google/protobuf/message.h"
#include "scann/base/single_machine_base.h"
#include "scann/data_format/dataset.h"
#include "scann/oss_wrappers/scann_status.h"
#include "scann/partitioning/partitioner.pb.h"
#include "scann/proto/brute_force.pb.h"
#include "scann/proto/centers.pb.h"
#include "scann/proto/scann.pb.h"
#include "scann/scann_ops/scann_assets.pb.h"
#include "scann/trees/kmeans_tree/kmeans_tree.pb.h"
#include "scann/tree_x_hybrid/tree_ah_hybrid_residual.h"
#include "scann/tree_x_hybrid/tree_x_params.h"
#include "scann/utils/common.h"
#include "scann/utils/io_npy.h"
#include "scann/utils/io_oss_wrapper.h"
#include "scann/utils/scann_config_utils.h"
#include "scann/utils/single_machine_autopilot.h"
#include "scann/utils/single_machine_retraining.h"
#include "scann/utils/threads.h"
#include "scann/utils/types.h"
#include "scann_core/available_cpus.h"
namespace research_scann {
namespace {
constexpr const int32_t kSoarEmptyToken = -1;
bool HasSoar(const ScannConfig& config) {
return config.partitioning().database_spilling().spilling_type() ==
DatabaseSpillingConfig::TWO_CENTER_ORTHOGONALITY_AMPLIFIED;
}
int GetNumCPUs() { return scann_core::AvailableCPUs(); }
unique_ptr<DenseDataset<float>> InitDataset(
ConstSpan<float> dataset, DatapointIndex n_points,
DimensionIndex n_dim = kInvalidDimension) {
if (dataset.empty() && n_dim == kInvalidDimension) return nullptr;
vector<float> dataset_vec(dataset.data(), dataset.data() + dataset.size());
auto ds =
std::make_unique<DenseDataset<float>>(std::move(dataset_vec), n_points);
if (n_dim != kInvalidDimension) {
ds->set_dimensionality(n_dim);
}
return ds;
}
template <typename T>
Status CheckDenseShape(ConstSpan<T> data, DatapointIndex n_points,
absl::string_view what) {
if (data.empty()) return OkStatus();
if (n_points == 0)
return InvalidArgumentError(absl::StrCat(
what, " has ", data.size(), " values but n_points is 0"));
if (data.size() % n_points != 0)
return InvalidArgumentError(absl::StrCat(
what, " has ", data.size(), " values, which is not a multiple of ",
"n_points (", n_points, ")"));
return OkStatus();
}
Status CheckAllFinite(ConstSpan<float> data, DimensionIndex dim,
absl::string_view what) {
for (size_t i = 0; i < data.size(); ++i) {
if (!std::isfinite(data[i]))
return InvalidArgumentError(absl::StrCat(
what, " row ", dim == 0 ? 0 : i / dim,
" contains NaN or infinity; ScaNN only supports finite values."));
}
return OkStatus();
}
#if defined(__linux__) && !defined(MADV_COLLAPSE)
#define MADV_COLLAPSE 25
#endif
bool HugePagesEnabled() {
const char* v = std::getenv("SCANN_HUGEPAGES");
return v == nullptr || std::string_view(v) != "0";
}
void AdviseHugePages(uintptr_t begin, uintptr_t end) {
#if defined(__linux__) && defined(MADV_HUGEPAGE)
constexpr uintptr_t kHuge = uintptr_t{2} << 20;
begin = (begin + kHuge - 1) & ~(kHuge - 1);
end &= ~(kHuge - 1);
if (end <= begin) return;
void* p = reinterpret_cast<void*>(begin);
madvise(p, end - begin, MADV_HUGEPAGE);
madvise(p, end - begin, MADV_COLLAPSE);
#endif
}
template <typename T>
bool AdviseDenseDataset(const Dataset* ds) {
auto* dense = dynamic_cast<const DenseDataset<T>*>(ds);
if (dense == nullptr || dense->data().empty()) return false;
const auto begin = reinterpret_cast<uintptr_t>(dense->data().data());
AdviseHugePages(begin, begin + dense->data().size() * sizeof(T));
return true;
}
void AdviseDataset(const Dataset* ds) {
if (ds == nullptr) return;
AdviseDenseDataset<float>(ds) || AdviseDenseDataset<int16_t>(ds) ||
AdviseDenseDataset<int8_t>(ds) || AdviseDenseDataset<uint8_t>(ds);
}
void AdviseHugePagesForSearcher(const SingleMachineSearcherBase<float>& s) {
if (!HugePagesEnabled()) return;
AdviseDataset(s.dataset());
if (s.reordering_enabled()) {
auto reordering = s.reordering_helper().dataset();
if (reordering.get() != s.dataset()) AdviseDataset(reordering.get());
}
if (auto* tree = dynamic_cast<const TreeAHHybridResidual*>(&s)) {
uintptr_t lo = std::numeric_limits<uintptr_t>::max(), hi = 0;
size_t total = 0;
tree->ForEachLeafPackedCodes([&](const uint8_t* data, size_t bytes) {
const auto b = reinterpret_cast<uintptr_t>(data);
lo = std::min(lo, b);
hi = std::max(hi, b + bytes);
total += bytes;
});
if (hi > lo && total >= (hi - lo) / 2) AdviseHugePages(lo, hi);
}
}
Status AddTokenizationToOptions(SingleMachineFactoryOptions& opts,
ConstSpan<int32_t> tokenization,
const int spilling_mult = 1) {
if (tokenization.empty()) return OkStatus();
if (opts.serialized_partitioner == nullptr)
return FailedPreconditionError(
"Non-empty tokenization but no serialized partitioner is present.");
const int32_t n_tokens = opts.serialized_partitioner->n_tokens();
if (n_tokens <= 0)
return InvalidArgumentError(absl::StrCat(
"The serialized partitioner has ", n_tokens, " partitions."));
if (tokenization.size() % spilling_mult != 0)
return InvalidArgumentError(absl::StrCat(
"The tokenization has ", tokenization.size(),
" entries; a SOAR tokenization has two per datapoint."));
for (auto [i, token] : Enumerate(tokenization)) {
const bool may_be_empty = spilling_mult > 1 && i % spilling_mult != 0;
if ((token < 0 || token >= n_tokens) &&
!(may_be_empty && token == kSoarEmptyToken))
return InvalidArgumentError(absl::StrCat(
"Datapoint ", i / spilling_mult, " has partition token ", token,
", outside [0, ", n_tokens, ")."));
if (may_be_empty && token == tokenization[i - 1])
return InvalidArgumentError(absl::StrCat(
"Datapoint ", i / spilling_mult, " is assigned to partition ", token,
" twice."));
}
opts.datapoints_by_token =
std::make_shared<vector<std::vector<DatapointIndex>>>(n_tokens);
for (auto [dp_idx, token] : Enumerate(tokenization)) {
if (token != kSoarEmptyToken) {
(*opts.datapoints_by_token)[token].push_back(dp_idx / spilling_mult);
}
}
return OkStatus();
}
constexpr absl::string_view kL2AsDotProductSavedDistance =
"SquaredL2Distance [l2_as_dot_product: needs scann-core >= 0.2.1]";
constexpr double kL2AsDotProductDefaultScale = 0.4;
float L2AsDotProductCoordinate(const float* x, size_t dim,
const ScannInterface::L2AsDotProduct& p) {
double sq = 0;
for (size_t j = 0; j < dim; ++j) sq += static_cast<double>(x[j]) * x[j];
return static_cast<float>((p.center - sq) / (2.0 * p.scale));
}
StatusOr<std::optional<ScannInterface::L2AsDotProduct>> ToSearcherConfig(
ScannConfig* config) {
const std::string distance = config->distance_measure().distance_measure();
if (!config->has_l2_as_dot_product()) {
if (distance == kL2AsDotProductSavedDistance)
return InvalidArgumentError(absl::StrCat(
"The config's distance_measure is \"", distance,
"\", but it has no l2_as_dot_product."));
return std::nullopt;
}
if (distance != "SquaredL2Distance" &&
distance != kL2AsDotProductSavedDistance)
return InvalidArgumentError(absl::StrCat(
"l2_as_dot_product searches by squared L2 distance through an "
"inner-product index: the config's distance_measure must be "
"SquaredL2Distance, not \"", distance, "\"."));
const L2AsDotProductConfig& p = config->l2_as_dot_product();
if (!p.has_scale() || !p.has_center())
return InvalidArgumentError(
"l2_as_dot_product needs its scale and center here (building an "
"index fills in the ones left unset; a saved index has both).");
if (!std::isfinite(p.scale()) || p.scale() <= 0)
return InvalidArgumentError(absl::StrCat(
"l2_as_dot_product.scale must be positive and finite, not ",
p.scale(), "."));
if (!std::isfinite(p.center()))
return InvalidArgumentError(absl::StrCat(
"l2_as_dot_product.center must be finite, not ", p.center(), "."));
if (IsSphericalPartitioning(*config))
return InvalidArgumentError(
"l2_as_dot_product can't be combined with spherical partitioning, "
"which normalizes the stored vectors (extra coordinate included).");
if (std::isfinite(config->epsilon_distance()) || config->has_min_distance())
return InvalidArgumentError(
"epsilon_distance and min_distance aren't supported with "
"l2_as_dot_product (the searcher's distances are inner products).");
const ScannInterface::L2AsDotProduct params{p.scale(), p.center()};
config->mutable_distance_measure()->set_distance_measure(
"DotProductDistance");
config->clear_l2_as_dot_product();
if (config->input_output().pure_dynamic_config().has_dimensionality()) {
auto* dynamic =
config->mutable_input_output()->mutable_pure_dynamic_config();
dynamic->set_dimensionality(dynamic->dimensionality() + 1);
}
return std::optional<ScannInterface::L2AsDotProduct>(params);
}
void ToGivenConfig(const ScannInterface::L2AsDotProduct& params,
ScannConfig* config) {
config->mutable_distance_measure()->set_distance_measure("SquaredL2Distance");
config->mutable_l2_as_dot_product()->set_scale(params.scale);
config->mutable_l2_as_dot_product()->set_center(params.center);
if (config->input_output().pure_dynamic_config().has_dimensionality()) {
auto* dynamic =
config->mutable_input_output()->mutable_pure_dynamic_config();
if (dynamic->dimensionality() > 0)
dynamic->set_dimensionality(dynamic->dimensionality() - 1);
}
}
DimensionIndex SearcherPureDynamicDimensionality(const ScannConfig& config) {
if (!config.input_output().pure_dynamic_config().has_dimensionality())
return kInvalidDimension;
return config.input_output().pure_dynamic_config().dimensionality() +
(config.has_l2_as_dot_product() ? 1 : 0);
}
StatusOr<shared_ptr<DenseDataset<float>>> L2AsDotProductDataset(
ConstSpan<float> dataset, DatapointIndex n_points, DimensionIndex n_dim,
ScannConfig* config) {
const std::string& distance = config->distance_measure().distance_measure();
if (distance != "SquaredL2Distance")
return InvalidArgumentError(absl::StrCat(
"l2_as_dot_product searches by squared L2 distance through an "
"inner-product index: the config's distance_measure must be "
"SquaredL2Distance, not \"", distance, "\"."));
size_t dim;
if (n_points > 0) {
dim = dataset.size() / n_points;
} else if (n_dim != kInvalidDimension && n_dim > 0) {
dim = n_dim;
} else {
return InvalidArgumentError(
"l2_as_dot_product with an empty dataset needs "
"input_output.pure_dynamic_config.dimensionality.");
}
L2AsDotProductConfig* p = config->mutable_l2_as_dot_product();
double sum_sq = 0;
for (float v : dataset) sum_sq += static_cast<double>(v) * v;
const double mean_sq = n_points > 0 ? sum_sq / n_points : 0.0;
if (!p->has_center()) p->set_center(mean_sq);
if (!p->has_scale()) {
const double ms = n_points > 0 ? mean_sq : p->center();
if (ms > 0 && std::isfinite(ms)) {
p->set_scale(kL2AsDotProductDefaultScale * std::sqrt(ms));
} else if (n_points > 0) {
p->set_scale(1.0); } else {
return InvalidArgumentError(
"l2_as_dot_product with an empty dataset needs a scale (or a "
"positive center): its default is computed from the data.");
}
}
if (!std::isfinite(p->scale()) || p->scale() <= 0)
return InvalidArgumentError(absl::StrCat(
"l2_as_dot_product.scale must be positive and finite, not ",
p->scale(), "."));
if (!std::isfinite(p->center()))
return InvalidArgumentError(absl::StrCat(
"l2_as_dot_product.center must be finite, not ", p->center(),
n_points > 0 ? " (the dataset's mean squared norm)." : "."));
const ScannInterface::L2AsDotProduct params{p->scale(), p->center()};
vector<float> stored(static_cast<size_t>(n_points) * (dim + 1));
for (size_t i = 0; i < n_points; ++i) {
const float* x = dataset.data() + i * dim;
float* out = stored.data() + i * (dim + 1);
std::copy(x, x + dim, out);
out[dim] = L2AsDotProductCoordinate(x, dim, params);
}
auto ds = std::make_shared<DenseDataset<float>>(std::move(stored), n_points);
if (n_points == 0) ds->set_dimensionality(dim + 1);
return ds;
}
}
namespace {
constexpr absl::string_view kIncompleteSerializationMarker =
"scann_core_incomplete_serialization";
Status CheckSerializationComplete(absl::string_view assets_pbtxt) {
if (absl::StrContains(assets_pbtxt, kIncompleteSerializationMarker))
return FailedPreconditionError(
"This index directory is incomplete: serialize() was interrupted "
"while writing it, or is still writing it. Serialize the index "
"again.");
return OkStatus();
}
class AssetReader {
public:
using Files = absl::flat_hash_map<std::string, absl::string_view>;
AssetReader() = default;
explicit AssetReader(const Files* files) : files_(files) {}
template <typename T>
StatusOr<pair<vector<T>, vector<size_t>>> Npy(absl::string_view path) const {
if (files_ == nullptr) return NumpyToVectorAndShape<T>(path);
SCANN_ASSIGN_OR_RETURN(absl::string_view bytes, Get(path));
return NumpyBytesToVectorAndShape<T>(path, bytes);
}
Status Proto(absl::string_view path,
google::protobuf::Message* message) const {
if (files_ == nullptr) return ReadProtobufFromFile(path, message);
SCANN_ASSIGN_OR_RETURN(absl::string_view bytes, Get(path));
if (!message->ParseFromString(bytes))
return InvalidArgumentError(
absl::StrCat("Failed to parse ", message->GetTypeName(),
" proto from ", path));
return OkStatus();
}
StatusOr<absl::string_view> Get(absl::string_view path) const {
auto it = files_->find(path);
if (it == files_->end())
it = files_->find(
std::filesystem::path(std::string(path)).filename().string());
if (it == files_->end())
return NotFoundError(
absl::StrCat("The index files have no ", path, "."));
return it->second;
}
private:
const Files* files_ = nullptr;
};
template <typename T>
StatusOr<pair<vector<T>, vector<size_t>>> LoadNpyOfRank(
const AssetReader& reader, absl::string_view path, size_t rank) {
SCANN_ASSIGN_OR_RETURN(auto v, reader.Npy<T>(path));
if (v.second.size() != rank)
return InvalidArgumentError(absl::StrCat(path, " has ", v.second.size(),
" dimensions; expected ", rank,
"."));
return v;
}
template <typename T>
StatusOr<shared_ptr<DenseDataset<T>>> LoadDenseNpy(const AssetReader& reader,
absl::string_view path) {
SCANN_ASSIGN_OR_RETURN(auto v, LoadNpyOfRank<T>(reader, path, 2));
const size_t n = v.second[0], d = v.second[1];
if (d == 0 && n > 0)
return InvalidArgumentError(absl::StrCat(path, " has 0 columns."));
if (n >= kInvalidDatapointIndex)
return InvalidArgumentError(
absl::StrCat(path, " has ", n, " rows, more than ScaNN supports."));
auto ds = make_shared<DenseDataset<T>>(std::move(v.first), n);
if (n == 0) ds->set_dimensionality(d);
return ds;
}
class ConsistentCount {
public:
ConsistentCount(absl::string_view quantity, bool ignore_zero)
: quantity_(quantity), ignore_zero_(ignore_zero) {}
Status Add(absl::string_view source, size_t value) {
if (ignore_zero_ && value == 0) return OkStatus();
if (source_.empty()) {
source_ = std::string(source);
value_ = value;
return OkStatus();
}
if (value == value_) return OkStatus();
return InvalidArgumentError(absl::StrCat(
"Inconsistent index files: ", source, " has ", value, " ", quantity_,
" but ", source_, " has ", value_,
". The directory may mix files of different indexes (e.g. from an "
"interrupted serialize()); serialize the index again."));
}
bool has_value() const { return !source_.empty(); }
size_t value() const { return value_; }
private:
std::string quantity_, source_;
bool ignore_zero_;
size_t value_ = 0;
};
Status ValidatePartitioner(const SerializedPartitioner& partitioner,
const ScannConfig& config, DimensionIndex dim) {
if (partitioner.n_tokens() <= 0)
return InvalidArgumentError(absl::StrCat(
"The serialized partitioner has ", partitioner.n_tokens(),
" partitions."));
if (!partitioner.has_kmeans() || !partitioner.kmeans().has_kmeans_tree() ||
partitioner.kmeans().has_next_bottom_up_level()) {
if (partitioner.n_tokens() > (1 << 26))
return InvalidArgumentError(absl::StrCat(
"The serialized partitioner has ", partitioner.n_tokens(),
" partitions."));
return OkStatus();
}
const SerializedKMeansTree::Node& root =
partitioner.kmeans().kmeans_tree().root();
size_t n_leaves = 0;
vector<const SerializedKMeansTree::Node*> stack = {&root};
while (!stack.empty()) {
const SerializedKMeansTree::Node* node = stack.back();
stack.pop_back();
if (node->children_size() == 0) ++n_leaves;
for (const auto& child : node->children()) stack.push_back(&child);
}
if (n_leaves != static_cast<size_t>(partitioner.n_tokens()))
return InvalidArgumentError(absl::StrCat(
"The serialized partitioner says it has ", partitioner.n_tokens(),
" partitions, but its tree has ", n_leaves, " leaves."));
if (config.partitioning().has_num_children() &&
partitioner.n_tokens() > config.partitioning().num_children())
return InvalidArgumentError(absl::StrCat(
"The serialized partitioner has ", partitioner.n_tokens(),
" partitions, but the config asks for at most ",
config.partitioning().num_children(),
". The directory may mix files of different indexes."));
if (dim != kInvalidDimension && !partitioner.uses_projection() &&
!config.partitioning().has_projection()) {
for (const auto& center : root.centers()) {
const size_t center_dim = std::max<size_t>(
center.dimension_size(), center.float_dimension_size());
if (center_dim != dim)
return InvalidArgumentError(absl::StrCat(
"The serialized partitioner's centers have dimensionality ",
center_dim, ", but the dataset has ", dim,
". The directory may mix files of different indexes."));
}
}
return OkStatus();
}
Status ValidateHashedDataset(const CentersForAllSubspaces& codebook,
const DenseDataset<uint8_t>& hashed,
absl::string_view what) {
const size_t n_blocks = codebook.subspace_centers_size();
if (hashed.empty()) return OkStatus();
if (hashed.dimensionality() != n_blocks)
return InvalidArgumentError(absl::StrCat(
"The ", what, " has ", hashed.dimensionality(),
" codes per datapoint, but the AH codebook has ", n_blocks,
" blocks. The directory may mix files of different indexes."));
ConstSpan<uint8_t> codes = hashed.data();
for (size_t i = 0; i < codes.size(); ++i) {
const size_t block = i % n_blocks;
if (codes[i] >= codebook.subspace_centers(block).center_size())
return InvalidArgumentError(absl::StrCat(
"The ", what, " has code ", codes[i], " for block ", block,
" of datapoint ", i / n_blocks, ", but the AH codebook has only ",
codebook.subspace_centers(block).center_size(),
" centers there."));
}
return OkStatus();
}
}
namespace {
StatusOr<ScannInterface::ScannArtifacts> LoadArtifactsWith(
const AssetReader& reader, const ScannConfig& config,
const ScannAssets& assets) {
SingleMachineFactoryOptions opts;
const bool soar = HasSoar(config);
absl::flat_hash_map<int, std::string> paths;
vector<int32_t> tokenization;
pair<vector<uint8_t>, vector<size_t>> soar_hashed;
shared_ptr<DenseDataset<float>> dataset;
auto fp = make_shared<PreQuantizedFixedPoint>();
for (const ScannAsset& asset : assets.assets()) {
const string_view asset_path = asset.asset_path();
const ScannAsset::AssetType type = asset.asset_type();
switch (type) {
case ScannAsset::AH_CENTERS:
case ScannAsset::PARTITIONER:
case ScannAsset::TOKENIZATION_NPY:
case ScannAsset::AH_DATASET_NPY:
case ScannAsset::AH_DATASET_SOAR_NPY:
case ScannAsset::DATASET_NPY:
case ScannAsset::INT8_DATASET_NPY:
case ScannAsset::INT8_MULTIPLIERS_NPY:
case ScannAsset::INT8_NORMS_NPY:
case ScannAsset::BF16_DATASET_NPY:
if (!paths.emplace(type, asset_path).second)
return InvalidArgumentError(absl::StrCat(
"The assets list more than one ",
ScannAsset::AssetType_Name(type), " file."));
break;
default:
break;
}
switch (type) {
case ScannAsset::AH_CENTERS:
opts.ah_codebook = std::make_shared<CentersForAllSubspaces>();
SCANN_RETURN_IF_ERROR(
reader.Proto(asset_path, opts.ah_codebook.get()));
break;
case ScannAsset::PARTITIONER:
opts.serialized_partitioner = std::make_shared<SerializedPartitioner>();
SCANN_RETURN_IF_ERROR(
reader.Proto(asset_path, opts.serialized_partitioner.get()));
break;
case ScannAsset::TOKENIZATION_NPY: {
SCANN_ASSIGN_OR_RETURN(auto v,
LoadNpyOfRank<int32_t>(reader, asset_path, 1));
tokenization = std::move(v.first);
break;
}
case ScannAsset::AH_DATASET_NPY: {
SCANN_ASSIGN_OR_RETURN(opts.hashed_dataset,
LoadDenseNpy<uint8_t>(reader, asset_path));
break;
}
case ScannAsset::AH_DATASET_SOAR_NPY: {
if (!soar)
return InvalidArgumentError(
"The assets include a SOAR hashed dataset, but the config has "
"no SOAR spilling. The directory may mix files of different "
"indexes.");
SCANN_ASSIGN_OR_RETURN(soar_hashed,
LoadNpyOfRank<uint8_t>(reader, asset_path, 2));
break;
}
case ScannAsset::DATASET_NPY: {
SCANN_ASSIGN_OR_RETURN(dataset,
LoadDenseNpy<float>(reader, asset_path));
break;
}
case ScannAsset::INT8_DATASET_NPY: {
SCANN_ASSIGN_OR_RETURN(fp->fixed_point_dataset,
LoadDenseNpy<int8_t>(reader, asset_path));
break;
}
case ScannAsset::INT8_MULTIPLIERS_NPY: {
SCANN_ASSIGN_OR_RETURN(auto v,
LoadNpyOfRank<float>(reader, asset_path, 1));
fp->multiplier_by_dimension =
make_shared<vector<float>>(std::move(v.first));
break;
}
case ScannAsset::INT8_NORMS_NPY: {
SCANN_ASSIGN_OR_RETURN(auto v,
LoadNpyOfRank<float>(reader, asset_path, 1));
fp->squared_l2_norm_by_datapoint =
make_shared<vector<float>>(std::move(v.first));
break;
}
case ScannAsset::BF16_DATASET_NPY: {
SCANN_ASSIGN_OR_RETURN(opts.bfloat16_dataset,
LoadDenseNpy<int16_t>(reader, asset_path));
break;
}
default:
break;
}
}
const auto has = [&paths](ScannAsset::AssetType type) {
return paths.contains(type);
};
const auto name = [&paths](ScannAsset::AssetType type) {
return absl::StrCat(ScannAsset::AssetType_Name(type), " (", paths[type],
")");
};
const auto mixed = [](absl::string_view what, absl::string_view section) {
return InvalidArgumentError(absl::StrCat(
"The assets include ", what, ", but the config has no ", section,
". The directory may mix files of different indexes (e.g. from an "
"interrupted serialize()); serialize the index again."));
};
if ((has(ScannAsset::AH_CENTERS) || has(ScannAsset::AH_DATASET_NPY)) &&
!config.has_hash())
return mixed("asymmetric-hashing data", "hash section");
if ((has(ScannAsset::PARTITIONER) || has(ScannAsset::TOKENIZATION_NPY)) &&
!config.has_partitioning())
return mixed("a partitioner or tokenization", "partitioning section");
if (has(ScannAsset::INT8_DATASET_NPY) &&
!config.brute_force().fixed_point().enabled() &&
!config.brute_force().scalar_quantized() &&
!config.exact_reordering().fixed_point().enabled() &&
!config.exact_reordering().use_fixed_point_if_possible())
return mixed("an int8 dataset", "int8 (fixed-point) scoring");
if (has(ScannAsset::BF16_DATASET_NPY) &&
!config.brute_force().bfloat16().enabled() &&
!config.exact_reordering().bfloat16().enabled())
return mixed("a bfloat16 dataset", "bfloat16 scoring");
ConsistentCount rows("datapoints", false);
ConsistentCount dims("dimensions", true);
if (dataset) {
SCANN_RETURN_IF_ERROR(rows.Add(name(ScannAsset::DATASET_NPY),
dataset->size()));
SCANN_RETURN_IF_ERROR(dims.Add(name(ScannAsset::DATASET_NPY),
dataset->dimensionality()));
}
if (opts.hashed_dataset)
SCANN_RETURN_IF_ERROR(rows.Add(name(ScannAsset::AH_DATASET_NPY),
opts.hashed_dataset->size()));
if (fp->fixed_point_dataset) {
SCANN_RETURN_IF_ERROR(rows.Add(name(ScannAsset::INT8_DATASET_NPY),
fp->fixed_point_dataset->size()));
SCANN_RETURN_IF_ERROR(dims.Add(name(ScannAsset::INT8_DATASET_NPY),
fp->fixed_point_dataset->dimensionality()));
if (fp->multiplier_by_dimension == nullptr ||
(fp->fixed_point_dataset->dimensionality() > 0 &&
fp->multiplier_by_dimension->size() !=
fp->fixed_point_dataset->dimensionality()))
return InvalidArgumentError(absl::StrCat(
"The int8 dataset has ", fp->fixed_point_dataset->dimensionality(),
" dimensions, but the assets have ",
fp->multiplier_by_dimension ? fp->multiplier_by_dimension->size() : 0,
" int8 multipliers (INT8_MULTIPLIERS_NPY)."));
}
if (fp->multiplier_by_dimension)
SCANN_RETURN_IF_ERROR(dims.Add(name(ScannAsset::INT8_MULTIPLIERS_NPY),
fp->multiplier_by_dimension->size()));
if (fp->squared_l2_norm_by_datapoint &&
!fp->squared_l2_norm_by_datapoint->empty())
SCANN_RETURN_IF_ERROR(rows.Add(name(ScannAsset::INT8_NORMS_NPY),
fp->squared_l2_norm_by_datapoint->size()));
if (opts.bfloat16_dataset) {
SCANN_RETURN_IF_ERROR(rows.Add(name(ScannAsset::BF16_DATASET_NPY),
opts.bfloat16_dataset->size()));
SCANN_RETURN_IF_ERROR(dims.Add(name(ScannAsset::BF16_DATASET_NPY),
opts.bfloat16_dataset->dimensionality()));
}
if (has(ScannAsset::AH_DATASET_SOAR_NPY))
SCANN_RETURN_IF_ERROR(
rows.Add(name(ScannAsset::AH_DATASET_SOAR_NPY), soar_hashed.second[0]));
const int spilling_mult = soar ? 2 : 1;
if (has(ScannAsset::TOKENIZATION_NPY)) {
if (tokenization.size() % spilling_mult != 0)
return InvalidArgumentError(absl::StrCat(
"The SOAR tokenization ", paths[ScannAsset::TOKENIZATION_NPY],
" has ", tokenization.size(),
" entries; it needs two per datapoint."));
SCANN_RETURN_IF_ERROR(rows.Add(
soar ? absl::StrCat("the SOAR tokenization ",
paths[ScannAsset::TOKENIZATION_NPY])
: name(ScannAsset::TOKENIZATION_NPY),
tokenization.size() / spilling_mult));
}
if (config.input_output().pure_dynamic_config().has_dimensionality())
SCANN_RETURN_IF_ERROR(
dims.Add(config.has_l2_as_dot_product()
? "the config (pure_dynamic_config.dimensionality, + 1 "
"for l2_as_dot_product)"
: "the config (pure_dynamic_config.dimensionality)",
SearcherPureDynamicDimensionality(config)));
if (opts.serialized_partitioner != nullptr)
SCANN_RETURN_IF_ERROR(ValidatePartitioner(
*opts.serialized_partitioner, config,
dims.has_value() ? dims.value() : kInvalidDimension));
SCANN_RETURN_IF_ERROR(
AddTokenizationToOptions(opts, tokenization, spilling_mult));
if (has(ScannAsset::TOKENIZATION_NPY) && tokenization.empty() &&
opts.serialized_partitioner != nullptr)
opts.datapoints_by_token =
std::make_shared<vector<std::vector<DatapointIndex>>>(
opts.serialized_partitioner->n_tokens());
if (opts.ah_codebook != nullptr && opts.hashed_dataset != nullptr)
SCANN_RETURN_IF_ERROR(ValidateHashedDataset(
*opts.ah_codebook, *opts.hashed_dataset, "hashed dataset"));
if (has(ScannAsset::AH_DATASET_SOAR_NPY)) {
if (!has(ScannAsset::TOKENIZATION_NPY) || !opts.hashed_dataset ||
!opts.ah_codebook)
return InvalidArgumentError(
"A SOAR hashed dataset needs the tokenization, the hashed dataset "
"and the AH codebook, which the assets lack.");
auto docids = std::make_unique<FixedLengthDocidCollection>(4);
docids->Reserve(tokenization.size() / 2);
for (size_t i = 1; i < tokenization.size(); i += 2)
SCANN_RETURN_IF_ERROR(
docids->Append(strings::Int32ToKey(tokenization[i])));
const size_t n = soar_hashed.second[0];
if (n > 0 && soar_hashed.second[1] != opts.hashed_dataset->dimensionality())
return InvalidArgumentError(absl::StrCat(
"The SOAR hashed dataset has ", soar_hashed.second[1],
" codes per datapoint, the hashed dataset ",
opts.hashed_dataset->dimensionality(), "."));
opts.soar_hashed_dataset = make_shared<DenseDataset<uint8_t>>(
std::move(soar_hashed.first), std::move(docids));
if (n == 0)
opts.soar_hashed_dataset->set_dimensionality(soar_hashed.second[1]);
SCANN_RETURN_IF_ERROR(ValidateHashedDataset(*opts.ah_codebook,
*opts.soar_hashed_dataset,
"SOAR hashed dataset"));
}
if (fp->fixed_point_dataset != nullptr) {
if (fp->squared_l2_norm_by_datapoint == nullptr)
fp->squared_l2_norm_by_datapoint = make_shared<vector<float>>();
opts.pre_quantized_fixed_point = fp;
}
return std::make_tuple(config, std::move(dataset), std::move(opts));
}
}
StatusOr<ScannInterface::ScannArtifacts> ScannInterface::LoadArtifacts(
const ScannConfig& config, const ScannAssets& assets) {
return LoadArtifactsWith(AssetReader(), config, assets);
}
StatusOr<ScannInterface::ScannArtifacts>
ScannInterface::LoadArtifactsFromMemory(
const absl::flat_hash_map<std::string, absl::string_view>& files) {
const AssetReader reader(&files);
ScannAssets assets;
SCANN_ASSIGN_OR_RETURN(absl::string_view assets_pbtxt,
reader.Get("scann_assets.pbtxt"));
SCANN_RETURN_IF_ERROR(CheckSerializationComplete(assets_pbtxt));
SCANN_RETURN_IF_ERROR(ParseTextProto(&assets, assets_pbtxt));
ScannConfig config;
SCANN_RETURN_IF_ERROR(reader.Proto("scann_config.pb", &config));
return LoadArtifactsWith(reader, config, assets);
}
std::string RewriteAssetFilenameIfRelative(const string& artifacts_dir,
const string& asset_path) {
std::filesystem::path path(asset_path);
if (path.is_relative()) {
return (artifacts_dir / path).string();
} else {
return asset_path;
}
}
StatusOr<ScannInterface::ScannArtifacts> ScannInterface::LoadArtifacts(
const std::string& artifacts_dir, const std::string& scann_assets_pbtxt) {
ScannAssets assets;
if (scann_assets_pbtxt.empty()) {
SCANN_ASSIGN_OR_RETURN(auto assets_pbtxt,
GetContents(artifacts_dir + "/scann_assets.pbtxt"));
SCANN_RETURN_IF_ERROR(CheckSerializationComplete(assets_pbtxt));
SCANN_RETURN_IF_ERROR(ParseTextProto(&assets, assets_pbtxt));
} else {
SCANN_RETURN_IF_ERROR(CheckSerializationComplete(scann_assets_pbtxt));
SCANN_RETURN_IF_ERROR(ParseTextProto(&assets, scann_assets_pbtxt));
}
ScannConfig config;
SCANN_RETURN_IF_ERROR(
ReadProtobufFromFile(artifacts_dir + "/scann_config.pb", &config));
for (auto i : Seq(assets.assets_size())) {
auto new_path = RewriteAssetFilenameIfRelative(
artifacts_dir, assets.assets(i).asset_path());
assets.mutable_assets(i)->set_asset_path(new_path);
}
return LoadArtifacts(config, assets);
}
StatusOr<std::unique_ptr<SingleMachineSearcherBase<float>>>
ScannInterface::CreateSearcher(ScannArtifacts artifacts) {
auto [config, dataset, opts] = std::move(artifacts);
if (config.has_l2_as_dot_product() ||
config.distance_measure().distance_measure() ==
kL2AsDotProductSavedDistance)
return FailedPreconditionError(
"This index uses l2_as_dot_product (squared L2 search through an "
"inner-product index): load it with ScannInterface::Initialize, "
"which applies the reduction to queries and results.");
if (dataset && config.has_partitioning() &&
config.partitioning().partitioning_type() ==
PartitioningConfig::SPHERICAL)
dataset->set_normalization_tag(research_scann::UNITL2NORM);
SCANN_ASSIGN_OR_RETURN(auto searcher, SingleMachineFactoryScann<float>(
config, dataset, std::move(opts)));
SCANN_RETURN_IF_ERROR(searcher->InitializeHealthStats());
searcher->MaybeReleaseDataset();
return searcher;
}
Status ScannInterface::Initialize(absl::string_view config_pbtxt,
absl::string_view scann_assets_pbtxt) {
SCANN_RETURN_IF_ERROR(ParseTextProto(&config_, config_pbtxt));
ScannAssets assets;
SCANN_RETURN_IF_ERROR(CheckSerializationComplete(scann_assets_pbtxt));
SCANN_RETURN_IF_ERROR(ParseTextProto(&assets, scann_assets_pbtxt));
SCANN_ASSIGN_OR_RETURN(auto dataset_and_opts, LoadArtifacts(config_, assets));
auto [_, dataset, opts] = std::move(dataset_and_opts);
return Initialize(std::tie(config_, dataset, opts));
}
Status ScannInterface::Initialize(
ScannConfig config, SingleMachineFactoryOptions opts,
ConstSpan<float> dataset, ConstSpan<int32_t> datapoint_to_token,
ConstSpan<uint8_t> hashed_dataset, ConstSpan<int8_t> int8_dataset,
ConstSpan<float> int8_multipliers, ConstSpan<float> dp_norms,
DatapointIndex n_points) {
config_ = config;
SCANN_RETURN_IF_ERROR(CheckDenseShape(dataset, n_points, "dataset"));
SCANN_RETURN_IF_ERROR(CheckDenseShape(int8_dataset, n_points, "int8 dataset"));
if (opts.ah_codebook != nullptr) {
if (hashed_dataset.empty())
return InvalidArgumentError("AH codebook present but hashed dataset is empty");
SCANN_RETURN_IF_ERROR(CheckDenseShape(hashed_dataset, n_points, "hashed dataset"));
vector<uint8_t> hashed_db(hashed_dataset.data(),
hashed_dataset.data() + hashed_dataset.size());
opts.hashed_dataset =
std::make_shared<DenseDataset<uint8_t>>(std::move(hashed_db), n_points);
}
const int spilling_mult = HasSoar(config_) ? 2 : 1;
SCANN_RETURN_IF_ERROR(
AddTokenizationToOptions(opts, datapoint_to_token, spilling_mult));
if (!int8_dataset.empty()) {
auto int8_data = std::make_shared<PreQuantizedFixedPoint>();
vector<int8_t> int8_vec(int8_dataset.data(),
int8_dataset.data() + int8_dataset.size());
int8_data->fixed_point_dataset =
std::make_shared<DenseDataset<int8_t>>(std::move(int8_vec), n_points);
int8_data->multiplier_by_dimension = make_shared<vector<float>>(
int8_multipliers.begin(), int8_multipliers.end());
int8_data->squared_l2_norm_by_datapoint =
make_shared<vector<float>>(dp_norms.begin(), dp_norms.end());
opts.pre_quantized_fixed_point = int8_data;
}
const DimensionIndex n_dim = SearcherPureDynamicDimensionality(config);
return Initialize(std::make_tuple(
config_, InitDataset(dataset, n_points, n_dim), std::move(opts)));
}
Status ScannInterface::Initialize(ConstSpan<float> dataset,
DatapointIndex n_points,
absl::string_view config,
int training_threads) {
SCANN_RETURN_IF_ERROR(ParseTextProto(&config_, config));
if (training_threads < 0)
return InvalidArgumentError("training_threads must be non-negative");
SCANN_RETURN_IF_ERROR(CheckDenseShape(dataset, n_points, "dataset"));
training_threads_ = training_threads;
if (training_threads == 0) training_threads = GetNumCPUs();
SingleMachineFactoryOptions opts;
opts.parallelization_pool =
StartThreadPool("scann_threadpool", training_threads - 1);
DimensionIndex n_dim = kInvalidDimension;
if (config_.input_output().pure_dynamic_config().has_dimensionality())
n_dim = config_.input_output().pure_dynamic_config().dimensionality();
shared_ptr<DenseDataset<float>> ds;
ApplyAutopilotL2AsDotProduct(&config_, dataset, n_points);
if (config_.has_l2_as_dot_product()) {
SCANN_ASSIGN_OR_RETURN(
ds, L2AsDotProductDataset(dataset, n_points, n_dim, &config_));
} else {
ds = InitDataset(dataset, n_points, n_dim);
}
if (ds && IsSphericalPartitioning(config_))
for (size_t i = 0; i < ds->size(); ++i)
NormalizeForSphericalPartitioning(ds->mutable_data(i));
return Initialize(std::make_tuple(config_, std::move(ds), std::move(opts)));
}
Status ScannInterface::Initialize(ScannInterface::ScannArtifacts artifacts) {
auto [config, dataset, opts] = std::move(artifacts);
SCANN_ASSIGN_OR_RETURN(l2_as_dot_product_, ToSearcherConfig(&config));
config_ = config;
if (config_.has_partitioning() &&
config_.partitioning().query_spilling().spilling_type() ==
QuerySpillingConfig::FIXED_NUMBER_OF_CENTERS &&
config_.partitioning().query_spilling().max_spill_centers() < 1)
return InvalidArgumentError(
"partitioning.query_spilling.max_spill_centers (the number of leaves "
"to search) must be > 0.");
if (dataset != nullptr)
SCANN_RETURN_IF_ERROR(
CheckAllFinite(dataset->data(), dataset->dimensionality(), "dataset"));
SCANN_ASSIGN_OR_RETURN(dimensionality_, opts.ComputeConsistentDimensionality(
config_, dataset.get()));
if (l2_as_dot_product_) {
if (dimensionality_ < 2)
return InvalidArgumentError(absl::StrCat(
"An l2_as_dot_product index stores vectors with an extra "
"coordinate, but this one's have ", dimensionality_,
" dimensions."));
--dimensionality_;
}
SCANN_ASSIGN_OR_RETURN(scann_,
CreateSearcher(std::tie(config_, dataset, opts)));
AdviseHugePagesForSearcher(*scann_);
if (scann_->config().has_value()) config_ = scann_->config().value();
absl::string_view distance = config_.distance_measure().distance_measure();
const absl::flat_hash_set<std::string> negated_distances{
"DotProductDistance", "BinaryDotProductDistance", "AbsDotProductDistance",
"LimitedInnerProductDistance"};
result_multiplier_ =
negated_distances.find(distance) == negated_distances.end() ? 1 : -1;
if (l2_as_dot_product_) {
result_multiplier_ = 1;
ToGivenConfig(*l2_as_dot_product_, &config_);
}
if (config_.has_partitioning()) {
min_batch_size_ = 1;
} else {
if (config_.has_hash())
min_batch_size_ = 16;
else
min_batch_size_ = 256;
}
SetNumThreads(GetNumCPUs());
return OkStatus();
}
void ScannInterface::SetNumThreads(int num_threads) {
absl::MutexLock lock(&pool_mu_);
num_threads_ = std::max(num_threads, 1);
parallel_query_pool_.reset();
pool_started_ = false;
}
std::shared_ptr<ThreadPool> ScannInterface::parallel_query_pool() const {
absl::MutexLock lock(&pool_mu_);
if (!pool_started_) {
parallel_query_pool_ =
StartThreadPool("ScannQueryingPool", num_threads_ - 1);
pool_started_ = true;
}
return parallel_query_pool_;
}
namespace {
std::shared_ptr<const TreeXOptionalParameters> TreeParametersForLeaves(
int leaves) {
thread_local int cached_leaves = -1;
thread_local std::shared_ptr<const TreeXOptionalParameters> cached;
if (leaves != cached_leaves || cached == nullptr) {
auto tree_params = std::make_shared<TreeXOptionalParameters>();
tree_params->set_num_partitions_to_search_override(leaves);
cached = std::move(tree_params);
cached_leaves = leaves;
}
return cached;
}
}
SearchParameters ScannInterface::GetSearchParameters(int final_nn,
int pre_reorder_nn,
int leaves) const {
SearchParameters params;
bool has_reordering = config_.has_exact_reordering();
int post_reorder_nn = -1;
if (has_reordering) {
post_reorder_nn = final_nn;
} else {
pre_reorder_nn = final_nn;
}
params.set_pre_reordering_num_neighbors(pre_reorder_nn);
params.set_post_reordering_num_neighbors(post_reorder_nn);
if (leaves > 0 && config_.has_partitioning())
params.set_searcher_specific_optional_parameters(
TreeParametersForLeaves(leaves));
return params;
}
vector<SearchParameters> ScannInterface::GetSearchParametersBatched(
int batch_size, int final_nn, int pre_reorder_nn, int leaves,
bool set_unspecified) const {
vector<SearchParameters> params(batch_size);
bool has_reordering = config_.has_exact_reordering();
int post_reorder_nn = -1;
if (has_reordering) {
post_reorder_nn = final_nn;
} else {
pre_reorder_nn = final_nn;
}
std::shared_ptr<const TreeXOptionalParameters> tree_params;
if (leaves > 0 && config_.has_partitioning())
tree_params = TreeParametersForLeaves(leaves);
for (auto& p : params) {
p.set_pre_reordering_num_neighbors(pre_reorder_nn);
p.set_post_reordering_num_neighbors(post_reorder_nn);
if (tree_params) p.set_searcher_specific_optional_parameters(tree_params);
if (set_unspecified) scann_->SetUnspecifiedParametersToDefaults(&p);
}
return params;
}
void ScannInterface::RefreshConfig() {
if (!scann_->config().has_value()) return;
config_ = *scann_->config();
if (l2_as_dot_product_) ToGivenConfig(*l2_as_dot_product_, &config_);
}
void ScannInterface::ToSquaredL2(const float* query,
NNResultsVector* res) const {
double base = l2_as_dot_product_->center;
for (size_t j = 0; j < dimensionality_; ++j)
base += static_cast<double>(query[j]) * query[j];
for (auto& [index, distance] : *res) {
const double d = base + 2.0 * static_cast<double>(distance);
distance = std::isnan(d) ? static_cast<float>(d)
: static_cast<float>(std::max(d, 0.0));
}
}
void ScannInterface::ToStoredDatapoints(ConstSpan<float> rows,
std::vector<float>* out) const {
const size_t dim = dimensionality_;
if (!l2_as_dot_product_) {
out->assign(rows.begin(), rows.end());
NormalizeDatapoints(MakeMutableSpan(*out));
return;
}
const size_t n = dim == 0 ? 0 : rows.size() / dim;
out->resize(n * (dim + 1));
for (size_t i = 0; i < n; ++i) {
const float* x = rows.data() + i * dim;
float* o = out->data() + i * (dim + 1);
std::copy(x, x + dim, o);
o[dim] = L2AsDotProductCoordinate(x, dim, *l2_as_dot_product_);
}
}
StatusOr<ScannConfig> ScannInterface::RetrainAndReindex(const string& config) {
absl::Mutex mu;
ScannConfig new_config = config_;
if (!config.empty())
SCANN_RETURN_IF_ERROR(ParseTextProto(&new_config, config));
if (l2_as_dot_product_) {
if (!new_config.has_l2_as_dot_product())
return InvalidArgumentError(
"This index uses l2_as_dot_product (its stored vectors have an "
"extra coordinate); a config to retrain it with must have "
"l2_as_dot_product too.");
L2AsDotProductConfig* p = new_config.mutable_l2_as_dot_product();
if ((p->has_scale() && p->scale() != l2_as_dot_product_->scale) ||
(p->has_center() && p->center() != l2_as_dot_product_->center))
return InvalidArgumentError(absl::StrCat(
"l2_as_dot_product's scale and center can't change when "
"retraining: the index's are ", l2_as_dot_product_->scale, " and ",
l2_as_dot_product_->center, "."));
p->set_scale(l2_as_dot_product_->scale);
p->set_center(l2_as_dot_product_->center);
} else if (new_config.has_l2_as_dot_product()) {
return InvalidArgumentError(
"l2_as_dot_product can't be added to an existing index by "
"retraining it; build a new index with it.");
}
SCANN_RETURN_IF_ERROR(ToSearcherConfig(&new_config).status());
std::shared_ptr<ThreadPool> pool =
training_threads_ > 0
? std::shared_ptr<ThreadPool>(
StartThreadPool("scann_threadpool", training_threads_ - 1))
: parallel_query_pool();
auto status_or =
RetrainAndReindexSearcher(scann_.get(), &mu, new_config, pool);
if (!status_or.ok()) return status_or.status();
scann_.reset(static_cast<SingleMachineSearcherBase<float>*>(
std::move(status_or.value().release())));
mu.WriterUnlock();
RefreshConfig();
SCANN_RETURN_IF_ERROR(scann_->InitializeHealthStats());
scann_->MaybeReleaseDataset();
AdviseHugePagesForSearcher(*scann_);
return config_;
}
bool ScannInterface::NormalizesDatapoints() const {
return IsSphericalPartitioning(config_);
}
void ScannInterface::NormalizeDatapoints(MutableSpan<float> rows) const {
if (!NormalizesDatapoints() || dimensionality_ == 0) return;
for (size_t begin = 0; begin + dimensionality_ <= rows.size();
begin += dimensionality_)
NormalizeForSphericalPartitioning(rows.subspan(begin, dimensionality_));
}
Status ScannInterface::Search(const DatapointPtr<float> query,
NNResultsVector* res, int final_nn,
int pre_reorder_nn, int leaves) const {
if (query.dimensionality() != dimensionality_)
return InvalidArgumentError(
absl::StrCat("Query has dimensionality ", query.dimensionality(),
", but the dataset has ", dimensionality_));
SearchParameters params =
GetSearchParameters(final_nn, pre_reorder_nn, leaves);
scann_->SetUnspecifiedParametersToDefaults(¶ms);
if (!l2_as_dot_product_) return scann_->FindNeighbors(query, params, res);
if (!query.IsDense())
return InvalidArgumentError("Queries must be dense.");
thread_local std::vector<float> augmented;
augmented.assign(query.values(), query.values() + dimensionality_);
augmented.push_back(static_cast<float>(l2_as_dot_product_->scale));
SCANN_RETURN_IF_ERROR(scann_->FindNeighbors(
DatapointPtr<float>(nullptr, augmented.data(), dimensionality_ + 1,
dimensionality_ + 1),
params, res));
ToSquaredL2(query.values(), res);
return OkStatus();
}
Status ScannInterface::SearchBatched(const DenseDataset<float>& queries,
MutableSpan<NNResultsVector> res,
int final_nn, int pre_reorder_nn,
int leaves) const {
if (queries.dimensionality() != dimensionality_)
return InvalidArgumentError(
absl::StrCat("Queries have dimensionality ", queries.dimensionality(),
", but the dataset has ", dimensionality_));
return SearchBatchedView(DefaultDenseDatasetView<float>(queries), res,
final_nn, pre_reorder_nn, leaves);
}
Status ScannInterface::SearchBatchedView(
const DefaultDenseDatasetView<float>& queries,
MutableSpan<NNResultsVector> res, int final_nn, int pre_reorder_nn,
int leaves) const {
SCANN_RETURN_IF_ERROR(
CheckAllFinite(queries.data(), dimensionality_, "query"));
if (!std::isinf(scann_->default_pre_reordering_epsilon()) ||
!std::isinf(scann_->default_post_reordering_epsilon()))
return InvalidArgumentError("Batch querying isn't supported with epsilon");
auto params = GetSearchParametersBatched(queries.size(), final_nn,
pre_reorder_nn, leaves, true);
if (!l2_as_dot_product_)
return scann_->FindNeighborsBatched(queries, params, MakeMutableSpan(res));
const size_t n = queries.size(), dim = dimensionality_;
std::vector<float> augmented(n * (dim + 1));
const float scale = static_cast<float>(l2_as_dot_product_->scale);
for (size_t i = 0; i < n; ++i) {
const float* q = queries.GetPtr(i);
std::copy(q, q + dim, augmented.data() + i * (dim + 1));
augmented[i * (dim + 1) + dim] = scale;
}
SCANN_RETURN_IF_ERROR(scann_->FindNeighborsBatched(
DefaultDenseDatasetView<float>(MakeConstSpan(augmented), dim + 1),
params, MakeMutableSpan(res)));
for (size_t i = 0; i < n; ++i) ToSquaredL2(queries.GetPtr(i), &res[i]);
return OkStatus();
}
Status ScannInterface::SearchBatchedParallel(const DenseDataset<float>& queries,
MutableSpan<NNResultsVector> res,
int final_nn, int pre_reorder_nn,
int leaves, int batch_size) const {
if (queries.dimensionality() != dimensionality_)
return InvalidArgumentError(
absl::StrCat("Queries have dimensionality ", queries.dimensionality(),
", but the dataset has ", dimensionality_));
return SearchBatchedRows(queries.data(), queries.dimensionality(), res,
final_nn, pre_reorder_nn, leaves, true,
batch_size);
}
Status ScannInterface::SearchBatchedRows(ConstSpan<float> queries,
size_t query_dim,
MutableSpan<NNResultsVector> res,
int final_nn, int pre_reorder_nn,
int leaves, bool parallel,
int batch_size,
const ChunkCallback& on_chunk) const {
if (query_dim != dimensionality_)
return InvalidArgumentError(
absl::StrCat("Queries have dimensionality ", query_dim,
", but the dataset has ", dimensionality_));
if (query_dim == 0 || queries.size() % query_dim != 0)
return InvalidArgumentError(absl::StrCat(
"Queries have ", queries.size(), " values, not a multiple of ",
query_dim));
const size_t num_queries = queries.size() / query_dim;
if (res.size() != num_queries)
return InvalidArgumentError(absl::StrCat(
"Result span has ", res.size(), " entries for ", num_queries,
" queries"));
if (batch_size < 1)
return InvalidArgumentError(
absl::StrCat("batch_size must be >= 1, got ", batch_size));
if (num_queries == 0) return OkStatus();
auto search_chunk = [&](size_t begin, size_t size) -> Status {
Status status;
if (size == 1) {
DatapointPtr<float> q(nullptr, queries.data() + begin * dimensionality_,
dimensionality_, dimensionality_);
status = Search(q, &res[begin], final_nn, pre_reorder_nn, leaves);
} else {
status = SearchBatchedView(
DefaultDenseDatasetView<float>(
queries.subspan(begin * dimensionality_, size * dimensionality_),
dimensionality_),
res.subspan(begin, size), final_nn, pre_reorder_nn, leaves);
}
if (status.ok() && on_chunk) on_chunk(begin, res.subspan(begin, size));
return status;
};
auto report = [&](Status status) {
if (status.ok()) return status;
Status finite = CheckAllFinite(queries, dimensionality_, "query");
return finite.ok() ? status : finite;
};
if (!parallel) return report(search_chunk(0, num_queries));
std::shared_ptr<ThreadPool> pool = parallel_query_pool();
const size_t workers = pool ? pool->NumThreads() + 1 : 1;
constexpr size_t kMaxSingleQueryChunk = 8;
const size_t cap = static_cast<size_t>(batch_size);
size_t chunk = std::min(
std::max(min_batch_size_, DivRoundUp(num_queries, workers)), cap);
if (min_batch_size_ == 1 && chunk <= kMaxSingleQueryChunk) chunk = 1;
Status status = OkStatus();
size_t failed_chunk = std::numeric_limits<size_t>::max();
std::atomic<bool> failed{false};
absl::Mutex status_mu;
ParallelFor<1>(Seq(DivRoundUp(num_queries, chunk)), pool.get(),
[&](size_t i) {
if (failed.load(std::memory_order_relaxed)) return;
const size_t begin = chunk * i;
Status chunk_status = search_chunk(
begin, std::min(num_queries - begin, chunk));
if (!chunk_status.ok()) {
absl::MutexLock lock(&status_mu);
if (i < failed_chunk) {
failed_chunk = i;
status = chunk_status;
}
failed.store(true, std::memory_order_relaxed);
}
});
return report(status);
}
StatusOr<ScannAssets> ScannInterface::Serialize(std::string path,
bool relative_path) {
SCANN_ASSIGN_OR_RETURN(auto opts,
scann_->ExtractSingleMachineFactoryOptions());
ScannAssets assets;
const auto add_asset = [&assets](absl::string_view fpath,
ScannAsset::AssetType type) {
ScannAsset* asset = assets.add_assets();
asset->set_asset_type(type);
asset->set_asset_path(fpath);
};
const auto convert_path = [&path, &relative_path](const std::string& fpath) {
std::string absolute_path = path + "/" + fpath;
return std::pair(relative_path ? fpath : absolute_path, absolute_path);
};
ScannConfig saved_config = config_;
if (l2_as_dot_product_)
saved_config.mutable_distance_measure()->set_distance_measure(
std::string(kL2AsDotProductSavedDistance));
SCANN_RETURN_IF_ERROR(
WriteProtobufToFile(path + "/scann_config.pb", saved_config));
if (opts.ah_codebook != nullptr) {
auto [rpath, fpath] = convert_path("ah_codebook.pb");
add_asset(rpath, ScannAsset::AH_CENTERS);
SCANN_RETURN_IF_ERROR(WriteProtobufToFile(fpath, *opts.ah_codebook));
}
if (opts.serialized_partitioner != nullptr) {
auto [rpath, fpath] = convert_path("serialized_partitioner.pb");
add_asset(rpath, ScannAsset::PARTITIONER);
SCANN_RETURN_IF_ERROR(
WriteProtobufToFile(fpath, *opts.serialized_partitioner));
}
if (opts.datapoints_by_token != nullptr) {
vector<int32_t> datapoint_to_token;
if (HasSoar(config_)) {
datapoint_to_token = vector<int32_t>(2 * n_points(), kSoarEmptyToken);
for (const auto& [token_idx, dps] :
Enumerate(*opts.datapoints_by_token)) {
for (auto dp_idx : dps) {
dp_idx *= 2;
if (datapoint_to_token[dp_idx] != -1) dp_idx++;
DCHECK_EQ(datapoint_to_token[dp_idx], -1);
datapoint_to_token[dp_idx] = token_idx;
}
}
} else {
datapoint_to_token = vector<int32_t>(n_points());
for (const auto& [token_idx, dps] : Enumerate(*opts.datapoints_by_token))
for (auto dp_idx : dps) datapoint_to_token[dp_idx] = token_idx;
}
auto [rpath, fpath] = convert_path("datapoint_to_token.npy");
add_asset(rpath, ScannAsset::TOKENIZATION_NPY);
SCANN_RETURN_IF_ERROR(VectorToNumpy(fpath, datapoint_to_token));
}
if (opts.hashed_dataset != nullptr) {
auto [rpath, fpath] = convert_path("hashed_dataset.npy");
add_asset(rpath, ScannAsset::AH_DATASET_NPY);
SCANN_RETURN_IF_ERROR(DatasetToNumpy(fpath, *(opts.hashed_dataset)));
if (opts.soar_hashed_dataset != nullptr) {
DCHECK(HasSoar(config_));
auto [rpath, fpath] = convert_path("hashed_dataset_soar.npy");
add_asset(rpath, ScannAsset::AH_DATASET_SOAR_NPY);
SCANN_RETURN_IF_ERROR(DatasetToNumpy(fpath, *(opts.soar_hashed_dataset)));
}
}
if (opts.bfloat16_dataset != nullptr) {
auto [rpath, fpath] = convert_path("bfloat16_dataset.npy");
add_asset(rpath, ScannAsset::BF16_DATASET_NPY);
SCANN_RETURN_IF_ERROR(DatasetToNumpy(fpath, *(opts.bfloat16_dataset)));
}
if (opts.pre_quantized_fixed_point != nullptr) {
auto fixed_point = opts.pre_quantized_fixed_point;
auto dataset = fixed_point->fixed_point_dataset;
if (dataset != nullptr) {
auto [rpath, fpath] = convert_path("int8_dataset.npy");
add_asset(rpath, ScannAsset::INT8_DATASET_NPY);
SCANN_RETURN_IF_ERROR(DatasetToNumpy(fpath, *dataset));
}
auto multipliers = fixed_point->multiplier_by_dimension;
if (multipliers != nullptr) {
auto [rpath, fpath] = convert_path("int8_multipliers.npy");
add_asset(rpath, ScannAsset::INT8_MULTIPLIERS_NPY);
SCANN_RETURN_IF_ERROR(VectorToNumpy(fpath, *multipliers));
}
auto norms = fixed_point->squared_l2_norm_by_datapoint;
if (norms != nullptr) {
auto [rpath, fpath] = convert_path("dp_norms.npy");
add_asset(rpath, ScannAsset::INT8_NORMS_NPY);
SCANN_RETURN_IF_ERROR(VectorToNumpy(fpath, *norms));
}
}
SCANN_ASSIGN_OR_RETURN(auto dataset, Float32DatasetIfNeeded());
if (dataset != nullptr) {
auto [rpath, fpath] = convert_path("dataset.npy");
add_asset(rpath, ScannAsset::DATASET_NPY);
SCANN_RETURN_IF_ERROR(DatasetToNumpy(fpath, *dataset));
}
return assets;
}
namespace {
constexpr absl::string_view kIndexFileNames[] = {
"ah_codebook.pb", "serialized_partitioner.pb",
"datapoint_to_token.npy", "hashed_dataset.npy",
"hashed_dataset_soar.npy", "bfloat16_dataset.npy",
"int8_dataset.npy", "int8_multipliers.npy",
"dp_norms.npy", "dataset.npy",
"scann_docids.pkl"};
Status WriteWholeFile(const std::string& path, absl::string_view contents) {
std::ofstream out(path, std::ofstream::binary | std::ofstream::trunc);
if (!out.write(contents.data(), contents.size()) || !out.flush())
return InternalError(absl::StrCat("Failed to write ", path));
return OkStatus();
}
Status FsyncPath(const std::string& path, bool directory) {
const int fd =
::open(path.c_str(), O_RDONLY | O_CLOEXEC | (directory ? O_DIRECTORY : 0));
if (fd < 0)
return InternalError(absl::StrCat("Failed to open ", path,
" for fsync: ", std::strerror(errno)));
const int rc = ::fsync(fd);
const int err = errno;
::close(fd);
if (rc != 0)
return InternalError(
absl::StrCat("fsync of ", path, " failed: ", std::strerror(err)));
return OkStatus();
}
Status RenamePath(const std::string& from, const std::string& to) {
std::error_code ec;
std::filesystem::rename(from, to, ec);
if (ec)
return InternalError(absl::StrCat("Failed to rename ", from, " to ", to,
": ", ec.message()));
return OkStatus();
}
}
Status ScannInterface::SerializeToDirectory(
const std::string& dir, bool relative_path,
const std::vector<std::pair<std::string, std::string>>& extra_files) {
namespace fs = std::filesystem;
std::error_code ec;
if (!fs::is_directory(dir, ec))
return NotFoundError(
absl::StrCat(dir, " isn't an existing directory; create it first."));
for (const auto& [name, contents] : extra_files) {
if (name.empty() || name[0] == '.' || name.find('/') != std::string::npos ||
name == "scann_config.pb" || name == "scann_assets.pbtxt" ||
(name != "scann_docids.pkl" &&
absl::c_linear_search(kIndexFileNames, name)))
return InvalidArgumentError(
absl::StrCat("Invalid extra file name \"", name, "\"."));
}
vector<fs::path> leftovers;
for (fs::directory_iterator it(dir, ec), end; !ec && it != end;
it.increment(ec)) {
if (absl::StartsWith(it->path().filename().string(), ".scann_staging_"))
leftovers.push_back(it->path());
}
for (const fs::path& leftover : leftovers) fs::remove_all(leftover, ec);
std::string staging;
std::random_device rd;
for (int attempt = 0;; ++attempt) {
staging = absl::StrCat(dir, "/.scann_staging_",
absl::Hex(rd(), absl::kZeroPad8),
absl::Hex(rd(), absl::kZeroPad8));
if (fs::create_directory(staging, ec)) break;
if (ec || attempt == 10)
return InternalError(absl::StrCat("Failed to create a staging directory ",
"in ", dir, ": ", ec.message()));
}
struct RemoveOnExit {
std::string path;
~RemoveOnExit() {
std::error_code ec;
fs::remove_all(path, ec);
}
} remove_staging{staging};
SCANN_ASSIGN_OR_RETURN(ScannAssets assets,
Serialize(staging, true));
fs::path absolute_dir;
if (!relative_path) {
absolute_dir = fs::absolute(dir, ec);
if (ec)
return InternalError(absl::StrCat("Failed to make ", dir,
" an absolute path: ", ec.message()));
}
vector<std::string> files = {"scann_config.pb"};
for (ScannAsset& asset : *assets.mutable_assets()) {
files.push_back(asset.asset_path());
if (!relative_path)
asset.set_asset_path(
(absolute_dir / asset.asset_path()).lexically_normal().string());
}
for (const auto& [name, contents] : extra_files) {
SCANN_RETURN_IF_ERROR(WriteWholeFile(staging + "/" + name, contents));
files.push_back(name);
}
std::string manifest;
if (!google::protobuf::TextFormat::PrintToString(assets, &manifest))
return InternalError("Failed to print the ScannAssets proto.");
SCANN_RETURN_IF_ERROR(
WriteWholeFile(staging + "/scann_assets.pbtxt", manifest));
SCANN_RETURN_IF_ERROR(WriteWholeFile(
staging + "/incomplete",
absl::StrCat("# scann-core: serialize() is writing this index "
"directory, or was\n# interrupted while writing it. Its "
"files may come from different indexes.\n# Serialize the "
"index again.\n",
kIncompleteSerializationMarker, ": true\n")));
for (const std::string& f : files)
SCANN_RETURN_IF_ERROR(FsyncPath(staging + "/" + f, false));
SCANN_RETURN_IF_ERROR(FsyncPath(staging + "/scann_assets.pbtxt", false));
SCANN_RETURN_IF_ERROR(FsyncPath(staging + "/incomplete", false));
const std::string manifest_path = dir + "/scann_assets.pbtxt";
SCANN_RETURN_IF_ERROR(RenamePath(staging + "/incomplete", manifest_path));
SCANN_RETURN_IF_ERROR(FsyncPath(dir, true));
for (absl::string_view name : kIndexFileNames) {
if (absl::c_linear_search(files, name)) continue;
const std::string path = absl::StrCat(dir, "/", name);
fs::remove(path, ec);
if (ec)
return InternalError(
absl::StrCat("Failed to remove ", path, ": ", ec.message()));
}
for (const std::string& f : files)
SCANN_RETURN_IF_ERROR(RenamePath(staging + "/" + f, dir + "/" + f));
SCANN_RETURN_IF_ERROR(FsyncPath(dir, true));
SCANN_RETURN_IF_ERROR(
RenamePath(staging + "/scann_assets.pbtxt", manifest_path));
return FsyncPath(dir, true);
}
StatusOr<ScannInterface::ScannHealthStats> ScannInterface::GetHealthStats()
const {
return scann_->GetHealthStats();
}
Status ScannInterface::InitializeHealthStats() {
return scann_->InitializeHealthStats();
}
StatusOr<SingleMachineFactoryOptions> ScannInterface::ExtractOptions() {
return scann_->ExtractSingleMachineFactoryOptions();
}
}