1 // Copyright (C) 2022 Google LLC 2 // 3 // Licensed under the Apache License, Version 2.0 (the "License"); 4 // you may not use this file except in compliance with the License. 5 // You may obtain a copy of the License at 6 // 7 // http://www.apache.org/licenses/LICENSE-2.0 8 // 9 // Unless required by applicable law or agreed to in writing, software 10 // distributed under the License is distributed on an "AS IS" BASIS, 11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12 // See the License for the specific language governing permissions and 13 // limitations under the License. 14 15 #ifndef ICING_INDEX_NUMERIC_INTEGER_INDEX_STORAGE_H_ 16 #define ICING_INDEX_NUMERIC_INTEGER_INDEX_STORAGE_H_ 17 18 #include <cstdint> 19 #include <memory> 20 #include <string> 21 #include <string_view> 22 #include <vector> 23 24 #include "icing/text_classifier/lib3/utils/base/status.h" 25 #include "icing/text_classifier/lib3/utils/base/statusor.h" 26 #include "icing/file/file-backed-vector.h" 27 #include "icing/file/filesystem.h" 28 #include "icing/file/memory-mapped-file.h" 29 #include "icing/file/persistent-storage.h" 30 #include "icing/file/posting_list/flash-index-storage.h" 31 #include "icing/file/posting_list/posting-list-identifier.h" 32 #include "icing/index/iterator/doc-hit-info-iterator.h" 33 #include "icing/index/numeric/integer-index-data.h" 34 #include "icing/index/numeric/posting-list-integer-index-serializer.h" 35 #include "icing/schema/section.h" 36 #include "icing/store/document-id.h" 37 #include "icing/util/crc32.h" 38 39 namespace icing { 40 namespace lib { 41 42 // IntegerIndexStorage: a class for indexing (persistent storage) and searching 43 // contents of integer type sections in documents. 44 // - Accepts new integer contents (a.k.a keys) and adds records (BasicHit, key) 45 // into the integer index. 46 // - Stores records (BasicHit, key) in posting lists and compresses them. 47 // - Bucketizes these records by key to make range query more efficient and 48 // manages them with the corresponding posting lists. 49 // - When a posting list reaches the max size and is full, the mechanism of 50 // PostingListAccessor is to create another new (max-size) posting list and 51 // chain them together. 52 // - It will be inefficient if we store all records in the same PL chain. E.g. 53 // small range query needs to iterate through the whole PL chain but skips a 54 // lot of non-relevant records (whose keys don't belong to the query range). 55 // - Therefore, we implement the splitting mechanism to split a full max-size 56 // posting list. Also adjust range of the original bucket and add new 57 // buckets. 58 // - Ranges of all buckets are disjoint and the union of them is [INT64_MIN, 59 // INT64_MAX]. 60 // - Buckets should be sorted, so we can do binary search to find the desired 61 // bucket(s). However, we may split a bucket into several buckets, and the 62 // cost to insert newly created buckets is high. 63 // - Thus, we introduce an unsorted bucket array for newly created buckets, 64 // and merge unsorted buckets into the sorted bucket array only if length of 65 // the unsorted bucket array exceeds the threshold. This mechanism will 66 // reduce # of merging events and amortize the overall cost for bucket order 67 // maintenance. 68 // Note: some tree data structures (e.g. segment tree, B+ tree) maintain the 69 // bucket order more efficiently than the sorted/unsorted bucket array 70 // mechanism, but the implementation is more complicated and doesn't improve 71 // the performance too much according to our analysis, so currently we 72 // choose sorted/unsorted bucket array. 73 // - Then we do binary search on the sorted bucket array and sequential search 74 // on the unsorted bucket array. 75 class IntegerIndexStorage : public PersistentStorage { 76 public: 77 struct Info { 78 static constexpr int32_t kMagic = 0x6470e547; 79 80 int32_t magic; 81 int32_t num_data; 82 GetChecksumInfo83 Crc32 GetChecksum() const { 84 return Crc32( 85 std::string_view(reinterpret_cast<const char*>(this), sizeof(Info))); 86 } 87 } __attribute__((packed)); 88 static_assert(sizeof(Info) == 8, ""); 89 90 // Bucket 91 class Bucket { 92 public: 93 // Absolute max # of buckets allowed. Since the absolute max file size of 94 // FileBackedVector on 32-bit platform is ~2^28, we can at most have ~13.4M 95 // buckets. To make it power of 2, round it down to 2^23. Also since we're 96 // using FileBackedVector to store buckets, add some static_asserts to 97 // ensure numbers here are compatible with FileBackedVector. 98 static constexpr int32_t kMaxNumBuckets = 1 << 23; 99 100 explicit Bucket(int64_t key_lower, int64_t key_upper, 101 PostingListIdentifier posting_list_identifier = 102 PostingListIdentifier::kInvalid, 103 int32_t num_data = 0) key_lower_(key_lower)104 : key_lower_(key_lower), 105 key_upper_(key_upper), 106 posting_list_identifier_(posting_list_identifier), 107 num_data_(num_data) {} 108 109 bool operator<(const Bucket& other) const { 110 return key_lower_ < other.key_lower_; 111 } 112 113 // For FileBackedVector 114 bool operator==(const Bucket& other) const { 115 return key_lower_ == other.key_lower_ && key_upper_ == other.key_upper_ && 116 posting_list_identifier_ == other.posting_list_identifier_; 117 } 118 key_lower()119 int64_t key_lower() const { return key_lower_; } 120 key_upper()121 int64_t key_upper() const { return key_upper_; } 122 set_key_lower(int64_t key_lower)123 void set_key_lower(int64_t key_lower) { key_lower_ = key_lower; } 124 set_key_upper(int64_t key_upper)125 void set_key_upper(int64_t key_upper) { key_upper_ = key_upper; } 126 posting_list_identifier()127 PostingListIdentifier posting_list_identifier() const { 128 return posting_list_identifier_; 129 } set_posting_list_identifier(PostingListIdentifier posting_list_identifier)130 void set_posting_list_identifier( 131 PostingListIdentifier posting_list_identifier) { 132 posting_list_identifier_ = posting_list_identifier; 133 } 134 num_data()135 int32_t num_data() const { return num_data_; } set_num_data(int32_t num_data)136 void set_num_data(int32_t num_data) { num_data_ = num_data; } 137 138 private: 139 int64_t key_lower_; 140 int64_t key_upper_; 141 PostingListIdentifier posting_list_identifier_; 142 int32_t num_data_; 143 } __attribute__((packed)); 144 static_assert(sizeof(Bucket) == 24, ""); 145 static_assert(sizeof(Bucket) == FileBackedVector<Bucket>::kElementTypeSize, 146 "Bucket type size is inconsistent with FileBackedVector " 147 "element type size"); 148 static_assert(Bucket::kMaxNumBuckets <= 149 (FileBackedVector<Bucket>::kMaxFileSize - 150 FileBackedVector<Bucket>::Header::kHeaderSize) / 151 FileBackedVector<Bucket>::kElementTypeSize, 152 "Max # of buckets cannot fit into FileBackedVector"); 153 154 struct Options { 155 // - According to the benchmark result, the more # of buckets, the higher 156 // latency for range query. Therefore, this number cannot be too small to 157 // avoid splitting bucket too aggressively. 158 // - We use `num_data_threshold_for_bucket_split / 2 + 5` as the cutoff 159 // threshold after splitting. This number cannot be too small (e.g. 10) 160 // because in this case we will have similar # of data in a single bucket 161 // before and after splitting, which contradicts the purpose of splitting. 162 // - For convenience, let's set 64 as the minimum value. 163 static constexpr int32_t kMinNumDataThresholdForBucketSplit = 64; 164 OptionsOptions165 explicit Options(int32_t num_data_threshold_for_bucket_split_in, 166 bool pre_mapping_fbv_in) 167 : num_data_threshold_for_bucket_split( 168 num_data_threshold_for_bucket_split_in), 169 pre_mapping_fbv(pre_mapping_fbv_in) {} 170 OptionsOptions171 explicit Options(std::vector<Bucket> custom_init_sorted_buckets_in, 172 std::vector<Bucket> custom_init_unsorted_buckets_in, 173 int32_t num_data_threshold_for_bucket_split_in, 174 bool pre_mapping_fbv_in) 175 : custom_init_sorted_buckets(std::move(custom_init_sorted_buckets_in)), 176 custom_init_unsorted_buckets( 177 std::move(custom_init_unsorted_buckets_in)), 178 num_data_threshold_for_bucket_split( 179 num_data_threshold_for_bucket_split_in), 180 pre_mapping_fbv(pre_mapping_fbv_in) {} 181 182 bool IsValid() const; 183 HasCustomInitBucketsOptions184 bool HasCustomInitBuckets() const { 185 return !custom_init_sorted_buckets.empty() || 186 !custom_init_unsorted_buckets.empty(); 187 } 188 189 // Custom buckets when initializing new files. If both are empty, then the 190 // initial bucket is (INT64_MIN, INT64_MAX). Usually we only set them in the 191 // unit test. Note that all buckets in custom_init_sorted_buckets and 192 // custom_init_unsorted_buckets should be disjoint and the range union 193 // should be [INT64_MIN, INT64_MAX]. 194 std::vector<Bucket> custom_init_sorted_buckets; 195 std::vector<Bucket> custom_init_unsorted_buckets; 196 197 // Threshold for invoking bucket splitting. If # of data in a bucket exceeds 198 // this number after adding new data, then it will invoke bucket splitting 199 // logic. 200 // 201 // Note: num_data_threshold_for_bucket_split should be >= 202 // kMinNumDataThresholdForBucketSplit. 203 int32_t num_data_threshold_for_bucket_split; 204 205 // Flag indicating whether memory map max possible file size for underlying 206 // FileBackedVector before growing the actual file size. 207 bool pre_mapping_fbv; 208 }; 209 210 // Metadata file layout: <Crcs><Info> 211 static constexpr int32_t kCrcsMetadataFileOffset = 0; 212 static constexpr int32_t kInfoMetadataFileOffset = 213 static_cast<int32_t>(sizeof(Crcs)); 214 static constexpr int32_t kMetadataFileSize = sizeof(Crcs) + sizeof(Info); 215 static_assert(kMetadataFileSize == 20, ""); 216 217 static constexpr WorkingPathType kWorkingPathType = 218 WorkingPathType::kDirectory; 219 static constexpr std::string_view kFilePrefix = "integer_index_storage"; 220 221 // Default # of data threshold for bucket splitting during indexing (AddKeys). 222 // When # of data in a bucket reaches this number, we will try to split data 223 // into multiple buckets according to their keys. 224 static constexpr int32_t kDefaultNumDataThresholdForBucketSplit = 65536; 225 226 // # of data threshold for bucket merging during optimization (TransferIndex) 227 // = kNumDataThresholdRatioForBucketMerge * 228 // options.num_data_threshold_for_bucket_split 229 // 230 // If total # data of adjacent buckets exceed this threshold, then flush the 231 // accumulated data. Otherwise merge buckets and their data. 232 static constexpr double kNumDataThresholdRatioForBucketMerge = 0.7; 233 234 // Length threshold to sort and merge unsorted buckets into sorted buckets. If 235 // the length of unsorted_buckets exceed the threshold, then call 236 // SortBuckets(). 237 // TODO(b/259743562): decide if removing unsorted buckets given that we 238 // changed bucket splitting threshold and # of buckets are small now. 239 static constexpr int32_t kUnsortedBucketsLengthThreshold = 5; 240 241 // Creates a new IntegerIndexStorage instance to index integers (for a single 242 // property). If any of the underlying file is missing, then delete the whole 243 // working_path and (re)initialize with new ones. Otherwise initialize and 244 // create the instance by existing files. 245 // 246 // filesystem: Object to make system level calls 247 // working_path: Specifies the working path for PersistentStorage. 248 // IntegerIndexStorage uses working path as working directory 249 // and all related files will be stored under this directory. It 250 // takes full ownership and of working_path_, including 251 // creation/deletion. It is the caller's responsibility to 252 // specify correct working path and avoid mixing different 253 // persistent storages together under the same path. Also the 254 // caller has the ownership for the parent directory of 255 // working_path_, and it is responsible for parent directory 256 // creation/deletion. See PersistentStorage for more details 257 // about the concept of working_path. 258 // options: Options instance. 259 // posting_list_serializer: a PostingListIntegerIndexSerializer instance to 260 // serialize/deserialize integer index data to/from 261 // posting lists. 262 // 263 // Returns: 264 // - INVALID_ARGUMENT_ERROR if any value in options is invalid. 265 // - FAILED_PRECONDITION_ERROR if the file checksum doesn't match the stored 266 // checksum. 267 // - INTERNAL_ERROR on I/O errors. 268 // - Any FileBackedVector/FlashIndexStorage errors. 269 static libtextclassifier3::StatusOr<std::unique_ptr<IntegerIndexStorage>> 270 Create(const Filesystem& filesystem, std::string working_path, 271 Options options, 272 PostingListIntegerIndexSerializer* posting_list_serializer); 273 274 // Deletes IntegerIndexStorage under working_path. 275 // 276 // Returns: 277 // - OK on success 278 // - INTERNAL_ERROR on I/O error Discard(const Filesystem & filesystem,const std::string & working_path)279 static libtextclassifier3::Status Discard(const Filesystem& filesystem, 280 const std::string& working_path) { 281 return PersistentStorage::Discard(filesystem, working_path, 282 kWorkingPathType); 283 } 284 285 // Delete copy and move constructor/assignment operator. 286 IntegerIndexStorage(const IntegerIndexStorage&) = delete; 287 IntegerIndexStorage& operator=(const IntegerIndexStorage&) = delete; 288 289 IntegerIndexStorage(IntegerIndexStorage&&) = delete; 290 IntegerIndexStorage& operator=(IntegerIndexStorage&&) = delete; 291 292 ~IntegerIndexStorage() override; 293 294 // Batch adds new keys (of the same DocumentId and SectionId) into the integer 295 // index storage. 296 // Note that since we separate different property names into different integer 297 // index storages, it is impossible to have keys in a single document across 298 // multiple sections to add into the same integer index storage. 299 // 300 // Returns: 301 // - OK on success 302 // - RESOURCE_EXHAUSTED_ERROR if # of integers in this storage exceed 303 // INT_MAX after adding new_keys 304 // - Any FileBackedVector or PostingList errors 305 libtextclassifier3::Status AddKeys(DocumentId document_id, 306 SectionId section_id, 307 std::vector<int64_t>&& new_keys); 308 309 // Returns a DocHitInfoIteratorNumeric<int64_t> (in DocHitInfoIterator 310 // interface type format) for iterating through all docs which have the 311 // specified (integer) property contents in range [query_key_lower, 312 // query_key_upper]. 313 // When iterating through all relevant doc hits, it: 314 // - Merges multiple SectionIds of doc hits with same DocumentId into a single 315 // SectionIdMask and constructs DocHitInfo. 316 // - Returns DocHitInfo in descending DocumentId order. 317 // 318 // Returns: 319 // - On success: a DocHitInfoIterator(Numeric) 320 // - INVALID_ARGUMENT_ERROR if query_key_lower > query_key_upper 321 // - Any FileBackedVector or PostingList errors 322 libtextclassifier3::StatusOr<std::unique_ptr<DocHitInfoIterator>> GetIterator( 323 int64_t query_key_lower, int64_t query_key_upper) const; 324 325 // Transfers integer index data from the current storage to new_storage and 326 // optimizes buckets (for new_storage only), i.e. merging adjacent buckets if 327 // total # of data among them are less than or equal to 328 // kNumDataThresholdForBucketMerge. 329 // 330 // REQUIRES: new_storage should be a newly created storage instance, i.e. not 331 // contain any data. Otherwise, existing data and posting lists won't be 332 // freed and space will be wasted. 333 // 334 // Returns: 335 // - OK on success 336 // - OUT_OF_RANGE_ERROR if sorted buckets length exceeds the limit after 337 // merging 338 // - INTERNAL_ERROR on IO error 339 libtextclassifier3::Status TransferIndex( 340 const std::vector<DocumentId>& document_id_old_to_new, 341 IntegerIndexStorage* new_storage) const; 342 num_data()343 int32_t num_data() const { return info().num_data; } 344 345 private: 346 static constexpr int8_t kNumDataAfterSplitAdjustment = 5; 347 IntegerIndexStorage(const Filesystem & filesystem,std::string && working_path,Options && options,PostingListIntegerIndexSerializer * posting_list_serializer,std::unique_ptr<MemoryMappedFile> metadata_mmapped_file,std::unique_ptr<FileBackedVector<Bucket>> sorted_buckets,std::unique_ptr<FileBackedVector<Bucket>> unsorted_buckets,std::unique_ptr<FlashIndexStorage> flash_index_storage)348 explicit IntegerIndexStorage( 349 const Filesystem& filesystem, std::string&& working_path, 350 Options&& options, 351 PostingListIntegerIndexSerializer* posting_list_serializer, 352 std::unique_ptr<MemoryMappedFile> metadata_mmapped_file, 353 std::unique_ptr<FileBackedVector<Bucket>> sorted_buckets, 354 std::unique_ptr<FileBackedVector<Bucket>> unsorted_buckets, 355 std::unique_ptr<FlashIndexStorage> flash_index_storage) 356 : PersistentStorage(filesystem, std::move(working_path), 357 kWorkingPathType), 358 options_(std::move(options)), 359 posting_list_serializer_(posting_list_serializer), 360 metadata_mmapped_file_(std::move(metadata_mmapped_file)), 361 sorted_buckets_(std::move(sorted_buckets)), 362 unsorted_buckets_(std::move(unsorted_buckets)), 363 flash_index_storage_(std::move(flash_index_storage)), 364 is_info_dirty_(false), 365 is_storage_dirty_(false) {} 366 367 static libtextclassifier3::StatusOr<std::unique_ptr<IntegerIndexStorage>> 368 InitializeNewFiles( 369 const Filesystem& filesystem, std::string&& working_path, 370 Options&& options, 371 PostingListIntegerIndexSerializer* posting_list_serializer); 372 373 static libtextclassifier3::StatusOr<std::unique_ptr<IntegerIndexStorage>> 374 InitializeExistingFiles( 375 const Filesystem& filesystem, std::string&& working_path, 376 Options&& options, 377 PostingListIntegerIndexSerializer* posting_list_serializer); 378 379 // Flushes data into posting list(s), creates a new bucket with range 380 // [key_lower, key_upper], and appends it into sorted buckets for storage. 381 // It is a helper function for TransferIndex. 382 // 383 // Returns: 384 // - OK on success 385 // - INTERNAL_ERROR if fails to write existing data into posting list(s) 386 // - Any FileBackedVector or PostingList errors 387 static libtextclassifier3::Status FlushDataIntoNewSortedBucket( 388 int64_t key_lower, int64_t key_upper, 389 std::vector<IntegerIndexData>&& data, IntegerIndexStorage* storage); 390 391 libtextclassifier3::Status PersistStoragesToDisk() override; 392 393 libtextclassifier3::Status PersistMetadataToDisk() override; 394 WriteMetadata()395 libtextclassifier3::Status WriteMetadata() override { 396 // IntegerIndexStorage::Header is mmapped. Therefore, writes occur when the 397 // metadata is modified. So just return OK. 398 return libtextclassifier3::Status::OK; 399 } 400 401 libtextclassifier3::StatusOr<Crc32> UpdateStoragesChecksum() override; 402 403 libtextclassifier3::StatusOr<Crc32> GetInfoChecksum() const override; 404 405 libtextclassifier3::StatusOr<Crc32> GetStoragesChecksum() const override; 406 407 // Helper function to add keys in range [it_start, it_end) into the given 408 // bucket. It handles the bucket and its corresponding posting list(s) to make 409 // searching and indexing efficient. 410 // 411 // When the (single) posting list of the bucket is full: 412 // - If the size of posting list hasn't reached the max size, then just simply 413 // add a new key into it, and PostingListAccessor mechanism will 414 // automatically double the size of the posting list. 415 // - Else: 416 // - If the bucket is splittable (i.e. key_lower < key_upper), then split it 417 // into several new buckets with new ranges, and split the data (according 418 // to their keys and the range of new buckets) of the original posting 419 // list into several new posting lists. 420 // - Otherwise, just simply add a new key into it, and PostingListAccessor 421 // mechanism will automatically create a new max size posting list and 422 // chain them. 423 // 424 // Returns: 425 // - On success: a vector of new Buckets (to add into the unsorted bucket 426 // array later) 427 // - Any FileBackedVector or PostingList errors 428 libtextclassifier3::StatusOr<std::vector<Bucket>> 429 AddKeysIntoBucketAndSplitIfNecessary( 430 DocumentId document_id, SectionId section_id, 431 const std::vector<int64_t>::const_iterator& it_start, 432 const std::vector<int64_t>::const_iterator& it_end, 433 FileBackedVector<Bucket>::MutableView& mutable_bucket); 434 435 // Merges all unsorted buckets into sorted buckets and clears unsorted 436 // buckets. 437 // 438 // Returns: 439 // - OK on success 440 // - OUT_OF_RANGE_ERROR if sorted buckets length exceeds the limit after 441 // merging 442 // - Any FileBackedVector errors 443 libtextclassifier3::Status SortBuckets(); 444 crcs()445 Crcs& crcs() override { 446 return *reinterpret_cast<Crcs*>(metadata_mmapped_file_->mutable_region() + 447 kCrcsMetadataFileOffset); 448 } 449 crcs()450 const Crcs& crcs() const override { 451 return *reinterpret_cast<const Crcs*>(metadata_mmapped_file_->region() + 452 kCrcsMetadataFileOffset); 453 } 454 info()455 Info& info() { 456 return *reinterpret_cast<Info*>(metadata_mmapped_file_->mutable_region() + 457 kInfoMetadataFileOffset); 458 } 459 info()460 const Info& info() const { 461 return *reinterpret_cast<const Info*>(metadata_mmapped_file_->region() + 462 kInfoMetadataFileOffset); 463 } 464 SetInfoDirty()465 void SetInfoDirty() { is_info_dirty_ = true; } 466 467 // When the storage is dirty, then the checksum in the info is invalid and 468 // must be recalculated. Therefore, also mark the info as dirty. SetDirty()469 void SetDirty() { 470 SetInfoDirty(); 471 is_storage_dirty_ = true; 472 } 473 is_info_dirty()474 bool is_info_dirty() const { return is_info_dirty_; } is_storage_dirty()475 bool is_storage_dirty() const { return is_storage_dirty_; } 476 477 Options options_; 478 479 PostingListIntegerIndexSerializer* posting_list_serializer_; // Does not own. 480 481 std::unique_ptr<MemoryMappedFile> metadata_mmapped_file_; 482 std::unique_ptr<FileBackedVector<Bucket>> sorted_buckets_; 483 std::unique_ptr<FileBackedVector<Bucket>> unsorted_buckets_; 484 std::unique_ptr<FlashIndexStorage> flash_index_storage_; 485 486 bool is_info_dirty_; 487 bool is_storage_dirty_; 488 }; 489 490 } // namespace lib 491 } // namespace icing 492 493 #endif // ICING_INDEX_NUMERIC_INTEGER_INDEX_STORAGE_H_ 494