[Feature]: Range size tracking

[yi-xmu]

In range partition mode, range size needs to be tracked in real time in order to trigger range splits promptly.

To achieve this feature, two range sizes variables are maintained:

• 1. Maintain two related variables:

  1.1. the in-memory range size (real-time value for split decisions)

  1.2. the persisted range size (durable value for rebuilding in-memory stats on restart or ccmap initialization).

• 2. Maintaining range sizes in memory:

Keep in-memory range sizes accurate across five key paths: PostWriteCc, ccmap initialization, range split, log replay, and Create SK.

• 2.1. PostWriteCc
  1) After each write, compute the size delta for the key’s range and add it to that range’s in-memory size.
  2) If the current range size has not been initialized, then perform the load range size operation to initialize the range size.

• 2.2. Ccmap Initialization (including restart)
  When a ccmap first executes a write request, lazily initialize range_sizes_ from persisted range sizes.

• 2.3. Range Split
  After a range split, initialize each new range’s size from the summed size of its slices while preserving the old range’s history.
  1) For the post write operation in the range split process (i.e. the "double write" phase), the change in range size is recorded in the delta size. At the same time, the delta size of the key belonging to the new range is not recorded in the delta size of the old range.
  1) During the post-commit phase of range splitting, the range size of all subranges is reset, i.e., persisted range size + delta size.

• 2.4. Log Replay
  This includes two aspects:
  1) Data log replay
  Use persisted range sizes as the baseline, apply conservative updates for replayed keys with unknown size, and route by range id instead of key hash.
  2) Range split log replay

• 2.5. Create SK(UploadBatchCc)
  With the target range known, send UploadBatchCc only to the target shard and update that range’s size when writing SKs.
  Update range sizes of this ccmap.

• 3. Maintaining range sizes in storage:
  3.1. On the write side, aggregate slice sizes per range during checkpoint or range-slice updates and persist them;
  3.2. On the read side, load these persisted values when initializing ccmap or after restart to rebuild in-memory range sizes.

[yi-xmu]

The locations where range size information needs to be updated include:

1. During the post-write process, update the range size based on the state of ccentry.

2. During range initialization, initialize the range size based on the slice size.

3. During range splitting, initialize a new range size based on the slice size information.

[yi-xmu]

For situations where the data store size for a key is unknown (such as during log replay/sk creation), special handling is required.

[yi-xmu]

To avoid nested hash map usage, the in-memory range size information is stored in ccmap instead of on the ccshard.

[yi-xmu]

In the event of the server restart (ignoring log replay for now), the range size needs to be set.

The first approach is to rely on StoreRangeSlices information.
The problem with this approach is that StoreRangeSlices information is lazy-loaded, so not all tables (such as secondary index tables) will have their range size set promptly.

Consider the second approach: after a checkpoint, update the range slice information in storage and persist the currently stored range size. Then, when the server restarts, use this value to set the in-memory range size.

[yi-xmu]

Updated Implementation:

1. For the store range size loading logic, a "lazy loading" mode is adopted. This means that when a range is accessed for the first time, its store range size information is loaded and set in memory. However, it's not necessary to load the store range size information for all ranges.

2. During range splitting, in the prepare-commit phase, a based range size is set for each subrange. Subsequent double-write operations will update the range size based on this size.

3. During double-write operations in the range split process, if the target shard of the new subrange and the target shard of the old range are the same shard, a forward write operation is still performed. However, it's necessary to mark the postwrite operations in the old range as not requiring range size updates. This is because after writing the prepare log, the range splitting transaction will definitely succeed.

[yi-xmu]

[yi-xmu]

When the log contains range-split logs, how can the range size be maintained during data log replay?