သိထားသင့်တဲ့ Database Design တွေ

application တွေက read-heavy (read intensive) နဲ့ write-heavy (write intensive) ဆိုပြီး ၂ မျိုးရှိတယ်။ Social Media app တွေက ယေဘုယျအားဖြင့်တော့ write ထက် read အဆပေါင်းများစွာ ပိုများတဲ့ software မျိုးတွေဖြစ်တယ်။ ဘာလို့ယေဘုယျအားဖြင့်လို့ ပြောလဲ ဘာလို့တထစ်ချလို့ မပြောနိုင်ရတာလဲဆိုတော့ application ရဲ့ nature ကဒီလိုရှိသည့်တိုင် application developer တွေရဲ့ implementation ကစကားပြောသေးလို့ပါပဲ။ တဖက်မှာ ETL pipeline တွေ၊ Data ingestion နဲ့ Financial system တွေက ယေဘုယျအားဖြင့် read ထက် write ဖက်ကိုပိုယိမ်းကြတယ်။ (ETL pipeline ဆိုတာ OLTP database ကနေ data warehouse (OLAP) ဆီကို data တွေပို့တဲ့ pipeline ကိုဆိုလိုတယ်။ pipeline တလျှောက်မှာ Extract (OLTP ကနေ data ထုတ်ယူ)၊ Transform (analytics အတွက် ပိုအဆင်ပြေစေမယ့် schema format ကိုပြောင်း)၊ Load (OLAP ကို data ထည့်) စတဲ့အလုပ်တွေလုပ်တယ်။)

တကယ်လို့ ကျွန်တော်တို့ရဲ့ application မှာ live stream feature ပါမယ်။ user တွေက stream အောက်မှာ comment တွေပိုးစိုးပက်စက် ရေးကြတယ်။ အဲဒီ comment တွေက 3 ရက်ကျော်သွားရင် ပြန်ဖတ်ဖို့ မလိုတော့ဘူး ဆိုပါတော့။ အဲလိုဆိုရင် ကျွန်တော်တို့ စဥ်းစားသင့်တဲ့ design တခုက throughput ကောင်းတဲ့ write-optimized database နဲ့ latency နည်းတဲ့ fan-out ပုံစံ pub/sub မျိုးပဲ။ ဒီတော့ read-optimized ဒါမှမဟုတ် write-optimized ဖြစ်တဲ့ database design နဲ့ engine တွေကဘယ်လိုမျိုးလဲ နားလည်ထားသင့်ပြီ။

Disk ပေါ်ရေးလိုက်တဲ့ data တွေနဲ့ပတ်သက်ပြီး အရေးကြီးတဲ့တချက်က ဘယ်နားဘာ data ရှိတယ်ဆိုတဲ့ metadata တွေကိုသာ မှတ်မထားဘူးဆိုရင် data ပြန်ဖတ်ချင်တဲ့အခါ သွားရှာရမယ့်နေရာက area အကြီးကြီး ဖြစ်နေလိမ့်မယ်။ ဒီတော့ ရေးလိုက်တဲ့ data တွေနဲ့ပတ်သက်ပြီး metadata တွေပါ လိုက်ဆောက်ရတယ်။ အဲဒါကို index လုပ်တယ်လို့ခေါ်တယ်။

လွယ်ကူတဲ့ index လုပ်နည်းတခုက ရေးလိုက်တဲ့ data တွေကနေ primary key (ID) တခုဆွဲထုတ်ပြီး primary key နဲ့ data ကို key value အတွဲ ဒါမှမဟုတ် primary key နဲ့ disk ပေါ်မှာ အဲဒီ data ရှိတဲ့ pointer နေရာကို key value အတွဲအဖြစ် သိမ်းလိုက်တာပဲ။ data structure အနေနဲ့ပြောရရင် hash map ပေါ့။ ဒါပေမယ့် အဲလိုလုပ်ရင် ပြဿနာတခုရှိတာက ရှိရှိသမျှ primary key အကုန်လုံးက RAM ပေါ်တင်ထားလို့ ဆံ့မှဖြစ်မယ်။ RAM ဟာ disk နဲ့စာရင် စျေးကြီးတာတကြောင်း၊ durable မဖြစ်တာကတကြောင်း ဒါ approach ကသိပ်ရွေးချယ်လို့ကောင်းတဲ့ option တခုမဟုတ်ခဲ့ဘူး။

ဒီတော့ ဒီ limitation ကိုဖြေရှင်းဖို့နည်းတခုက data ကိုတနည်းနည်းနဲ့ sort ထားပြီး key တချို့ကိုပဲ memory ပေါ်တင်ထားမယ်ဆိုရင် ကိုယ်သွားရှာရမယ့် ဧရိယာကို ကျဥ်းချပစ်လို့ရတယ်။ ဒါပေမယ့် အဲဒီလိုလုပ်နိုင်ဖို့ဆိုရင် data reference ကို sort ထားတာပဲဖြစ်ဖြစ် တကယ့် concrete data ကို sort ထားတာပဲဖြစ်ဖြစ် သိမ်းထားတဲ့ data တွေက sorted ဖြစ်မှရမယ်။ reference ကို sort ထားတယ်ဆိုတာက record တခုချင်းစီက leaf page တွေမှာ order အစဥ်လိုက် မရှိနိုင်သည့်တိုင် parent page တွေမှာ အဲဒီ reference တွေကို range အလိုက် sort ထားနိုင်မှ key တခုကို ဘယ် page မှာသွားရှာရမလဲသိမယ်။ concrete data ကိုပါ sort လိုက်ရင်တော့ file ပေါ်မှာ binary search ပုံစံ start နဲ့ end range နှစ်ခုသတ်မှတ်ပြီး အဲဒီ data ကို တိုက်ရိုက်သွားရှာလို့ရမယ်ပေါ့။

ဒါပေမယ့် ဒီ indexing သဘောကိုပဲ database အုပ်စု ၂ ခုက မတူညီတဲ့ ပုံစံတွေနဲ့ implement လုပ်ကြတယ်။ ပထမတစုက range တခုထဲမှာရှိတဲ့ data တွေကို page တွေအဖြစ် ရေးတယ်။ အဲဒီ page တွေကို leaf page လို့ခေါ်တယ်။ leaf page တွေရဲ့ reference ကို parent page တွေက range အလိုက် ​ပြန်သိမ်းထားတယ်။ parent တခုမှာ child တွေအများကြီး ရှိနိုင်မယ်။ ဒီ ranged reference ကိုကိုင်ထားတဲ့ child တွေကိုလည်း range အလိုက် sort ထားတယ်ပေါ့။ ရှင်းရှင်းပြောရရင် B-Tree structure ပဲ။

နောက်တမျိုးက data တွေကို range အလိုက် သိမ်းမနေဘူး။ file တွေခွဲပြီး ledger စာအုပ်ပုံစံ append လုပ်ရေးသွားတယ်။ log-structured ပေါ့။ file တခုချင်းစီထဲမှာတော့ data တွေကို key အလိုက် sort ထားတယ်။ ဖိုင်တခုချင်းစီရဲ့ key တချို့ကိုလည်း သူတို့ရဲ့ byte offset တွေကို hash map ထဲမှာ cache ထားတယ်။ file ထဲမှာ key တွေ sorted ဖြစ်နေအောင် ဘယ်လိုလုပ်သလဲဆိုရင် file အဖြစ် disk ပေါ်မရေးခင် data တွေကို Red Black Tree နဲ့အရင် memory ပေါ် buffer ထားတယ်။ Tree ပြည့်လာပြီဆိုတော့မှ disk ပေါ်ကို ချရေးလိုက်တာ။

disk layer ကို data ရေးတဲ့အခါမှာလည်း update တွေကို in-place ပြင်ရေးတာနဲ့ append ဆက်ရေးတာနဲ့ဆိုပြီး philosophy 2 မျိုးရှိတယ်။ storage တွေက data ရေးရင် physical level မှာအသေးဆုံးယူနစ်ဖြစ်တဲ့ block တွေအနေနဲ့ ရေးရတာမို့လို့ in-place ပြင်ရင် block လိုက်ကြီး အသစ်ရေးရစေတယ်။ ဒီတော့ ကိုယ်တကယ်ပြင်ချင်တဲ့ data ကနည်းနည်းလေးဆိုရင်တောင်မှ block တခုစာ overhead ရှိမယ်။ ဒီရဲ့ပြဿနာက Write Amplification လို့ခေါ်တဲ့ WA ပေါ့။ ကိုယ်တကယ်ရေးချင်တာက 1 kb လောက်ပေမယ့် တကယ်ရေးလိုက်ရတာက 4 kb ဆိုတာမျိုး။ storage လည်းပိုကုန်သလို အချိန်လည်း ပိုကြာတယ်။ တဖက်မှာ append လုပ်တာကတော့ ပြင်စရာရှိရင် နောက်ကပဲ record အသစ်တခုအနေနဲ့ ဆက်ရေးသွားတယ်ပေါ့။ ဒီပုံစံက write တွေကို HDD ပေါ်မှာတောင် အတော်လေး မြန်ဆန်စေတယ်။

data ကို referenced page တွေအဖြစ် range အလိုက်သိမ်းတဲ့ B-Tree database တွေရဲ့ သဘာဝက in-place update ကိုသုံးရတယ်။ ဘာလို့လဲဆိုတော့ ranged ကိုး။ append ရေးရင် range guarantee ပျက်သွားမှာ။ အဲဒီတော့ in-place သုံးရတဲ့အတွက် B-Tree database တွေက write နှေးတယ်။ ဒါပေမယ့် read ရင်တော့ ဒက်ကနဲပဲ။ reference တွေနဲ့ root ကနေ leaf ကို အဆင့်ဆင့်လိုက်ပြီး ကိုယ်လိုချင်တဲ့ data ကိုတန်းရှာနိုင်တယ်။ ဒါက theory အရပေါ့။ လက်တွေ့မှာတော့ write ကိုအတိုင်းအတာတခုထိ optimized ဖြစ်အောင် Copy On Write သုံးတဲ့ မူကွဲတွေရှိတယ်။

Copy On Write (CoW) ဆိုတာက ကိုယ်ပြောင်းချင်တဲ့ data ကို in-place modification လုပ်မယ့်အစား ပြောင်းဖို့မလိုအပ်တဲ့ data တွေကို ဒီအတိုင်းထား၊ ပြောင်းရမယ့် data ကိုပဲ တခြားတနေရာမှာ အသစ်ရေးလိုက်တာမျိုးပဲ။ ဒါကတနည်း log-appending သဘောဆန်တဲ့အတွက် Write Amplification နည်းမယ်။ ဒါပေမယ့် အဓိက performance gain ကဒီ WA နည်းမယ်ဆိုတဲ့ အချက်ကနေ လာတာမဟုတ်ဘူး။ CoW ဒီဇိုင်းကို သုံးတဲ့အခါ B-Tree မှာ ကိုယ်ပြင်လိုက်တဲ့ page (node) ရဲ့ parent reference တွေကို လိုက်ပြင်ဖို့လိုတယ်။ ဒါပေမယ့် Tree height ကို သုံးလေးဆင့်ထက် မပိုအောင် branching factor ကိုမြင့်မြင့်ထားနိုင်ရင် updated ဖြစ်သွားတဲ့ reference တွေရဲ့ node path ကိုလိုက်ချိန်းရမှာ သိပ်မများဘူး။ ဒီတော့ B-Tree အဟောင်းကို copy ချန်ထားပြီး လိုအပ်တဲ့ node အသစ်တွေကို overhead နည်းနည်းနဲ့ ဆောက်ထားလိုက်နိုင်တယ်။

ဒီတော့ ACID သဘောအရဆိုရင် ဒီအချက်က snapshot isolation ကိုဘာ cost မှများများစားစား ထပ်မရှိပဲ free ရစေတယ်။ ဆိုပါတော့ database backup လုပ်တဲ့အခါမှာဖြစ်ဖြစ် transaction တွေမှာဖြစ်ဖြစ် row တခုချင်းစီရဲ့ xmin (creation) နဲ့ xmax (deletion) တွေ၊ commit status တွေကို လိုက်တိုက်ကြည့်ပြီး visible read ​ဖြစ်မဖြစ် ဆုံးဖြတ်နေဖို့ မလိုတော့ဘူး။ သက်ဆိုင်ရာ B-Tree အဟောင်းအတိုင်း traverse လုပ်ချသွားရုံပဲ။ ACID အကြောင်းကိုတော့ နောက်မှသပ်သပ် ချဲ့ပြောမယ်။

နောက်တချက်က B-Tree database တွေမှာ range query တွေပိုလွယ်အောင် leaf page တွေကို နီးနီးကပ်ကပ် ထားနိုင်ဖို့လုပ်ရတယ်။ နောက်ပြီး ကပ်ရက် range ရဲ့ reference တွေကို parent node ဆီပြန်တက်မကြည့်ရအောင် leaf page တွေမှာပါ ရှေ့နဲ့နောက် leaf page တွေရဲ့ reference ကိုကိုင်ခိုင်းထားတာမျိုးတွေ လုပ်ရတယ်။ ဒါပေမယ့် read နဲ့ write ကဆန့်ကျင်ဖက် trade off တွေဖြစ်တဲ့အတွက် read ပိုလွယ်သွားအောင်လုပ်တိုင်း တဖက်မှာ write လုပ်တဲ့အခါ အာရုံစိုက်ပြီး လိုက်ပြင်စရာတွေ ပိုများလာမှာကိုတော့ သတိထားရမှာပေါ့။

အခြားတဖက်မှာ data ကို file တွေအဖြစ်ခွဲပြီး သိမ်းတဲ့ database တွေမှာကျတော့ in-place ပြင်ဖို့ မလိုအပ်ဘူး။ update စရာရှိရင် နောက်ကနေ log (record) အသစ်တခုအဖြစ် ဆက်ရေးသွားရုံပဲ။ client ဆီက ရောက်လာတဲ့ data တွေကို အတိုင်းအတာတခုထိ memory ပေါ်မှာစုထားပြီး size limit ဒါမှမဟုတ် time duration တခုရောက်မှ file အသစ် ရေးလိုက်လို့ရတယ်။ အဲတော့ disk ကိုမစောင့်ရတဲ့အတွက်ရော၊ ရှေ့ log ကို random access သွားမရှာရတဲ့အတွက်ရော LSM-Tree database တွေမှာ write ကမတရား smooth ဖြစ်တယ်။

ဒါပေမယ့် read ရင်တော့ data ကဘယ် file ထဲရှိလို့ရှိမှန်းမသိပဲ အကုန်လိုက်ရှာရတဲ့အတွက် ခက်တယ်။ အဲတော့ read ကိုနည်းနည်းဖြစ်ဖြစ် ပိုလွယ်ကူအောင် disk ပေါ်ရေးလိုက်တဲ့ file တွေကို merge ပြီး file အရေအတွက် လျှော့ချဖို့ compaction လုပ်တာ၊ disk ကနေ file တခုကို မတောင်းခင် key တခု အဲ file ထဲရှိနိုင်ချေ အရင် check နိုင်အောင် Bloom Filter ထားတာ၊ နောက်​ပြီး server restart လုပ်တဲ့အခါ file တခုချင်းစီရဲ့ hash map တွေကို အစကနေ ပြန်မဆောက်ရအောင် hash map ကိုပါ disk ပေါ်ရေးထားတာ စသဖြင့် လုပ်ကြရတယ်။

ဒါပေမယ့် ဘယ် design ကိုသုံးသုံး server crash သွားရင်ဆိုတဲ့ အခြေအနေမျိုးတွေကို ထည့်စဥ်းစားထားဖို့ လိုလိမ့်မယ်။ ဥပမာ B-Tree database တွေမှာ leaf page တွေကိုပြင်ပြီး parent node တွေမှာ reference update မလုပ်ရသေးခင် server ကျသွားရင် data corrputed ဖြစ်နိုင်တယ်။ LSM-Tree database တွေမှာလည်း file အဖြစ် disk ပေါ်မရေးရသေးခင် server ကျသွားရင် memory ပေါ်စုထားတဲ့ batch ထဲက data ပျောက်သွားနိုင်တယ်။ အဲဒီတော့ နှစ်ခုက motivation မတူပေမယ့် Write Ahead Log လို့ခေါ်တဲ့ WAL မဖြစ်မနေ ထားကြရတယ်။ client က data ရေးဖို့ request ပို့လာရင် WAL ကိုအရင်ရေးပြီးမှ design အလိုက် ကျန်တဲ့လုပ်စရာရှိတာကို ဆက်လုပ်ကြတာမျိုးပေါ့။

B-Tree ကို Mysql, Postgresql, Mongodb တွေရဲ့ database engine တွေမှာ သုံးကြတယ်။ data ကိုဘယ်မှာရှာတွေ့နိုင်မလဲဆိုတာကို အာမခံတဲ့ ranged reference တွေ ဆောက်တယ်။ ဒီ​တော့ read ကောင်းတယ်။ ဒါပေမယ့် range မပျက်စေဖို့ in-place update လုပ်ရတဲ့အတွက် write နှေးလိမ့်မယ်။ read intensive ဖြစ်မယ့် application တွေက ဒါမျိုး database engine မျိုးနဲ့ လိုက်ဖက်တယ်။ တဖက်မှာလည်း HBase, Cassandra စတဲ့ database တွေက LSM-Tree ကိုသုံးကြတယ်။ data တွေကို batch လိုက်စုပြီး file တွေအဖြစ် sequential write လုပ်ပြီး write optimized ဖြစ်ဖို့ လုပ်ထားတယ်။ read မှာတော့ နှေးကောင်းနှေးမယ်။ throughput ကောင်းဖို့လိုတဲ့ app မျိုးဆိုရင် ဒီလို database engine မျိုးက သင့်တော်တယ်။