本文中我们将分享大规模图计算上的跨语言探索，GraphScope 的高效图分析 Java 开发包 GRAPE-JDK。

1. 图分析上跨语言的需求与挑战

图分析是图计算任务中的重要场景，例如大家熟悉的单源最短路径就是一种常见的图分析算法。GraphScope的图分析引擎源自于GRAPE[1]，其内置了常见的图分析算法如 SSSP，PageRank 等，用户可以直接进行调用。但在实际生产场景中，业务逻辑在通用算法上一般还有一些定制实现，而业务侧开发者往往在大数据生态中对 Java 更有经验。要求 Java 用户跨越 Java 与 C++ 之间的语言障碍来完成图计算业务逻辑的开发无疑增加了开发成本，提高了开发难度。如何平衡 Java 的灵活性和图计算 C++ 引擎的高效性？因此，允许用户使用 Java 进行自定义图算法的实现，并且高效地运行在 GraphScope 图分析引擎上，是一个十分现实的需求。

为了满足用户对于跨语言图分析的需求，我们需要在 C++ 实现的图分析引擎 GRAPE 基础上开发 Java SDK。在这样的场景下，使用 JVM 的标准的跨语言编程框架 Java Native Interface(JNI)[2] 是常见的方案。JNI 存在的原因是因为在 Java 中，我们无法像在 C++ 中那样以非常底层的方法访问系统的硬件资源，而为了能够使用这些硬件资源，我们就需要 Java 和 C++ 之间的桥接代码来使用 native library 中可执行代码。JNI 就是 JVM 上的 FFI (Foreign Function Interface) 标准框架。

因此我们可以找到一种简单直观的解决方案：使用 Raw JNI 手写 Java 和 C++ 的桥接代码，将图计算引擎的 C++ 接口封装为 Java 接口，暴露给用户使用。 但是事实上这个 naive (baseline) 方案存在着各种问题，并不能够满足大规模图计算的实际需求，主要面临的挑战在以下三个方面：

挑战1: JNI编程的困难

直接基于 JNI 进行跨语言编程存在开发困难，调试困难和维护困难的问题。

• 开发困难：为了使得 Java 能够和 C++ 进行交互/通信，程序猿需要编写大量的机械单调，枯燥无味的 JNI 代码，如下图所示。JNI 代码中经常涉及到指针转换，更加增加了出错的风险。

JNIEXPORT void JNICALL Java_com_alibaba_graphscope_stdcxx_StdVector_1cxx_10x8cbe72bf_nativeClear(JNIEnv*, jclass, jlong ptr) {
    reinterpret_cast<std::vector<gs::VertexArrayDefault<double>>*>(ptr)->clear();
}

• 调试困难：编写出来的JNI代码需要通过c++/c编译器编译成动态库，以供JVM载入并调用其中定义的函数。JNI代码的编译调试也是较为痛苦的过程。
• 维护困难：维护JNI代码的成本也是较高昂的。由于JNI代码高度依赖于C++ native code，因此当图计算引擎的C++接口和实现发生变动时，程序猿必须手动更改JNI实现以进行适配。

挑战2: 跨语言访问的巨大开销

JNI 虽然提供了充足的 API 以供 Java 和 C++ 之间进行通信，但是由于其本身跨语言的特性，JNI 带来的开销也是巨大的。根据我们的调研，JNI 在实际大规模图计算场景中可能引入的开销主要来自于以下几个方面调用的开销。

• JNI 调用本身的开销[3]。在 JNI 函数中调用本身就有着较大开销，包括在 JNI 代码实现中访问 Java Object，都是导致非常耗时的操作。
• Java native 方法无法被 JVM inline。在 Java 中，对于代码的优化基本都来自于 JVM，对于高频调用的 Java 方法，JVM 可以通过 inline 来避免函数调用的开销。但是对于 JNI 实现的 native 方法，JVM 无法对其进行优化。而在图计算这样 data-intensive 的场景中，从 Java 通过 JNI 访问存储在 C++ 内存中的数据是非常频繁热点的操作，因此无法被 inline 的 native 方法会是程序执行过程中很大的一部分开销。
• Java native 方法无法被 JIT 进行优化。native 方法已经被 C++/C 编译器进行编译为二进制，JVM 当然无法对其进行 JIT 优化。

挑战3: 对用户自定义类型的支持

在一些复杂的实际生产场景中，用户往往对自定义点，边上的数据类型，甚至消息类型有着较强的需求。仅仅依靠 JNI 是做不到这一点的，因为每当用户定义新的数据类型，我们都需要在 C++ 中进行实现，然后再编写 JNI 方法映射到 Java 中。

2. 设计与实现

为了攻克这些难点，GraphScope 团队与阿里云程序语言与编译器 - JVM 团队紧密合作，设计并实现了一套性能高效、用户友好的跨语言图计算解决方案。同时在 GRAPE-JDK 开发过程中也催生了一套现代的、先进的 FFI (Foreign Function Interface) 框架：FastFFI（在 github:alibaba/fastFFI[4] 开源）。GRPAE-SDK 在 GraphScope 系统中所处的位置如下所示。

2.1 FastFFI

GRAPE-JDK 的功能依赖于 FastFFI 。FastFFI 是一款先进、现代、高效的 Java FFI 框架，其特性源自于我们在 GRAPE-JDK 的探索中所获得的 Java 和 C++ 跨语言编程的沉淀和积累。FastFFI 成功解决了我们前面提到的三个挑战。

FastFFI可以分为两个部分，FFI SDK 和 LLVM4JNI-SDK。FFI-SDK 提供全面的 JNI 开发支持，降低编程的复杂度；LLVM4JNI-SDK 提供 JNI 代码优化支持，提升运行性能。

2.2 GRAPE-JDK

基于 FastFFI 提供的 JNI 支持，我们开发了 GRAPE 的 Java PIE SDK：GRAPE-JDK。我们以 Vertex 为例，来介绍 FastFFI 是如何降低 JNI 开发复杂度并提升性能的。

C++与Java类的映射

Vertex作为图中最基础的抽象，往往拥有绑定的编号（ID）和绑定的数据。例如，在 GRAPE 中，点的接口抽象如下

template <typename T>
class Vertex {
 public:
  Vertex() {}
  ~Vertex() {}
  //Other code fragments are omitted here, see full code at
  // https://github.com/alibaba/libgrape-lite/blob/master/grape/utils/vertex_array.h#L36
  
  // Get the id bound with this vertex.
  inline T GetValue() const { return value_; }

  // Set the id bound with this vertex.
  inline void SetValue(T value) { value_ = value; }

 private:
  T value_;
}

为了将 C++ 的 Vertex 类映射到 Java 中的，我们只需在 Java 中编写如下代码

@FFIGen(library = "grape-jni")
@CXXHead("grape/utils/vertex_array.h")
@FFITypeAlias("grape::Vertex")
@CXXTemplate(
        cxx = {"uint64_t"},
        java = {"Long"})
public interface Vertex<VID_T> extends FFIPointer {
    VID_T GetValue();

    void SetValue(VID_T id);
}

类似于 @FFIGen() 就是一个 Java 注解的定义，通过注解提供的额外信息，我们就可以在编译 Java 代码时进行代码生成。例如，@CXXHead（"grape/utils/vertex_array.h"） 就指明在生成的 C++ 代码中，需要包含 grape/utils/vertex_array.h 这个头文件。

Vertex.java 在编译之后会生成两份代码，其中一份是生成的 Java Vertex 接口的实现类，其中会定义相应的 native 方法。

public class Vertex_cxx_0xaccf3424 extends FFIPointerImpl implements Vertex<Long> {

  public Vertex_cxx_0xaccf3424(final long address) {
    super(address);
  }

  public Long GetValue() {
    return new java.lang.Long(nativeGetValue(address));
  }
  //The actual working native method.
  public static native long nativeGetValue(long ptr);

  public void SetValue(Long arg0) {
    nativeSetValue(address, arg0);
  }
  // The actual working native method.
  public static native void nativeSetValue(long ptr, long arg00);
}

同时，还会有一份 .cc 文件包含 natvie 方法的实现

// headers are omitted.
#ifdef __cplusplus
extern "C" {
#endif

//JVM根据native的函数签名在动态库中查找相应的native 实现代码，具体参加JNI规范。
JNIEXPORT
jlong JNICALL Java_com_alibaba_graphscope_ds_Vertex_1cxx_10xaccf3424_nativeGetValue(JNIEnv*, jclass, jlong ptr) {
    return (jlong)(reinterpret_cast<grape::Vertex<uint64_t>*>(ptr)->GetValue());
}

JNIEXPORT
void JNICALL Java_com_alibaba_graphscope_ds_Vertex_1cxx_10xaccf3424_nativeSetValue(JNIEnv*, jclass, jlong ptr, jlong arg0 /* arg00 */) {
    reinterpret_cast<grape::Vertex<uint64_t>*>(ptr)->SetValue(arg0);
}
#ifdef __cplusplus
}
#endif

以此类推，对于任何一个 C++ 类，我们都可以将其映射到一个 Java 类。

FFIMirror：自定义数据类型

在 GRAPE-JDK 中，我们支持用户创建一个没有 C++ 对应实现的自定义数据结构，并将其作为点 ID，点或边上的数据类型。只需要使用 @FFIMirror 这个注解来修饰自己定义的接口。例如我们可以定义一个简单的只包含 long，double 两个字段的数据结构，在编译阶段会自动生成相应的 c++ struct 代码，JNI 代码，Java 实现类代码。

@FFIMirror
@FFINameSpace("sample")
@FFITypeAlias("MyData")
public interface MyData  extends CXXPointer {
    //Get the long field.
    @FFIGetter long longField();
     //Set the long field.
    @FFISetter void longField(long value);
    
    @FFIGetter double doubleField();
    @FFISetter void doubleField(double value);

    //Create MyData with this factory
    MyData.Factory factory = FFITypeFactory.getFactory(MyData.class);
    @FFIFactory
    interface Factory {
        MyData create();
    }
}

接下来，和普通的 JNI 项目一样，我们将获得的 .cc 文件编译链接为动态库，在 Java 代码中通过 System.loadLibaray() 进行载入后，就可以在 Java 中访问 C++ 的对象和方法了。

可以看到，基于 FastFFI 的 GRAPE-JDK 的实现完美解决了 JNI 进行跨语言编程存在开发调试和维护困难的问题，满足用户自定数据类型的需求。

2.3 JNI 代码优化

LLVM4JNI-SDK 是一套纯 Java 实现的 "BitCode to ByteCode" 转换工具。LLVM4JNI 的工作原理是通过对 LLVM-IR （JNI 代码在使用 LLVM11 编译时使用 option -mllvm=-lto-embed-bitcode[5] 来将 IR 嵌入到动态库 binary 中）进行分析，挑选出能够转换为 Java ByteCode 的代码（并不是所有 LLVM IR 都可以转换为 ByteCode）进行字节码生成，最后替换掉对应的 Java native 方法。 例如，对于上面定义的 Veretx，运行 LLVM4JNI 进行优化，我们会对Vertex实现类中的native方法进行替换

public class Vertex_cxx_0xaccf3424 extends FFIPointerImpl implements Vertex<Long> {
  //Notice that this a no longer a native method now!
  public static long nativeGetValue(long ptr){
      return JavaRuntime.getLong(var0);
  }

  public static void nativeSetValue(long ptr, long arg00){
       JavaRuntime.putLong(ptr, arg00);
  }
}

可以看到，原来的 native 方法被替换为正常的 Java 方法，方法内的实现中的 JavaRuntime 是 LLVM4JNI-runtime 中对 Java UNSAFE 的封装，其本质上仍然是调用 UNSAFE 来访问堆外内存。 通过将 native 方法替换为 Java 方法，我们避免了可观的JNI调用的开销。

3. 用户接口

通过只暴露给用户一个简单的编程模型接口 ParallelAppBase，我们可以将 GRAPE-JDK 复杂的实现隐藏起来。用户不需要了解任何的底层实现，只需要继承该接口，并且实现其中 PEval 和 IncEval 两个方法，就可以将算法运行在GraphScope 的图分析引擎上。更多教程请参考 GAE-java-tutorial[6]。

public class Traverse implements ParallelAppBase<Long, Long, Double, Long, TraverseContext>,
    ParallelEngine {
    @Override
    public void PEval(IFragment<Long, Long, Double, Long> fragment,
        ParallelContextBase<Long, Long, Double, Long> context,
        ParallelMessageManager messageManager) {
           
    }
    @Override
    public void IncEval(IFragment<Long, Long, Double, Long> fragment,
        ParallelContextBase<Long, Long, Double, Long> context,
        ParallelMessageManager messageManager) {

    }
}
public class TraverseContext extends
    VertexDataContext<IFragment<Long, Long, Double, Long>, Long> implements ParallelContextBase<Long,Long,Double,Long> {
    @Override
    public void Init(IFragment<Long, Long, Double, Long> frag,
        ParallelMessageManager messageManager, JSONObject jsonObject) {

    }

    @Override
    public void Output(IFragment<Long, Long, Double, Long> frag) {

    }
}

4. 性能验证

为了验证 GRAPE-JDK 在大规模图计算场景中的运行性能，我们在 LDBC Graphalytics[7] 提供的数据集选取了数亿点和数十亿条边的数据集上进行了多种常见算法的测试，测试配置为 4 台 400GB 内存/96核的集群，GraphScope workers 数为 4。具体的性能测试报告结果请参考 GRAPE-JDK 性能测试[8]，我们这里以 SSSP 和 PageRank 算法为例，来展示实验结果。

4.1 Java app vs C++ app

首先，我们比较基于 GRAPE-JDK 实现的 Java-SSSP 算法和基于 libgrape-lite 实现的 CPP-SSSP 算法在 com-fiendster 和 Datagen-9_0-fb 数据集上的性能差距，可以看到，Java app 和 C++ app 的整体性能差距在 2 倍左右。

4.2 LLVM4JNI 带来的性能提升

LLVM4JNI 为 GRAPE-JDK 的性能带来了巨大的提升。如下表所示，使用 GRAPE-JDK 实现的 Java-PageRank 算法在与 CPP-PageRank 之间的性能已经较为接近。在并发度较高的情况下，已经与 C++ 的时间非常接近了（如第二个表中并发度为 32 的列）。

5. 总结

在本文中，我们简单介绍了 GraphScope 在跨语言图分析的探索，借助于 FastFFI，GRAPE-JDK 在为 Java 用户提供友好的用户接口的同时也具有高效的图查询性能。