Ubuntu – boost serialization incompatibility between 1.74 and 1.83 with multi index container

Looking at this a long time, I couldn’t see it. However, by fixing the seeds and verifying that we get deterministic data, I noticed that the results were "identical" but for the order.

I noticed the default index already relies on the hash indirectly, multiple times:

                      ┌─────────────────────┐
                      │                     │
                  ┌−−−−−−−−−−−−−−−−−┐       │
                  ╎      both       ╎       │
                  ╎                 ╎       ▼
┌───────────┐     ╎ ┌─────────────┐ ╎     ┌────────┐     ┌───────────────┐     ┌───────────────────────┐
│ operator< │ ──▶ ╎ │    id()     │ ╎ ──▶ │ hash() │ ──▶ │ boost::hash<> │ ──▶ │ boost::hash_combine() │
└───────────┘     ╎ └─────────────┘ ╎     └────────┘     └───────────────┘     └───────────────────────┘
                  ╎   │             ╎
                  ╎   │             ╎
                  ╎   ▼             ╎
                  ╎ ┌─────────────┐ ╎
                  ╎ │ frozen_id() │ ╎
                  ╎ └─────────────┘ ╎
                  ╎                 ╎
                  └−−−−−−−−−−−−−−−−−┘

Since the first index is actually also unique, and the only constituent parts are hashes and the angle, this might cause different uniqueness across version of Boost ContainerHash.

Boost hash_combine does not guarantee stability or portability. In fact, most common hash functions don’t, e.g. std::hash:

The actual hash functions are implementation-dependent and are not required to fulfill any other quality criteria except those specified above

In fact persisting information depending on deterministic hash is a logic error anywhere, unless you’re only re-reading the same information in the same process, because

Hash functions are only required to produce the same result for the same input within a single execution of a program; this allows salted hashes that prevent collision denial-of-service attacks.

Specifically, hash_combine has received many changes between 1.74 and 1.83. You should rethink your indexes. In fact, I would consider it a smell that a hash depending on non-unique hashes is being used as the key (identity) to a unique index.

Fixing?

To avoid violating the total ordering contract that the index expects (it’s basically like you edited the key fields by "editing" the hash function), I’d expect the hash to be something like

inline constexpr std::tuple<double, angle_type> key() const { return {_length, _angle}; }
friend std::size_t hash_value(content const& c) { return boost::hash_value(c.key()); }

And then perhaps something more like:

    using key_type = std::tuple<double, angle_type>;
    key_type      key() const                  { return {_length, _angle}; }
    key_type      frozen_key() const           { return frozen().key(); }

    friend size_t hash_value(content const& c) { return boost::hash_value(c.key()); }
    size_t        hash() const                 { return hash_value(*this); }

    auto idkey() const                         { return std::tuple(frozen_key(), key(), angle()); }
    std::string id() const                     { return fmt::format("{}", idkey()); }
    bool operator<(content const& other) const { return idkey() < other.idkey(); }

Where I substituted libfmt for Boost Format, because it can directly format tuples without me doing the work 🙂

Basically, I’d not throw away the information, which seemed like code smell anyways, but also caused the indexes to rely on non-deterministic functions.

Here’s my motivating code listing, complete with the tweaks to optionally use a fixed seed:

Live On Coliru

#include <boost/archive/binary_iarchive.hpp>
#include <boost/archive/binary_oarchive.hpp>
#include <boost/archive/text_iarchive.hpp>
#include <boost/archive/text_oarchive.hpp>
#include <boost/container_hash/hash.hpp>
#include <boost/core/nvp.hpp>
#include <boost/lexical_cast.hpp>
#include <boost/multi_index/key.hpp>
#include <boost/multi_index/ordered_index.hpp>
#include <boost/multi_index_container.hpp>
#include <boost/serialization/utility.hpp>
#include <boost/serialization/vector.hpp>
#include <cstdint>
#include <filesystem>
#include <fstream>
#include <iostream>
#include <random>
#include <string>

#include <fmt/format.h>
#include <fmt/ranges.h>

static constexpr boost::archive::archive_flags FLAGS = boost::archive::archive_flags::no_tracking; //  {};

#if 1
    using IA = boost::archive::binary_iarchive;
    using OA = boost::archive::binary_oarchive;
#else
    using IA = boost::archive::text_iarchive;
    using OA = boost::archive::text_oarchive;
#endif

namespace mre {

    struct content {
        friend class boost::serialization::access;
        using angle_type = std::size_t;

        inline content(angle_type angle) : _angle(angle) {}
        inline angle_type angle() const { return _angle; }

        void reset_angle_random(size_t seed) {
            static std::mt19937             rng_angle(seed);
            std::uniform_int_distribution<> angle_dist(0, 180);
            _angle = angle_dist(rng_angle);
        }

        void freeze() {
            // complicated deterministic business logic
            _angle = 0;
        }
        content frozen() const {
            mre::content copy(*this);
            copy.freeze();
            return copy;
        }

        static content generate() {
            return generate(std::random_device{}());
        }
        static content generate(size_t seed) {
            static std::mt19937              rng(seed);
            std::uniform_real_distribution<> dist_length(-0.5f, 0.5f);

            mre::content content{0};
            content._length = dist_length(rng);
            content.reset_angle_random(rng());
            return content;
        }

        template <class Archive> void serialize(Archive& ar, unsigned) {
            ar& boost::serialization::make_nvp("length", _length);
            ar& boost::serialization::make_nvp("angle", _angle);
        }

        using key_type = std::tuple<double, angle_type>;
        key_type      key() const                  { return {_length, _angle}; }
        key_type      frozen_key() const           { return frozen().key(); }

        friend size_t hash_value(content const& c) { return boost::hash_value(c.key()); }
        size_t        hash() const                 { return hash_value(*this); }

        auto idkey() const                         { return std::tuple(frozen_key(), key(), angle()); }
        std::string id() const                     { return fmt::format("{}", idkey()); }
        bool operator<(content const& other) const { return idkey() < other.idkey(); }

      private:
        double     _length;
        angle_type _angle;

      private:
        content() = default;
    };

    struct parameters {
        std::size_t degree;
        std::size_t frame_size;

        template <class Archive> void serialize(Archive& ar, unsigned) {
            ar& boost::serialization::make_nvp("degree", degree);
            ar& boost::serialization::make_nvp("frame_size", frame_size);
        }
    };

    std::ostream& operator<<(std::ostream& stream, mre::parameters const& params);

    namespace bmi = boost::multi_index;

    struct package {
        friend class boost::serialization::access;

        struct tags {
            struct id {};
            struct content {};
            struct angle {};
            struct frozen {};
        };

        using container = bmi::multi_index_container<
            mre::content,
            bmi::indexed_by<
                bmi::ordered_unique<bmi::identity<mre::content>>,
                bmi::ordered_unique<bmi::tag<tags::id>,          bmi::key<&mre::content::id>>,
                bmi::ordered_non_unique<bmi::tag<tags::content>, bmi::key<&mre::content::hash>>,
                bmi::ordered_non_unique<bmi::tag<tags::angle>,   bmi::key< &mre::content::angle>>,
                bmi::ordered_non_unique<bmi::tag<tags::frozen>,  bmi::key<&mre::content::frozen_key>>>>;

        inline explicit package(mre::parameters const& params) : _loaded(false), _parameters(params) {}
        inline explicit package() : _loaded(false) {}
        void                          save(std::string const& filename) const;
        void                          load(std::string const& filename);
        inline std::size_t            size() const { return _samples.size(); }
        inline bool                   loaded() const { return _loaded; }
        mre::content const&           operator[](std::string const& id) const;
        mre::parameters const&        params() const { return _parameters; }
        template <class Archive> void serialize(Archive& ar, unsigned) {
            ar& boost::serialization::make_nvp("samples", _samples);
            ar& boost::serialization::make_nvp("params", _parameters);
        }

      public:
        std::size_t generate(std::size_t contents, std::size_t angles, size_t seed);
        std::size_t generate(std::size_t contents, std::size_t angles) {
            return generate(contents, angles, std::random_device{}());
        }

      private:
        bool            _loaded;
        container       _samples;
        mre::parameters _parameters;
    };

} // namespace mre

// { sources

std::ostream& mre::operator<<(std::ostream& stream, mre::parameters const& params) {
    stream << "params {" << std::endl;
    stream << "    degree:     " << params.degree << std::endl;
    stream << "    frame_size: " << params.frame_size << std::endl;
    stream << "}";
    return stream;
}

void mre::package::save(std::string const& filename) const {
    std::ofstream stream(filename, std::ios::binary);
    try {
        OA out(stream, FLAGS);
        std::cout << "serialization library version: " << out.get_library_version() << std::endl;
        out << *this;
    } catch (std::exception const& e) {
        std::cout << "Error saving archive: " << e.what() << std::endl;
    }
    stream.close();
}

void mre::package::load(std::string const& filename) {
    std::ifstream stream(filename, std::ios::binary);
    try {
        IA in(stream, FLAGS);
        std::cout << "deserialization library version: " << in.get_library_version() << std::endl;
        in >> *this;
        _loaded = true;
    } catch (std::exception const& e) {
        std::cout << "Error loading archive: " << e.what() << std::endl;
    }
    stream.close();
}

std::size_t mre::package::generate(std::size_t contents, std::size_t angles, size_t seed) {
    std::size_t count     = 0;
    std::size_t v_content = 0;
    while (v_content++ < contents) {
        mre::content x       = mre::content::generate(seed);
        std::size_t  v_angle = 0;
        while (v_angle++ < angles) {
            mre::content x_angle = x;
            x_angle.reset_angle_random(seed); // commenting out this line makes it work
            if (_samples.insert(x_angle).second)
                ++count;
        }
    }
    return count;
}

int main(int argc, char** argv) {
    std::cout << "Boost " << BOOST_VERSION << "n";
    if (argc < 2) {
        std::cout << "Usage: " << std::endl
                  << argv[0] << " pack FILENAME N" << std::endl
                  << argv[0] << " unpack FILENAME" << std::endl;
        return 1;
    }
    if (argv[1] == std::string("pack")) {
        auto         params = mre::parameters{.degree = 4, .frame_size = 128};
        mre::package package(params);
        std::size_t  count = package.generate(boost::lexical_cast<std::size_t>(argv[3]), 4, 0xcafebabe);
        package.save(argv[2]);
        std::cout << "serialized: " << count << " contents" << std::endl;
        return 0;
    } else if (argv[1] == std::string("unpack")) {
        mre::package package;
        package.load(argv[2]);
        if (package.loaded()) {
            std::cout << "Package loaded: " << package.size() << std::endl << package.params() << std::endl;
            package.save("roundtrip");
            return 0;
        }
        return 1;
    } else {
        std::cout << "Usage: " << std::endl
                  << argv[0] << " pack FILENAME N" << std::endl
                  << argv[0] << " unpack FILENAME" << std::endl;
        return 1;
    }
}

TL;DR

Basically, don’t ever use non-perfect hashes as keys. Additionally, don’t rely on determinism of the algorithm, except with published cryptographical digests.