图是一种简单直观的数据表现方式,现实世界中的很多问题都可以转化成图,例如社交网络中的用户关系、电子商务应用中的用户评价都可以借助图来表示。很多基于图数据的处理系统也就应运而生,这些都统称为图计算系统。图计算系统大致有分布式图计算和单机图计算这两大类:分布式图计算的思想是,通过增加机器数量以达到分散数据、平衡负载的目的,常用于处理大规模图数据;单机图计算又可细分为单机内存式和单机外存式,分别用于对小规模和大规模数据的处理中,该类图计算系统一般根据服务器性能分配相应数量的线程以提高系统的并发能力,out-of-core技术也被运用到单机外存系统中以解决I/O数据加载问题。在相同资源条件限制下,单机系统往往具有比分布式系统更好的性能,这是因为分布式中多台机器的通信和同步都需要更高代价。在处理大规模数据时,通过增加廉价的外存设备资源以及对并行I/O技术的优化,单机外存系统就能达到不错性能,而无需浪费昂贵的分布式资源。现阶段已有一些针对单机外存系统的研究,例如GraphChi、X-stream、GridGraph。它们大都致力于优化外存数据访问以提高I/O性能,例如X-stream和GridGraph通过保证对外存数据的顺序读写来降低I/O延迟,GridGraph则是通过减少外存数据加载量、粗粒度的提交请求数据来减少I/O访问次数。但它们都疏忽了对内存处理效率的优化,随着I/O性能的提升,内存处理时间会逐渐突出,甚至上升为系统性能瓶颈,而那时它们不再占据优势。本文提出了一个通过并行I/O技术,能够在单机上运行大规模图数据的计算系统,并从计算和I/O加载的协同关系、内存访问方面进行优化,从而解决以上问题。本文提出的异步计算-I/O加载模型真正的让计算和I/O过程并行起来,而不再是GridGraph所用的同步模型的串行执行。在异步模型中,计算和I/O加载过程相对独立,可以根据各自任务的访问需求分配不同线程组,避免了同步模型中统一分配策略造成的I/O线程过量问题,从而达到充分利用内存和I/O带宽的目的;此外,本文系统通过异步I/O引擎LIBAIO不仅提升了外存访问带宽,而且还进一步平衡了各线程在内存中的工作负载;在内存访问方面,本文系统基于NUMA架构进行了优化,通过远端顺序和本地随机相结合的内存访问策略,避免了对远端数据的随机访问,极大的提高了内存访问效率。为了保证对远端数据的顺序访问,在预处理阶段,本文系统需要对图数据按照源点或目的顶点重新排列,为了减少排序开销,本文提出in-memory排序和归并外排相结合的排序策略,从而避免排序对预处理性能的影响。通过实验数据,不难发现,本文系统无论是在I/O性能还是内存访问效率方面都具有显著优势。