簡介
在加速運作上，Aptos 採用的是往平行化運作的方式來做設計 — 尤其希望可以在已知有存取衝突時盡可能地加速。有些平行執行引擎會強制要求使用者預先提出會遇到的 dependency，但此做法也會大幅的限制了 transaction (tx) 的行為，也可能會造成該 tx 失敗或重新執行。
為了避免這些問題，目的就相當明確了，就是希望可以在內部管理所有衝突，並自動化的適應這些 workloads。
在現階段區塊鏈的設計上，大多是只能是序列化的執行 tx，少數雖說有辦法可以支援平行化，但也僅限那些沒有內部衝突的 tx。
STM
STM(Software Transactional Memory) 的做法會將記憶體的存取作為偵測與管理衝突的工具：在有 OCC (optimistic concurrency control) 的情況下會於執行時紀錄記憶體的存取，並驗證所有 tx 執行完的結果，並在驗證發現衝突時終止其 tx 並重新執行。然而，因為需要紀錄衝突跟終止 tx，造成了 STM 會受到更多性能的限制，因此也較少被使用。
但在一些特殊情境上，STM的執行效率可以有效的提升
區塊鏈的使用情境
由於運作方式的關係，相對於一般的情境，區塊鏈有以下三個特色：
不需要個別的 commit txs
相比其他使用於一般用途的 STM，在鏈上的狀態是一次性的在每個區塊上更新的。
在此情況下，Block-STM 就可以避免因為個別 commit 所造成的同步問題；而是只需要在每次的區塊上 commits 該區塊的所有 txs 即可，大幅減低了同步上的問題。
另一方面，也讓 garbage collection 更直觀：在區塊之間清掉記憶體即可。
VM 保證了 optimistic memory access 足夠的安全性
由於 tx：
- 都由特定的語言寫成（像是 Move、Solidity 或 Rust）
- 都在 VM 中隔離運作，保證了安全性
因此有辦法讓 Block-STM 在足夠抽象化的同時，不必處理在平行化執行時所產生的狀態不一致的後果
預先訂好的順序可以減少同步的需求
STM 的設計上通常會將 determinism 視為限制，希望可以在交易為 non-determinism 的情況運作（畢竟 STM 會希望他每個交易的運作都是獨立並行的），但區塊鏈上就不適用這個想法，因為不同的執行順序會影響狀態。這也造成了在 Block-STM 設計上，可以免除一些效能需求。
另一方面來看，當一般的 STM 需要去解決 non-determinism 造成的共識問題時， Block-STM 只需要去確保 tx 的執行即可，因此也可以相當程度的降低難度。
核心技術
Block-STM 在設計上的一些想法:
樂觀併發控制 （Optimistic concurrency control）
- Tx 會先被平行化的執行，其運行結果則會在運行結束後被驗證，未被驗證通過的 tx 將會被重新執行。
- 由於運行的順序是預先被訂定的，故 validators 之間必須根據 tx 的順序來運行，並非各自獨立的。
- 此外，值得注意的是：與過去的其他鏈不同，驗證成功並不代表 tx 可以被提交；相反的，驗證失敗的 tx 也只代表更後面的 tx 只能在此 tx 被 commit 後運行。
多版本的資料結構 （Multi-version data structure）
- Block-STM 使用了 multi-version 的資料結構來避免 write-write conflicts.
- 一個相同位置的所有讀取會連帶他們的版本一同存放，存放的內容也會包含該 tx 的 ID 以及被重新執行了寫入 tx 的次數
- 當有一個 tx 讀取某個記憶體位置時，會連帶從多版本的資料結構中讀取在此 tx 前的最後一筆 tx 中寫入的值以及其版本。
驗證（Validation）
- 在執行時， tx 會紀錄一個 read-set 跟一個 write-set。
- 在驗證時，會讀取所有在 read-set 中的記憶體位置，並比較其拿到的版本跟在 read-set 中相對應的版本進行比較。
協作排程（Collaborative schedule）
Block-STM 提出了一個協作的排程器從線程上來協調驗證與執行的任務。
在運作上， tx 的排序決定了其必須是有順序性的被 commit，如果在前面的區塊中的交易發生了被終止及需要重新執行的時候，read-set 會被 invalidate，導致需要重新執行的情況（因此成功驗證交易執行並不保證該交易執行會被 commit）。
因此，在排程上並沒有辦法用靜態的方式來指派該交易要由哪個線程來進行，而是會需要一個協作排程器來優先考慮順序較前的執行與驗證工作。
雖然有序集和優先序列在多核環境下很難做到擴展，但 Block-STM 使用了計數的方法迴避了這個問題：這也可以通過 tx 的預設排序和 compact indexation 來實現。（怕篇幅太長，詳細的方式會在之後的文章介紹）
動態預測依賴性（Dynamic dependency estimation）
前面有提到，tx 的終止在 STM 系統上會造成相當程度的速度損耗，因此Block-STM 透過預設排序來盡可能地避免 tx 終止的情況發生。
當驗證失敗時，tx 的最後一次執行的 write-set 會透過在多版本的資料結構中的 “所有寫入” 標記為 ESTIMATION 來估計 dependency。而當其他 tx 遇到被標為 ESTIMATION 的資料時，則會等到其 dependency resolved 後再進行。
若在沒有 ESTIMATION 的情況下，該交易很容易因為前面交易驗證失敗的情況而被終止。
相比於教科書上基於上個區塊的狀態來平行化預先執行所有交易，透過 Block-STM 可以達到兩種好處：
- 可以在有需要的時候再產生預估
- 預估可以基於比該區塊的初始還要更新的狀態
後記
aucLab 作為一個實驗性的組織，不斷地接觸最新的技術，在 Aptos 也是，我們最近也正在著手策劃 Aptos 生態系的開發，歡迎有興趣的有志之士可以加入我們，一起做出些貢獻！
可以直接寄 email 到 akira@auclab.xyz 給我！或是
參考資料
[1] Block-STM: How We Execute Over 160k Transactions Per Second on the Aptos Blockchain (https://medium.com/aptoslabs/block-stm-how-we-execute-over-160k-transactions-per-second-on-the-aptos-blockchain-3b003657e4ba)
[2] Block-STM: Scaling Blockchain Execution by Turning Ordering Curse to a Performance Blessing (https://arxiv.org/pdf/2203.06871.pdf)
