Implementasi Merkle tree untuk platform hosting

Cheap, safe, efficient: Choose three

Implementasi Merkle tree untuk platform hosting

Sebagai pengingat siapa tau gue lupa, gue akan dokumentasikan apa yang sedang gue pelajari & terapkan dalam platform hosting yang sedang dikembangkan.

Membuat PoC pertama untuk si edgy sudah selesai, enggak ada magic sama sekali.

Core nya, hanya bertindak sebagai "jembatan" antara client & S3—yang mana basically S3 menyediakan static file server juga. Setiap deployment yang ada, artifak nya akan diunggah ke bucket yang ada di S3 dan endpoint akan mengarah kesitu.

Contoh:

  • key: endpoint:wwwid.edgyfn.app
  • value: 33d9be5e

Jika user mengakses https://wwwid.edgyfn.app, si edgy akan melakukan request via httputil.ReverseProxy nya Go ke S3 server, misal ke s3.faultable.dev/bucket/33d9be5e/index.html.

Key dari cache nya adalah deployment_id yang mana didapat dari nilai yang ada di key endpoint:hostname, cache invalidation terlihat "sederhana" dan juga untuk mengubah endpoint, tinggal mengarahkan ke deployment_id yang baru.

Btw, gue menggunakan pendekatan ini karena tidak menggunakan SNI (Server Name Indication) yang biasa dilakukan. Bayangkan bila gue memiliki 10 endpoint, kasarnya, ada 10 port yang harus dialokasikan untuk memproses request tersebut.

Lanjut, masalah selanjutnya ada di efisiensi file system tanpa menghilangkan fitur yang ingin gue tawarkan juga: Deployment Rollback.

Sebelumnya, gue menggunakan teknik kotor—karena untuk PoC aja—yang mana setiap artifak dari hasil build ketika membuat deployment disimpan sebagaimana ada nya.

Hasilnya, situs w3id memiliki ukuran artifak ~108M. Jika membuat deployment baru, yang disimpan di storage gue berarti ~216M dengan alasan misal bila ingin melakukan "rollback" tinggal mengarahkan (endpoint) ke versi sebelumnya aja (dari 21d9bedd balik lagi ke 33d9be5e)

Sederhana.

Berarti, jika project tersebut melakukan 10x deployment, untuk project tersebut saja sudah menghabiskan ~1.8G alias kagak efisien untuk level manapun itu khususnya orang miskin kayak gue.

Maka gue harus melakukan cara untuk bisa menyelesaikan masalah ini, dan setelah hasil riset ~5 hari, here we go.

Merkle tree, on git

Merkle tree bukanlah konsep baru, sudah di terapkan di Git, Mercurial, Cassandra, ZFS, Bitcoin, IPFS, dsb.

Sebagai bahan riset, gue ambil contoh dari Git.

Lihat bagaimana ukuran direktori dari branch master dan dua berbeda?

Harusnya, di direktori /tmp/kon tersebut berukuran ~82M karena gue memiliki berkas yes yang mana berukuran ~81M.

Tapi disitu (branch master) hanya berukuran ~448K.

Bagaimana ini bisa terjadi?

Kemana ~81M berkas yang tadi sudah dibuat?

Berdasarkan yang gue dapet, git menggunakan "virtual work tree". Mungkin tulisan ini sedikit mencerahkan.

Sedikit ber-eksplorasi, mari kita lihat struktur direktori nya plus dengan inode nya.

Disitu terlihat bahwa setiap gue melakukan checkout, inode untuk berkas yes selalu berubah. Dan ketika cek langsung di inode nya mac:

Data tersebut tidak ada. Gue gak tau teknis nya gimana, tapi gue yakin itu kerjaan git: nge-assign ke inode lain yang mengarah ke entah kemana.

Oke oke kita sedang tidak membahas Git Fundamental™, jadi mari kita skip hal diatas.

Git menyimpan "metadata" di direktori .git/objects, yang mana metadata yang disimpan tersebut menyangkut:

  • Commit
  • Tree
  • Blob

Dalam kasus gue, 3 metadata tersebut gue representasikan sebagai:

  • Commit (deployment context)
  • Tree (directory structure context)
  • Blob (content)

Misal gue melakukan commit (create new deployment), dengan hash 9e38c22.

Dari situ, gue bisa dapet tree nya berdasarkan hash tree:

Berdasarkan tree tersebut (beserta dengan "checksum" per berkas nya), kita bisa mengarahkan nya.

Sekarang kita masuk ke pembahasan merkle tree benerannya, untuk kasus gue.

Lihat disitu berkas kita memiliki hash 45b983b, berarti, blob tersebut tersimpan di objects/45/b983b...

Isi dari beras tersebut sudah di compress dengan algoritma gzip. Untuk melihat kontennya, kita bisa menggunakan metoda deflate dari zlib yang mana disini gue menggunakan bantuan Ruby, my old friend.

Disitu isinya adalah (dari kiri ke kanan):

  • Tipe (blob)
  • Byte counts (3)
  • Content (hi)

Jika kita inspeksi sedikit, ini yang kita dapat:

Mengapa ukuran nya bisa berbeda (yang satu 336,438B dan yang satu 77,090,816B)?

Karena di kompres!

Tapi karena disini gue bukan sedang membuat "the next git", jadi, mari kita skip hal-hal terkait git ini.

Merkle tree, on our my needs

Sebelumnya, disimpan "as is" aja, sekarang berarti ada beberapa hal yang perlu gue ubah.

Mari ilustrasikan dengan kasus nyata.

Pertama, gue buat project berdasarkan repository git@github.com:w3id/wwwid.org.git.

Lalu, gue buat deployment (initial). Di S3, struktur direktorinya berarti (misalnya) menjadi 0788dc8/80fc7bb yang mana:

  • 0788dc8 adalah project id
  • 80fc788 adalah deployment id

Dari situ, "builder" melakukan proses build, setiap artifak akan dibuat checksum, dari checksum tersebut akan disimpan blob & meta datanya.

Misal berkas nya hanya index.html dan css css/app.css, dengan checksum:

  • effccf7b8fd0a9eec53bd66ed2d3c0dc7f1c8b46 index.html
  • fbd8dd543fb0fe19fda3c4983a5169d25c6575c7 css/app.css

Yang berarti, direktori 0788dc8 (project id) akan berisi:

  • 80/fc788... tempat "mapping" route
  • ef/fccf7... untuk berkas index.html
  • fb/d8dd5... untuk berkas css/app.css

Kurang lebih berkas fc788... tersebut berisi:

[
  {
    "src": "/index.html",
    "dest": "ef/fccf7b8fd0a9eec53bd66ed2d3c0dc7f1c8b46",
    "content-type": "text/html",
    "hash": "effccf7b8fd0a9eec53bd66ed2d3c0dc7f1c8b46"
  },
  {
    "src": "/css/app.css",
    "dest": "fb/d8dd543fb0fe19fda3c4983a5169d25c6575c7",
    "content-type": "text/css",
    "hash": "fbd8dd543fb0fe19fda3c4983a5169d25c6575c7"
  }
]

Familiar?

Checksum diatas (hash) berguna untuk... Siapa tau berkas tersebut ada yang inject :))

Dan ya, untuk set header Etag juga.

Sekarang kita buat deployment baru, untuk deployment id terbary nya adalah 40a934e.

Dengan kasus di deployment tersebut hanya menambahkan js/app.js yang mana memiliki checksum afc6a753a0f9de0ce9044d1a01f2b97814bd780e .

Karena deployment bersifat incremental—dan tergantung "versi mana" yang dijadikan "rujukan"—jika dalam kasus ini rujukannya adalah 80fc788, berarti struktur direktori dari 0788dc8 yang tambahannya adalah:

  • 40/a934e tempat "mapping" route
  • af/c6a75 untuk berkas js/app.js

Berarti, untuk isi dari a934e... tersebut seperti ini:

[
  {
    "src": "/index.html",
    "dest": "ef/fccf7b8fd0a9eec53bd66ed2d3c0dc7f1c8b46",
    "content-type": "text/html",
    "hash": "effccf7b8fd0a9eec53bd66ed2d3c0dc7f1c8b46"
  },
  {
    "src": "/css/app.css",
    "dest": "fb/d8dd543fb0fe19fda3c4983a5169d25c6575c7",
    "content-type": "text/css",
    "hash": "fbd8dd543fb0fe19fda3c4983a5169d25c6575c7"
  },
  {
    "src": "/js/app.js",
    "dest": "af/c6a753a0f9de0ce9044d1a01f2b97814bd780e",
    "content-type": "application/javascript",
    "hash": "afc6a753a0f9de0ce9044d1a01f2b97814bd780e"
  }
]

Jika mengambil kasus gimana cara gue melakukan caching (di level si edgy ke S3), sepertinya gue enggak perlu mengubah algoritma cara buat invalidate cache nya, mengingat struktur path nya immutable.

Jika di level atas nya si edgy (seperti Varnish), mungkin, tinggal flushing via vcl nya Varnish :))

Tentunya struktur (JSON) diatas lebih baik disimpan di database saja, untuk mengurangi round trip. Khusus yang diatas ya, akan dibahas selengkapnya dibawah.

Gambaran

Berdasarkan hasil penjabaran diatas, sebagai gambaran, struktur direktori untuk project id 0788dc8 menjadi:

# tree 0788dc8

.
├── af
│   └── c6a753a0f9de0ce9044d1a01f2b97814bd780e
├── ef
│   └── fccf7b8fd0a9eec53bd66ed2d3c0dc7f1c8b46
└── fb
    └── d8dd543fb0fe19fda3c4983a5169d25c6575c7

3 directories, 3 files

Dan secara virtual, untuk deployment/versi 80fc788, direktorinya adalah seperti ini:

# tree 80fc788

.
├── ef
│   └── fccf7b8fd0a9eec53bd66ed2d3c0dc7f1c8b46
└── fb
    └── d8dd543fb0fe19fda3c4983a5169d25c6575c7

2 directories, 2 files

Bagaimana untuk kasus "delete", misal, delete css/app.css di versi selanjutnya?

Tinggal urus mapping nya saja!

Bagaimana bila untuk hal-hal terkait "sumber" alias the "src" thing?

Ini belum gue coba, tapi gue punya ide seperti ini:

  • Ambil source dari origin (repo) dan simpan ke S3 per branch
  • Metadata terkait url, branch, dsb simpan ke database
  • Deployment baru (via webhook), ambil payload dari webhook tersebut
  • Ambil source berdasarkan base branch
  • git init dan git remote add origin <url>
  • git checkout <base_branch>
  • git fetch origin
  • git merge origin/<new_branch>
  • ...Build?

Gue belum tau apakah ini efektif atau tidak, let's see!

Tapi jika ada yang sudah berpengalaman, feedback are welcome!

Pendekatan diatas bertujuan diusahakan untuk hanya mengambil berkas-berkas yang dibutuhkan saja, alias bila repo mu sebesar ~200M setidaknya yang kena pull hanya

Dan kemungkinan "conflict" bisa di cek dari mergeable nya PR yang ada.

Dan yaa kalau push langsung ke master kan kalau ada conflict ngurus nya di sisi pengguna hahaha.

I _only_ see the Hash List here!

Oke oke ini dapat dimengerti, karena kita daritadi bahasa nya dari sisi si edgy nya aja kan ya.

Sekarang, mari kita di sisi platform.

Bagimana si platform bisa tau berkas mana aja yang harus di upload?

Checksum?

Technically, yes.

Bagaimana bila lo cuma ngubah dari css/app.css menjadi css/apps.css yang mana memiliki dest (hash) yang sama tapi memiliki src yang berbeda?

...Misal karena typo?

Bagaimana cara menyusun "virtual tree" bila menggunakan murni hash list?

Kita buat deployment pertama!

Karena ini fresh, jadi tidak perlu melakukan pengecekan terhadap "sumber" apa saja yang harus di download oleh si "builder".

Lalu si builder mem-build project—berdasarkan framework yang digunakan, jika terdeteksi—dan karena belum ada tree nya, maka si builder harus membuat sendiri tree nya.

Disini bagian yang sedikit tricky, gue menggunakan bash script sederhana untuk membuat (initial) tree view nya:

# pwd
/koalaci/aec77d/public

# find * -type f -print0 | \
    xargs -0 shasum   |  \
    jq -R 'split(" ") | { hash:.[0], src: "/\(.[2])" }' | \
    jq -s

[
  {
    "hash": "da39a3ee5e6b4b0d3255bfef95601890afd80709",
    "src": "/css/style.css"
  },
  {
    "hash": "6d96270004515a0486bb7f76196a72b40c55a47f",
    "src": "/index.html"
  }
]

Yang mana data tersebut akan disimpan ke database untuk proses validasi apakah berkas-berkas hasil build oleh KoalaCI sama dengan yang disimpan di S3, bila proses build berhasil.

Setelah proses build selesai dengan berhasil, hasil build (dan kode sumber) akan disimpan di arsip nya masing-masing (ber-ekstensi tar.gz) yang mana akan diproses oleh platform.

Proses nya adalah meng-ekstrak arsip tersebut, melakukan verifikasi per-berkas, menambahkan beberapa metadata seperti tipe mime, dan membuat virtual direktori berdasarkan hash yang ada (da/39..., 6d/96..., dsb) lalu direktori virtual tersebut akan di-sinkronisasi ke S3.

Data yang ada di database hasilnya menjadi seperti ini kurang lebih:

- deployment_id: 80fc788...
- parent_id: null
- tree:
  - src: /index.html
    dest: /6d/9627...
    content-type: text/html
    hash: 6d9627...
  - src: /css/style.css
    dest: /da/39a3...
    content-type: text/css
    hash: da39a3...

Dan bila ada deployment baru, data (yang baru nya) seperti ini:

- deployment_id: cd32asc...
- parent_id: 80fc788
- tree:
  - src: /index.html
    dest: /6d/9627...
    content-type: text/html
    hash: 6d9627...
  - src: /css/style.css
    dest: /da/39a3...
    content-type: text/css
    hash: da39a3...
  - src: /js/app.js
    dest: /3a/bc29...
    content-type: application/javascript
    hash: 3abc29...

Bagaimana bila ada hanya perubahan nama berkas?

- deployment_id: dx1337f...
- parent_id: cd32asc
- tree:
  - src: /js/apps.js
    dest: /3a/bc29...
    content-type: application/javascript
    hash: 3abc29...
  - src: /index.html
    dest: /6d/9627...
    content-type: text/html
    hash: 6d9627...
  - src: /css/style.css
    dest: /da/39a3...
    content-type: text/css
    hash: da39a3...

Bagaimana bisa tau yang berubah adalah itu (dari /js/app.js ke /js/apps.js)?

Dari payload!

Database tidak peduli dengan isi dari konten, nama berkas, ataupun dari hash.

Tapi dia bisa tau berkas mana saja yang baru, yang berubah, dan yang dihapus.

Dengan membandingkan tree sebelumnya (parent) dengan yang sekarang, jadi tinggal ubah src ke dest yang sama.

Bagaimana bila perubahan konten dengan nama berkas yang sama?

Dari payload juga!

Yang mana tinggal mengubah dest (dan hash) ke src yang sama.

Bagaimana bila ada penghapusan berkas?

Dari payload juga!

Ukuran tree di database akan selalu bertambah (bila terdapat penambahan), yang mana berdasarkan yang gue liat dari git juga begitu :))

Merkle tree (atau Hash tree) disini—menurut gue—membantu untuk menentukan tree selanjutnya berdasarkan tree sebelumnya, dan bukankah memang itu benefitnya?

Kita bisa berpindah-pindah ke versi manapun, dengan sedikit kemungkinan terjadinya galat (karena corrupt bukan karena file missing), juga tetap bisa menyimpan berkas dengan efisien.

Dan gue enggak tau gimana cara ngelakuin itu di Hash list, sekalipun gue melakukan mapping juga (untuk membuat "virtual tree") which is basically the merkle tree, kan?

Dan hey, bukankah merkle tree adalah hasil generalisasi nya dari hash list?

Where does the merkle tree _really_ work here?

Masalah yang diselesaikan dengan menggunakan merkle tree disini antara lain:

  • Efisiensi di network I/O (saving bandwidth)
  • Integritas di penyimpanan berkas (prevent file corrupt)
  • Konsistensi di disk space (incremental upload/download)

Di versi deployment pertama, ingat kan kita melakukan validasi berkas dengan yang sudah ter-upload ke S3?

Di versi selanjutnya (ketika menambahkan js/app.js), berkas yang di upload hanya berkas itu, bukan keseluruhan hasil dari build.

Berikut dengan berkas apa saja yang harus di validasi juga.

Dan bagaimana pendekatan tersebut bisa dicapai?

Dengan membandingkan tree "origin" dan "parent".

Yang mana mencari perbedaan terhadap tree sebelumnya dengan tree yang baru dibuat, lalu perubahan tersebut lah yang di simpan ke database beserta dengan "parent tree" yang dibandingkan tersebut.

Dan hanya berkas yang berubah saja yang di upload ke S3.

Bisa kita lihat bahwa kita hanya melakukan perbandingan terhadap tree yang sebelumnya dengan tree yang ada, bukan dengan keseluruhan tree yang ada.

Karena tree yang sebelumnya sudah terjamin integritas nya karena sudah ada melakukan hal yang serupa sebelumnya.

Probably I'm wrong here

Entah secara konsep, ataupun implementasi.

Feedback is very welcome!

Sejauh ini PoC yang gue buat sudah hampir memenuhi kebutuhan gue.

Nantinya, untuk improvisasi, gue akan coba berani ber-eksperimen dengan mendistribusikan tree-tree ini ke berbagai mesin (chunked) bukan dengan replica.

Terlebih merkle tree memang cocok untuk komputasi yang terdistribusi.

Terima kasih.