南方科技大学知识苑(SUSTech KC): Accelerating Merkle Patricia Trie with GPU

题名	Accelerating Merkle Patricia Trie with GPU
作者	Deng, Yangshen; Yan, Muxi; Tang, Bo
通讯作者	Tang, Bo
发表日期	2024-04-01
DOI	10.14778/3659437.3659443
发表期刊	PROCEEDINGS OF THE VLDB ENDOWMENT 影响因子和分区
ISSN	2150-8097
卷号	17 期号:8
摘要	["Merkle Patricia Trie (MPT) is a type of trie structure that offers efficient lookup and insert operators for immutable data systems that require multi-version access and tamper-evident controls, such as blockchains and verifiable databases. The performance of these systems is critically dependent on the throughput of the underlying index structure MPT. In this paper, we present a novel approach to accelerate MPT by leveraging the massive parallelism of GPU. However, achieving it is challenging as (i) lock-free data structures are difficult to implement and (ii) traditional fine-grained locking does not scale on GPU.","To address them, we first analyze the technical challenges of accelerating MPT via GPU, including node splitting conflicts and hash computing conflicts caused by parallel insert operations. We then propose a lock-free algorithm PhaseNU and a lock-based algorithm LockNU on GPU to resolve the node splitting conflict. We also devise a decision model for users to choose the proper one for different workloads. We next propose a GPU-based hash-compute algorithm PhaseHC to avoid hash computing conflicts. Last, we demonstrate the effectiveness of our proposed techniques by: (i) integrating them into both the real-world blockchain system Geth and verifiable database LedgerDB, and demonstrating its superiority with corresponding workloads; and (ii) conducting extensive experimental studies on two real-world datasets and one synthetic dataset. Our proposed solutions significantly outperform the deployed MPT solution in Geth in all datasets."]
相关链接	[来源记录]
收录类别	SCI ; EI
语种	英语
学校署名	第一 ; 通讯
资助项目	Shenzhen Fundamental Research Program[20220815112848002] ; Guangdong Provincial Key Laboratory[2020B121201001]
WOS研究方向	Computer Science
WOS类目	Computer Science, Information Systems ; Computer Science, Theory & Methods
WOS记录号	WOS:001253076500006
出版者	ASSOC COMPUTING MACHINERY
来源库	Web of Science
引用统计
成果类型	期刊论文
条目标识符	http://sustech.caswiz.com/handle/2SGJ60CL/789901
专题	南方科技大学
作者单位	Southern Univ Sci & Technol, AlayaDB AI, Shenzhen, Peoples R China
第一作者单位	南方科技大学
通讯作者单位	南方科技大学
第一作者的第一单位	南方科技大学
推荐引用方式 GB/T 7714	Deng, Yangshen,Yan, Muxi,Tang, Bo. Accelerating Merkle Patricia Trie with GPU[J]. PROCEEDINGS OF THE VLDB ENDOWMENT,2024,17(8).
APA	Deng, Yangshen,Yan, Muxi,&Tang, Bo.(2024).Accelerating Merkle Patricia Trie with GPU.PROCEEDINGS OF THE VLDB ENDOWMENT,17(8).
MLA	Deng, Yangshen,et al."Accelerating Merkle Patricia Trie with GPU".PROCEEDINGS OF THE VLDB ENDOWMENT 17.8(2024).