strawberry/tests/test_fleet_merge.cpp
trvon 758ef9db07
fleet: node-share cap never below the fair share 1/N
Seen in the dockerized 3-sensor run: max_node_share=0.25 (pillar default) with
3 similar-sized nodes cut every node to 25% of the total, dropping 158/468
windows (34%) while correcting no imbalance. The cap is now
max(max_node_share, 1/N) * total, so a balanced fleet is never trimmed and
only nodes above an equal share are cut. Test: balanced 3-node fleet keeps
all windows; a dominant 4th node is still trimmed.

Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
2026-11-14 11:29:06 -07:00

446 lines
20 KiB
C++

#include <unistd.h>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <filesystem>
#include <string>
#include <vector>
#include "strawberry/fleet_export.hpp"
#include "strawberry/fleet_merge.hpp"
#include "strawberry/learn/mlp.hpp"
#include "strawberry/learn/train.hpp"
using namespace strawberry;
using namespace strawberry::fleet;
#define CHECK(cond) \
do { \
if (!(cond)) { \
std::fprintf(stderr, "FAIL %s:%d: %s\n", __FILE__, __LINE__, #cond); \
std::exit(1); \
} \
} while (0)
static std::string temp_path(const char* tag) {
static int n = 0;
auto p = std::filesystem::temp_directory_path() /
("sb_fleet_merge_" + std::to_string(::getpid()) + "_" + tag + "_" + std::to_string(n++) + ".seg");
std::filesystem::remove(p);
return p.string();
}
static std::string make_bundle(const char* tag, const std::string& node_uid, int n_windows, int n_positive) {
std::vector<store::PendingRecord> recs;
for (int i = 0; i < n_windows; ++i) {
const std::string wid = "w" + std::to_string(i);
ExportWindow w;
w.window_id = wid;
w.start_ns = i;
recs.push_back({store::RecordType::export_window, encode_export_window(w)});
ExportWindowFeature f;
f.window_id = wid;
for (std::size_t j = 0; j < f.features.size(); ++j) f.features[j] = static_cast<float>(i);
recs.push_back({store::RecordType::export_window_feature, encode_export_window_feature(f)});
if (i < n_positive) {
ExportLabel l;
l.window_id = wid;
l.polarity = LabelPolarity::positive;
recs.push_back({store::RecordType::export_label, encode_export_label(l)});
}
}
ExportManifest m;
m.node_uid = node_uid;
const std::string path = temp_path(tag);
std::string err;
CHECK(write_export_bundle(path, m, recs, err));
return path;
}
// Bundle with a learnable signal: every 3rd window is positive (feature = 1), and each window's
// top3_bits is set to 4.5. Written to `path`.
static void make_signal_bundle(const std::string& path, const std::string& node_uid, int n_windows) {
std::vector<store::PendingRecord> recs;
for (int i = 0; i < n_windows; ++i) {
const std::string wid = "w" + std::to_string(i);
const bool positive = i % 3 == 0;
ExportWindow w;
w.window_id = wid;
w.start_ns = i;
w.top3_bits = 4.5f;
recs.push_back({store::RecordType::export_window, encode_export_window(w)});
ExportWindowFeature f;
f.window_id = wid;
for (std::size_t j = 0; j < f.features.size(); ++j) f.features[j] = positive ? 1.0f : 0.0f;
recs.push_back({store::RecordType::export_window_feature, encode_export_window_feature(f)});
if (positive) {
ExportLabel l;
l.window_id = wid;
l.polarity = LabelPolarity::positive;
recs.push_back({store::RecordType::export_label, encode_export_label(l)});
}
}
ExportManifest m;
m.node_uid = node_uid;
std::string err;
CHECK(write_export_bundle(path, m, recs, err));
}
static ExportRaritySketch make_sketch(uint8_t kind, uint32_t w, float v, double total) {
ExportRaritySketch sk;
sk.kind = kind;
sk.width_log2 = w;
sk.depth = 2;
sk.total = total;
sk.cells.assign((std::size_t(1) << w) * sk.depth, v);
return sk;
}
static std::string make_rarity_bundle(const char* tag, const std::vector<ExportRaritySketch>& sks) {
std::vector<store::PendingRecord> recs;
for (const auto& sk : sks) recs.push_back({store::RecordType::export_rarity_delta, encode_export_rarity(sk)});
ExportManifest m;
m.node_uid = tag;
const std::string path = temp_path(tag);
std::string err;
CHECK(write_export_bundle(path, m, recs, err));
return path;
}
struct WinSpec {
const char* id;
int64_t start_ns;
float feat;
bool positive;
};
static std::string make_node_bundle(const char* tag, const std::string& node_uid, uint64_t created_ns,
const std::vector<WinSpec>& wins,
const std::vector<ExportRaritySketch>& sketches = {}) {
std::vector<store::PendingRecord> recs;
for (const auto& ws : wins) {
ExportWindow w;
w.window_id = ws.id;
w.start_ns = ws.start_ns;
recs.push_back({store::RecordType::export_window, encode_export_window(w)});
ExportWindowFeature f;
f.window_id = ws.id;
f.features.fill(ws.feat);
recs.push_back({store::RecordType::export_window_feature, encode_export_window_feature(f)});
if (ws.positive) {
ExportLabel l;
l.window_id = ws.id;
l.polarity = LabelPolarity::positive;
recs.push_back({store::RecordType::export_label, encode_export_label(l)});
}
}
for (const auto& sk : sketches) recs.push_back({store::RecordType::export_rarity_delta, encode_export_rarity(sk)});
ExportManifest m;
m.node_uid = node_uid;
m.created_unix_ns = created_ns;
const std::string path = temp_path(tag);
std::string err;
CHECK(write_export_bundle(path, m, recs, err));
return path;
}
int main() {
{ // M-dup: same window across one node's bundles is merged once; labels OR; newest wins; nodes stay separate
const std::string a1 = make_node_bundle("mdup_a1", "nodeA", 100, {{"W", 10, 1.0f, false}, {"X", 20, 5.0f, false}});
const std::string a2 = make_node_bundle("mdup_a2", "nodeA", 200, {{"W", 11, 2.0f, true}});
const std::string b1 = make_node_bundle("mdup_b1", "nodeB", 150, {{"W", 30, 9.0f, false}});
FleetMergeOptions opt;
opt.max_node_share = 0;
std::vector<learn::TrainingExample> out;
const FleetMergeReport r = fleet_merge({a1, a2, b1}, opt, out);
CHECK(r.duplicate_windows == 1);
CHECK(r.examples == 3 && out.size() == 3);
CHECK(r.positives == 1);
// first-seen order: A:W, A:X, B:W
CHECK(out[0].entity == "nodeA" && out[0].label == 1.0f);
CHECK(out[0].start_ns == 11 && out[0].x[0] == 2.0f); // newest bundle's features/start
CHECK(out[1].entity == "nodeA" && out[1].label == 0.0f && out[1].start_ns == 20);
CHECK(out[2].entity == "nodeB" && out[2].label == 0.0f && out[2].start_ns == 30 && out[2].x[0] == 9.0f);
// Newer bundle first in the path list: features still come from the newest, label stays OR'd.
std::vector<learn::TrainingExample> rev;
const FleetMergeReport r2 = fleet_merge({a2, a1, b1}, opt, rev);
CHECK(r2.duplicate_windows == 1);
CHECK(rev.size() == 3);
std::size_t aw = 0;
for (const auto& e : rev) {
if (e.entity == "nodeA" && e.start_ns == 11) {
++aw;
CHECK(e.label == 1.0f && e.x[0] == 2.0f);
}
}
CHECK(aw == 1);
// Order-independence once the paths are sorted.
std::vector<std::string> p1{a1, a2, b1}, p2{b1, a2, a1};
std::sort(p1.begin(), p1.end());
std::sort(p2.begin(), p2.end());
std::vector<learn::TrainingExample> o1, o2;
fleet_merge(p1, opt, o1);
fleet_merge(p2, opt, o2);
CHECK(o1.size() == o2.size());
for (std::size_t i = 0; i < o1.size(); ++i)
CHECK(o1[i].entity == o2[i].entity && o1[i].label == o2[i].label && o1[i].start_ns == o2[i].start_ns);
for (const auto& p : {a1, a2, b1}) std::filesystem::remove(p);
}
{ // O-newest: only the newest bundle per node contributes; overlay files are skipped
const std::string a1 = make_node_bundle("onew_a1", "nodeA", 100, {}, {make_sketch(0, 4, 1.0f, 10)});
const std::string a2 = make_node_bundle("onew_a2", "nodeA", 200, {}, {make_sketch(0, 4, 2.0f, 20)});
const std::string b1 = make_node_bundle("onew_b1", "nodeB", 50, {}, {make_sketch(0, 4, 4.0f, 40)});
const std::string ovl = make_node_bundle("onew_ovl", "fleet-overlay", 0, {}, {make_sketch(0, 4, 100.0f, 1000)});
for (const auto& order : {std::vector<std::string>{a1, a2, b1, ovl}, std::vector<std::string>{ovl, b1, a2, a1}}) {
FleetOverlay ov;
std::string err;
const auto rep = merge_rarity_overlay(order, "", ov, err);
CHECK(rep.bundles_read == 4);
CHECK(rep.bundles_superseded == 1);
CHECK(rep.overlays_skipped == 1);
CHECK(ov.nodes_merged == 2);
CHECK(ov.present[0]);
CHECK(ov.sketches[0].cells.size() == 32);
for (float c : ov.sketches[0].cells) CHECK(c == 6.0f); // s2 + s3
CHECK(ov.sketches[0].total == 60.0);
}
for (const auto& p : {a1, a2, b1, ovl}) std::filesystem::remove(p);
}
{ // join, no cap
const std::string a = make_bundle("a", "a", 3, 1);
const std::string b = make_bundle("b", "b", 2, 0);
FleetMergeOptions opt;
opt.max_node_share = 0;
std::vector<learn::TrainingExample> out;
FleetMergeReport r = fleet_merge({a, b}, opt, out);
CHECK(out.size() == 5);
CHECK(r.positives == 1);
CHECK(r.nodes == 2);
CHECK(r.examples == 5);
int pos = 0;
for (const auto& e : out) pos += e.label == 1.0f ? 1 : 0;
CHECK(pos == 1);
CHECK(out[0].entity == "a");
CHECK(out[0].label == 1.0f);
CHECK(out[0].x[0] == 0.0f && out[0].x[255] == 0.0f);
CHECK(out[1].x[0] == 1.0f && out[1].start_ns == 1);
CHECK(out[3].entity == "b");
std::filesystem::remove(a);
std::filesystem::remove(b);
}
{ // cap
const std::string big = make_bundle("big", "big", 100, 0);
const std::string small = make_bundle("small", "small", 1, 0);
FleetMergeOptions opt;
opt.max_node_share = 0.25;
opt.seed = 7;
std::vector<learn::TrainingExample> out1, out2;
FleetMergeReport r = fleet_merge({big, small}, opt, out1);
std::size_t nbig = 0, nsmall = 0;
for (const auto& e : out1) {
if (e.entity == "big") ++nbig;
if (e.entity == "small") ++nsmall;
}
// 2 nodes: the fair-share floor 1/2 beats 0.25 -> cap = floor(0.5 * 101) = 50.
CHECK(nbig == 50);
CHECK(nsmall == 1);
CHECK(out1.size() == 51);
CHECK(r.capped_nodes == 1);
CHECK(r.dropped_for_cap == 50);
fleet_merge({big, small}, opt, out2);
CHECK(out1.size() == out2.size());
for (std::size_t i = 0; i < out1.size(); ++i) CHECK(out1[i].start_ns == out2[i].start_ns);
std::filesystem::remove(big);
std::filesystem::remove(small);
}
{ // balanced fleet is never trimmed; a dominant node still is
const std::string a = make_bundle("ba", "ba", 40, 0);
const std::string b = make_bundle("bb", "bb", 40, 0);
const std::string c = make_bundle("bc", "bc", 40, 0);
const std::string d = make_bundle("bd", "bd", 200, 0);
FleetMergeOptions opt;
opt.max_node_share = 0.25;
std::vector<learn::TrainingExample> bal, dom;
const FleetMergeReport rb = fleet_merge({a, b, c}, opt, bal);
CHECK(bal.size() == 120 && rb.capped_nodes == 0 && rb.dropped_for_cap == 0);
const FleetMergeReport rd = fleet_merge({a, b, c, d}, opt, dom);
// total 320, N=4: share max(0.25, 0.25) = 0.25 -> cap 80; only the 200-window node is trimmed.
CHECK(rd.capped_nodes == 1 && rd.dropped_for_cap == 120 && dom.size() == 200);
for (const auto& f : {a, b, c, d}) std::filesystem::remove(f);
}
{ // skip
const std::string good = make_bundle("good", "g", 2, 1);
const std::string missing = temp_path("missing");
FleetMergeOptions opt;
opt.max_node_share = 0;
std::vector<learn::TrainingExample> out;
FleetMergeReport r = fleet_merge({missing, good}, opt, out);
CHECK(r.bundles_failed == 1);
CHECK(r.bundles_read == 1);
CHECK(r.errors.size() == 1);
CHECK(out.size() == 2);
std::filesystem::remove(good);
}
{ // rarity_bits carried from ExportWindow.top3_bits
const std::string p = temp_path("rarity");
std::vector<store::PendingRecord> recs;
ExportWindow w;
w.window_id = "w0";
w.start_ns = 0;
w.top3_bits = 4.5f;
recs.push_back({store::RecordType::export_window, encode_export_window(w)});
ExportWindowFeature f;
f.window_id = "w0";
recs.push_back({store::RecordType::export_window_feature, encode_export_window_feature(f)});
ExportManifest m;
m.node_uid = "r";
std::string err;
CHECK(write_export_bundle(p, m, recs, err));
FleetMergeOptions opt;
opt.max_node_share = 0;
std::vector<learn::TrainingExample> out;
fleet_merge({p}, opt, out);
CHECK(out.size() == 1);
CHECK(out[0].rarity_bits == 4.5f);
std::filesystem::remove(p);
}
{ // merge + train, in-process
const auto dir = std::filesystem::temp_directory_path() / ("sb_fleet_train_" + std::to_string(::getpid()));
std::filesystem::remove_all(dir);
std::filesystem::create_directories(dir);
const std::string a = (dir / "a.seg").string();
const std::string b = (dir / "b.seg").string();
make_signal_bundle(a, "a", 60);
make_signal_bundle(b, "b", 60);
FleetMergeOptions opt;
opt.max_node_share = 0;
std::vector<learn::TrainingExample> examples;
fleet_merge({a, b}, opt, examples);
CHECK(examples.size() == 120);
auto model = learn::Model::initialized(learn::ModelShape{}, 1);
learn::TrainOptions topt;
topt.epochs = 5;
topt.seed = 1;
const auto tr = learn::train_value(model, examples, topt);
if (!tr.error.empty()) std::fprintf(stderr, "train error: %s (examples %zu)\n", tr.error.c_str(), examples.size());
CHECK(tr.error.empty());
CHECK(tr.train > 0 && tr.test > 0);
CHECK(tr.train_positives > 0 && tr.test_positives > 0);
std::filesystem::remove_all(dir);
}
{ // rarity overlay
const std::string A = make_rarity_bundle("ra", {make_sketch(0, 4, 1.0f, 10), make_sketch(2, 4, 1.0f, 10)});
const std::string B = make_rarity_bundle("rb", {make_sketch(0, 4, 2.0f, 20), make_sketch(2, 4, 2.0f, 20)});
const std::string C = make_rarity_bundle("rc", {make_sketch(0, 5, 7.0f, 5)});
{ // sum
FleetOverlay ov;
std::string err;
const auto rep = merge_rarity_overlay({A, B}, "", ov, err);
CHECK(rep.bundles_read == 2);
CHECK(ov.nodes_merged == 2);
CHECK(ov.present[0]);
CHECK(ov.present[2]);
CHECK(ov.sketches[0].cells.size() == 32);
for (std::size_t i = 0; i < ov.sketches[0].cells.size(); ++i) CHECK(ov.sketches[0].cells[i] == 3.0f);
CHECK(ov.sketches[0].total == 30.0);
}
{ // mismatch
FleetOverlay ov;
std::string err;
const auto rep = merge_rarity_overlay({A, C}, "", ov, err);
CHECK(rep.skipped_mismatch >= 1);
CHECK(ov.sketches[0].width_log2 == 4);
CHECK(ov.sketches[0].cells.size() == 32);
for (std::size_t i = 0; i < ov.sketches[0].cells.size(); ++i) CHECK(ov.sketches[0].cells[i] == 1.0f);
}
{ // serialize round-trip
FleetOverlay ov;
std::string err;
const std::string outp = temp_path("overlay_out");
merge_rarity_overlay({A, B}, outp, ov, err);
ExportManifest back;
bool found = false;
const bool ok = read_export_bundle(outp, back, [&](uint32_t type, std::string_view payload) {
if (type != static_cast<uint32_t>(store::RecordType::export_rarity_delta)) return;
ExportRaritySketch sk;
if (!decode_export_rarity(payload, sk) || sk.kind != 0) return;
found = true;
CHECK(sk.width_log2 == 4);
for (float c : sk.cells) CHECK(c == 3.0f);
});
CHECK(ok);
CHECK(found);
CHECK(back.node_uid == "fleet-overlay");
std::filesystem::remove(outp);
}
{ // dir -> overlay -> load (the flow `fleet overlay` runs)
const auto dirp = std::filesystem::temp_directory_path() / ("sb_fleet_overlay_dir_" + std::to_string(::getpid()));
std::filesystem::remove_all(dirp);
std::filesystem::create_directories(dirp);
std::filesystem::copy_file(A, dirp / "a.seg");
std::filesystem::copy_file(B, dirp / "b.seg");
std::vector<std::string> globbed;
for (const auto& e : std::filesystem::directory_iterator(dirp)) {
if (e.is_regular_file()) globbed.push_back(e.path().string());
}
std::sort(globbed.begin(), globbed.end());
CHECK(globbed.size() == 2);
const std::string outp = temp_path("overlay_dir_out");
FleetOverlay ov;
std::string err;
const auto rep = merge_rarity_overlay(globbed, outp, ov, err);
CHECK(rep.bundles_read == 2);
LoadedOverlay lo;
std::string e2;
CHECK(load_fleet_overlay(outp, lo, e2));
CHECK(lo.loaded >= 1);
std::filesystem::remove(outp);
std::filesystem::remove_all(dirp);
}
{ // skip missing
FleetOverlay ov;
std::string err;
const auto rep = merge_rarity_overlay({"/nonexistent/sb_no_such_bundle.seg", A}, "", ov, err);
CHECK(rep.bundles_failed == 1);
CHECK(rep.errors.size() >= 1);
CHECK(rep.bundles_read == 1);
CHECK(ov.present[0]);
}
std::filesystem::remove(A);
std::filesystem::remove(B);
std::filesystem::remove(C);
}
{ // overlay surprisal primitives
learn::CountMinSketch sk(8, 2);
for (int i = 0; i < 200; ++i) sk.add("common");
const double common = learn::sketch_surprisal_bits(sk, "common");
const double rare = learn::sketch_surprisal_bits(sk, "never-seen-tuple");
CHECK(common >= 0.0);
CHECK(rare > common);
auto sk2 = learn::CountMinSketch::from_cells(sk.width_log2(), sk.depth(), sk.cells(), sk.total());
CHECK(sk2.estimate("common") == sk.estimate("common"));
CHECK(learn::sketch_surprisal_bits(sk2, "common") == common);
learn::CountMinSketch ck(8, 2);
for (int i = 0; i < 500; ++i) ck.add("curl|public|443");
ExportRaritySketch es;
es.kind = static_cast<uint8_t>(learn::TupleKind::exe_connect);
es.width_log2 = ck.width_log2();
es.depth = ck.depth();
es.total = ck.total();
es.cells = ck.cells();
const std::string path = make_rarity_bundle("ovl", {es});
LoadedOverlay ov;
std::string err;
CHECK(load_fleet_overlay(path, ov, err));
CHECK(ov.loaded >= 1);
const double seen = overlay_surprisal(ov, learn::TupleKind::exe_connect, "curl|public|443");
const double unseen = overlay_surprisal(ov, learn::TupleKind::exe_connect, "nope|x|1");
CHECK(unseen > seen);
CHECK(overlay_surprisal(ov, learn::TupleKind::lineage3, "a>b>c") == 0.0);
std::filesystem::remove(path);
}
std::puts("ok");
return 0;
}