1use std::collections::{BTreeMap, BTreeSet, HashMap, HashSet};
16use std::ops::Bound;
17use std::sync::atomic::AtomicUsize;
18use std::sync::atomic::Ordering::Relaxed;
19use std::sync::{Arc, LazyLock};
20
21use await_tree::InstrumentAwait;
22use bytes::Bytes;
23use foyer::Hint;
24use futures::future::try_join;
25use futures::{FutureExt, StreamExt, stream};
26use itertools::Itertools;
27use risingwave_common::catalog::TableId;
28use risingwave_hummock_sdk::key::{EPOCH_LEN, FullKey};
29use risingwave_hummock_sdk::key_range::KeyRange;
30use risingwave_hummock_sdk::{EpochWithGap, KeyComparator, LocalSstableInfo};
31use risingwave_pb::hummock::{PbSstableFilterLayout, PbSstableFilterType};
32use thiserror_ext::AsReport;
33use tracing::error;
34
35use crate::compaction_catalog_manager::{CompactionCatalogAgentRef, CompactionCatalogManagerRef};
36use crate::hummock::compactor::compaction_filter::DummyCompactionFilter;
37use crate::hummock::compactor::compaction_utils::{
38 blocked_xor_filter_key_count_threshold, estimate_output_key_count_by_size,
39};
40use crate::hummock::compactor::context::{CompactorContext, await_tree_key};
41use crate::hummock::compactor::{CompactOutput, Compactor, check_flush_result};
42use crate::hummock::event_handler::uploader::UploadTaskOutput;
43use crate::hummock::iterator::{Forward, HummockIterator, MergeIterator, UserIterator};
44use crate::hummock::{
45 CachePolicy, GetObjectId, HummockError, HummockResult, ObjectIdManagerRef,
46 SstableBuilderOptions,
47};
48use crate::mem_table::ImmutableMemtable;
49use crate::opts::StorageOpts;
50
51const GC_DELETE_KEYS_FOR_FLUSH: bool = false;
52
53pub async fn compact(
55 context: CompactorContext,
56 object_id_manager: ObjectIdManagerRef,
57 payload: Vec<ImmutableMemtable>,
58 compaction_catalog_manager_ref: CompactionCatalogManagerRef,
59) -> HummockResult<UploadTaskOutput> {
60 let table_ids_with_old_value: HashSet<TableId> = payload
61 .iter()
62 .filter(|imm| imm.has_old_value())
63 .map(|imm| imm.table_id)
64 .collect();
65 let mut non_log_store_new_value_payload = Vec::with_capacity(payload.len());
66 let mut log_store_new_value_payload = Vec::with_capacity(payload.len());
67 let mut old_value_payload = Vec::with_capacity(payload.len());
68 for imm in payload {
69 if table_ids_with_old_value.contains(&imm.table_id) {
70 if imm.has_old_value() {
71 old_value_payload.push(imm.clone());
72 }
73 log_store_new_value_payload.push(imm);
74 } else {
75 assert!(!imm.has_old_value());
76 non_log_store_new_value_payload.push(imm);
77 }
78 }
79 let non_log_store_new_value_future = async {
80 if non_log_store_new_value_payload.is_empty() {
81 Ok(vec![])
82 } else {
83 compact_shared_buffer::<true>(
84 context.clone(),
85 object_id_manager.clone(),
86 compaction_catalog_manager_ref.clone(),
87 non_log_store_new_value_payload,
88 )
89 .instrument_await("shared_buffer_compact_non_log_store_new_value")
90 .await
91 }
92 };
93
94 let log_store_new_value_future = async {
95 if log_store_new_value_payload.is_empty() {
96 Ok(vec![])
97 } else {
98 compact_shared_buffer::<true>(
99 context.clone(),
100 object_id_manager.clone(),
101 compaction_catalog_manager_ref.clone(),
102 log_store_new_value_payload,
103 )
104 .instrument_await("shared_buffer_compact_log_store_new_value")
105 .await
106 }
107 };
108
109 let old_value_future = async {
110 if old_value_payload.is_empty() {
111 Ok(vec![])
112 } else {
113 compact_shared_buffer::<false>(
114 context.clone(),
115 object_id_manager.clone(),
116 compaction_catalog_manager_ref.clone(),
117 old_value_payload,
118 )
119 .instrument_await("shared_buffer_compact_log_store_old_value")
120 .await
121 }
122 };
123
124 let ((non_log_store_new_value_ssts, log_store_new_value_ssts), old_value_ssts) = try_join(
126 try_join(non_log_store_new_value_future, log_store_new_value_future),
127 old_value_future,
128 )
129 .await?;
130
131 let mut new_value_ssts = non_log_store_new_value_ssts;
132 new_value_ssts.extend(log_store_new_value_ssts);
133
134 Ok(UploadTaskOutput {
135 new_value_ssts,
136 old_value_ssts,
137 wait_poll_timer: None,
138 })
139}
140
141async fn compact_shared_buffer<const IS_NEW_VALUE: bool>(
146 context: CompactorContext,
147 object_id_manager: ObjectIdManagerRef,
148 compaction_catalog_manager_ref: CompactionCatalogManagerRef,
149 mut payload: Vec<ImmutableMemtable>,
150) -> HummockResult<Vec<LocalSstableInfo>> {
151 if !IS_NEW_VALUE {
152 assert!(payload.iter().all(|imm| imm.has_old_value()));
153 }
154 let existing_table_ids: HashSet<TableId> =
156 payload.iter().map(|imm| imm.table_id).dedup().collect();
157 assert!(!existing_table_ids.is_empty());
158
159 let compaction_catalog_agent_ref = compaction_catalog_manager_ref
160 .acquire(existing_table_ids.iter().copied().collect())
161 .await?;
162 let existing_table_ids = compaction_catalog_agent_ref
163 .table_ids()
164 .collect::<HashSet<_>>();
165 payload.retain(|imm| {
166 let ret = existing_table_ids.contains(&imm.table_id);
167 if !ret {
168 error!(
169 "cannot find table {:?}; it may have been removed by the meta service",
170 imm.table_id
171 );
172 }
173 ret
174 });
175
176 let total_key_count = payload.iter().map(|imm| imm.key_count()).sum::<usize>();
177 let (splits, sub_compaction_sstable_size, table_vnode_partition, compact_data_size) =
178 generate_splits(&payload, &existing_table_ids, context.storage_opts.as_ref());
179 let parallelism = splits.len();
180 let mut compact_success = true;
181 let mut output_ssts = Vec::with_capacity(parallelism);
182 let mut compaction_futures = vec![];
183 let estimated_output_key_count = estimate_output_key_count_by_size(
186 total_key_count as u64,
187 compact_data_size,
188 sub_compaction_sstable_size as usize,
189 );
190 let sstable_filter_layout =
191 if risingwave_hummock_sdk::filter_utils::should_use_blocked_xor_filter_by_kv_count(
192 estimated_output_key_count as u64,
193 None,
194 ) {
195 PbSstableFilterLayout::Blocked
196 } else {
197 PbSstableFilterLayout::Plain
198 };
199 let sstable_filter_type = if IS_NEW_VALUE {
200 PbSstableFilterType::SstableFilterXor16
202 } else {
203 PbSstableFilterType::SstableFilterNone
205 };
206
207 for (split_index, key_range) in splits.into_iter().enumerate() {
208 let compactor = SharedBufferCompactRunner::new(
209 split_index,
210 key_range,
211 context.clone(),
212 sub_compaction_sstable_size as usize,
213 estimated_output_key_count,
214 table_vnode_partition.clone(),
215 sstable_filter_layout,
216 sstable_filter_type,
217 object_id_manager.clone(),
218 );
219 let mut forward_iters = Vec::with_capacity(payload.len());
220 for imm in &payload {
221 forward_iters.push(imm.clone().into_directed_iter::<Forward, IS_NEW_VALUE>());
222 }
223 let compaction_executor = context.compaction_executor.clone();
224 let compaction_catalog_agent_ref = compaction_catalog_agent_ref.clone();
225 let handle = compaction_executor.spawn({
226 static NEXT_SHARED_BUFFER_COMPACT_ID: LazyLock<AtomicUsize> =
227 LazyLock::new(|| AtomicUsize::new(0));
228 let tree_root = context.await_tree_reg.as_ref().map(|reg| {
229 let id = NEXT_SHARED_BUFFER_COMPACT_ID.fetch_add(1, Relaxed);
230 reg.register(
231 await_tree_key::CompactSharedBuffer { id },
232 format!(
233 "Compact Shared Buffer: {:?}",
234 payload
235 .iter()
236 .map(|imm| imm.epoch())
237 .collect::<BTreeSet<_>>()
238 ),
239 )
240 });
241 let future = compactor.run(
242 MergeIterator::new(forward_iters),
243 compaction_catalog_agent_ref,
244 );
245 if let Some(root) = tree_root {
246 root.instrument(future).left_future()
247 } else {
248 future.right_future()
249 }
250 });
251 compaction_futures.push(handle);
252 }
253
254 let mut buffered = stream::iter(compaction_futures).buffer_unordered(parallelism);
255 let mut err = None;
256 while let Some(future_result) = buffered.next().await {
257 match future_result {
258 Ok(Ok((split_index, ssts, table_stats_map))) => {
259 output_ssts.push((split_index, ssts, table_stats_map));
260 }
261 Ok(Err(e)) => {
262 compact_success = false;
263 tracing::warn!(error = %e.as_report(), "Shared Buffer Compaction failed with error");
264 err = Some(e);
265 }
266 Err(e) => {
267 compact_success = false;
268 tracing::warn!(
269 error = %e.as_report(),
270 "Shared Buffer Compaction failed with future error",
271 );
272 err = Some(HummockError::compaction_executor(
273 "failed while execute in tokio",
274 ));
275 }
276 }
277 }
278
279 output_ssts.sort_by_key(|(split_index, ..)| *split_index);
281
282 if compact_success {
283 let mut level0 = Vec::with_capacity(parallelism);
284 let mut sst_infos = vec![];
285 for (_, ssts, _) in output_ssts {
286 for sst_info in &ssts {
287 context
288 .compactor_metrics
289 .write_build_l0_bytes
290 .inc_by(sst_info.file_size());
291
292 sst_infos.push(sst_info.sst_info.clone());
293 }
294 level0.extend(ssts);
295 }
296 if context.storage_opts.check_compaction_result {
297 let compaction_executor = context.compaction_executor.clone();
298 let mut forward_iters = Vec::with_capacity(payload.len());
299 for imm in &payload {
300 if !existing_table_ids.contains(&imm.table_id) {
301 continue;
302 }
303 forward_iters.push(imm.clone().into_forward_iter());
304 }
305 let iter = MergeIterator::new(forward_iters);
306 let left_iter = UserIterator::new(
307 iter,
308 (Bound::Unbounded, Bound::Unbounded),
309 u64::MAX,
310 0,
311 None,
312 );
313 compaction_executor.spawn(async move {
314 match check_flush_result(left_iter, sst_infos, context).await {
315 Err(e) => {
316 tracing::warn!(
317 error = %e.as_report(),
318 "failed to check the memtable flush result",
319 );
320 }
321 Ok(true) => (),
322 Ok(false) => {
323 panic!(
324 "failed to check flush result consistency of state-table {:?}",
325 existing_table_ids
326 );
327 }
328 }
329 });
330 }
331 Ok(level0)
332 } else {
333 Err(err.unwrap())
334 }
335}
336
337fn generate_splits(
339 payload: &Vec<ImmutableMemtable>,
340 existing_table_ids: &HashSet<TableId>,
341 storage_opts: &StorageOpts,
342) -> (Vec<KeyRange>, u64, BTreeMap<TableId, u32>, u64) {
343 let mut size_and_start_user_keys = vec![];
344 let mut compact_data_size = 0;
345 let mut table_size_infos: HashMap<TableId, u64> = HashMap::default();
346 let mut table_vnode_partition = BTreeMap::default();
347 for imm in payload {
348 let data_size = {
349 (imm.value_count() * EPOCH_LEN + imm.size()) as u64
351 };
352 compact_data_size += data_size;
353 size_and_start_user_keys.push((
354 data_size,
355 FullKey {
356 user_key: imm.start_user_key(),
357 epoch_with_gap: EpochWithGap::new_max_epoch(),
358 }
359 .encode(),
360 ));
361 let v = table_size_infos.entry(imm.table_id).or_insert(0);
362 *v += data_size;
363 }
364
365 size_and_start_user_keys
366 .sort_by(|a, b| KeyComparator::compare_encoded_full_key(a.1.as_ref(), b.1.as_ref()));
367 let mut splits = Vec::with_capacity(size_and_start_user_keys.len());
368 splits.push(KeyRange::new(Bytes::new(), Bytes::new()));
369 let sstable_size = (storage_opts.sstable_size_mb as u64) << 20;
370 let min_sstable_size = (storage_opts.min_sstable_size_mb as u64) << 20;
371 let parallel_compact_size = (storage_opts.parallel_compact_size_mb as u64) << 20;
372 let parallelism = std::cmp::min(
373 storage_opts.share_buffers_sync_parallelism as u64,
374 size_and_start_user_keys.len() as u64,
375 );
376 let sub_compaction_data_size = if compact_data_size > parallel_compact_size && parallelism > 1 {
377 compact_data_size / parallelism
378 } else {
379 compact_data_size
380 };
381
382 if parallelism > 1 && compact_data_size > sstable_size {
383 let mut last_buffer_size = 0;
384 let mut last_key: Vec<u8> = vec![];
385 for (data_size, key) in size_and_start_user_keys {
386 if last_buffer_size >= sub_compaction_data_size && !last_key.eq(&key) {
387 splits.last_mut().unwrap().right = Bytes::from(key.clone());
388 splits.push(KeyRange::new(Bytes::from(key.clone()), Bytes::default()));
389 last_buffer_size = data_size;
390 } else {
391 last_buffer_size += data_size;
392 }
393
394 last_key = key;
395 }
396 }
397
398 if compact_data_size > sstable_size {
399 for table_id in existing_table_ids {
402 if let Some(table_size) = table_size_infos.get(table_id)
403 && *table_size > min_sstable_size
404 {
405 table_vnode_partition.insert(*table_id, 1);
406 }
407 }
408 }
409
410 let sub_compaction_sstable_size = std::cmp::min(sstable_size, sub_compaction_data_size * 6 / 5);
413 (
414 splits,
415 sub_compaction_sstable_size,
416 table_vnode_partition,
417 compact_data_size,
418 )
419}
420
421pub struct SharedBufferCompactRunner {
422 compactor: Compactor,
423 split_index: usize,
424}
425
426impl SharedBufferCompactRunner {
427 pub fn new(
428 split_index: usize,
429 key_range: KeyRange,
430 context: CompactorContext,
431 sub_compaction_sstable_size: usize,
432 estimated_output_key_count: usize,
433 table_vnode_partition: BTreeMap<TableId, u32>,
434 sstable_filter_layout: PbSstableFilterLayout,
435 sstable_filter_type: PbSstableFilterType,
436 object_id_getter: Arc<dyn GetObjectId>,
437 ) -> Self {
438 let mut options: SstableBuilderOptions = context.storage_opts.as_ref().into();
439 options.capacity = sub_compaction_sstable_size;
440 options.estimated_output_key_count = Some(estimated_output_key_count);
441 options.filter_hash_prealloc_key_count_cap = blocked_xor_filter_key_count_threshold(None);
442 let compactor = Compactor::new(
443 context,
444 options,
445 super::TaskConfig {
446 key_range,
447 cache_policy: CachePolicy::Fill(Hint::Normal),
448 gc_delete_keys: GC_DELETE_KEYS_FOR_FLUSH,
449 retain_multiple_version: true,
450 table_vnode_partition,
451 sstable_filter_layout,
452 sstable_filter_type,
453 table_schemas: Default::default(),
454 disable_drop_column_optimization: false,
455 },
456 object_id_getter,
457 );
458 Self {
459 compactor,
460 split_index,
461 }
462 }
463
464 pub async fn run(
465 self,
466 iter: impl HummockIterator<Direction = Forward>,
467 compaction_catalog_agent_ref: CompactionCatalogAgentRef,
468 ) -> HummockResult<CompactOutput> {
469 let dummy_compaction_filter = DummyCompactionFilter {};
470 let (ssts, table_stats_map) = self
471 .compactor
472 .compact_key_range(
473 iter,
474 dummy_compaction_filter,
475 compaction_catalog_agent_ref,
476 None,
477 None,
478 None,
479 )
480 .await?;
481 Ok((self.split_index, ssts, table_stats_map))
482 }
483}
484
485#[cfg(test)]
486mod tests {
487 use std::collections::HashSet;
488
489 use bytes::Bytes;
490 use risingwave_common::catalog::TableId;
491 use risingwave_common::hash::VirtualNode;
492 use risingwave_common::util::epoch::test_epoch;
493 use risingwave_hummock_sdk::key::{TableKey, prefix_slice_with_vnode};
494
495 use crate::hummock::compactor::shared_buffer_compact::generate_splits;
496 use crate::hummock::shared_buffer::shared_buffer_batch::SharedBufferValue;
497 use crate::mem_table::ImmutableMemtable;
498 use crate::opts::StorageOpts;
499
500 fn generate_key(key: &str) -> TableKey<Bytes> {
501 TableKey(prefix_slice_with_vnode(
502 VirtualNode::from_index(1),
503 key.as_bytes(),
504 ))
505 }
506
507 #[tokio::test]
508 async fn test_generate_splits_in_order() {
509 let imm1 = ImmutableMemtable::build_shared_buffer_batch_for_test(
510 test_epoch(3),
511 0,
512 vec![(
513 generate_key("dddd"),
514 SharedBufferValue::Insert(Bytes::from_static(b"v3")),
515 )],
516 1024 * 1024,
517 TableId::new(1),
518 );
519 let imm2 = ImmutableMemtable::build_shared_buffer_batch_for_test(
520 test_epoch(3),
521 0,
522 vec![(
523 generate_key("abb"),
524 SharedBufferValue::Insert(Bytes::from_static(b"v3")),
525 )],
526 (1024 + 256) * 1024,
527 TableId::new(1),
528 );
529
530 let imm3 = ImmutableMemtable::build_shared_buffer_batch_for_test(
531 test_epoch(2),
532 0,
533 vec![(
534 generate_key("abc"),
535 SharedBufferValue::Insert(Bytes::from_static(b"v2")),
536 )],
537 (1024 + 512) * 1024,
538 TableId::new(1),
539 );
540 let imm4 = ImmutableMemtable::build_shared_buffer_batch_for_test(
541 test_epoch(3),
542 0,
543 vec![(
544 generate_key("aaa"),
545 SharedBufferValue::Insert(Bytes::from_static(b"v3")),
546 )],
547 (1024 + 512) * 1024,
548 TableId::new(1),
549 );
550
551 let imm5 = ImmutableMemtable::build_shared_buffer_batch_for_test(
552 test_epoch(3),
553 0,
554 vec![(
555 generate_key("aaa"),
556 SharedBufferValue::Insert(Bytes::from_static(b"v3")),
557 )],
558 (1024 + 256) * 1024,
559 TableId::new(2),
560 );
561
562 let storage_opts = StorageOpts {
563 share_buffers_sync_parallelism: 3,
564 parallel_compact_size_mb: 1,
565 sstable_size_mb: 1,
566 ..Default::default()
567 };
568 let payload = vec![imm1, imm2, imm3, imm4, imm5];
569 let (splits, _sstable_capacity, vnodes, _) = generate_splits(
570 &payload,
571 &HashSet::from_iter([1.into(), 2.into()]),
572 &storage_opts,
573 );
574 assert_eq!(
575 splits.len(),
576 storage_opts.share_buffers_sync_parallelism as usize
577 );
578 assert!(vnodes.is_empty());
579
580 for i in 1..splits.len() {
582 assert_eq!(splits[i].left, splits[i - 1].right);
583 assert!(splits[i].left > splits[i - 1].left);
584 assert!(splits[i].right.is_empty() || splits[i].left < splits[i].right);
585 }
586 }
587
588 #[tokio::test]
589 async fn test_generate_splits_no_duplicate_keys() {
590 let imm1 = ImmutableMemtable::build_shared_buffer_batch_for_test(
593 test_epoch(1),
594 0,
595 vec![(
596 generate_key("zzz"), SharedBufferValue::Insert(Bytes::from_static(b"v1")),
598 )],
599 2 * 1024 * 1024, TableId::new(1),
601 );
602
603 let imm2 = ImmutableMemtable::build_shared_buffer_batch_for_test(
604 test_epoch(1),
605 0,
606 vec![(
607 generate_key("aaa"), SharedBufferValue::Insert(Bytes::from_static(b"v1")),
609 )],
610 2 * 1024 * 1024, TableId::new(1),
612 );
613
614 let imm3 = ImmutableMemtable::build_shared_buffer_batch_for_test(
615 test_epoch(1),
616 0,
617 vec![(
618 generate_key("mmm"), SharedBufferValue::Insert(Bytes::from_static(b"v1")),
620 )],
621 2 * 1024 * 1024, TableId::new(1),
623 );
624
625 let storage_opts = StorageOpts {
626 share_buffers_sync_parallelism: 3, parallel_compact_size_mb: 2, sstable_size_mb: 1, ..Default::default()
630 };
631
632 let payload = vec![imm1, imm2, imm3];
634 let (splits, _sstable_capacity, _vnodes, _) =
635 generate_splits(&payload, &HashSet::from_iter([1.into()]), &storage_opts);
636
637 assert!(
639 splits.len() > 1,
640 "Expected multiple splits, got {}",
641 splits.len()
642 );
643
644 for i in 0..splits.len() {
646 for j in (i + 1)..splits.len() {
647 let split_i = &splits[i];
648 let split_j = &splits[j];
649
650 if !split_i.right.is_empty() && !split_j.left.is_empty() {
652 assert!(
653 split_i.right <= split_j.left || split_j.right <= split_i.left,
654 "Split {} and {} overlap: [{:?}, {:?}) vs [{:?}, {:?})",
655 i,
656 j,
657 split_i.left,
658 split_i.right,
659 split_j.left,
660 split_j.right
661 );
662 }
663 }
664 }
665
666 for i in 1..splits.len() {
668 if !splits[i - 1].right.is_empty() && !splits[i].left.is_empty() {
669 assert!(
670 splits[i - 1].right <= splits[i].left,
671 "Splits are not in sorted order at index {}: {:?} > {:?}",
672 i,
673 splits[i - 1].right,
674 splits[i].left
675 );
676 }
677 }
678 }
679}