LSM Compaction: Write Amplification Explorer

%23%20%2F%2F%2F%20script%0A%23%20requires-python%20%3D%20%22%3E%3D3.11%22%0A%23%20dependencies%20%3D%20%5B%0A%23%20%20%20%20%20%22marimo%22%2C%0A%23%20%20%20%20%20%22numpy%3D%3D2.4.3%22%2C%0A%23%20%20%20%20%20%22matplotlib%3D%3D3.10.3%22%2C%0A%23%20%5D%0A%23%20%2F%2F%2F%0A%0Aimport%20marimo%0A%0A__generated_with%20%3D%20%220.22.5%22%0Aapp%20%3D%20marimo.App(%0A%20%20%20%20width%3D%22medium%22%2C%0A%20%20%20%20app_title%3D%22LSM%20Compaction%3A%20Write%20Amplification%20Explorer%22%2C%0A)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_()%3A%0A%20%20%20%20import%20marimo%20as%20mo%0A%20%20%20%20import%20textwrap%20as%20_tw%0A%0A%20%20%20%20import%20matplotlib.pyplot%20as%20plt%0A%20%20%20%20import%20numpy%20as%20np%0A%0A%20%20%20%20def%20dedent_md(s)%3A%0A%20%20%20%20%20%20%20%20return%20mo.md(_tw.dedent(s))%0A%0A%20%20%20%20def%20centered_fig(fig)%3A%0A%20%20%20%20%20%20%20%20html%20%3D%20mo.as_html(fig).text%0A%20%20%20%20%20%20%20%20return%20mo.Html(%0A%20%20%20%20%20%20%20%20%20%20%20%20f'%3Cdiv%20style%3D%22display%3Aflex%3Bjustify-content%3Acenter%3Bmargin-top%3A1.5rem%22%3E'%0A%20%20%20%20%20%20%20%20%20%20%20%20f%22%7Bhtml%7D%3C%2Fdiv%3E%22%0A%20%20%20%20%20%20%20%20)%0A%0A%20%20%20%20return%20centered_fig%2C%20dedent_md%2C%20mo%2C%20np%2C%20plt%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(dedent_md)%3A%0A%20%20%20%20dedent_md(r%22%22%22%0A%20%20%20%20%20%20%20%20%23%20LSM%20Compaction%3A%20Write%20Amplification%20Explorer%0A%0A%20%20%20%20%20%20%20%20This%20notebook%20is%20a%20companion%20to%20the%20%5B%5BLSM%20Compaction%5D%5D%20note.%20The%0A%20%20%20%20%20%20%20%20note%20explains%20how%20LSM%20trees%20work%2C%20how%20compaction%20rewrites%20data%2C%0A%20%20%20%20%20%20%20%20and%20why%20write%20amplification%20is%20~T%20per%20level.%20This%20notebook%20lets%0A%20%20%20%20%20%20%20%20you%20**explore%20the%20tradeoff%20interactively**.%0A%0A%20%20%20%20%20%20%20%20Use%20the%20sliders%20below%20to%20change%20the%20number%20of%20levels%20and%20the%20size%0A%20%20%20%20%20%20%20%20ratio%2C%20and%20see%20how%20write%20amplification%2C%20level%20capacities%2C%20and%20the%0A%20%20%20%20%20%20%20%20comparison%20with%20other%20configurations%20change%20in%20real%20time.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20levels_slider%20%3D%20mo.ui.slider(%0A%20%20%20%20%20%20%20%202%2C%206%2C%20value%3D3%2C%20step%3D1%2C%0A%20%20%20%20%20%20%20%20label%3D%22Number%20of%20levels%20(L)%22%2C%20show_value%3DTrue%2C%0A%20%20%20%20)%0A%20%20%20%20ratio_slider%20%3D%20mo.ui.slider(%0A%20%20%20%20%20%20%20%202%2C%2010%2C%20value%3D10%2C%20step%3D1%2C%0A%20%20%20%20%20%20%20%20label%3D%22Size%20ratio%20(T)%22%2C%20show_value%3DTrue%2C%0A%20%20%20%20)%0A%20%20%20%20mo.hstack(%5Blevels_slider%2C%20ratio_slider%5D%2C%20gap%3D2)%0A%20%20%20%20return%20levels_slider%2C%20ratio_slider%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(centered_fig%2C%20dedent_md%2C%20levels_slider%2C%20mo%2C%20np%2C%20plt%2C%20ratio_slider)%3A%0A%20%20%20%20_L%20%3D%20levels_slider.value%0A%20%20%20%20_T%20%3D%20ratio_slider.value%0A%20%20%20%20_write_amp%20%3D%20_T%20*%20(_L%20-%201)%0A%0A%20%20%20%20_capacities%20%3D%20%5B_T**i%20for%20i%20in%20range(_L)%5D%0A%20%20%20%20_max_cap%20%3D%20_capacities%5B-1%5D%0A%0A%20%20%20%20_fig%2C%20(_ax_pyramid%2C%20_ax_bar)%20%3D%20plt.subplots(%0A%20%20%20%20%20%20%20%201%2C%202%2C%20figsize%3D(12%2C%20max(4%2C%20_L%20*%201.1))%2C%0A%20%20%20%20%20%20%20%20gridspec_kw%3D%7B%22width_ratios%22%3A%20%5B3%2C%202%5D%7D%2C%0A%20%20%20%20)%0A%20%20%20%20_fig.patch.set_facecolor(%22white%22)%0A%20%20%20%20for%20_a%20in%20(_ax_pyramid%2C%20_ax_bar)%3A%0A%20%20%20%20%20%20%20%20_a.set_facecolor(%22white%22)%0A%0A%20%20%20%20_colors%20%3D%20%5B%22%23E57373%22%2C%20%22%23FFA726%22%2C%20%22%2366BB6A%22%2C%20%22%235C6BC0%22%2C%20%22%23BA68C8%22%2C%20%22%234DD0E1%22%5D%0A%0A%20%20%20%20%23%20Left%3A%20pyramid%20of%20levels%0A%20%20%20%20for%20_i%20in%20range(_L)%3A%0A%20%20%20%20%20%20%20%20_cap%20%3D%20_capacities%5B_i%5D%0A%20%20%20%20%20%20%20%20_w%20%3D%20max(0.5%2C%208%20*%20(_cap%20%2F%20_max_cap))%0A%20%20%20%20%20%20%20%20_x%20%3D%20(8%20-%20_w)%20%2F%202%0A%20%20%20%20%20%20%20%20_y%20%3D%20(_L%20-%201%20-%20_i)%20*%201.3%0A%0A%20%20%20%20%20%20%20%20_n_parts%20%3D%20min(max(1%2C%20_T%20if%20_i%20%3D%3D%200%20else%20_T%20%2F%2F%202)%2C%208)%0A%20%20%20%20%20%20%20%20_part_w%20%3D%20_w%20%2F%20(_n_parts%20%2B%200.5)%0A%20%20%20%20%20%20%20%20for%20_j%20in%20range(_n_parts)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20_px%20%3D%20_x%20%2B%20_j%20*%20(_w%20%2F%20_n_parts)%20%2B%20(_w%20%2F%20_n_parts%20-%20_part_w)%20%2F%202%0A%20%20%20%20%20%20%20%20%20%20%20%20_ax_pyramid.add_patch(plt.Rectangle(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20(_px%2C%20_y)%2C%20_part_w%2C%200.9%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20facecolor%3D_colors%5B_i%20%25%20len(_colors)%5D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20edgecolor%3D%22%23333%22%2C%20linewidth%3D1.0%2C%20alpha%3D0.8%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20))%0A%0A%20%20%20%20%20%20%20%20_ax_pyramid.text(-0.5%2C%20_y%20%2B%200.45%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20f%22L%7B_i%7D%5Cn%7B_cap%7D%5Cu00d7%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20ha%3D%22right%22%2C%20va%3D%22center%22%2C%20fontsize%3D10%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20fontweight%3D%22bold%22%2C%20color%3D%22%23333%22)%0A%0A%20%20%20%20%20%20%20%20%23%20Per-level%20write%20amp%20contribution%0A%20%20%20%20%20%20%20%20if%20_i%20%3E%200%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20_ax_pyramid.text(8.5%2C%20_y%20%2B%200.45%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20f%22%2B%7B_T%7D%5Cu00d7%20rewrites%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20ha%3D%22left%22%2C%20va%3D%22center%22%2C%20fontsize%3D9%2C%20color%3D%22%23C62828%22)%0A%0A%20%20%20%20%20%20%20%20if%20_i%20%3C%20_L%20-%201%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20_ax_pyramid.annotate(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22%22%2C%20xy%3D(4%2C%20_y%20%2B%200.95)%2C%20xytext%3D(4%2C%20_y%20%2B%201.25)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20arrowprops%3Ddict(arrowstyle%3D%22-%3E%22%2C%20color%3D%22%23333%22%2C%20lw%3D1.2)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20)%0A%0A%20%20%20%20_ax_pyramid.set_xlim(-2.5%2C%2011)%0A%20%20%20%20_ax_pyramid.set_ylim(-0.5%2C%20_L%20*%201.3%20%2B%200.3)%0A%20%20%20%20_ax_pyramid.axis(%22off%22)%0A%20%20%20%20_ax_pyramid.set_title(%0A%20%20%20%20%20%20%20%20f%22%7B_L%7D%20levels%20%5Cu00d7%20%7B_T%7D%5Cu00d7%20ratio%20%5Cu2192%20~%7B_write_amp%7D%5Cu00d7%20write%20amp%22%2C%0A%20%20%20%20%20%20%20%20fontsize%3D11%2C%20fontweight%3D%22bold%22%2C%20color%3D%22%23333%22%2C%20pad%3D8%2C%0A%20%20%20%20)%0A%0A%20%20%20%20%23%20Right%3A%20bar%20chart%20comparing%20configurations%0A%20%20%20%20_configs%20%3D%20%5B%0A%20%20%20%20%20%20%20%20(2%2C%2010)%2C%20(3%2C%2010)%2C%20(4%2C%2010)%2C%20(5%2C%2010)%2C%0A%20%20%20%20%20%20%20%20(3%2C%204)%2C%20(3%2C%202)%2C%0A%20%20%20%20%5D%0A%20%20%20%20_bar_labels%20%3D%20%5B%5D%0A%20%20%20%20_bar_values%20%3D%20%5B%5D%0A%20%20%20%20_bar_colors%20%3D%20%5B%5D%0A%20%20%20%20for%20_ll%2C%20_tt%20in%20_configs%3A%0A%20%20%20%20%20%20%20%20_bar_labels.append(f%22L%3D%7B_ll%7D%5CnT%3D%7B_tt%7D%22)%0A%20%20%20%20%20%20%20%20_bar_values.append(_tt%20*%20(_ll%20-%201))%0A%20%20%20%20%20%20%20%20_bar_colors.append(%22%23C62828%22%20if%20(_ll%20%3D%3D%20_L%20and%20_tt%20%3D%3D%20_T)%20else%20%22%2390A4AE%22)%0A%0A%20%20%20%20_y_pos%20%3D%20np.arange(len(_configs))%0A%20%20%20%20_ax_bar.barh(_y_pos%2C%20_bar_values%2C%20color%3D_bar_colors%2C%20edgecolor%3D%22%23333%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20linewidth%3D0.5%2C%20height%3D0.6)%0A%20%20%20%20_ax_bar.set_yticks(_y_pos)%0A%20%20%20%20_ax_bar.set_yticklabels(_bar_labels%2C%20fontsize%3D9)%0A%20%20%20%20_ax_bar.set_xlabel(%22Write%20amplification%20(%5Cu00d7)%22%2C%20fontsize%3D10)%0A%20%20%20%20_ax_bar.set_title(%22Comparison%22%2C%20fontsize%3D11%2C%20fontweight%3D%22bold%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20color%3D%22%23333%22%2C%20pad%3D8)%0A%20%20%20%20for%20_spine%20in%20_ax_bar.spines.values()%3A%0A%20%20%20%20%20%20%20%20_spine.set_color(%22%23ccc%22)%0A%0A%20%20%20%20%23%20Label%20bars%0A%20%20%20%20for%20_idx%2C%20_val%20in%20enumerate(_bar_values)%3A%0A%20%20%20%20%20%20%20%20_ax_bar.text(_val%20%2B%200.5%2C%20_idx%2C%20f%22%7B_val%7D%5Cu00d7%22%2C%20va%3D%22center%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20fontsize%3D9%2C%20color%3D%22%23333%22)%0A%0A%20%20%20%20_ax_bar.set_xlim(0%2C%20max(_bar_values)%20%2B%208)%0A%20%20%20%20plt.tight_layout()%0A%0A%20%20%20%20mo.vstack(%5B%0A%20%20%20%20%20%20%20%20centered_fig(_fig)%2C%0A%20%20%20%20%20%20%20%20dedent_md(f%22%22%22%0A%20%20%20%20%20%20%20%20%20%20%20%20**Current%3A%20%7B_L%7D%20levels%20%5Cu00d7%20%7B_T%7D%5Cu00d7%20ratio%20%3D%20%7B_write_amp%7D%5Cu00d7%20write%20amplification.**%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20Each%20level%20transition%20contributes%20%7B_T%7D%5Cu00d7%20rewrites%20(because%20L%24_%7B%7Bi%2B1%7D%7D%24%20is%0A%20%20%20%20%20%20%20%20%20%20%20%20%7B_T%7D%5Cu00d7%20larger%20than%20L%24_i%24%2C%20so%20merging%201%20file%20touches%20~%7B_T%7D%20files).%20With%0A%20%20%20%20%20%20%20%20%20%20%20%20%7B_L%20-%201%7D%20transitions%2C%20the%20total%20is%20%7B_T%7D%20%5Cu00d7%20%7B_L%20-%201%7D%20%3D%20**%7B_write_amp%7D%5Cu00d7**.%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20The%20bar%20chart%20shows%20how%20different%20configurations%20compare.%20Notice%20that%0A%20%20%20%20%20%20%20%20%20%20%20%20increasing%20the%20ratio%20*or*%20the%20number%20of%20levels%20increases%20write%20amp%20%E2%80%94%0A%20%20%20%20%20%20%20%20%20%20%20%20but%20the%20ratio%20has%20a%20much%20larger%20effect.%0A%20%20%20%20%20%20%20%20%22%22%22)%2C%0A%20%20%20%20%5D)%0A%20%20%20%20return%0A%0A%0Aif%20__name__%20%3D%3D%20%22__main__%22%3A%0A%20%20%20%20app.run()%0A