基于三数组Trie索引树的词典查询机制

对双数组Trie进行改进,设计实现基于三数组Trie索引树原理的汉语词典查询机制,并用递归算法实现构词状态表的自动构建。

ErlangShen:基于流水线低访问开销的图式区块链高效事务执行机制

基于有向无环图(DAG)的图式区块链能够显著提升系统性能,已成为近年来业界的研究热点。相较于传统串行化的链式区块链,图式区块链可在单位时间内并发处理大量事务从而提升吞吐量。随着事务量的激增,图式区块链面临事务执行效率低的瓶颈问题,即海量事务执行对状态数据访问的需求大幅增加,导致高昂的输入/输出(I/O)开销。实现低I/O访问主要包括两方面的全新挑战:一方面,图式区块链若直接采用传统的事务预取机制,将因执行逻辑不一致引入大量的陈旧读;另一方面,针对不同账户的状态访问会在默克尔树的高层节点中造成重复的I/O开销。为此,本文设计基于流水线的图式区块链高效事务执行机制—ErlangShen,包括Epoch粒度的状态预取机制和默克尔高层路径缓存机制来分别减少陈旧读的数量和重复的I/O开销。具体而言,ErlangShen充分分析并利用了事务访问频次的冷热特征,将访问热事务的逻辑执行与冷事务的状态预取并行化,以避免状态预取对事务执行的影响。此外,为了进一步提升事务执行的吞吐量,根据访问冷热状态事务的特性设计了定制化的并发控制方法。实验结果表明,ErlangShen机制能够减少约90%的陈旧读数量,与最新图式区块链事务处理机制Nezha相比,可将性能提升3~4倍。