From 7749808309f13be2a544e05e5efe92731ee3810b Mon Sep 17 00:00:00 2001 From: Sage Weil Date: Tue, 12 May 2020 12:34:13 -0500 Subject: [PATCH] common/FastCDC: initial implementation Loosely based on the paper, but with a few changes. Signed-off-by: Sage Weil --- src/common/CDC.cc | 4 + src/common/CMakeLists.txt | 1 + src/common/FastCDC.cc | 114 ++++++++++++++++++++++++++ src/common/FastCDC.h | 46 +++++++++++ src/test/common/CMakeLists.txt | 5 ++ src/test/common/test_cdc.cc | 145 +++++++++++++++++++++++++++++++++ 6 files changed, 315 insertions(+) create mode 100644 src/common/FastCDC.cc create mode 100644 src/common/FastCDC.h create mode 100644 src/test/common/test_cdc.cc diff --git a/src/common/CDC.cc b/src/common/CDC.cc index ee83738fea3..d497308919b 100644 --- a/src/common/CDC.cc +++ b/src/common/CDC.cc @@ -4,6 +4,7 @@ #include #include "CDC.h" +#include "FastCDC.h" #include "rabin.h" std::unique_ptr CDC::create( @@ -16,5 +17,8 @@ std::unique_ptr CDC::create( p->set_target_bits(bits, windowbits); return std::unique_ptr(p); } + if (type == "fastcdc") { + return std::unique_ptr(new FastCDC(bits, windowbits)); + } return nullptr; } diff --git a/src/common/CMakeLists.txt b/src/common/CMakeLists.txt index 2f7e27f942f..90f7524b449 100644 --- a/src/common/CMakeLists.txt +++ b/src/common/CMakeLists.txt @@ -18,6 +18,7 @@ set(common_srcs Cycles.cc CDC.cc DecayCounter.cc + FastCDC.cc Finisher.cc Formatter.cc Graylog.cc diff --git a/src/common/FastCDC.cc b/src/common/FastCDC.cc new file mode 100644 index 00000000000..5fa8e0d9853 --- /dev/null +++ b/src/common/FastCDC.cc @@ -0,0 +1,114 @@ +// -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*- +// vim: ts=8 sw=2 smarttab + +#include + +#include "FastCDC.h" +#include "rabin.h" + + +// if we are close to the target, use the target mask. if we are very +// small or very large, use an adjusted mask. this tries to keep /most/ +// cut points using the same mask. + +// how many bits to set/clear in the small/large masks +#define TARGET_WINDOW_MASK_BITS 2 + +// how big the 'target window' is (in which we use the target mask) +#define TARGET_WINDOW_BITS 1 + +// hard limits on size +#define SIZE_WINDOW_BITS 2 + +void FastCDC::_setup(int target, int size_window_bits) +{ + target_bits = target; + + if (!size_window_bits) { + size_window_bits = SIZE_WINDOW_BITS; + } + min_bits = target - size_window_bits; + max_bits = target + size_window_bits; + + std::mt19937_64 engine; + + // prefill table + for (unsigned i = 0; i < 256; ++i) { + table[i] = engine(); + } + + // set mask + int did = 0; + uint64_t m = 0; + while (did < target_bits + TARGET_WINDOW_MASK_BITS) { + uint64_t bit = 1ull << (engine() & 63); + if (m & bit) { + continue; // this bit is already set + } + m |= bit; + ++did; + if (did == target_bits - TARGET_WINDOW_MASK_BITS) { + large_mask = m; + } else if (did == target_bits) { + target_mask = m; + } else if (did == target_bits + TARGET_WINDOW_MASK_BITS) { + small_mask = m; + } + } +} + +void FastCDC::calc_chunks( + bufferlist& bl, + std::vector> *chunks) +{ + unsigned char *ptr = (unsigned char *)bl.c_str(); + size_t len = bl.length(); + + size_t pos = 0; + while (pos < len) { + size_t cstart = pos; + + uint64_t fp = 0; + + // skip forward to the min chunk size cut point (minus the window, so + // we can initialize the rolling fingerprint). + pos = std::min(pos + (1 << min_bits) - window, len); + + // first fill the window + while (pos < std::min(window, len)) { + fp = (fp << 1) ^ table[ptr[pos]]; + ++pos; + } + if (pos >= len) { + chunks->push_back(std::pair(cstart, pos - cstart)); + break; + } + + // find an end marker + // small + size_t max = std::min(len, + cstart + (1 << (target_bits - TARGET_WINDOW_BITS))); + while ((fp & small_mask) != small_mask && pos < max) { + fp = (fp << 1) ^ table[ptr[pos]]; + ++pos; + } + if (pos >= max) { + // target + max = std::min(len, cstart + (1 << (target_bits + TARGET_WINDOW_BITS))); + while ((fp & target_mask) != target_mask && pos < max) { + fp = (fp << 1) ^ table[ptr[pos]]; + ++pos; + } + if (pos >= max) { + // large + max = std::min(len, cstart + (1 << max_bits)); + while ((fp & large_mask) != large_mask && pos < max) { + fp = (fp << 1) ^ table[ptr[pos]]; + ++pos; + } + } + } + + chunks->push_back(std::pair(cstart, pos - cstart)); + } +} diff --git a/src/common/FastCDC.h b/src/common/FastCDC.h new file mode 100644 index 00000000000..414bcc3be1f --- /dev/null +++ b/src/common/FastCDC.h @@ -0,0 +1,46 @@ +// -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*- +// vim: ts=8 sw=2 smarttab + +#pragma once + +#include "CDC.h" + +// Based on this paper: +// https://www.usenix.org/system/files/conference/atc16/atc16-paper-xia.pdf +// +// Changes: +// - window size fixed at 64 bytes (to match our word size) +// - use XOR instead of + +// - match mask instead of 0 +// - use target mask when close to target size (instead of +// small/large mask). The idea here is to try to use a consistent (target) +// mask for most cut points if we can, and only resort to small/large mask +// when we are (very) small or (very) large. + +// Note about the target_bits: The goal is an average chunk size of 1 +// << target_bits. However, in reality the average is ~1.25x that +// because of the hard mininum chunk size. + +class FastCDC : public CDC { +private: + int target_bits, min_bits, max_bits; + uint64_t target_mask, small_mask, large_mask; + uint64_t table[256]; + + const size_t window = 64; + + void _setup(int target, int window_bits); + +public: + FastCDC(int target = 18, int window_bits = 0) { + _setup(target, window_bits); + }; + + void set_target_bits(int target, int window_bits) override { + _setup(target, window_bits); + } + + void calc_chunks( + bufferlist& bl, + std::vector> *chunks) override; +}; diff --git a/src/test/common/CMakeLists.txt b/src/test/common/CMakeLists.txt index 25eb51285b1..45fc428fd74 100644 --- a/src/test/common/CMakeLists.txt +++ b/src/test/common/CMakeLists.txt @@ -334,6 +334,11 @@ add_executable(unittest_rabin_chunk test_rabin_chunk.cc target_link_libraries(unittest_rabin_chunk global ceph-common) add_ceph_unittest(unittest_rabin_chunk) +add_executable(unittest_cdc test_cdc.cc + $) +target_link_libraries(unittest_cdc global ceph-common) +add_ceph_unittest(unittest_cdc) + add_executable(unittest_ceph_timer test_ceph_timer.cc) add_ceph_unittest(unittest_ceph_timer) diff --git a/src/test/common/test_cdc.cc b/src/test/common/test_cdc.cc new file mode 100644 index 00000000000..91ee96fa0b9 --- /dev/null +++ b/src/test/common/test_cdc.cc @@ -0,0 +1,145 @@ +// -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*- +// vim: ts=8 sw=2 smarttab + +#include +#include +#include + +#include "include/types.h" +#include "include/buffer.h" + +#include "common/CDC.h" +#include "gtest/gtest.h" + +void generate_buffer(int size, bufferlist *outbl) +{ + outbl->clear(); + outbl->append_zero(size); + char *b = outbl->c_str(); + std::mt19937_64 engine; + for (size_t i = 0; i < size / sizeof(uint64_t); ++i) { + ((uint64_t*)b)[i] = engine(); + } +} + +class CDCTest : public ::testing::Test, + public ::testing::WithParamInterface { +public: + std::unique_ptr cdc; + + CDCTest() { + auto plugin = GetParam(); + cdc = std::move(CDC::create(plugin, 18)); + } +}; + +TEST_P(CDCTest, insert_front) +{ + for (int frontlen = 1; frontlen < 163840; frontlen *= 3) { + bufferlist bl1, bl2; + generate_buffer(4*1024*1024, &bl1); + generate_buffer(frontlen, &bl2); + bl2.append(bl1); + bl2.rebuild(); + + vector> chunks1, chunks2; + cdc->calc_chunks(bl1, &chunks1); + cdc->calc_chunks(bl2, &chunks2); + cout << "1: " << chunks1 << std::endl; + cout << "2: " << chunks2 << std::endl; + + ASSERT_GE(chunks2.size(), chunks1.size()); + int match = 0; + for (unsigned i = 0; i < chunks1.size(); ++i) { + unsigned j = i + (chunks2.size() - chunks1.size()); + if (chunks1[i].first + frontlen == chunks2[j].first && + chunks1[i].second == chunks2[j].second) { + match++; + } + } + ASSERT_GE(match, chunks1.size() - 1); + } +} + +TEST_P(CDCTest, insert_middle) +{ + for (int frontlen = 1; frontlen < 163840; frontlen *= 3) { + bufferlist bl1, bl2; + generate_buffer(4*1024*1024, &bl1); + bufferlist f, m, e; + generate_buffer(frontlen, &m); + f.substr_of(bl1, 0, bl1.length() / 2); + e.substr_of(bl1, bl1.length() / 2, bl1.length() / 2); + bl2 = f; + bl2.append(m); + bl2.append(e); + bl2.rebuild(); + + vector> chunks1, chunks2; + cdc->calc_chunks(bl1, &chunks1); + cdc->calc_chunks(bl2, &chunks2); + cout << "1: " << chunks1 << std::endl; + cout << "2: " << chunks2 << std::endl; + + ASSERT_GE(chunks2.size(), chunks1.size()); + int match = 0; + unsigned i; + for (i = 0; i < chunks1.size()/2; ++i) { + unsigned j = i; + if (chunks1[i].first == chunks2[j].first && + chunks1[i].second == chunks2[j].second) { + match++; + } + } + for (; i < chunks1.size(); ++i) { + unsigned j = i + (chunks2.size() - chunks1.size()); + if (chunks1[i].first + frontlen == chunks2[j].first && + chunks1[i].second == chunks2[j].second) { + match++; + } + } + ASSERT_GE(match, chunks1.size() - 2); + } +} + +void do_size_histogram(CDC& cdc, bufferlist& bl, + map *h) +{ + vector> chunks; + cdc.calc_chunks(bl, &chunks); + for (auto& i : chunks) { + //unsigned b = i.second & 0xfffff000; + unsigned b = 1 << cbits(i.second); + (*h)[b]++; + } +} + +void print_histogram(map& h) +{ + cout << "size\tcount" << std::endl; + for (auto i : h) { + cout << i.first << "\t" << i.second << std::endl; + } +} + +TEST_P(CDCTest, chunk_random) +{ + map h; + for (int i = 0; i < 32; ++i) { + cout << "."; + cout.flush(); + bufferlist r; + generate_buffer(16*1024*1024, &r); + do_size_histogram(*cdc, r, &h); + } + cout << std::endl; + print_histogram(h); +} + + +INSTANTIATE_TEST_SUITE_P( + CDC, + CDCTest, + ::testing::Values( + "fastcdc" + )); -- 2.39.5