xref: /aosp_15_r20/external/icing/icing/index/numeric/integer-index-storage.h (revision 8b6cd535a057e39b3b86660c4aa06c99747c2136)
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