Upgrade to Pro — share decks privately, control downloads, hide ads and more …

Rustでon-diskなB+Treeを作ったときの細かな話

 Rustでon-diskなB+Treeを作ったときの細かな話

Rust LT Online #3 で発表したスライドです
https://rust.connpass.com/event/209279/

KOBA789

May 19, 2021
Tweet

More Decks by KOBA789

Other Decks in Programming

Transcript

  1. KOBA789 ݱࡏਐߦܗͰແ৬ ‣ 3VTUྺ͸೥͘Β͍ ‣ ී௨ʹ΢ΣϒαʔόʔΛॻ͍ͨΓ ‣ %#.4Λॻ͍ͨΓ ‣ ϒϥ΢βͰಈ͘ճ࿏$"%Λॻ͍ͨΓ

    
 8"4.λʔήοτ  ‣ ࣗ࡞ΩʔϘʔυͷ 
 ϑΝʔϜ΢ΣΞΛॻ͍ͨΓ 
 ͍ΘΏΔ૊ΈࠐΈ3VTU ͓͢͢Ίͷ࢓ࣄʹؔ͢Δ৘ใ͸ 
 ͍ͭͰ΋׻ܴ͍ͯ͠·͢ https://gihyo.jp/magazine/wdpress/archive/2021/vol122 ʲະঝ୚޿ࠂʳࡶࢽʹهࣄॻ͖·ͨ͠
  2. σΟεΫʢϑΝΠϧʣ ϊʔυ ϊʔυ ϊʔυ ϊʔυ ϊʔυ ϊʔυ ϊʔυ ϊʔυ ϊʔυ

    ϊʔυ CPU # 5SFFΛૢ࡞͍ͨ͠ σΟεΫΛ௚઀ಡΈॻ͖͢Δͷ͸஗͍͠ෆศ
  3. ϝϞϦ σΟεΫʢϑΝΠϧʣ ϊʔυ ϊʔυ ϊʔυ ϊʔυ ϊʔυ ϊʔυ ϊʔυ ϊʔυ

    ϊʔυ ϊʔυ ϊʔυ ϊʔυ ϊʔυ ϊʔυ ϊʔυ CPU
  4. ϝϞϦ σΟεΫʢϑΝΠϧʣ ϊʔυ ϊʔυ ϊʔυ ϊʔυ ϊʔυ ϊʔυ ϊʔυ ϊʔυ

    ϊʔυ ϊʔυ ϊʔυ ϊʔυ ϊʔυ ϊʔυ ϊʔυ CPU ϊʔυͷҰ෦ΛϝϞϦ΁
  5. ϝϞϦ σΟεΫʢϑΝΠϧʣ ϊʔυ ϊʔυ ϊʔυ ϊʔυ ϊʔυ ϊʔυ ϊʔυ ϊʔυ

    ϊʔυ ϊʔυ ϊʔυ ϊʔυ ϊʔυ ϊʔυ ϊʔυ CPU ಡΈॻ͖ ೖΕସ͑ όοϑΝϓʔϧϚωʔδϟ
  6. ϊʔυ ϊʔυ ϊʔυ ϊʔυ ϊʔυ ϊʔυ ϊʔυ ϊʔυ ϊʔυ ϊʔυ

    Ұ෦ͷϊʔυͷΈ͕ϝϞϦʹ͋Δ# 5SFFͱ͍͑Δ ന͍ϊʔυ͸σΟεΫʹ͔͠ͳ͍
  7. ϝϞϦ σΟεΫʢϑΝΠϧʣ ϊʔυ ϊʔυ ϊʔυ ϊʔυ ϊʔυ ϊʔυ ϊʔυ ϊʔυ

    ϊʔυ ϊʔυ ϊʔυ ϊʔυ ϊʔυ ϊʔυ ϊʔυ CPU ಡΈॻ͖ ೖΕସ͑ ͱ͜ΖͰɺ
  8. ϝϞϦ σΟεΫʢϑΝΠϧʣ ϊʔυ ϊʔυ ϊʔυ ϊʔυ ϊʔυ ϊʔυ ϊʔυ ϊʔυ

    ϊʔυ ϊʔυ ϊʔυ ϊʔυ ϊʔυ ϊʔυ ϊʔυ CPU ಡΈॻ͖ ೖΕସ͑ ϚϧνίΞΛ׆༻͍ͨ͠Ͱ͢ΑͶʁ CPU CPU CPU
  9. ϝϞϦ σΟεΫʢϑΝΠϧʣ ϊʔυ ϊʔυ ϊʔυ ϊʔυ ϊʔυ ϊʔυ ϊʔυ ϊʔυ

    ϊʔυ ϊʔυ ϊʔυ ϊʔυ ϊʔυ ϊʔυ ϊʔυ CPU ར༻தͷϊʔυΛόοϑΝ͔Β௥͍ग़ͨ͠Γ͢Δͱ͍ͨ΁Μͳ͜ͱʹ CPU CPU CPU ΛಡΈ͍ͨɻΛ௥͍ग़ͦ͏ ଴ͯίϥ ϊʔυ ར༻த
  10. ϝϞϦ σΟεΫʢϑΝΠϧʣ ϊʔυ ϊʔυ ϊʔυ ϊʔυ ϊʔυ ϊʔυ ϊʔυ ϊʔυ

    ϊʔυ ϊʔυ ϊʔυ ϊʔυ ϊʔυ ϊʔυ ϊʔυ CPU ར༻தͷϊʔυΛόοϑΝ͔Β௥͍ग़ͨ͠Γ͢Δͱ͍ͨ΁Μͳ͜ͱʹ CPU CPU CPU ΛಡΈ͍ͨɻΛ௥͍ग़ͦ͏ ଴ͯίϥ ϊʔυ ར༻த ͜ͷ΁Μͷ 
 σʔλߏ଄ɾΞϧΰϦζϜΛ 
 3VTUͰͲ͏͢Δ͔ POEJTLಛ༗ͷ೉͕͋͠͞Δ
  11. 3VTUͰ͸Ͳ͏͢Δ͔ Ҋ"SDͰอޢ w "SDʹ͸HFU@NVU NVU"SD5 ͱ͍͏ 
 ϝιου͕͋Δ w ࢀরΧ΢ϯλ͕ͷͱ͖ʹ͚ͩNVU5͕औΕΔ

    w όοϑΝϓʔϧͷʮϐϯʯͱ૬ੑ͕Αͦ͞͏ͳػೳ w ͨͩ͠Ϩγʔό͸NVU w όοϑΝϓʔϧશମΛอޢ͢Δ.VUFY͕͋ΔͷͰ 
 Մมࢀর͕औΕΔ
  12. 1US ,FZ 7BMVF ,FZ 7BMVF ,FZ 7BMVF 1US 1US OVN@TMPUT

    QPJOUFST IFBEFS CPEZ ͜ͷਤΛΑ͘ݟͯ΄͍͠
  13. 1US ,FZ 7BMVF ,FZ 7BMVF ,FZ 7BMVF 1US 1US OVN@TMPUT

    QPJOUFST IFBEFS CPEZ QPJOUFST͸CPEZΛआ༻͍ͯ͠Δ
  14. 1US ,FZ 7BMVF ,FZ 7BMVF ,FZ 7BMVF 1US 1US OVN@TMPUT

    QPJOUFST IFBEFS CPEZ QPJOUFST͸CPEZΛआ༻͍ͯ͠Δ ͭ·Γɺ,FZ7BMVFϖΞΛมߋ͢Δͱ͖ʹ͸ 
 ͍͍ͪͪQPJOUFSTΛख์͞ͳ͚Ε͹ͳΒͳ͍ ͩΔ͍ 
 ʢ͔ͨ͠ͳ͠ʣ
  15. ϊʔυ ϊʔυ ϊʔυ ϊʔυ ϊʔυ ϊʔυ ϊʔυ ϊʔυ ϊʔυ ϊʔυ

    ϩοΫ͕औΕͨΒɺ্ͷϩοΫ͸ख์ͯ͠΋Α͍ CPU CPU
  16. ϊʔυ ϊʔυ ϊʔυ ϊʔυ ϊʔυ ϊʔυ ϊʔυ ϊʔυ ϊʔυ ϊʔυ

    Լͷϊʔυ͕ᷓΕͦ͏ͳ৔߹͸ɺ্ͷϩοΫΛख์ͯ͠͸ͳΒͳ͍ 
 ʢॻ͖ࠐΈͷ৔߹ʣ CPU CPU
  17. # 5SFFͷഉଞ੍ޚ ૉ๿ʹ࣮૷ page: 
 Arc<RwLock<Page>> ro_page: 
 RwLockReadGuard<_, Page>

    next_page: 
 Arc<RwLock<Page>> ro_next_page: 
 RwLockReadGuard<_, Page> next_pageΛಈ͔͍͕ͨ͠ かといってRwLockReadGuardΛ 
 ख์͢Θ͚ʹ͸͍͔ͳ͍ ro_page͕pageΛɺ 
 ro_next_page͕next_pageΛ 
 ࢀর͍ͯ͠ΔͷͰಈ͔ͤͳ͍
  18. # 5SFFͷഉଞ੍ޚ ૉ๿ʹ࣮૷ page: 
 Arc<RwLock<Page>> ro_page: 
 RwLockReadGuard<_, Page>

    next_page: 
 Arc<RwLock<Page>> ro_next_page: 
 RwLockReadGuard<_, Page> next_pageΛಈ͔͍͕ͨ͠ かといってRwLockReadGuardΛ 
 ख์͢Θ͚ʹ͸͍͔ͳ͍ ro_page͕pageΛɺ 
 ro_next_page͕next_pageΛ 
 ࢀর͍ͯ͠ΔͷͰಈ͔ͤͳ͍ ٧Έ
  19. ࠓ೔঺հͨ͠ίʔυ͸͍͍ͩͨ(JU)VCʹ͋Δ RQ w IUUQTHJUIVCDPN,0#"RQ w ϚϧνεϨου w ίʔυ͕ͱͯ΋Ԛ͍ SFMMZ w

    IUUQTHJUIVCDPN,0#"SFMMZ w γϯάϧεϨου w 8&# %#13&447PMͷͨΊʹ 
 ॻ͖ԼΖͨ͠ w ͪΐͬͱίʔυ͕៉ྷ