In order to analyze and process the large graphs with high cost efficiency,researchers have developed a number of out-of-core graph processing systems in recent years based on just one commodity computer.On the other ...In order to analyze and process the large graphs with high cost efficiency,researchers have developed a number of out-of-core graph processing systems in recent years based on just one commodity computer.On the other hand,with the rapidly growing need of analyzing graphs in the real-world,graph processing systems have to efficiently handle massive concurrent graph processing(CGP)jobs.Unfortunately,due to the inherent design for single graph processing job,existing out-of-core graph processing systems usually incur unnecessary data accesses and severe competition of I/O bandwidth when handling the CGP jobs.In this paper,we propose GraphCP,a disk I/O optimized out-of-core graph processing system that efficiently supports the processing of CGP jobs.GraphCP proposes a benefit-aware sharing execution model to share the I/O access and processing of graph data among the CGP jobs and adaptively schedule the graph data loading based on the states of vertices,which efficiently overcomes above challenges faced by existing out-of-core graph processing systems.Moreover,GraphCP adopts a dependency-based future-vertex updating model so as to reduce disk I/Os in the future iterations.In addition,GraphCP organizes the graph data with a Source-Sorted Sub-Block graph representation for better processing capacity and I/O access locality.Extensive evaluation results show that GraphCP is 20.5×and 8.9×faster than two out-of-core graph processing systems GridGraph and GraphZ,and 3.5×and 1.7×faster than two state-of-art concurrent graph processing systems Seraph and GraphSO.展开更多
At present, I/O is the performance bottleneck limiting the speed of computer systems. A large number of I/O operations are synchronous read/write operations of only small data blocks. However, reducing the latency of ...At present, I/O is the performance bottleneck limiting the speed of computer systems. A large number of I/O operations are synchronous read/write operations of only small data blocks. However, reducing the latency of synchronous I/O operation is a non-trivial problem. In this paper, we propose two methods to address this problem. The first method, FastSync, uses a cache disk optimized for write operation via use of a disk-head position prediction algorithm. In this way, disk capacity is traded for synchronous I/O performance. The second method, LND, uses free memory capacity in a network environment as a cache disk for the buffering of synchronous I/O operation. Data integrity in FastSync is ensured by using a data log on the cache disk, whereas in LND, integrity is ensured by the storage in distributed memory of multiple copies of each data block. Both methods succeed in dramatically increasing the performance of synchronous I/O operation. The performance of LND is limited by the network speed, whereas performance of FastSync is determined mostly by the data block size.展开更多
In distributed cloud storage systems, inevitably there exist multiple node failures at the same time. The existing methods of regenerating codes, including minimum storage regenerating(MSR) codes and minimum bandwidth...In distributed cloud storage systems, inevitably there exist multiple node failures at the same time. The existing methods of regenerating codes, including minimum storage regenerating(MSR) codes and minimum bandwidth regenerating(MBR) codes, are mainly to repair one single or several failed nodes, unable to meet the repair need of distributed cloud storage systems. In this paper, we present locally minimum storage regenerating(LMSR) codes to recover multiple failed nodes at the same time. Specifically, the nodes in distributed cloud storage systems are divided into multiple local groups, and in each local group(4, 2) or(5, 3) MSR codes are constructed. Moreover, the grouping method of storage nodes and the repairing process of failed nodes in local groups are studied. Theoretical analysis shows that LMSR codes can achieve the same storage overhead as MSR codes. Furthermore, we verify by means of simulation that, compared with MSR codes, LMSR codes can reduce the repair bandwidth and disk I/O overhead effectively.展开更多
基金supported by the National Natural Science Foundation of China(Grant Nos.61832020,61821003 and U1705261)National Defense Preliminary Research Project(No.31511010202)+3 种基金the Fundamental Research Funds for the Central Universities,the Open Project Program of Wuhan National Laboratory for Optoelectronics(No.2022WNLOKF017)the Natural Science Foundation of Fujian Province(No.2020J01493)Zhejiang provincial“Ten Thousand Talents Program”(No.2021R52007)Center-initiated Research Project of Zhejiang Lab(No.2021DA0AM01).
文摘In order to analyze and process the large graphs with high cost efficiency,researchers have developed a number of out-of-core graph processing systems in recent years based on just one commodity computer.On the other hand,with the rapidly growing need of analyzing graphs in the real-world,graph processing systems have to efficiently handle massive concurrent graph processing(CGP)jobs.Unfortunately,due to the inherent design for single graph processing job,existing out-of-core graph processing systems usually incur unnecessary data accesses and severe competition of I/O bandwidth when handling the CGP jobs.In this paper,we propose GraphCP,a disk I/O optimized out-of-core graph processing system that efficiently supports the processing of CGP jobs.GraphCP proposes a benefit-aware sharing execution model to share the I/O access and processing of graph data among the CGP jobs and adaptively schedule the graph data loading based on the states of vertices,which efficiently overcomes above challenges faced by existing out-of-core graph processing systems.Moreover,GraphCP adopts a dependency-based future-vertex updating model so as to reduce disk I/Os in the future iterations.In addition,GraphCP organizes the graph data with a Source-Sorted Sub-Block graph representation for better processing capacity and I/O access locality.Extensive evaluation results show that GraphCP is 20.5×and 8.9×faster than two out-of-core graph processing systems GridGraph and GraphZ,and 3.5×and 1.7×faster than two state-of-art concurrent graph processing systems Seraph and GraphSO.
基金the National Key Basic Research and Development Program of China (No. G1999032702) the National High-Tech Research and Development Program of China (No.2001AA111010) and the National Natural Science Foundation of China (No.60131160743)
文摘At present, I/O is the performance bottleneck limiting the speed of computer systems. A large number of I/O operations are synchronous read/write operations of only small data blocks. However, reducing the latency of synchronous I/O operation is a non-trivial problem. In this paper, we propose two methods to address this problem. The first method, FastSync, uses a cache disk optimized for write operation via use of a disk-head position prediction algorithm. In this way, disk capacity is traded for synchronous I/O performance. The second method, LND, uses free memory capacity in a network environment as a cache disk for the buffering of synchronous I/O operation. Data integrity in FastSync is ensured by using a data log on the cache disk, whereas in LND, integrity is ensured by the storage in distributed memory of multiple copies of each data block. Both methods succeed in dramatically increasing the performance of synchronous I/O operation. The performance of LND is limited by the network speed, whereas performance of FastSync is determined mostly by the data block size.
基金supported in part by the National Natural Science Foundation of China (61640006, 61572188)the Natural Science Foundation of Shaanxi Province, China (2015JM6307, 2016JQ6011)the project of science and technology of Xi’an City (2017088CG/RC051(CADX002))
文摘In distributed cloud storage systems, inevitably there exist multiple node failures at the same time. The existing methods of regenerating codes, including minimum storage regenerating(MSR) codes and minimum bandwidth regenerating(MBR) codes, are mainly to repair one single or several failed nodes, unable to meet the repair need of distributed cloud storage systems. In this paper, we present locally minimum storage regenerating(LMSR) codes to recover multiple failed nodes at the same time. Specifically, the nodes in distributed cloud storage systems are divided into multiple local groups, and in each local group(4, 2) or(5, 3) MSR codes are constructed. Moreover, the grouping method of storage nodes and the repairing process of failed nodes in local groups are studied. Theoretical analysis shows that LMSR codes can achieve the same storage overhead as MSR codes. Furthermore, we verify by means of simulation that, compared with MSR codes, LMSR codes can reduce the repair bandwidth and disk I/O overhead effectively.
