diff options
Diffstat (limited to '')
-rw-r--r-- | src/rocksdb/env/unique_id_gen.h | 71 |
1 files changed, 71 insertions, 0 deletions
diff --git a/src/rocksdb/env/unique_id_gen.h b/src/rocksdb/env/unique_id_gen.h new file mode 100644 index 000000000..17e71e622 --- /dev/null +++ b/src/rocksdb/env/unique_id_gen.h @@ -0,0 +1,71 @@ +// Copyright (c) Facebook, Inc. and its affiliates. All Rights Reserved. +// This source code is licensed under both the GPLv2 (found in the +// COPYING file in the root directory) and Apache 2.0 License +// (found in the LICENSE.Apache file in the root directory). + +// This file is for functions that generate unique identifiers by +// (at least in part) by extracting novel entropy or sources of uniqueness +// from the execution environment. (By contrast, random.h is for algorithmic +// pseudorandomness.) +// +// These functions could eventually migrate to public APIs, such as in Env. + +#pragma once + +#include <atomic> +#include <cstdint> + +#include "rocksdb/rocksdb_namespace.h" + +namespace ROCKSDB_NAMESPACE { + +// Generates a new 128-bit identifier that is universally unique +// (with high probability) for each call. The result is split into +// two 64-bit pieces. This function has NOT been validated for use in +// cryptography. +// +// This is used in generating DB session IDs and by Env::GenerateUniqueId +// (used for DB IDENTITY) if the platform does not provide a generator of +// RFC 4122 UUIDs or fails somehow. (Set exclude_port_uuid=true if this +// function is used as a fallback for GenerateRfcUuid, because no need +// trying it again.) +void GenerateRawUniqueId(uint64_t* a, uint64_t* b, + bool exclude_port_uuid = false); + +#ifndef NDEBUG +// A version of above with options for challenge testing +void TEST_GenerateRawUniqueId(uint64_t* a, uint64_t* b, bool exclude_port_uuid, + bool exclude_env_details, + bool exclude_random_device); +#endif + +// Generates globally unique ids with lower probability of any collisions +// vs. each unique id being independently random (GenerateRawUniqueId). +// We call this "semi-structured" because between different +// SemiStructuredUniqueIdGen objects, the IDs are separated by random +// intervals (unstructured), but within a single SemiStructuredUniqueIdGen +// object, the generated IDs are trivially related (structured). See +// https://github.com/pdillinger/unique_id for how this improves probability +// of no collision. In short, if we have n SemiStructuredUniqueIdGen +// objects each generating m IDs, the first collision is expected at +// around n = sqrt(2^128 / m), equivalently n * sqrt(m) = 2^64, +// rather than n * m = 2^64 for fully random IDs. +class SemiStructuredUniqueIdGen { + public: + // Initializes with random starting state (from GenerateRawUniqueId) + SemiStructuredUniqueIdGen() { Reset(); } + // Re-initializes, but not thread safe + void Reset(); + + // Assuming no fork(), `lower` is guaranteed unique from one call + // to the next (thread safe). + void GenerateNext(uint64_t* upper, uint64_t* lower); + + private: + uint64_t base_upper_; + uint64_t base_lower_; + std::atomic<uint64_t> counter_; + int64_t saved_process_id_; +}; + +} // namespace ROCKSDB_NAMESPACE |