vinothchandar commented on code in PR #17827: URL: https://github.com/apache/hudi/pull/17827#discussion_r3406217434
########## rfc/rfc-103/rfc-103.md: ########## @@ -0,0 +1,246 @@ + <!-- + Licensed to the Apache Software Foundation (ASF) under one or more + contributor license agreements. See the NOTICE file distributed with + this work for additional information regarding copyright ownership. + The ASF licenses this file to You under the Apache License, Version 2.0 + (the "License"); you may not use this file except in compliance with + the License. You may obtain a copy of the License at + + http://www.apache.org/licenses/LICENSE-2.0 + + Unless required by applicable law or agreed to in writing, software + distributed under the License is distributed on an "AS IS" BASIS, + WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + See the License for the specific language governing permissions and + limitations under the License. +--> +# RFC-103: Hudi LSM tree layout + +## Proposers + +- @zhangyue19921010 +- @xushiyan + +## Approvers +- @danny0405 +- @vinothchandar + +## Status + +Main issue: https://github.com/apache/hudi/issues/14310 + +## Background + +LSM Trees (Log-Structured Merge-Trees) are data structures optimized for write-intensive workloads and are widely used in modern database systems such as Paimon, LevelDB, RocksDB, Cassandra, etc. By leveraging sequential writes and a tiered merge (compaction) mechanism, they offer clear advantages in: + +- **High write throughput** +- **Efficient, tiered compaction** +- **Optimized read paths** + +## Goal + +This RFC proposes applying LSM-inspired principles (**sequential writes + tiered merges**) to improve the data organization protocol for **Hudi MOR tables**, and replacing **Avro** with **Parquet** as the on-disk format for individual log files, to achieve: + +1. Improve the **read performance**, **write performance**, and **overall stability** of MOR tables—especially for **wide tables**—in scenarios such as: + - predicate pushdown + - point lookups + - column/data pruning +2. Improve the **performance** and **stability** of MOR **compaction** +3. Increase the **compression ratio** of log files + +## Design Overview + + + +The core idea is to treat, **within each file group**: + +- **Log files** as **Level-0 (L0)** of an LSM tree +- The only **Base file** as **Level-1 (L1)** + +The file naming formats for base and log files should retain unchanged. + +To realize this layout: + +- Records inside **log and base files must be sorted** (**Core Feature 1**) +- Records should be deduplicated before writing to any log file, i.e., no dups within a log file. Duplicates can be seen across log files. +- Existing services should implement **sorted merge-based compaction**: + - **log-compaction** handles **L0 compaction** + - **compaction table service** handles **L0 → L1 compaction** + - both use a **sorted merge algorithm** (**Core Feature 2**) + +## Considerations + +### Table configs + +The layout should be enforced by a table property, for e.g. `hoodie.table.storage.layout=base_log|lsm_tree` (default `base_log`, which is current base/log file organization): + +- The config is not allowed to be set to `lsm_tree` for an existing table +- The config is allowed to be set to `base_log` for an existing table + +The layout is only applicable to MOR table, and not applicable to COW. When setting the layout config for a COW table, the persisted config for the layout will always be false. + +When an LSM-tree layout enabled MOR table is migrated to COW, the layout config will automatically set to `false`. + +### Engine-agnostic + +The layout should be engine-agnostic. Writer engines can make use of shared implementation and add specific logic or design to comform to the layout. + +For example, Flink writers use buffer sort, the Flink sink must flush sorted records into a single file to guarantee file-level ordering. + +### Write operations + +Write operations should remain semantically unchanged when the layout is enabled. + +In MOR tables, when **small file handling** occurs, inserts may be bin-packed into file slices without log files, creating a new base file, the **sorted write** needs to be applied. + +The most performant writer setup for LSM tree layout will be bucket index + bulk insert, which best utilizes sorted merging. The downside would be that small files may proliferate, which can be mitigated by doing log compaction. + +### Indexes + +Writer indexes should still function as is under this layout. Same for reader indexes. + +### Clustering + +Clustering will be restricted to **record key sorting** only. + +For **MOR + bucket index** setup, clustering is typically not needed. + +## Core Feature 1: Sorted Write + +All writes are sorted. That is, within any written file (**base or log**), records are fully sorted by key(s). + +### Initial support (v1) + +- `bulk_insert` +- `insert_overwrite` +- with **bucket index** + +### Future support + +- `insert`, `upsert` +- other index types + +### Example: Flink Streaming Write Pipeline + + + +The write pipeline mainly consists of four core stages: + +- **Repartitioning** +- **Sorting** +- **Deduplication** +- **I/O** + +Optimizations: + +1. **Asynchronous processing architecture** Review Comment: did we resolve this, by running sth on 1.1+ again? now, on 1.2+? Not a blocker if we are just reusing machinery already in place ########## rfc/rfc-103/rfc-103.md: ########## @@ -0,0 +1,414 @@ + <!-- + Licensed to the Apache Software Foundation (ASF) under one or more + contributor license agreements. See the NOTICE file distributed with + this work for additional information regarding copyright ownership. + The ASF licenses this file to You under the Apache License, Version 2.0 + (the "License"); you may not use this file except in compliance with + the License. You may obtain a copy of the License at + + http://www.apache.org/licenses/LICENSE-2.0 + + Unless required by applicable law or agreed to in writing, software + distributed under the License is distributed on an "AS IS" BASIS, + WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + See the License for the specific language governing permissions and + limitations under the License. +--> +# RFC-103: Hudi LSM tree layout + +## Proposers + +- @zhangyue19921010 +- @xushiyan + +## Approvers + +- @danny0405 +- @vinothchandar + +## Status + +Main issue: https://github.com/apache/hudi/issues/14310 + +## Background + +LSM Trees (Log-Structured Merge-Trees) are data structures optimized for write-intensive workloads and are widely used in modern database systems such as LevelDB, RocksDB, Cassandra, etc. They offer higher write performance typically compared to traditional B+Tree structures. + +Systems like Paimon, adopt the LSM structure for data lake workloads as well, with a tiered merge (compaction) mechanism, they offer some valid tradeoffs in terms of: + +- Lower memory requirements to merge logs compared to hash merge algorithms(when the number of files to merge is small); efficient compaction +- Layout sorted by keys within each file group, that can be faster for point lookup + +## Goal + +This RFC proposes applying LSM-inspired principles (**sorted writes + N-way merges**) to improve the data organization protocol for Hudi tables, +and favoring native Parquet log file format over log format in Avro or embedded Parquet log block, to achieve improvements on the performance and stability of MOR compaction, +and point lookup efficiency. + +Comparing to Avro log format, using native Parquet log format further achieves read performance improvements on native predicate pushdown, stats pruning, and better compression. + +## Design Overview + + + +The core idea is to treat, **within each file group**: + +- **Log files** as **Level-0 (L0)** of an LSM tree +- The single **Base file** as **Level-1 (L1)** + +The file namings: + +- The base file naming retain unchanged. +- The data log file naming switches from `.<fileId>_<instant>.log.<version>_<writeToken>` to `<fileId>_<writeToken>_<instant>_<version>.parquet`: the file is not a hidden file now, Review Comment: lets do `<fileId>_<writeToken>_<instant>_<version>.log.parquet` . the file is still a change log, and ordered ########## rfc/rfc-103/rfc-103.md: ########## @@ -0,0 +1,414 @@ + <!-- + Licensed to the Apache Software Foundation (ASF) under one or more + contributor license agreements. See the NOTICE file distributed with + this work for additional information regarding copyright ownership. + The ASF licenses this file to You under the Apache License, Version 2.0 + (the "License"); you may not use this file except in compliance with + the License. You may obtain a copy of the License at + + http://www.apache.org/licenses/LICENSE-2.0 + + Unless required by applicable law or agreed to in writing, software + distributed under the License is distributed on an "AS IS" BASIS, + WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + See the License for the specific language governing permissions and + limitations under the License. +--> +# RFC-103: Hudi LSM tree layout + +## Proposers + +- @zhangyue19921010 +- @xushiyan + +## Approvers + +- @danny0405 +- @vinothchandar + +## Status + +Main issue: https://github.com/apache/hudi/issues/14310 + +## Background + +LSM Trees (Log-Structured Merge-Trees) are data structures optimized for write-intensive workloads and are widely used in modern database systems such as LevelDB, RocksDB, Cassandra, etc. They offer higher write performance typically compared to traditional B+Tree structures. + +Systems like Paimon, adopt the LSM structure for data lake workloads as well, with a tiered merge (compaction) mechanism, they offer some valid tradeoffs in terms of: + +- Lower memory requirements to merge logs compared to hash merge algorithms(when the number of files to merge is small); efficient compaction +- Layout sorted by keys within each file group, that can be faster for point lookup + +## Goal + +This RFC proposes applying LSM-inspired principles (**sorted writes + N-way merges**) to improve the data organization protocol for Hudi tables, +and favoring native Parquet log file format over log format in Avro or embedded Parquet log block, to achieve improvements on the performance and stability of MOR compaction, +and point lookup efficiency. + +Comparing to Avro log format, using native Parquet log format further achieves read performance improvements on native predicate pushdown, stats pruning, and better compression. + +## Design Overview + + + +The core idea is to treat, **within each file group**: + +- **Log files** as **Level-0 (L0)** of an LSM tree +- The single **Base file** as **Level-1 (L1)** + +The file namings: + +- The base file naming retain unchanged. +- The data log file naming switches from `.<fileId>_<instant>.log.<version>_<writeToken>` to `<fileId>_<writeToken>_<instant>_<version>.parquet`: the file is not a hidden file now, + hidden file brings in adoptions issues in some engines(Apache Hive), exposing the log files make it more straight-forward(for debugging or for file scanning). The native file format + suffix is used for the similar purposes: easy adoption for query engines, easy to extend(to other formats like Lance). +- The delete log file naming: `<fileId>_<writeToken>_<instant>_<version>.delete.parquet` + +The reason not to add `.log` in the log file name: + +- regex match can already distinguish the existing files; +- with LSM tree, there is no strict boundaries for these files, the only difference is the layer the file belongs to and whether it is compacted/replaced + +To realize this layout: + +- Records inside **log and base files must be sorted by record key(s)** (**Core Feature 1**) +- Records can be optionally deduplicated before writing to any log file. (optional for query optimization) +- Existing services should implement **sorted merge-based compaction**: + - **log-compaction** handles **L0 compaction** + - **compaction table service** handles **L0 → L1 compaction** + - both use a **sorted merge algorithm** (**Core Feature 2**) + +## Considerations + +### Table configs + +The layout should be enforced by a table property, for e.g. `hoodie.table.storage.layout=default|lsm_tree` (default value: `default`, which is current base/log file organization). The layout applies to both COW and MOR table. + +### Engine-agnostic + +The layout should be engine-agnostic. Writer engines can make use of shared implementation and add specific logic or design to conform to the layout. + +For example, Flink writers use buffer sort, the Flink sink must flush sorted records into a single file to guarantee file-level ordering. + +### Write operations + +Write operations should remain semantically unchanged when the layout is enabled. + +In MOR tables, when **small file handling** occurs, inserts may be bin-packed into file slices without log files, creating a new base file, the **sorted write** needs to be applied. +A `SortedCreateHandle` is needed for writing base files, similar to `SortedMergeHandle`. + +For MOR tables, the most performant writer setup for LSM tree layout will be bucket index + bulk insert, which best utilizes sort-merging. The downside would be that small files may proliferate, which can be mitigated by doing log compaction. + +### Indexes + +Writer indexes should still function as is under this layout. Same for reader indexes. + +### Clustering + +Clustering can be supported by adopting a hybrid clustering strategy that keeps records sorted by record key(s) within each file group, while keep records collocated in file groups based on user-specified non-record key fields. + +## Core Feature 1: Sorted Write + +All writes are sorted. That is, within any written file (**base or log**), records are fully sorted by record key(s). + +All write operations and writer index types should be supported, as the layout is only about keeping records sorted in data files, which is orthogonal to the choice of write operation and index type. + +### Example: Flink Streaming Write Pipeline + + + +The write pipeline mainly consists of four core stages: + +- **Repartitioning** +- **Sorting** +- **Deduplication**(optional) +- **I/O** + +Optimizations: + +1. **Asynchronous processing architecture** + Introduce a **Disruptor ring buffer** within the sink operator to decouple production and consumption, significantly improving throughput and handling cases where the producer outpaces the consumer. + +2. **Efficient memory management** + Integrate Flink’s built-in **MemorySegmentPool** with **BinaryInMemorySortBuffer** to enable fine-grained memory control and efficient sorting, greatly reducing GC pressure and sorting overhead. + +## Core Feature 2: Sorted Merge Read / Compaction + +During read and compaction, merging can be performed as k-way merging: + +- Resulting **log files** contain fully sorted records +- Resulting **base files** contain fully sorted records +- File group reads reuse the same sorted merge logic, with **predicate pruning** applied when present + +Merging write handles and file group reader should activate the code path for using the merging algorithm when LSM tree layout is enabled for the table. + +### K-way merging algorithm + +To optimize the merging performance, we propose a statemachine-based loser-tree merging algorithm to perform k-way merging. + + + +This part assumes k pre-sorted input streams and implements high-throughput merge reading in SortMergeReaderLoserTreeStateMachine by combining two mechanisms: + +- A loser tree for efficient global winner selection. +- A state machine for continuous same-key consumption and transition control. + +#### 1. Design Goals + +- Minimize latency and memory overhead for multi-way sorted merge. +- Guarantee deterministic ordering for records with the same key. +- Support streaming merge semantics (including delete/upsert) without building large per-key buffers. + +#### 2. Core Structures + +- tree[]: loser-tree internal nodes, where tree[0] is the current champion leaf index. +- leaves[]: current head record of each input stream plus node state. +- firstSameKeyIndex: fast jump pointer to another contender with the same key. +- States: + - WINNER_WITH_NEW_KEY + - WINNER_WITH_SAME_KEY + - WINNER_POPPED + - LOSER_WITH_NEW_KEY + - LOSER_WITH_SAME_KEY + - LOSER_POPPED + +#### 3. Execution Flow + +1. Initialization + Read one record from each input stream, set initial state, and build the loser tree via adjust. +2. Winner/loser propagation + adjust only updates one root path (O(log k)). Comparison is key-based; if equal, sourceIndex is used as a deterministic tie-breaker. +3. Same-key linking + Equal-key comparisons mark losers as LOSER_WITH_SAME_KEY and record firstSameKeyIndex for fast same-key handoff. +4. Pop and advance + popWinner() marks current winner as popped and re-adjusts: + - If same-key contenders exist, it switches directly to WINNER_WITH_SAME_KEY. + - Otherwise, popAdvance() pulls the next record from that source and resumes normal competition. +5. Group merge output + The iterator repeatedly pops and merges all records of one key using mergeFunctionWrapper, then emits one merged result for that key. + +#### 4. Performance Characteristics + +- Time complexity: O(N log k) for N total records. +- Space complexity: O(k) (one active record per stream plus tree metadata). +- Benefits: + - Fewer redundant comparisons than naive merge approaches. + - No large same-key temporary list. + - Stable, reproducible merge order via deterministic tie-breaking. + +--- + +## Log format v2: native log file format + +### Current log format (v1) + +Current log format is organized as below (ref: [tech spec v8](https://hudi.apache.org/learn/tech-specs-1point0#log-format)): + +```text +#HUDI# (magic, 6 bytes) +Block Size (8 bytes) +Log Format Version (4 bytes) +Block Type (4 bytes) +Header Metadata (variable) +Content Length (8 bytes) +Content (variable) - data block, embedded Avro/Parquet/HFile binary data +Footer Metadata (variable) +Reverse Pointer (8 bytes) +``` + +These fields are encoded into a custom binary format and stored in log files with extension like `.log.<version>_<write_token>`. + +### Proposed log format v2 + +The proposed new log format leverages native file format's metadata layer to capture the metadata fields defined by Hudi log format, while keeping the content field (data block). Take parquet for example: + +```text +Row group 1 (data) +Row group 2 (data) +... +Footer + - Parquet schema + - Row group metadata + - key-value metadata <-- Hudi log format metadata goes in here +``` + +Hudi log format metadata can be stored as a single entry in the Parquet footer with key = `hudi.log.format.metadata` and value being a serialized map of the metadata entries: + +| Hudi log format metadata | +|:---------------------------------------------| +| log format version | +| block type | +| `INSTANT_TIME` | +| `TARGET_INSTANT_TIME` | +| `SCHEMA` | +| `COMMAND_BLOCK_TYPE` | +| `COMPACTED_BLOCK_TIMES` | +| `RECORD_POSITIONS` | +| `BLOCK_IDENTIFIER` | +| `IS_PARTIAL` | +| `BASE_FILE_INSTANT_TIME_OF_RECORD_POSITIONS` | + +When using native log format, the log file name uses a suffix like `.<native format>`, for e.g., `.parquet`. + +### Why native file format over embedded Parquet log blocks? + +An alternative approach is to keep the V1 log format structure and embed Parquet-encoded data as block content. However, the embedding approach has drawbacks compared to using native Parquet files: + +| Aspect | Embedded Parquet (V1) | Native Parquet (V2) | +|---------------------------|----------------------------------------------------------------------------------------------------------------------------|-------------------------------------------------------------------------------| +| **Parquet optimizations** | Vectorized reads, predicate pushdown, column pruning available after block location via InLineFileSystem | Available directly via standard Parquet read path | +| **Write model** | Designed for append (for HDFS, not for object storage) | Write-once model (aligns with object storage) | +| **Reading overhead** | Must read log block header first, then use InLineFileSystem abstraction with offset translation to access embedded content | Read Parquet footer for metadata, then direct file read (no InLineFileSystem) | +| **Tool compatibility** | Requires Hudi-specific readers | Any Parquet-compatible tool can read | +| **Compression** | Block-level only | Parquet's columnar encoding | +| **Schema storage** | Duplicated in header and content | Consolidated in Parquet footer | + +Using native log file format can also be extended to other file format, like [Lance](https://lance.org/format/file/) for example. The Hudi log format metadata can be stored in Lance file's [global buffer](https://lance.org/format/file/#external-buffers) to facilitate log file operations. + +### Block type handling + +**Data log**: The data file is a native Parquet file with `hudi.log.block_type` = `parquet_data`. The Parquet schema is the writer's table schema, including Hudi metadata columns (`_hoodie_commit_time`, `_hoodie_commit_seqno`, `_hoodie_record_key`, `_hoodie_partition_path`, `_hoodie_file_name`), followed by the user-defined data columns. Review Comment: `hudi.log.block_type` is another footer? ########## rfc/rfc-103/rfc-103.md: ########## @@ -0,0 +1,414 @@ + <!-- + Licensed to the Apache Software Foundation (ASF) under one or more + contributor license agreements. See the NOTICE file distributed with + this work for additional information regarding copyright ownership. + The ASF licenses this file to You under the Apache License, Version 2.0 + (the "License"); you may not use this file except in compliance with + the License. You may obtain a copy of the License at + + http://www.apache.org/licenses/LICENSE-2.0 + + Unless required by applicable law or agreed to in writing, software + distributed under the License is distributed on an "AS IS" BASIS, + WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + See the License for the specific language governing permissions and + limitations under the License. +--> +# RFC-103: Hudi LSM tree layout + +## Proposers + +- @zhangyue19921010 +- @xushiyan + +## Approvers + +- @danny0405 +- @vinothchandar + +## Status + +Main issue: https://github.com/apache/hudi/issues/14310 + +## Background + +LSM Trees (Log-Structured Merge-Trees) are data structures optimized for write-intensive workloads and are widely used in modern database systems such as LevelDB, RocksDB, Cassandra, etc. They offer higher write performance typically compared to traditional B+Tree structures. + +Systems like Paimon, adopt the LSM structure for data lake workloads as well, with a tiered merge (compaction) mechanism, they offer some valid tradeoffs in terms of: + +- Lower memory requirements to merge logs compared to hash merge algorithms(when the number of files to merge is small); efficient compaction +- Layout sorted by keys within each file group, that can be faster for point lookup + +## Goal + +This RFC proposes applying LSM-inspired principles (**sorted writes + N-way merges**) to improve the data organization protocol for Hudi tables, +and favoring native Parquet log file format over log format in Avro or embedded Parquet log block, to achieve improvements on the performance and stability of MOR compaction, +and point lookup efficiency. + +Comparing to Avro log format, using native Parquet log format further achieves read performance improvements on native predicate pushdown, stats pruning, and better compression. + +## Design Overview + + + +The core idea is to treat, **within each file group**: + +- **Log files** as **Level-0 (L0)** of an LSM tree +- The single **Base file** as **Level-1 (L1)** + +The file namings: + +- The base file naming retain unchanged. +- The data log file naming switches from `.<fileId>_<instant>.log.<version>_<writeToken>` to `<fileId>_<writeToken>_<instant>_<version>.parquet`: the file is not a hidden file now, + hidden file brings in adoptions issues in some engines(Apache Hive), exposing the log files make it more straight-forward(for debugging or for file scanning). The native file format + suffix is used for the similar purposes: easy adoption for query engines, easy to extend(to other formats like Lance). +- The delete log file naming: `<fileId>_<writeToken>_<instant>_<version>.delete.parquet` + +The reason not to add `.log` in the log file name: + +- regex match can already distinguish the existing files; Review Comment: IMO this argument is not very strong. We regex match anything. My comment comes from semantics. `.log` is what encodes that relationship of the file as a "Delta log" against a base. This is a core design principle in Hudi. Lets keep it that way please? ########## rfc/rfc-103/rfc-103.md: ########## @@ -0,0 +1,332 @@ + <!-- + Licensed to the Apache Software Foundation (ASF) under one or more + contributor license agreements. See the NOTICE file distributed with + this work for additional information regarding copyright ownership. + The ASF licenses this file to You under the Apache License, Version 2.0 + (the "License"); you may not use this file except in compliance with + the License. You may obtain a copy of the License at + + http://www.apache.org/licenses/LICENSE-2.0 + + Unless required by applicable law or agreed to in writing, software + distributed under the License is distributed on an "AS IS" BASIS, + WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + See the License for the specific language governing permissions and + limitations under the License. +--> +# RFC-103: Hudi LSM tree layout + +## Proposers + +- @zhangyue19921010 +- @xushiyan + +## Approvers + +- @danny0405 +- @vinothchandar + +## Status + +Main issue: https://github.com/apache/hudi/issues/14310 + +## Background + +LSM Trees (Log-Structured Merge-Trees) are data structures optimized for write-intensive workloads and are widely used in modern database systems such as LevelDB, RocksDB, Cassandra, etc. They offer higher write performance typically compared to traditional B+Tree structures. + +Systems like Paimon, adopt the LSM structure for data lake workloads as well, with a tiered merge (compaction) mechanism, they offer some valid tradeoffs in terms of: + +- Lower memory requirements to merge logs compared to hash merge algorithms; efficient compaction +- Layout sorted by keys within each file group, that can be faster for point lookup + +## Goal + +This RFC proposes applying LSM-inspired principles (**sorted writes + N-way merges**) to improve the data organization protocol for Hudi tables, and favoring native Parquet log file format over log format in Avro or embedded Parquet log block, to achieve improvements on the performance and stability of MOR compaction, and point lookup efficiency. + +Comparing to Avro log format or log file with embedded Parquet log block, using native Parquet log format further achieves read performance improvements on native predicate pushdown, stats pruning, and better compression. + +## Design Overview + + + +The core idea is to treat, **within each file group**: + +- **Log files** as **Level-0 (L0)** of an LSM tree +- The only **Base file** as **Level-1 (L1)** + +The file naming formats for base and log files should retain unchanged. + +To realize this layout: + +- Records inside **log and base files must be sorted by record key(s)** (**Core Feature 1**) +- Records should be deduplicated before writing to any log file, i.e., no dups within a log file. Duplicates can be seen across log files. +- Existing services should implement **sorted merge-based compaction**: + - **log-compaction** handles **L0 compaction** + - **compaction table service** handles **L0 → L1 compaction** + - both use a **sorted merge algorithm** (**Core Feature 2**) + +## Considerations + +### Table configs + +The layout should be enforced by a table property, for e.g. `hoodie.table.storage.layout=default|lsm_tree` (default value: `default`, which is current base/log file organization). The layout applies to both COW and MOR table. + +### Engine-agnostic + +The layout should be engine-agnostic. Writer engines can make use of shared implementation and add specific logic or design to comform to the layout. + +For example, Flink writers use buffer sort, the Flink sink must flush sorted records into a single file to guarantee file-level ordering. + +### Write operations + +Write operations should remain semantically unchanged when the layout is enabled. + +In MOR tables, when **small file handling** occurs, inserts may be bin-packed into file slices without log files, creating a new base file, the **sorted write** needs to be applied. A `SortedCreateHandle` would be needed, similar to `SortedMergeHandle`. + +For MOR tables, the most performant writer setup for LSM tree layout will be bucket index + bulk insert, which best utilizes sorted merging. The downside would be that small files may proliferate, which can be mitigated by doing log compaction. + +### Indexes + +Writer indexes should still function as is under this layout. Same for reader indexes. + +### Clustering + +Clustering will be restricted to **record key sorting** only. + +For **MOR + bucket index** setup, clustering is typically not needed. + +## Core Feature 1: Sorted Write + +All writes are sorted. That is, within any written file (**base or log**), records are fully sorted by record key(s). + +All write operations and writer index types should be supported, as the layout is only about keeping records sorted in data files, which is orthogonal to the choice of write operation and index type. + +### Example: Flink Streaming Write Pipeline + + + +The write pipeline mainly consists of four core stages: + +- **Repartitioning** +- **Sorting** +- **Deduplication** +- **I/O** + +Optimizations: + +1. **Asynchronous processing architecture** + Introduce a **Disruptor ring buffer** within the sink operator to decouple production and consumption, significantly improving throughput and handling cases where the producer outpaces the consumer. + +2. **Efficient memory management** + Integrate Flink’s built-in **MemorySegmentPool** with **BinaryInMemorySortBuffer** to enable fine-grained memory control and efficient sorting, greatly reducing GC pressure and sorting overhead. + +## Core Feature 2: Sorted Merge Read / Compaction + +During read and compaction, merging can be performed as k-way merging: + +- Resulting **log files** contain fully sorted records +- Resulting **base files** contain fully sorted records +- File group reads reuse the same sorted merge logic, with **predicate pruning** applied when present + +Merging write handles and file group reader should activate the code path for using the merging algorithm when LSM tree layout is enabled for the table. + +### K-way merging algorithm + +To optimize the merging performance, we propose a statemachine-based loser-tree merging algorithm to perform k-way merging. Review Comment: can we please add link to make the readers be aware. -- This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. To unsubscribe, e-mail: [email protected] For queries about this service, please contact Infrastructure at: [email protected]
