From 9ab445a42d96150d27188f59c28e367f1a180f06 Mon Sep 17 00:00:00 2001 From: Sage Weil Date: Thu, 1 Dec 2011 20:57:23 -0800 Subject: [PATCH] ObjectStore: Add collection_list_partial for hash order Signed-off-by: Samuel Just --- src/os/CollectionIndex.h | 9 +++ src/os/FileStore.cc | 17 +++++ src/os/FileStore.h | 3 + src/os/FlatIndex.cc | 9 +++ src/os/FlatIndex.h | 9 +++ src/os/HashIndex.cc | 142 +++++++++++++++++++++++++++++++++------ src/os/HashIndex.h | 33 ++++++++- src/os/LFNIndex.cc | 9 +++ src/os/LFNIndex.h | 18 +++++ src/os/ObjectStore.h | 17 +++++ src/test/store_test.cc | 17 +++++ 11 files changed, 261 insertions(+), 22 deletions(-) diff --git a/src/os/CollectionIndex.h b/src/os/CollectionIndex.h index 2fca26fb0a6e5..c6af505d1e6d5 100644 --- a/src/os/CollectionIndex.h +++ b/src/os/CollectionIndex.h @@ -142,6 +142,15 @@ protected: collection_list_handle_t *last ) = 0; + /// List contents of collection by hash + virtual int collection_list_partial( + const hobject_t &start, ///< [in] object at which to start + int min_count, ///< [in] get at least min_count objects + int max_count, ///< [in] return at most max_count objects + vector *ls, ///< [out] Listed objects + hobject_t *next ///< [out] Next object to list + ) = 0; + /// List contents of collection. virtual int collection_list( vector *ls ///< [out] Listed Objects diff --git a/src/os/FileStore.cc b/src/os/FileStore.cc index 7f88ea91a30e9..d6117402628e7 100644 --- a/src/os/FileStore.cc +++ b/src/os/FileStore.cc @@ -3740,6 +3740,23 @@ int FileStore::collection_list_partial(coll_t c, snapid_t seq, vector return 0; } +int FileStore::collection_list_partial(coll_t c, hobject_t start, + int min, int max, + vector *ls, hobject_t *next) +{ + if (fake_collections) return -1; + Index index; + int r = get_index(c, &index); + if (r < 0) + return r; + r = index->collection_list_partial(start, + min, max, + ls, next); + if (r < 0) + return r; + return 0; +} + int FileStore::collection_list(coll_t c, vector& ls) { if (fake_collections) return collections.collection_list(c, ls); diff --git a/src/os/FileStore.h b/src/os/FileStore.h index 3eb1400f3c4ef..ce4464aa54ffb 100644 --- a/src/os/FileStore.h +++ b/src/os/FileStore.h @@ -354,6 +354,9 @@ public: bool collection_empty(coll_t c); int collection_list_partial(coll_t c, snapid_t seq, vector& o, int count, collection_list_handle_t *handle); int collection_list(coll_t c, vector& o); + int collection_list_partial(coll_t c, hobject_t start, + int min, int max, + vector *ls, hobject_t *next); int _create_collection(coll_t c); int _destroy_collection(coll_t c); diff --git a/src/os/FlatIndex.cc b/src/os/FlatIndex.cc index 93e02f38f1ec7..19fe57ba3ea61 100644 --- a/src/os/FlatIndex.cc +++ b/src/os/FlatIndex.cc @@ -383,6 +383,15 @@ int FlatIndex::collection_list_partial(snapid_t seq, int max_count, return 0; } +int FlatIndex::collection_list_partial(const hobject_t &start, + int min_count, + int max_count, + vector *ls, + hobject_t *next) { + assert(0); // Should not be called + return 0; +} + int FlatIndex::collection_list(vector *ls) { char dir_name[PATH_MAX], buf[PATH_MAX], new_name[PATH_MAX]; strncpy(dir_name, base_path.c_str(), sizeof(dir_name)); diff --git a/src/os/FlatIndex.h b/src/os/FlatIndex.h index 53e27f5ec08ac..30c710764840d 100644 --- a/src/os/FlatIndex.h +++ b/src/os/FlatIndex.h @@ -76,6 +76,15 @@ public: int collection_list( vector *ls ); + + /// @see CollectionIndex + int collection_list_partial( + const hobject_t &start, + int min_count, + int max_count, + vector *ls, + hobject_t *next + ); }; #endif diff --git a/src/os/HashIndex.cc b/src/os/HashIndex.cc index cfbd9bf0cf452..279cbccd61f6e 100644 --- a/src/os/HashIndex.cc +++ b/src/os/HashIndex.cc @@ -163,6 +163,16 @@ int HashIndex::_collection_list(vector *ls) { return list(path, NULL, NULL, NULL, NULL, ls); } +int HashIndex::_collection_list_partial(const hobject_t &start, + int min_count, + int max_count, + vector *ls, + hobject_t *next) { + vector path; + *next = start; + return list_by_hash(path, min_count, max_count, next, ls); +} + int HashIndex::start_split(const vector &path) { bufferlist bl; InProgressOp op_tag(InProgressOp::SPLIT, path); @@ -371,12 +381,12 @@ int HashIndex::complete_split(const vector &path, subdir_info_s info) { void HashIndex::get_path_components(const hobject_t &hoid, vector *path) { char buf[MAX_HASH_LEVEL + 1]; - snprintf(buf, sizeof(buf), "%.*X", MAX_HASH_LEVEL, hoid.hash); + snprintf(buf, sizeof(buf), "%.*X", MAX_HASH_LEVEL, hoid.get_filestore_key()); - // Path components are the hex characters of hoid.hash in, least + // Path components are the hex characters of hoid.hash, least // significant first for (int i = 0; i < MAX_HASH_LEVEL; ++i) { - path->push_back(string(&buf[MAX_HASH_LEVEL - 1 - i], 1)); + path->push_back(string(&buf[i], 1)); } } @@ -394,28 +404,34 @@ string HashIndex::get_path_str(const hobject_t &hoid) { return get_hash_str(hoid.hash); } -int HashIndex::list(const vector &path, - const int *max_count, - const snapid_t *seq, - const string *lower_bound, - uint32_t *index, - vector *out) { - if (lower_bound) - assert(index); - vector next_path = path; - next_path.push_back(""); - set hash_prefixes; - multimap objects; +uint32_t HashIndex::hash_prefix_to_hash(string prefix) { + while (prefix.size() < sizeof(uint32_t) * 2) { + prefix.push_back('0'); + } + uint32_t hash; + sscanf(prefix.c_str(), "%x", &hash); + // nibble reverse + hash = ((hash & 0x0f0f0f0f) << 4) | ((hash & 0xf0f0f0f0) >> 4); + hash = ((hash & 0x00ff00ff) << 8) | ((hash & 0xff00ff00) >> 8); + hash = ((hash & 0x0000ffff) << 16) | ((hash & 0xffff0000) >> 16); + return hash; +} + +int HashIndex::get_path_contents_by_hash(const vector &path, + const string *lower_bound, + const hobject_t *next_object, + const snapid_t *seq, + set *hash_prefixes, + multimap *objects) { + set subdirs; map rev_objects; int r; - int max = max_count ? *max_count : 0; string cur_prefix; for (vector::const_iterator i = path.begin(); i != path.end(); ++i) { cur_prefix.append(*i); } - r = list_objects(path, 0, 0, &rev_objects); if (r < 0) return r; @@ -425,12 +441,13 @@ int HashIndex::list(const vector &path, string hash_prefix = get_path_str(i->second); if (lower_bound && hash_prefix < *lower_bound) continue; + if (next_object && i->second < *next_object) + continue; if (seq && i->second.snap < *seq) continue; - hash_prefixes.insert(hash_prefix); - objects.insert(pair(hash_prefix, i->second)); + hash_prefixes->insert(hash_prefix); + objects->insert(pair(hash_prefix, i->second)); } - set subdirs; r = list_subdirs(path, &subdirs); if (r < 0) return r; @@ -440,9 +457,92 @@ int HashIndex::list(const vector &path, string candidate = cur_prefix + *i; if (lower_bound && candidate < lower_bound->substr(0, candidate.size())) continue; - hash_prefixes.insert(cur_prefix + *i); + if (next_object && + candidate < get_path_str(*next_object).substr(0, candidate.size())) + continue; + hash_prefixes->insert(cur_prefix + *i); } + return 0; +} +int HashIndex::list_by_hash(const vector &path, + int min_count, + int max_count, + hobject_t *next, + vector *out) { + assert(next); + assert(out); + vector next_path = path; + next_path.push_back(""); + set hash_prefixes; + multimap objects; + int r = get_path_contents_by_hash(path, + NULL, + next, + NULL, + &hash_prefixes, + &objects); + if (r < 0) + return r; + for (set::iterator i = hash_prefixes.begin(); + i != hash_prefixes.end(); + ++i) { + multimap::iterator j = objects.find(*i); + if (j == objects.end()) { + if (out->size() > (unsigned)min_count) { + *next = hobject_t("", "", CEPH_NOSNAP, hash_prefix_to_hash(*i)); + return 0; + } + *(next_path.rbegin()) = *(i->rbegin()); + hobject_t next_recurse = *next; + r = list_by_hash(next_path, + min_count, + max_count, + &next_recurse, + out); + + if (r < 0) + return r; + if (!next_recurse.max) { + *next = next_recurse; + return 0; + } + } else { + while (j != objects.end() && j->first == *i) { + if (out->size() == (unsigned)max_count) { + *next = j->second; + return 0; + } + if (j->second >= *next) { + out->push_back(j->second); + } + ++j; + } + } + } + *next = hobject_t::get_max(); + return 0; +} + +int HashIndex::list(const vector &path, + const int *max_count, + const snapid_t *seq, + const string *lower_bound, + uint32_t *index, + vector *out) { + if (lower_bound) + assert(index); + vector next_path = path; + next_path.push_back(""); + int max = max_count ? *max_count : 0; + set hash_prefixes; + multimap objects; + int r = get_path_contents_by_hash(path, + lower_bound, + NULL, + seq, + &hash_prefixes, + &objects); uint32_t counter = 0; for (set::iterator i = hash_prefixes.begin(); i != hash_prefixes.end() && (!max_count || max > 0); diff --git a/src/os/HashIndex.h b/src/os/HashIndex.h index a4256e3fd24d4..5f568068f0d6c 100644 --- a/src/os/HashIndex.h +++ b/src/os/HashIndex.h @@ -167,6 +167,13 @@ protected: int _collection_list( vector *ls ); + int _collection_list_partial( + const hobject_t &start, + int min_count, + int max_count, + vector *ls, + hobject_t *next + ); private: /// Tag root directory at beginning of split int start_split( @@ -246,7 +253,22 @@ private: uint32_t hash ///< [in] Hash to convert to a string. ); ///< @return String representation of hash - /** + /// Get hash from hash prefix string e.g. "FFFFAB" -> 0xFFFFAB00 + uint32_t hash_prefix_to_hash( + string prefix ///< [in] string to convert + ); ///< @return Hash + + /// Get path contents by hash + int get_path_contents_by_hash( + const vector &path, /// [in] Path to list + const string *lower_bound, /// [in] list > *lower_bound + const hobject_t *next_object, /// [in] list > *next_object + const snapid_t *seq, /// [in] list >= *seq + set *hash_prefixes, /// [out] prefixes in dir + multimap *objects /// [out] objects + ); + + /** * Recursively lists all objects in path. * * Lists all objects in path or a subdirectory of path which @@ -267,6 +289,15 @@ private: uint32_t *index, ///< [in,out] last index (NULL iff !lower_bound) vector *out ///< [out] Listed objects ); ///< @return Error Code, 0 on success + + /// List objects in collection in hobject_t order + int list_by_hash( + const vector &path, /// [in] Path to list + int min_count, /// [in] List at least min_count + int max_count, /// [in] List at most max_count + hobject_t *next, /// [in,out] List objects >= *next + vector *out /// [out] Listed objects + ); ///< @return Error Code, 0 on success }; #endif diff --git a/src/os/LFNIndex.cc b/src/os/LFNIndex.cc index 7684b1d746cee..cf4f2d50d1f69 100644 --- a/src/os/LFNIndex.cc +++ b/src/os/LFNIndex.cc @@ -123,6 +123,15 @@ int LFNIndex::collection_list(vector *ls) { return _collection_list(ls); } + +int LFNIndex::collection_list_partial(const hobject_t &start, + int min_count, + int max_count, + vector *ls, + hobject_t *next) { + return _collection_list_partial(start, min_count, max_count, ls, next); +} + /* Derived class utility methods */ int LFNIndex::fsync_dir(const vector &path) { diff --git a/src/os/LFNIndex.h b/src/os/LFNIndex.h index e0321b45dbfed..cad93eedc281b 100644 --- a/src/os/LFNIndex.h +++ b/src/os/LFNIndex.h @@ -140,6 +140,15 @@ public: vector *ls ); + /// @see CollectionIndex + int collection_list_partial( + const hobject_t &start, + int min_count, + int max_count, + vector *ls, + hobject_t *next + ); + protected: virtual int _init() = 0; @@ -187,6 +196,15 @@ protected: vector *ls ///< [out] Listed objects. ) = 0; + /// @see CollectionIndex + virtual int _collection_list_partial( + const hobject_t &start, + int min_count, + int max_count, + vector *ls, + hobject_t *next + ) = 0; + protected: /* Non-virtual utility methods */ diff --git a/src/os/ObjectStore.h b/src/os/ObjectStore.h index 63a68e51977bd..35b59bf009ba2 100644 --- a/src/os/ObjectStore.h +++ b/src/os/ObjectStore.h @@ -623,6 +623,23 @@ public: virtual int collection_list_partial(coll_t c, snapid_t seq, vector& o, int count, collection_list_handle_t *handle) = 0; virtual int collection_list(coll_t c, vector& o) = 0; + + /** + * list partial contents of collection relative to a hash offset/position + * + * @param c collection + * @param start list objects that sort >= this value + * @param min return at least this many results, unless we reach the end + * @param max return no more than this many results + * @param ls [out] result + * @param next [out] next item sorts >= this value + * @return zero on success, or negative error + */ + virtual int collection_list_partial(coll_t c, hobject_t start, + int min, int max, + vector *ls, hobject_t *next) = 0; + + /* virtual int _create_collection(coll_t c) = 0; virtual int _destroy_collection(coll_t c) = 0; diff --git a/src/test/store_test.cc b/src/test/store_test.cc index 568fa1296c876..b18a3c80e40f8 100644 --- a/src/test/store_test.cc +++ b/src/test/store_test.cc @@ -369,12 +369,29 @@ public: if (objects.size() < 50) break; objects.clear(); } + hobject_t next, current; + set objects_set2; + while (1) { + cerr << "scanning (by hash)..." << std::endl; + int r = store->collection_list_partial(cid, current, 50, 100, &objects, &next); + ASSERT_EQ(r, 0); + objects_set2.insert(objects.begin(), objects.end()); + if (next.max) break; + objects.clear(); + current = next; + } ASSERT_EQ(objects_set.size(), available_objects.size()); + ASSERT_EQ(objects_set2.size(), available_objects.size()); for (set::iterator i = objects_set.begin(); i != objects_set.end(); ++i) { ASSERT_GT(available_objects.count(*i), (unsigned)0); } + for (set::iterator i = objects_set2.begin(); + i != objects_set2.end(); + ++i) { + ASSERT_GT(available_objects.count(*i), (unsigned)0); + } } int stat() { -- 2.39.5