Storaged, the core storage component of NebulaGraph, is responsible for ensuring durability, availability, and scalability. It plays a critical role in handling reads and writes efficiently. This article explores the architecture of Storaged from the perspective of its underlying storage engine, RocksDB [1], and shares insights from real production use cases on diagnosing and resolving performance bottlenecks. 

One notable production example is Snapchat, which uses NebulaGraph to enhance its friend recommendation system at scale. (Read more [here](https://www.nebula-graph.io/posts/snapchat_enhances_friend_recommendations_with_nebulagraph).)

# How is data read and written in NebulaGraph

In NebulaGraph, both vertices and edges are stored as key-value pairs using RocksDB as the storage engine. In version 3.x, we use RocksDB 3.7.3. The data is partitioned and replicated, with each partition replica backed by a separate RocksDB instance.

![image](https://www-cdn.nebula-graph.io/blogs/storage.png)

To distribute data across multiple storage nodes, we use hash function:
- **Vertices** are partitioned based on their vertex ID.
- **Edges** are partitioned based on the source vertex ID.

This design ensures that a vertex and all its outgoing edges reside in the same partition, improving query performance. However, **super nodes** (e.g., highly connected entities such as celebrities or popular websites) can cause load imbalances. Hashing helps distribute these nodes more evenly across Storaged instances.

# Consistency and Replication via Raft

To maintain consistency between replicas, NebulaGraph employs the **Raft consensus algorithm** [2], which elects a **Leader** among the replicas. The Leader handles most read and write requests, while **Followers** serve as backups. If a Leader fails due to network issues or maintenance, a new Leader is elected.

The data write and replication process follows these steps:

1. The Leader writes data to the **Write-Ahead Log (WAL)**.
2. The write is replicated to all Followers, who also write to their own WAL.
3. Followers asynchronously persist the data to RocksDB and acknowledge the Leader.
4. Once the Leader receives acknowledgments from all Followers, it commits the write to RocksDB.

The diagram below illustrates this process.
![image](https://www-cdn.nebula-graph.io/blogs/storage_process.png)

# High Availability with Zones

For environments requiring high availability, we recommend distributing partition replicas across different zones. A zone refers to a distinct logical or physical grouping of infrastructure. In cloud environments, zones typically correspond to availability zones (AZs) [3] - geographically separate data centers within a region. These zones are close enough to support low-latency connections but far enough apart to minimize the risk of simultaneous failures due to localized disruptions (e.g., power outages or extreme weather). In this setup:

* Writes are always handled by the Leader, regardless of zone placement.
* Reads can be optimized with **zone affinity**, where queries prioritize a Storaged instance within the same zone as the compute node (Graphd) handling the query. 
* With zone affinity enabled, both Leaders and Followers can serve read requests, improving efficiency and reducing cross-zone data transfer costs. (E.g., In AWS, intra-zone data transfer is free.)

# Diagnosing High Storaged Latency: Common Causes and Solutions

In production environments, high P90 query latency and increased query failures often signal performance issues. While some problems originate from Graphd (our compute nodes) or Metad (our meta service nodes), when the root cause lies in Storaged, it always manifests as high storage latency. This section covers the most common causes of high storage latency and how to mitigate them.

## 1. Low Resource Utilization

If Storaged latency is high, but CPU usage, disk I/O, and disk throughput remain low, the software may not be fully utilizing available hardware resources. A key area to check is thread allocation for the Thrift server and RocksDB. 

Storaged relies on three main thread pools:
- Thrift IO thread pool – Handles incoming connections in an event loop. 
- Thrift worker thread pool – Handles service requests, including writes.
- Read handler thread pool – Manages disk reads via RocksDB.

The Thrift IO threads process the connections very fast and rarely cause latency issues. If latency persists, focus on the worker and read handler pools. In production, setting these pools to match the number of CPU cores on the machine or pod running Storaged typically yields optimal performance.

## 2. High CPU usage

If high CPU usage is observed across all Storaged instances, the root cause likely falls into one of the following categories.

### (1) CPU Spikes During Data Ingestion

If high CPU usage occurs primarily during data ingestion, the most likely cause is RocksDB compaction [4]. Compaction is an essential process that merges and reorganizes data in RocksDB’s Log-Structured Merge Tree (LSM tree) to optimize read performance. However, it can be resource-intensive.

To mitigate excessive CPU usage during compaction, consider the following optimizations:

* **Reduce compaction concurrency:**
    * Lower `max_subcompactions` and `max_background_jobs` to slow down compaction and distribute CPU load more efficiently.
* **Optimize custom compaction filtering**:
    * In NebulaGraph, expired data is garbage-collected using a **custom compaction filter** [5] when TTL is enabled [6]. This filter scans affected vertices and edges during compaction and verifies whether their TTL has expired. This additional check incurs CPU overhead.
    * The config `min_level_for_custom_filter` determines at which LSM level the custom compaction filter starts processing data.
    * A lower value of `min_level_for_custom_filter` will scan more levels of data and thus increase CPU load.
    * A higher value of `min_level_for_custom_filter` postpones TTL filtering to later stages, which reduces CPU usage but increases the temporary retention of expired data.

Since an excessively high value of `min_level_for_custom_filter` can result in bloated storage and potential availability issues, careful fine-tuning is necessary. The goal is to determine an optimal value that balances CPU efficiency with the retention of expired data. We will explore the impact of accumulated expired data later in this article.

### (2) Persistent High CPU Usage, Regardless of Writes

If high CPU usage persists even when there are no active writes, the cause is likely related to RocksDB read operations or thread contention within Storaged. To diagnose the issue more precisely, we recommend running `perf top` on a high-CPU Storaged instance.

* On physical or virtual machines, running `perf top` is straightforward.
* On Kubernetes deployments, additional privilege changes are required. Our Nebula Operator [7] includes the necessary configurations and can enable `perf top` with a single setting.

If `perf top` shows excessive thread context switching and preemption occurring within Thrift’s internal queues, this indicates over-threading - too many active threads competing for CPU resources. Reducing the number of worker and read handler threads can improve CPU efficiency.

## 3. High Disk I/O Utilization

If IOPS or I/O throughput reaches the disk's limits, query latency can degrade significantly. Identifying the underlying cause is crucial for maintaining performance.

### (1) High I/O During Data Ingestion

If excessive disk I/O occurs only during data ingestion, the likely causes are:
* High data ingestion speed
* High compaction concurrency

To alleviate this, consider:
* Reducing ingestion speed or adjusting the batch size
* Lowering the values of `max_subcompactions` and `max_background_jobs` to limit compaction concurrency

### (2) Constantly High I/O with Storage Errors

If disk I/O remains persistently high and approaches the disk's limit, and error logs such as `RPC failure in StorageClient` with `timeout` or `loadshedding` appear in Graphd, this likely indicates excessive amount of expired data..

In this case, Storaged is scanning the disk excessively to filter out expired data, which significantly increases I/O load. To verify this, check the statistics by running:

```
SUBMIT JOB STATS;
SHOW STATS;
```
If the amount of stale data is twice the normal level or higher, trigger a full compaction to clean up expired data:

```
SUBMIT JOB COMPACT;
```
# Conclusion

Storaged is a critical component of NebulaGraph, and its performance directly impacts query latency and system stability. This article provided insights into how data is stored, partitioned, replicated, and accessed in Storaged, along with best practices for diagnosing and resolving high storage latency.

#Reference

[1] Rocksdb. https://github.com/facebook/rocksdb 

[2] Raft. Ongaro, Diego, and John Ousterhout. "In search of an understandable consensus algorithm." 2014 USENIX annual technical conference (USENIX ATC 14). 2014.

[3] Availability Zone. https://learn.microsoft.com/en-us/azure/reliability/availability-zones-overview?tabs=azure-cli 

[4] Rocksdb Compaction. https://github.com/facebook/rocksdb/wiki/Compaction 

[5] Compaction Filter. https://github.com/facebook/rocksdb/wiki/Compaction-Filter 

[6] TTL in NebulaGraph. https://docs.nebula-graph.io/3.8.0/3.ngql-guide/8.clauses-and-options/ttl-options/

[7] Nebula Operator. https://github.com/vesoft-inc/nebula-operator 





This article explores the architecture of Storaged from the perspective of its underlying storage engine, RocksDB, and shares insights from real production use cases on diagnosing and resolving performance bottlenecks.

When NebulaGraph Slows Down: Diagnosing Storage-Related Performance Issues


# Summary


NebulaGraph is an open-source, distributed, and easily scalable native graph database capable of hosting very large datasets containing hundreds of billions of points and trillions of edges and providing millisecond queries.

Thanks to their unique data model and efficient query performance, graph databases play an important role in many business scenarios. Here are several typical business applications of graph databases:

* **Knowledge Graph**: Businesses and organizations need to build domain knowledge graphs from various data silos to support intelligent Q&A and semantic search.
* **Social Network Analysis**: Social network platforms need to analyze relationships, interests, and interactions between users to offer personalized recommendations and targeted advertisements.
* **Financial Risk Control**: Financial institutions need to monitor anomalous transaction activity, detect potential fraud, and assess credit risk.
* **Recommendation system**: E-commerce and media platforms need to provide personalized product or content recommendations based on the user's browsing history, purchase records, and other information.

NebulaGraph Cloud is a **fully managed cloud service** designed for NebulaGraph, and this article will detail how to realize cost reductions and efficiencies in synergy with AWS offerings.(For further instructions, please [refer to the AWS Marketplace product landing page](https://aws.amazon.com/marketplace/pp/prodview-wctboqxrwqkjy?sr=0-1&ref_=beagle&applicationId=AWSMPContessa)


# Platform architecture and components





## Platform architecture
![image|561x499](https://nebula-website-cn.oss-cn-hangzhou.aliyuncs.com/nebula-website-5.0/share/941.webp)



NebulaGraph Cloud is designed and built on K8S with the following considerations:

* K8S's Operator mode enables the automation of all internal cluster activities, significantly reducing development costs.
* K8S offers a range of abstraction capabilities to streamline the management of compute, storage, and network resources, which can help users avoid vendor lock-in and achieve complete cloud-agnostic
* K8S's inherent features such as scaling up and down, scheduling framework, resource monitoring, and service discovery simplify various management operations.


## Service component


NebulaGraph Cloud is composed of two main parts:


### Control Plane


The control plane provides user console access for organizational management, user rights control, database management, network security settings, monitoring, alerting, and various other features designed to assist users in managing their NebulaGraph clusters.


### Data Plane


The data plane receives commands from the control plane, including resource scheduling, provisioning, versioning, horizontal scaling, specification adjustments, backup and recovery, observability, metering, and additional functions.


## Cost-optimized design


Illustrated with a sample database configuration:


```
apiVersion: apps.nebula-cloud.io/v1alpha1
kind: Database
metadata:
  name: db123456
  namespace: db123456
spec:
  provider: aws
  region: "us-east-2"
  k8sRef:
     name: "k8s-ml65nmjg"
     namespace: "k8s-ml65nmjg"
  tier: standard
  graphInstanceType: NG.C4.M32.D0
  graphNodes: 1
  StorageInstanceType: NG.C4.M32.D50
  StorageNodes: 1
  version: v3.8.2c
```


The database instance is defined using a Custom Resource Definition (CRD), and a database controller manages its operations within the control plane. Dependent compute resources are defined using the CRD NodePool, which is an abstraction of the compute resources of each cloud vendor, and is used to manage NodeGroups in AWS's EKS.As previously mentioned, NebulaGraph is a compute-storage separated architecture, so a database instance will correspond to two NodePool objects.

```
# Graph resource pool
apiVersion: apps.nebula-cloud.io/v1alpha1
kind: NodePool
metadata:
  name: gnp-7d0b156e
  namespace: db123456
spec:
  databaseRef:
    name: db123456
    namespace: db123456
  instanceCount: 1
  instanceType: x
  k8sRef:
    name: k8s-ml65nmjg
    namespace: k8s-ml65nmjg
  labels:
    platform.nebula-cloud.io/database-name: db123456
    platform.nebula-cloud.io/graph-pool: db123456-f24a
  provider: aws
  region: us-east-2
  zoneIndex: 0
# Storage resource pool
apiVersion: apps.nebula-cloud.io/v1alpha1
kind: NodePool
metadata:
  name: snp-59e9cc63
  namespace: db123456
spec:
  databaseRef:
    name: db123456
    namespace: db123456
  instanceCount: 1
  instanceType: x
  k8sRef:
    name: k8s-ml65nmjg
    namespace: k8s-ml65nmjg
  labels:
    platform.nebula-cloud.io/database-name: db123456
    platform.nebula-cloud.io/Storage-pool: db123456-un6g
  provider: aws
  region: us-east-2
  zoneIndex: 0
```



## Specification adjustments

Choosing the appropriate instance size is a more challenging task than expected for both users and service providers. Users frequently struggle to determine the optimal instance size for their needs. For example, as a user's data grows from 100GB to 1TB, they may be uncertain about the required number of CPU cores or the amount of memory necessary at each stage. It is up to the user and the SA to collaborate and ascertain these requirements.

When using fully managed cloud services, we provide an instance specification tuning function, which supports individual tuning of Query nodes or Storage nodes to meet the needs of users in terms of cost control and performance standards. Users can determine whether a single-node processing bottleneck has been reached based on the historical curve of the monitoring panel, and the cloud platform will also issue an internal alert.

![image|561x499](https://nebula-website-cn.oss-cn-hangzhou.aliyuncs.com/nebula-website-5.0/share/8d951d16b31294fcfbf25667fe48bc48.png)





## Horizontal expansion and contraction


Horizontal scale-up and scale-down supports individual tuning of the Query node, which can be regarded as a stateless service. This node can be scaled up or down to manage fluctuations in query traffic. Similarly, the Storage node, responsible for storing graph data and providing read and write capabilities, can also be scaled, with several data slices distributed across each Storage node. Each instance of expansion or contraction necessitates data migration and data slice rebalancing, thereby requiring meticulous operation.

Before proceeding with node expansion, it is essential to prepare the corresponding computing resources. The database controller will send the current desired number of nodes to the infra-controller to trigger the NodeGroup expansion of EKS. Here we do not enable CA or Karpenter for the following reasons:

* Scale-up/down decisions depend on specific cluster conditions and resource requests, and if these conditions are not met, it may not perform the intended scale-up/down operation
* Cross-availability scenarios do not guarantee the expansion and contraction of a given region
* The Pending Pod-based model is not tightly integrated with our business systems.

![image|561x499](https://nebula-website-cn.oss-cn-hangzhou.aliyuncs.com/nebula-website-5.0/share/1725438154945.jpg)

## Automatic elastic expansion and contraction


Supporting different workloads through automatic scaling up/down is a critical goal for us. Since computing and storage are separated, we can increase or decrease CPU and memory resources based on the utilization of each service node.

The Elastic Scaling Service architecture is as follows:

Every 10 minutes, the Elastic Scaling Service calculates the amount of resources that should be allocated to a database instance based on historical and current values of the monitored data and ultimately determines whether compute resources should be increased or scaled down. It can drive both horizontal scaling and vertical scaling (adjusting instance specifications) to ensure that business peaks are popped ahead of time. We will continue to make continuous improvements on this foundation to shorten the time to scale up and scale down by incorporating more metrics and proactive prediction strategies.

![image|561x499](https://nebula-website-cn.oss-cn-hangzhou.aliyuncs.com/nebula-website-5.0/share/873527167f86b6180154c413ddf8e499.png)


# Design for Efficiency Improvement





## Network security access

![image|561x499](https://nebula-website-cn.oss-cn-hangzhou.aliyuncs.com/nebula-website-5.0/share/2debb93e640f5e28273aeef9229a9230.png)

Currently, we offer two types of network connections to our users: network whitelisting and private link private connections. To ensure network security and simplify configuration steps, we introduced a proxy service, ngproxy, between the database instances and the Network Load Balancing (NLB), which takes full advantage of the functionality provided by the NLB. 

The NLB is capable of setting a PPv2 header on every transmitted packet. ngproxy parses these packets to verify whether the user's endpoint ID matches the ID configured in the console, with any mismatched requests being rejected. The same principle applies to the public network. The same principle applies to the whitelisting of public network access. Only if the source address matches the address in the whitelist will it be allowed to pass.






## Backup and recovery


Data backup serves as the primary defense against data loss, whether due to hardware failure, software error, data corruption, or human error, ensuring the safety of your data.

We provide users with both manual and scheduled backups and upload the backup data to AWS's object storage S3. We do not use a backup recovery solution based on cloud storage snapshots, as SST-based backup recovery is more rapid and does not depend on the cloud vendor's underlying services. Note that DDL and DML statements will be blocked during data backup, so it is recommended to perform backup operations during low business peak periods.

Backup data catalog structure:


```
backup_root_url/
- BACKUP_2024_08_20_16_31_43
├── BACKUP_2024_08_20_16_31_43.meta
├── data
│   └── 10.0.0.12:9779
│       └── data0
│           └── 5
│               ├── data
│               │   ├── 000009.sst
│               │   ├── 000011.sst
│               │   ├── 000013.sst
│               │   ├── CURRENT
│               │   ├── MANIFEST-000004
│               │   └── OPTIONS-000007
│               └── wal
│                   ├── 1
│                   │   ├── 0000000000000000001.wal
│                   │   └── 0000000000000000005.wal
.....
│                   ├── 30
│                   │   ├── 0000000000000000001.wal
│                   │   ├── 0000000000000000004.wal
│                   │   └── 0000000000000000005.wal
└── meta
    ├── __disk_parts__.sst
    ├── __edges__.sst
    ├── __id__.sst
    ├── __indexes__.sst
    ├── __index__.sst
    ├── __last_update_time__.sst
    ├── __local_id__.sst
    ├── __parts__.sst
    ├── __roles__.sst
    ├── __spaces__.sst
    └── __tags__.sst
- BACKUP_2024_08_20_19_02_35
```


Recovering data to a new instance of the program, so that you can take full advantage of the elastic expansion of resources on the cloud, specify a point in time after the backup set to quickly pull up a new database instance, and the user can be verified that the new database instance is working properly after the release of the old instance.




## High availability


For those who demand the highest level of service reliability, we offer a cross-availability zone disaster recovery solution. In NebulaGraph, a zone is a collection of service nodes that divide multiple Storage nodes into manageable logical zones to achieve resource isolation. At the same time, the platform service controls the access of Query nodes to replica data within the designated Zone, thus reducing network latency and traffic costs incurred by cross-availability zone communication.

One of the main challenges in managing stateful services across availability zones is the issue of zone affinity of storage volumes. To address this issue, we have taken the approach of placing a NodeGroup in each availability zone. This avoids the possibility that a newly expanded Node may be incorrectly placed in an incorrect availability zone, resulting in the Pod not being scheduled.

Drawing from past user experiences, we also support the solution of expanding capacity individually in a certain availability zone. The cloud-native community's HPA-like solution only solves the problem of the quantity after expansion, but it cannot be expanded to a specified region. Scaling according to the business traffic carried by each region can effectively improve the quality of service. If a region observes a sudden surge in QPS, the elastic scaling service of the data plane will allow the scaling of Query nodes in this region.

![image|561x499](https://nebula-website-cn.oss-cn-hangzhou.aliyuncs.com/nebula-website-5.0/share/a6c9b11cc02fcf83606ea5d3c5ee37f5.png)


# Practical exercises on the cloud




**Welcome to [NebulaGraph Cloud](https://cloud.nebula-graph.io) .** After initiating a subscription and creating a database, the next step demonstrates several ways to access the database:

## Visualization tools

Select an instance from the Database list, go to Data->Graph graph space management, and click Explorer Graph to enter the visualization application.

![image|561x499](https://nebula-website-cn.oss-cn-hangzhou.aliyuncs.com/nebula-website-5.0/share/89b9e3f86138ba8b72bcc6417c3e31e6.png)

Clicking on the Console in the upper right corner opens the console and allows you to execute queries for GQL statements.
![image|561x499](https://nebula-website-cn.oss-cn-hangzhou.aliyuncs.com/nebula-website-5.0/share/da4da5f0e3f63450cffd982bd39791fc.png)

## network whitelisting

On the Overview page of the database instance, click Connect and select the Public method.
![image|561x499](https://nebula-website-cn.oss-cn-hangzhou.aliyuncs.com/nebula-website-5.0/share/60437776c9f1654c165a796afbab220b.png)
When network whitelisting is not configured, the database instance cannot be accessed directly from the public network.


```
$ ./nebula-console -addr nebula-graph-ncqqo19eh0aus73e4un6g.aws.cloud.nebula-graph.io -port 9669 -u dbaas-test@vesoft.com -p $PASSWORD -enable_ssl
Welcome!
(dbaas-test@vesoft.com@nebula) [(none)]> show spaces;
+------------------------+
| Name                   |
+------------------------+
| "genshin"              |
| "hanxiaotest"          |
| "movie_recommendation" |
| "nba"                  |
+------------------------+
Got 4 rows (time spent 602µs/222.883326ms)
Mon, 02 Sep 2024 16:52:39 CST
```

## Privatelink private network connection

Follow the configuration steps for **Create Private Link Endpoint** to determine the VPC ID and Subnet ID where the service resides.

Run the command to create the Endpoint:


```
aws ec2 create-vpc-endpoint --vpc-id <YOUR-VPC-ID>  --region us-east-2 --service-name com.amazonaws.vpce.us-east-2.vpce-svc-04f25889c855f891b --vpc-endpoint-type Interface --subnet-ids  <YOUR-SUBNET-IDs>
```


Log in to the AWS console to view Endpoint status
![image|561x499](https://nebula-website-cn.oss-cn-hangzhou.aliyuncs.com/nebula-website-5.0/share/7cc3c33b5f8e6be1464ce3af6e4d2e0a.png)

Test access within the business VPC
![image|561x499](https://nebula-website-cn.oss-cn-hangzhou.aliyuncs.com/nebula-website-5.0/share/af0b663545e30935f090334da7bb2dac.png)
Next, you can maintain the data on the cloud through official eco-tools according to your business needs.


# Summary and outlook


This paper describes the architectural details of landing a fully managed cloud service for NebulaGraph on AWS based on cloud-native concepts, focusing on how AWS offerings can yield substantial benefits to users, and provide a new solution that combines cost and elasticity advantages for using NebulaGraph in the cloud.

While ensuring the quality of our services, we will persist in exploring possibilities to **reduce user costs and increase ease of use.** Our goal is for users to pay only for the resources they use, **implementing the concept of cost in every detail.**

Beta trials are currently underway, with a maximum spend of $1 per month, and you can subscribe via [AWS Marketplace ](https://aws.amazon.com/marketplace/pp/prodview-wctboqxrwqkjy?sr=0-1&ref_=beagle&applicationId=AWSMPContessa)  or [Sign up for an account](https://cloud.nebula-graph.io).

If you are interested in NebulaGraph Cloud, please [join the group](https://join.slack.com/t/nebulagraph/shared_invite/zt-2k1eawak2-00D7XxOIZr8mDt0R4JfsSw) to unlock more DBaaS-related content. 




This paper describes the architectural details of landing a fully managed cloud service for NebulaGraph on AWS.

NebulaGraph Cloud on AWS：Auto Scale, Start Free

In the rapidly evolving digital landscape, Database-as-a-Service (DBaaS) has emerged as a pivotal solution for organizations seeking to streamline their database management. The rise of DBaaS is closely related to the popularization of cloud computing. As enterprises become increasingly dependent on data, DBaaS has become an important part of IT infrastructure, providing functions such as data backup and recovery, scalability, and performance monitoring.

# What is DBaaS

Essentially, DBaaS is a fully programmable database system deployed in a public cloud and managed by the DBaaS provider. It is designed to be automated, highly available, secure, and requires minimal routine maintenance from the user's side. This service model simplifies database management by handling deployment, management, and operations, allowing end-users to concentrate on their core business objectives and application development. 

# Comparison between DBaaS and traditional database

Below is the comparison table in English, highlighting the key differences between Database-as-a-Service (DBaaS) and traditional databases from the perspectives of cost, risk, efficiency, and risks as well as challenges:

| Aspect          | Traditional Databases                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                      | DBaaS (Database-as-a-Service)                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                      |
|-----------------|----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|
| Costs           | Requires significant upfront investment in hardware, software licenses, and employment of DBAs for maintenance, leading to continuous operational costs.                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        | Typically follows a pay-as-you-go model, reducing hardware costs and avoiding large initial investments, transforming CapEx to OpEx, and allowing for more efficient resource allocation.                                                                                                                                                                                                                                                                                                                                                                                                                                                            |
| Risk            | Enterprises bear the risks of maintenance and upgrades, including data security, system compatibility, and backup recovery.                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                | DBaaS providers manage database maintenance, upgrades, and security patches, reducing the risks associated with technical updates and system maintenance. Automated backup and disaster recovery features also mitigate the risks of data loss and system failures.                                                                                                                                                                                                                                                                                                                                                 |
| Efficiency      | Deployment and configuration can take a long time and require specialized knowledge for management.                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                      | Enhances efficiency through automated management tasks and rapid deployment capabilities. Allows users to quickly configure and scale database resources through self-service portals, accelerating development and operational processes.                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                              |
| Risks and Challenges | In certain situations, such as when there are complex database logical relationships or when the database needs to be bound to specific workloads, traditional databases might be a better choice. | There is a risk of vendor lock-in, which may limit the ability of enterprises to migrate or change service providers in the future.                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                               |

# Benefits of DBaaS

DBaaS (Database-as-a-Service) is particularly beneficial for companies without a dedicated database team, with the following detailed advantages:

- **Simplified Database Management**: DBaaS allows for easy management of database instances through a user-friendly control panel, including operations such as creation, scaling, backup, and recovery, without the need for in-depth knowledge of database technical details.

- **Cost Reduction**: DBaaS eliminates the costs associated with purchasing, configuring, and maintaining hardware equipment, as well as hiring professionals, enabling businesses to utilize resources more effectively.

- **Automated Maintenance**: Cloud service providers take care of automatic backup, monitoring, and upgrades for the database, ensuring high availability and stability.

- **Enhanced Security**: DBaaS providers typically implement strict security measures, including data encryption, authentication, and access control, to protect user data from threats.

- **Rapid Deployment and Configuration**: DBaaS allows developers and IT professionals to quickly establish configuration and provisioning standards, communicating with the database through simple APIs or low-code applications, without worrying about the database itself.

- **Future-Proofing**: DBaaS can scale quickly with the expansion of the business, without the need to purchase additional storage, ensuring that the database infrastructure always aligns with business needs.

- **Professional Database Management**: DBaaS solutions are managed by a team of experts from the provider, who are responsible for monitoring, backup, recovery, node repair, cluster resizing operations, node management, applying hotfixes, and upgrades.

- **Reduced Hassle and Overhead**: With DBaaS solutions, teams do not need to develop or hire specialized personnel, such as database administrators, DevOps, and security personnel to manage the database. There is also no need to select hardware, purchase it, wait for it to arrive, install it, or set it up, or maintain it, thus saving on the costs of hardware data center technicians.

- **Disaster Recovery**: Distributed DBaaS typically replicates your data across multiple availability zones within a region, so there is no single point of failure.  Adding more replicas and expanding clusters to multiple data centers are allowed as needed.

- **Ease of Use**: DBaaS service providers usually offer user-friendly interfaces and tools that make it easy for users to manage and access their databases, even without technical expertise.

- **Professional Support**: DBaaS providers typically offer technical support to help users troubleshoot any database issues that may arise, which is a valuable resource for users who may not have in-house IT staff or expertise.

# Who Should Consider DBaaS?

Both enterprises and developers can benefit from DBaaS. For **enterprises** DBaaS offers a way to manage large volumes of data efficiently while maintaining high availability and performance . **Developers**, on the other hand, can leverage DBaaS for rapid application development, testing, and deployment without the complexity of managing databases.

# What factors should you think about when adopting DBaaS?

When selecting DBaaS (Database-as-a-Service) as its data management solution, a company should consider the following key factors to determine if it meets its specific needs:

- **Technical Team's Expertise**: If a company lacks a professional database management team, DBaaS can provide convenient database management services, including automatic backup and recovery, allowing the company to focus more on the development of its core business.

- **Specific Scenarios of Project Requirements**: DBaaS is suitable for application scenarios that require rapid deployment and flexible scaling, such as temporary database needs for continuous integration or backend testing.

- **Applicability to Micro-services Architecture**: In a production environment that adopts a micro-services design composed of numerous databases, DBaaS can provide the capability to quickly go into production.

- **Cost-Benefit Analysis**: DBaaS can bring economic benefits by reducing the costs of hardware and software upgrades, lowering capital expenditures, and simplifying database management.

- **Trade-off of Control**: Using DBaaS may mean giving up direct control over databases and servers in some cases, as the cloud service provider is responsible for the underlying infrastructure and security.

- **Network Dependency**: DBaaS requires a stable Internet connection; any network issues can affect the availability and performance of the database.

- **Security Considerations**: Companies need to assess the security measures of DBaaS providers to ensure the safety of sensitive data and compliance with data protection regulations.

- **Risk of Vendor Lock-in**: Choosing DBaaS may expose companies to the risk of vendor lock-in, especially if the service is tightly integrated with a specific cloud platform.

- **Performance Requirements**: For applications that require high performance and large-scale processing capabilities, the performance of DBaaS may need to meet the demands of specific workloads.

- **Testing and Prototyping Exploration**: Before making a final decision, companies should consider creating and exploring DBaaS prototypes to assess whether their performance and functionality meet the actual needs of the application.

# Conclusion

The global DBaaS market is projected to experience significant growth, driven by the increasing demand for cost-efficient database management solutions and the widespread adoption of cloud-based services across various industries. As organizations continue to prioritize agility, scalability, and data-driven insights, DBaaS is set to become an integral part of the digital transformation journey.

For anyone considering DBaaS, it's crucial to evaluate the specific needs of your organization, the type of DBaaS that aligns with your tech stack, and the potential for scalability and integration with existing systems. With the right choice, DBaaS can be a powerful enabler of business growth and innovation.

This blog introduces what database-as-a-service is and why enterprises and developers should consider it as an option.

Why Database As A Service

Machine Learning has become the fundamental pillar of Artificial Intelligence. And companies are putting it into use cases that are delivering iconic results. Whether it's providing recommendations to shoppers online or helping in making decisions related to cooling of data centers, this technology is simply revolutionary.

However, as we marvel at the rewarding benefits of ML, we must never forget that Machine Learning is driven by data. But there's a catch: the data ought to be sourced correctly, be clean and connected. Knowledge graphs solve the catch, and this is where the connection with machine learning comes in.

You see, when you have a lot of information from which you need to infer important relationships, the traditional simplistic methods like copying records and pasting them in some spreadsheet don't cut it. Neither can web scraping do it, as much as it's helpful for collecting information especially from the web. To solve such challenges, the intersection between knowledge graphs and machine learning becomes extremely important.

For illustration purposes, put yourself in the shoes of a data analyst tasked with ranking musicians based on a set of defined parameters. Some of these parameters could be the number of each musician’s songs that have been featured on top of at least x charts, number of major events the musician has attended, annual income threshold, etc. Now, if you were to get data relating to these items for just one musician, then the work would be easy. But what if you need to get this data for thousands of musicians?  The amount of work is voluminous. Luckily, knowledge graphs can work with machine learning to make such work a piece of cake - and this is just one small example. It's a magical connection as we'll discover in the rest of this article.

**Also Read:** [The Power of Graph Databases to Unleash the Full Potential of AI](https://www.nebula-graph.io/posts/graph-databases-and-ai-applications)


# The knowledge graph


A knowledge graph is a structured representation of knowledge. Information is organized in a graph format, linking entities, facts, and relationships to provide context and facilitate understanding. This way, the knowledge is enhanced for specific uses. 
For example, Google's knowledge graph is used to enhance search results. Other top tech companies as well as many other corporations and small to medium businesses also use knowledge graphs to achieve two key goals: 
1. Better user experience 
2. Better organization of information for efficient retrieval.

Knowledge graphs are being used in real-world use cases by an increasing number of businesses of all sizes in almost all industries.

**Also Read:** H[ow to Build a Knowledge Graph](https://www.nebula-graph.io/posts/how-to-build-knowledge-graph)

# Machine learning

As we know, machine learning is the development of computer systems (popularly known as models) that have the ability to learn from data and eventually perform tasks without being instructed directly.  

# Knowledge Graph + Machine Learning - The Big Connection

You may have very good data sources with right information that will improve the quality of your ML algorithms. But you need to easily feed this data to the machine learning models. Knowledge graphs make this much easier to accomplish - compared to other alternative approaches. They do this by helping in modeling domain knowledge and connecting disparate sources of data.

Knowledge graphs bring the best out of machine learning models. With knowledge graphs, the results that machine learning models give are better refined with and deliver high levels of trust because of rich explainability. 

# How the Connection Between Knowledge Graphs and Machine Learning Works

Simply put, knowledge graphs enhance or enrich machine learning models. With this enhancement, the data is ripe for easy consumption by all sorts of ML models and other systems. The result? Less time sourcing data, cleaning and repurposing it for ML consumption. This is achieved through various approaches including  augmentation, mapping and storage. For example, knowledge graphs can augment training data in situations where the data that a machine learning model is using is insufficient.

Knowledge graphs also capture critical metadata. This metadata is useful to ML, as it ensures that the results the model gives are based on accurate facts that are classified with precision.

A knowledge graph can also combine results from different ML models to come up with a more powerful model that can inform transformative decisions such as the introduction of new products, risk discovery, etc.

To accomplish all these, the first thing a knowledge graph does is that it brings out the deep relationships that are inherent in data. Next, they add semantics to the data to enhance its meaning and context. These two steps give rise to intelligence, transforming the data from a boring mountain of information to an intelligent, easy to use source of rich knowledge.

"Context" here means the additional information or background that helps understand the significance or meaning of the data. This allows machine learning models to make more informed decisions or predictions.

Context has been elusive in the traditional approaches that ML models have been using. It's not easy to process data structures and connections. But with knowledge graphs, this is easy.

With this understanding, we'll now discuss the workings of knowledge graphs from the lens of the core areas where the combination with machine learning delivers big results.

## 1. Knowledge graphs enhance data collection & cleaning

Data collection is the giant step in the all important relationship between knowledge graphs and machine learning. Of course, this data can come from anywhere. Web scraping is the most common data collection method if you are building large knowledge graphs that will be used by millions of people, especially the public. Web scraping is basically the use of a web crawler or a bot to copy the information you need from the web to the database, e.g a graph database. But if you are going to collect data from various sources within the company, then you will likely employ more alternative approaches. For data that is going to be utilized by machine learning models, a knowledge graph fits the bill. 

The process of collecting and cleaning data before channeling it to use is one that data scientists have dreaded for a long time as it was always manual. Commonly known as data wrangling, data scientists spent so much time looking for and organizing the data sources, before extracting the right information from these sources and eventually feeding it for use - like for training ML models. It used to be such an intensive exercise.

Knowledge graphs enhance data sourcing. Specifically, they are deployed to track the source of the data (where it's coming from). In doing the tracking, knowledge graphs provide answer to these fundamental questions:

* The origin of the data
* The different changes the data has undergone
* Where the data has been used or is being used
* Who has used the data or who is using it

This audit trail is useful as well for industries where compliance is paramount, like healthcare and finance industries that are heavily scrutinized by regulators.


## 2. Knowledge graphs enhance data accuracy & security

Without accuracy and security entrenched into the data that machine learning models rely on for training, the results will not be of value. Knowledge graphs deliver this component through visualization capabilities.

Instead of operating on vectors, a machine learning model that incorporates knowledge graphs operates from a  graph structure. What this means is that the models can always leverage new sets of information, making them even more accurate in terms of the results they provide.

## 3. Knowledge graphs enhance ML model training

Machine Learning algorithms need to be fed with data to train on. Without context, the training becomes complex and this restricts the models in terms of which use cases they can be deployed in. But knowledge graphs bring context, and this solves the challenge. This context empowers machine learning models to be more efficient in prediction. Besides, it widens the scope of use for the ML system.

The entry of knowledge graphs has also transformed the training process completely. They have made it possible to train models on unified data - meaning the data is free of conflicting  definitions. 

This is possible through the use of what we call an inference engine. With an inference engine, all that is needed is to apply rules on the data - instead of copying the underlying data. So if, for example,  you have multiple data sets that contain similar data but named differently, an inference engine unifies these datasets and pulls them as one data. This saves an enormous amount of time.

## 4. Knowledge graphs enhance quality analysis

When you finally have a complete machine learning model, it needs to be analyzed to establish if it's truly delivering value. Is it performing to expectations? Is it making the correct predictions?

This is the investigation stage, and knowledge graphs make it so easy to carry out thanks to the relationship information that is already included. Domain experts can use built-in features to establish all the facts. They can troubleshoot and debug outlier outcomes or test hypotheses.

# Use cases for knowledge graphs with machine learning

Across many industries, companies are finding interesting use cases that harness the power of knowledge graphs with machine learning. 

From simple applications to complex ones that deliver immense value for the organization, here are some examples:

* **Predictive maintenance:** This is mostly applicable in the manufacturing industry. Manufacturing companies can extract important information from equipment and machinery documents. This information is then added to a knowledge graph. The knowledge graph leverages relationships to give context to the data. This context  is then applied to the machine learning models. With this context, the models can accurately predict when machines are due for maintenance. This saves companies a lot of time plus expenses in addition to improving productivity.
* **Shopping bot:** eCommerce companies can leverage knowledge graphs to add context to the models that power tools like recommendation engines so that they can make more refined decisions with regard to user intent.

The connection between knowledge graphs and machine learning is also symbiotic. For example, machine learning can be used to make it easy to construct knowledge graphs. A good example is extracting entities and relations.

# How NebulaGraph Enables the Augmented Power of Knowledge Graph

NebulaGraph, an open-source distributed graph database, is built for super large-scale graphs with milliseconds of latency. Adhering to this principle, NebulaGraph introduced Graph RAG, an acronym for Retrieval-augmented generation, which is an AI framework for enhancing the quality of responses that are generated by Large Language models. This solution pioneered the Text2Cypher technology, making it possible to build and query knowledge graphs based on natural language.

With this, you get to enjoy powerful capabilities in data management, easy understanding of semantics, and extraction of information. Learn more about NebulaGraph and Large Language Models.

**Also Read:** [Graphs and Language](https://www.nebula-graph.io/posts/graph_and_language)

# Conclusion

The key takeaway is that since knowledge graphs offer an intuitive and logical way to capture  relationships in complex data and convey the meaning of those relationships in a simple way,  they can be used in combination with Machine Learning to introduce intelligence to the data that ML models use to train. This gives the models the context that they need to give results that are more accurate and explainable. This is the essence of bringing knowledge graphs to machine learning.

In short, knowledge graphs are exactly what companies needed to realize the full potential of AI systems. This ability has been elusive even as more and more organizations embraced AI. But with the entry of knowledge graphs, we are going to witness an era of contextual AI where AI will fulfill its promise as the ultimate solution for complex challenges in organizations.

Essentially, when you combine knowledge graphs with machine learning, you are extending the capabilities of machine learning beyond the ordinary. It's like adding advanced skills to employees through excellent training and certification. This way, the results provided by the ML models will be more solid, grounded, explainable and with high trust levels.

When you combine knowledge graphs with machine learning, you are extending the capabilities of machine learning beyond the ordinary.

The Connection Between Knowledge Graphs and Machine Learning


![Overall Architecture - NebulaGraph](https://user-images.githubusercontent.com/57335825/87115631-a8852580-c228-11ea-877a-b48ba92fbb8b.png)

 NebulaGraph is an [open-source](https://en.wikipedia.org/wiki/Open-source_software) distributed [graph database](https://www.nebula-graph.io) solution. As an open-source project, we would like those who are interested in graph databases to know as much as possible about it. This includes how NebulaGraph is designed and why it is a highly performant database.

As a result, we have developed a series of graph database architecture articles. In them, we are going to cover three areas. First, we will provide a high-level overview of the architecture of NebulaGraph – the focus of this article. Next, we will cover how NebulaGraph’s storage engine works. And finally, we will illustrate how NebulaGraph’s query engine works, including how we have designed nGQL, our graph query language.

# NebulaGraph Database Architecture Diagram

![NebulaGraph Architecture Diagram](https://user-images.githubusercontent.com/38887077/76277232-1ba27d80-62c3-11ea-9389-cc1aca329c7b.png)

In the diagram above, there is a fully deployed NebulaGraph cluster that contains three services. They include a Meta Service, Query Service, and Storage Service. Each service has its own executable binary. These [binaries](https://github.com/vesoft-inc/nebula/releases) can be deployed either on the same set of hosts or on different hosts.

## Meta Service

In the below diagram, on the right side of the architecture diagram, it shows a cluster of Meta Service. The Meta Service follows a leader/follower architecture. The leader is elected by all Meta Service hosts in the cluster and serves all traffic. Followers stand by and take the updates replicated from the leader. Once the leader dies, one of the followers will be re-elected as the new leader.

![Meta Service](https://user-images.githubusercontent.com/38887077/76277238-1e9d6e00-62c3-11ea-9d10-8391c26b0b20.png)

The Meta Service does not only store and provide meta information about the graph, such as schema and graph partition information. It also takes the role of the coordinator to orchestrate the data movement and to force the leader shift.

## Separation of Query and Storage Layers

![Separation of Query and Storage Layers](https://user-images.githubusercontent.com/38887077/76277242-2230f500-62c3-11ea-8566-4b6be458adee.png)

In the above diagram, to the left of the Meta Service, is NebulaGraph’s main services. NebulaGraph divides the query execution and the graph storage into two separate services. Above the dotted line is the Query Service. Below the dotted line is the Storage Service.
This separation has several benefits. The most straightforward benefit is that the query layer and storage layer can be expanded or shrunk independently. The separation also makes the linear horizontal expansion possible. Last but not the least, the separation provides an opportunity to make it possible for the Storage Service to serve multiple computation layers.
The current Query Service can be considered a high-priority computation layer. Meanwhile an iterative computation framework could be another one.

## Stateless Query Layer

![Stateless Query Layer](https://user-images.githubusercontent.com/38887077/76277245-25c47c00-62c3-11ea-912b-5de3ce4e18fe.png)

As to the Query Service, each individual Query Service host runs a stateless query engine. The Query Service hosts will never communicate with each other. They only read the meta information from the Meta Service and interact with the Storage Service.

This design makes sure the Query Service cluster can be easily managed by Kubernetes (aka. k8s) or be deployed on the cloud. A cloud deployment is already available for NebulaGraph.
See [how to deploy NebulaGraph on Kubernetes](https://www.nebula-graph.io/posts/how-to-deploy-nebula-graph-in-kubernetes).

There are two ways to balance the Query Service load. The most common way is to place a [load balancer](https://www.nebula-graph.io/posts/nebula-graph-storage-banlancing-data-migration) in front of the Query Service. The second way is to configure the client library with all Query Service hosts’ IP addresses. The client will randomly pick one to connect to.

Each query engine takes the request from the client, parses the statement, and generates an Abstract Syntax Tree (AST). Then the AST will be handed over to the execution planner and the optimizer. The final AST will be passed to the executors.

Below is a flow chart of how NebulaGraph’s query engine works. For a detailed explanation, please refer to [an introduction to the query engine](https://www.nebula-graph.io/posts/nebula-graph-query-engine-overview).

![image](https://user-images.githubusercontent.com/38887077/78201029-28318480-74c3-11ea-90ed-03e9c2ca25d4.png)

## Shared-nothing Distributed Storage Layer

![Shared-nothing Distributed Storage Layer](https://user-images.githubusercontent.com/38887077/78201059-3a132780-74c3-11ea-95a0-61249c1566a4.png)

The Storage Service is designed to be a [shared-nothing distributed architecture](https://en.wikipedia.org/wiki/Shared-nothing_architecture). Each storage host has multiple local key/value stores as the physical data storage.

A quorum consensus protocol (we chose [RAFT](https://raft.github.io/) over paxos due to its simplicity) is built on top of the key/value stores. Together, they provide a distributed key/value store. On top of this distributed key/value store, a graph semantic layer is provided. It translates the graph operations into key/value operations. The graph data (vertices and edges) are hashed into multiple partitions by the rule (vertex_id % the_number_of_partitions).
A partition is a virtual set of data in NebulaGraph. These partitions are allocated to all storage hosts. The allocation information is stored in the Meta Service and can be accessed by storage hosts and query hosts.

# Conclusion

This bird’s eye view into NebulaGraph covers the architecture to provide a basic understanding of how the distributed graph database works. For a more detailed introduction to the major components of the system, please refer to:

- [An introduction to NebulaGraph's Storage Engine](https://www.nebula-graph.io/posts/nebula-graph-storage-engine-overview)
- [An Introduction to NebulaGraph's Query Engine](https://www.nebula-graph.io/posts/nebula-graph-query-engine-overview)

If you have anything to share about distributed systems or graph databases, please feel free to leave us a comment below. We look forward to hear from you.

# You might also like

1. [The Review on Graph Database](https://www.nebula-graph.io/posts/review-on-graph-databases)
1. [Graph Query Language Comparison Series - Gremlin vs Cypher vs nGQL](https://www.nebula-graph.io/posts/graph-query-language-comparison-cypher-gremlin-ngql)
2. [Graph Database vs Relational Database](https://www.nebula-graph.io/posts/graph-database-vs-relational-database)
3. [What are the Benefits of Graph Databases](https://www.nebula-graph.io/posts/why-use-graph-databases)


NebulaGraph is an open-source, distributed, highly performant graph database. This article explains its technical architecture in detail.

NebulaGraph Database Architecture — A Bird’s Eye View


![Understanding Subgraph in NebulaGraph 2.0](https://user-images.githubusercontent.com/57335825/124857891-aabac500-dfdf-11eb-8461-f77ffe6f6136.png)

# Introduction

In An Introduction to [NebulaGraph 2.0 Query Engine](https://nebula-graph.io/posts/nebula-query-engine-introduction/), I introduced how the query engine differs between V2.0 and V1.0 of NebulaGraph.

![NebulaGraph Architecture Change](https://user-images.githubusercontent.com/57335825/124858026-e3f33500-dfdf-11eb-8f0f-0821af5d84b7.png)

As shown in the preceding figure, you can see that when a query statement is sent from the client, how the query engine parses the statement, generates an AST, validates the AST, and then generates an execution plan. In this article, I will introduce more about the query engine through the new subgraph feature in NebulaGraph 2.0 and focus on the execution plan generation process, to help you understand the source code better.

# Definition of Subgraph

A subgraph of a graph is composed of a subset of the graph's vertices and a subset of its edges. When a starting vertex is given, a traversal starts from it and expands following the specified edge type until all the vertices at the specified number of hops are reached. All the reachable vertices and edges form a subgraph. 

# Syntax of Subgraph

```shell
GET SUBGRAPH [<step_count> STEPS] FROM {<vid>, <vid>...} [IN <edge_type>, <edge_type>...]
[OUT <edge_type>, <edge_type>...] [BOTH <edge_type>, <edge_type>...]
```

- step_count: Specifies the number of hops from the starting vertex to obtain a subgraph consisting of vertices and edges that are reached at 0 to `step_count` hops. It must be a non-negative integer. The default value is 1.
- vid: Specifies the ID of the starting vertex.
- edge_type: Specifies the edge type. `IN`, `OUT`, and `BOTH` can be added to specify the direction of the edges from the starting vertex. By default, `BOTH` is used.

# Implementation of Subgraph

When the query engine receives a `GET SUBGRAPH` statement, the Parser, composed of Flex and Bison, will extract the necessary content from the query statement according to the specified rule, that is, the `get_subgraph_sentence` rule defined in [parser.yy](https://github.com/vesoft-inc/nebula-graph/blob/master/src/parser/parser.yy), and then generate an AST, as shown in the following figure.

![NebulaGraph Subgraph Implementation](https://user-images.githubusercontent.com/57335825/124858306-5e23b980-dfe0-11eb-8f66-bd15790a0eef.png)

And then in the Validate stage, the generated AST is validated, aiming to make sure that all the inputs from users conform to the syntax rule. For more information, see [An Introduction to NebulaGraph 2.0 Query Engine](https://nebula-graph.io/posts/nebula-query-engine-introduction/). When the validation is successful, the content of the AST will be extracted and an execution plan will be generated.

How is the execution plan generated? Database solutions may differ in the form of the execution plan, but their implementations are the same, that is, depending on which operators are used and how the query layer interacts with the storage layer, because data needs to be taken from the storage layer for each query statement. In NebulaGraph, the query engine interacts with the storage layer through RPC (fbthrift), of which the interfaces are defined in the `interface` directory of the `common` repository. `getNeighbors` and `getProps` are the key interfaces.

In fbthrift, `getNeighbors` is defined as follows:

```shell
struct GetNeighborsRequest {    
    1: common.GraphSpaceID                      space_id,
    2: list<binary>                             column_names,
    3: map<common.PartitionID, list<common.Row>>
        (cpp.template = "std::unordered_map")   parts,
    4: TraverseSpec                             traverse_spec
}
```

To understand the variables in the preceding structure, see the comments in the source code: [https://github.com/vesoft-inc/nebula-common/blob/master/src/common/interface/storage.thrift](https://github.com/vesoft-inc/nebula-common/blob/master/src/common/interface/storage.thrift).

It mainly aims to enable this process:

1. The query engine passes the starting vertex and the specified edge types according to the defined structure.
2. In the storage layer, the starting vertex is located.
3. The properties of the vertex and its outgoing edges are assembled into a table and the table is returned to the query engine. The table format is defined in `GetNeighborsResponse`. For more information, see [https://github.com/vesoft-inc/nebula-common/blob/master/src/common/interface/storage.thrift](https://github.com/vesoft-inc/nebula-common/blob/master/src/common/interface/storage.thrift).
4. The query engine extracts the necessary content from the table.

For example, for the NBA dataset, when `Tim Duncan` and `Manu Ginobili` are given as the starting vertices and `like` of both directions are given as the edge type, we can get the information of `$^.player.name`, `like._dst`, `$$.player.name`, and `like.likeness` as follows:

![NebulaGraph Subgraph](https://user-images.githubusercontent.com/57335825/124858735-32ed9a00-dfe1-11eb-8bb1-057bed6ac316.png)

Because the traversal is done in both directions, `+ like` in the fourth column of the preceding table represents outgoing edges, and `- like` in the fifth column represents incoming edges.

In NebulaGraph, edges are stored with their source vertices in the storage layer, so all the properties of a vertex and its outgoing edges can be obtained through the `GetNeighbor` interface. However, if you want to obtain the property information of the destination vertices of these edges, the `getProps` interface is needed. A `FETCH` statement also needs this interface to obtain the property information of a vertex or an edge. For more information about `GetPropRequest`, see [https://github.com/vesoft-inc/nebula-common/blob/master/src/common/interface/storage.thrift](https://github.com/vesoft-inc/nebula-common/blob/master/src/common/interface/storage.thrift).

## Execution Plan

With the preceding interfaces, an execution plan can be generated. The operators, `start`, `getNeighbor`, `subgraph`, `loop`, and `dataCollect`, are necessary.

- start: A leaf node of an execution plan. It does nothing but informs the scheduler that no more operator can be relied upon. In other words, this is the termination condition in the recursive algorithm.
- loop: Equivalent to the `WHILE` loop in C language. It is composed of three parts: `depend`, `condition`, and `loopBody`. `depend` is used in multi-statements and the PIPE and no more details about it is involved in this article. `condition` is equivalent to the termination condition. `loopBody` is equivalent to the loop body in a `WHILE` loop.
- subgraph: Responsible for extracting the properties of `_dst`, the destination vertex, from the `getNeighbor` result, filtering out the destination vertices that have been traversed to avoid repeatedly fetching data from the storage layer, and then using them as the input for the next hop executed by `getNeighbor`.
- datacollect: Responsible for assembling the properties of the reachable vertices and their edges into the vertices and edge types.

For more information about these operators, see the source code: [https://github.com/vesoft-inc/nebula-graph/tree/master/src/executor](https://github.com/vesoft-inc/nebula-graph/tree/master/src/executor).

Let's take the graph in the following figure as an example to introduce how a subgraph is generated.

![Build a Subgraph in NebulaGraph](https://user-images.githubusercontent.com/57335825/124859204-0a19d480-dfe2-11eb-8a1d-c83af10038fe.png)

**Single-hop traversal**

It is easy to start from Vertex A and traverse along the `like` edges at one hop for the vertices and edges. In this scenario, only getNeighbor and dataCollect are needed. The execution plan is as follows.

![Single-hop traversal](https://user-images.githubusercontent.com/57335825/124859285-37668280-dfe2-11eb-9021-ab538e2ac90b.png)

**Multi-hop traversal**

The single-hop traversal is a special case of the multi-hop traversal, so it can be treated as part of a multi-hop traversal. In a three-hop traversal starting from Vertex A along the `like` edges at three hops, the destination vertices can be extracted after `getNeighbor` is executed and these vertices can be the starting vertices to call the `getNeighbor` interface. Two loops are sufficient for such a scenario. The number of hops can be set as the termination condition in `loop`. Therefore, the execution plan is as follows.

![Multi-hop traversal](https://user-images.githubusercontent.com/57335825/124859410-77c60080-dfe2-11eb-836e-3450dfa005bd.png)

**Input and output**

Generally, the input of each operator is the output of the one that it depends on, so according to the dependencies represented in the execution plan, you can see the input and output of each operator. However, in some cases, for example, in a multi-hop traversal, the input of each `getNeighbor` is the destination vertex that is reached following an edge, that is, the output of the `subgraph` operator, so the output of `subgraph` is the input of `getNeighbor`. Such a dependency is different from that shown in the preceding figure. Therefore, the input and output of each operator must be set separately. From [An Introduction to NebulaGraph 2.0 Query Engine](https://nebula-graph.io/posts/nebula-query-engine-introduction/), you know that the input and output of each operator are stored in a hash table, of which values are of the `vector` type. The following ResultMap table is an example.

![ResultMap](https://user-images.githubusercontent.com/57335825/124859705-f4f17580-dfe2-11eb-8e9e-5b7bbadc5686.png)

- The starting vertex is stored in ResultMap["StartVid"].
- The input of getNeighbor is ResultMap["StartVid"] and its output is stored in ResultMap["GN_1"].
- The input of getNeighbor is ResultMap["StartVid"] and its output is stored in ResultMap["GN_1"].
- No data is generated by loop. It is used as a logic loop, so neither input nor output is necessary.
- The input of dataCollect is ResultMap["GN_1"] and its output is stored in ResultMap["DATACOLLECT_2"].

At this time, the getNeighbor operator puts the result of each loop at the end of the vector in ResultMap["GN_1"], and the subgraph operator takes the value from the end of the vector in ResultMap["GN_1"] and then stores the starting vertex for the next hop in ResultMap["StartVid"].

After the first hop, the result of ResultMap is as follows.
​
![ResultMap](https://user-images.githubusercontent.com/57335825/124859885-3eda5b80-dfe3-11eb-8eff-e0705c0404e9.png)

To make the result clearer, only the properties of `_dst` are shown as the result of `getNeighbor`. In the actual result, the properties of all the edges and the starting vertex are listed, as show in Table 1.

`subgraph` receives "GN_1" as its input, extracts the properties of `_dst`, and then stores the result in "StartVid".

After the second hop traversal, the ResultMap is as follows.

![ResultMap](https://user-images.githubusercontent.com/57335825/124860033-882aab00-dfe3-11eb-8237-0987c712006a.png)

After the third hop traversal, the ResultMap is as follows.

![ResultMap](https://user-images.githubusercontent.com/57335825/124860085-a2fd1f80-dfe3-11eb-8f14-54aaaa0950ca.png)

Finally, `dataCollect` takes all the vertex sets and edge sets traversed in the process, assembles them into the final result, and returns it for users.

# Example

In this section, I will use an example to show the execution plan structure of a subgraph in NebulaGraph 2.0:

1. Open Nebula Console.
2. Switch to the `nba` graph space. 
3. Run `EXPLAIN format="dot" GET SUBGRAPH 2 STEPS FROM 'Tim Duncan' IN like, serve`. Data of the DOT format is generated on Nebula Console.
4. Open the [Graphviz Online](https://dreampuf.github.io/GraphvizOnline/) website and copy and paste the DOT data on it.

The execution plan is shown as follows.

![Result in DOT format](https://user-images.githubusercontent.com/57335825/124860296-fc654e80-dfe3-11eb-86fc-589ed9a3babe.png)

In this plan, `depend` of `loop` depends on `Start_0`. However, because there is no multi-statement or PIPE, it is not necessary.
​
Welcome to join the NebulaGraph [Slack](https://join.slack.com/t/nebulagraph/shared_invite/zt-7ybejuqa-NCZBroh~PCh66d9kOQj45g) channel to learn more about NebulaGraph.


This article introduces the query engine, the execution plan generation process in particular, through the new subgraph feature in NebulaGraph 2.0 to help you understand the source code better.

Understanding Subgraph in NebulaGraph 2.0


![An Introduction to NebulaGraph 2.0 Query Engine](https://user-images.githubusercontent.com/57335825/111279545-c20f2480-8675-11eb-8699-a8429c237dec.png)

# Introduction

Compared with V1.0, NebulaGraph, a distributed graph database, has been significantly changed in V2.0. One of the most obvious changes is that in NebulaGraph 1.0, the code of the Query, Storage, and Meta modules are placed in one repository, while from NebulaGraph 2.0 onwards, these modules are placed in three repositories:

* `nebula-graph`: Mainly contains the code of the Query module.
* `nebula-common`: Mainly contains expression definitions, function definitions, and some public interfaces.
* `nebula-storage`: Mainly contains the code of the Storage and Meta modules.

This article introduces the overall structure of the Query layer and uses an nGQL statement to describe how it is processed in the four main modules of the Query layer.

# Architecture

This figure shows the architecture of the Query layer. It has four submodules:

* Parser: Performs lexical analysis and syntax analysis.
* Validator: Validates the statements.
* Planner: Generates and optimizes the execution plans.
* Executor: Executes the operators.

![The architecture of the Query layer](https://user-images.githubusercontent.com/57335825/111279912-2af69c80-8676-11eb-8377-492a0955c3cd.png)

# Source Code Hierarchy

Now, let's look at the source code hierarchy under the`nebula-graph`repository.

```plain
|--src
    |--context     // contexts for validation and execution
    |--daemons 
    |--executor    // execution operators
    |--mock
    |--optimizer   // optimization rules
    |--parser      // lexical analysis and syntax analysis
    |--planner     // structure of the execution plans
    |--scheduler   // scheduler
    |--service
    |--util        // basic components
    |--validator   // validation of the statements
    |--visitor
```

#  How a Query is Executed

Starting from the release ofNebulaGraph 2.0-alpha, nGQL gets to support vertex IDs of the`String`type. It is working to support vertex IDs of the`Int`type in NebulaGraph 2.0 to get compatible with NebulaGraph 1.0.

To introduce how the Query layer works, let's take an nGQL statement like`GO FROM "Tim" OVER like WHERE like.likeness > 8.0 YIELD like._dst`as an example. Its data flow through the Query layer is shown in the following figure.

![How a Query is Executed](https://user-images.githubusercontent.com/57335825/111281267-b886bc00-8677-11eb-91ba-fcbf3371ce06.png)

When the statement is input, it is processed as follows.

## Stage 1: Generating an AST

In the first stage, the statement is parsed by the Parser (composed of Flex and Bison) and its corresponding AST is generated. The structure of the AST is shown in the following figure.

![Generating an AST](https://user-images.githubusercontent.com/57335825/111280086-5ed1c200-8676-11eb-98fa-86ba7029a7a9.png)

In this stage, the Parser intercepts the statements that do not conform to the syntax rules. For example, a statement like`GO "Tim" FROM OVER like YIELD like._dst`will be directly intercepted in this stage because of its invalid syntax.

## Stage 2: Validation

In the second stage, the Validator performs a series of validations on the AST. It mainly works on these tasks:

* Validating metadata

When parsing the `OVER` , `WHERE` , and `YIELD` clauses, the Validator looks up the Schema and verifies whether the edge and tag data exist or not. For an `INSERT` statement, the Validator verifies whether the types of the inserted data are the same as the ones defined in the Schema.

* Validating contextual reference

For multiple statements, like `$var = GO FROM "Tim" OVER like YIELD like._dst AS ID; GO FROM $var.ID OVER serve YIELD serve._dst`, the Validator verifies `$var.ID`: first to see if `var` was defined, and then to check if the `ID` property is attached to the `var` variable. If `$var.ID` is replaced with `$var1.ID` or `$var.IID` , the validation fails.

* Validating type inference

The Validator infers what type the result of an expression is and verifies the type against the specified clause. For example, the `WHERE` clause requires the result to be a Boolean value, a NULL value, or empty.

* Replacing `*`

Take a statement like `GO FROM "Tim" OVER * YIELD like._dst, like.likeness, serve._dst` as an example. When verifying the `OVER` clause, the Validator needs to query the Schema and replace `*` with all the edges defined in the Schema. For example, if only `like` and `serve` edges are defined, the statement is as follows.

```plain
GO FROM "Tim" OVER serve, like YIELD like._dst, like.likeness, serve._dst
```

* Validating input and output

For an nGQL statement with the PIPE operator, such as`GO FROM "Tim" OVER like YIELD like._dst AS ID | GO FROM $-.ID OVER serve YIELD serve._dst`, the Validator verifies `$-.ID` . In the example statement, the `ID` property in the second clause was already defined in the previous clause, so the second clause is verified legal. If `$-.ID` is changed to `$-.a` , where `a` was not defined, the second clause is illegal.

## Stage 3: Generating an Execution Plan

When the validation succeeds, an execution plan is generated in Stage 3. Its data structure is stored in the `src/planner` directory, with the following logical structure.

![Generating an Execution Plan](https://user-images.githubusercontent.com/57335825/111280198-86c12580-8676-11eb-8226-d4e7f9a8c474.png)

### Query Execution Flow

The generated execution plan is a directed acyclic graph where the dependencies between nodes are determined in the [toPlan()](https://github.com/vesoft-inc/nebula-graph/blob/master/src/validator/PipeValidator.cpp) function of each module in the Validator. As shown in the preceding figure, the Project node depends on the Filter node, the Filter node depends on the GetNeighbor node, and so on, up to the Start node.

During the execution stage, the Executor generates an operator for each node and starts scheduling from the root node (e.g., the Project node in this example). If the root node is found to be dependent on other nodes, the Executor **recursively calls** the nodes that the root node depends on until it finds a node that is not dependent on any node (e.g., the Start node in this example), and then starts execution. After the execution, the Executor continues executing the node that depends on the executed node (e.g., the GetNeighbor node in this example), and so on, until the root node is reached.

### Query Data Flow

The input and output of each node are also determined in [toPlan()](https://github.com/vesoft-inc/nebula-graph/blob/master/src/validator/PipeValidator.cpp). Although the execution is performed in the order defined in the execution plan, the input of each node can be customized and does not completely depend on the previous node, because the input and output of all nodes are actually stored in a hash table, where the keys are the names customized during the creation of each node. For example, if the hash table is named as `ResultMap`, when creating the Filter node, you can determine that the node takes data from `ResultMap["GN1"]`, then puts the result into `ResultMap["Filter2"]`, and so on. All these work as the input and output of each node. The hash table is defined in `src/context/ExecutionContext.cpp` under the `nebula-graph` repository. The execution plan is not really executed, so the value of each key in the associated hash table is empty (except for the starting node, where the input variables hold the starting data), and they will be computed and filled in the Executor stage.

This is a simple example. A more complex one will be shown at the end for you to better understand how an execution plan works.

## Stage 4: Optimizing the Execution Plan

An execution plan generated in the preceding stage can be optimized optionally. In the `etc/nebula-graphd.conf` file, when `enable_optimizer` is set to `true`, the execution plans will be optimized. In this example, when optimization is enabled, the data flow is as follows.

![Optimizing the Execution Plan](https://user-images.githubusercontent.com/57335825/111280908-53cb6180-8677-11eb-83c5-01cb632309dd.png)

As shown in the preceding figure, the Filter node is integrated into the GetNeighbor node. Therefore, when the GetNeighbor operator calls interfaces of the Storage layer to get the neighboring edges of a vertex during the execution stage, the Storage layer will directly filter out the unqualified edges internally. Such optimization greatly reduces the amount of data transfer,which is commonly known as filter push down.

In the execution plan, each node directly depends on other nodes. To explore equivalent transformations and to reuse the same parts of an execution plan, such a direct dependency between nodes is converted into an OptGroupNode to OptGroup dependency. Each OptGroup contains an equivalent set of OptGroupNodes, and each OptGroupNode contains one node in the execution plan. An OptGroupNode depends on an OptGroup but not on other OptGroupNodes. Therefore, from one OptGroupNode, many equivalent execution plans can be explored because the OptGroup it depends on contains different OptGroupNodes, which saves storage space.

All the optimization rules we have implemented so far are considered as RBO (Rule-Based Optimization), which means the plans optimized based on the rules must be better than their original versions. The CBO (Cost-Based Optimization) feature is under development. The optimization process is a "bottom-up" exploration process: For each rule, the root node of the execution plan (in this case, the Project node) is the entry point, along the node dependencies, the bottom node is found, and then from the bottom node, the OptGroupNode in each OptGroup is explored to see if it matches the rule, until the entire execution plan can no longer apply the rule. Then, the next rule is explored.

This figure shows the optimization process of this example.

![Execution plan optimization process](https://user-images.githubusercontent.com/57335825/111280406-bf60ff00-8676-11eb-9f87-71390f706bac.png)

As shown in the preceding figure, when the Filter node is explored, it is found that its children node is GetNeighbors, which matches successfully with the pre-defined pattern in the rule, so a transformation is initiated to integrate the Filter node into the GetNeighbors node, the Filter node is removed, and then the process continues to the next rule.

The optimized code is in the `src/optimizer/` directory under the `nebula-graph` repository.

## Stage 5: Execution

In the fifth stage, the Scheduler generates the corresponding execution operators against the execution plan, starting from the leaf nodes and ending at the root node. The structure is as follows.

![Execution plan execution](https://user-images.githubusercontent.com/57335825/111280526-ea4b5300-8676-11eb-84fa-25353a0b86ed.png)

Each node of the execution plan has one execution operator node, whose input and output have been determined in the execution plan. Each operator only needs to get the values for the input variables, compute them, and finally put the results into the corresponding output variables. Therefore, it is only necessary to execute step by step from the starting node, and the result of the last operator is returned to the user as the final result.

# An Example Query

Now we will get acquainted with the structure of an execution plan by executing a `FIND SHORTEST PATH` statement.

Open nebula-console and enter the following statement.

```plain
FIND SHORTEST PATH FROM "YAO MING" TO "Tim Duncan" OVER like, serve UPTO 5 STEPS
```

To get the details of the execution plan of this statement, precede it with the`EXPLAIN`.

![Detailed execution plan](https://user-images.githubusercontent.com/57335825/111280632-07802180-8677-11eb-8c9d-e016bfee3130.png)

The preceding figure shows, from left to right, the unique ID of each node in the execution plan, their names, the IDs of their dependent nodes, the profiling data (information about the execution of the `PROFILE` command), and the details of each node (including the names of the input and output variables, the column names of the output results, and the parameters of the node).

To visualize the information, you can follow these steps:

1. Use `EXPLAIN format="dot"` instead of `EXPLAIN`. nebula-console can generate the data in the DOT format.

2. Open the [Graphviz Online](https://dreampuf.github.io/GraphvizOnline/) website and paste the generated DOT data. You can see the structure as shown in the following figure. This structure corresponds to the execution flow of the operators in the execution stage.

![Visualized execution plan](https://user-images.githubusercontent.com/57335825/111280728-1ff03c00-8677-11eb-84c8-5d67b6aa97ce.png)

The shortest path algorithm uses the two-way breadth-first search algorithm, expanding from both "YAO MING" and "Tim Duncan", so GetNeighbors, BFSShortest, Project, and Dedup have two operators, respectively, the input is connected by the PassThrough operator, and the path is stitched by the ConjunctPath operator. The LOOP operator then controls the number of steps to be extended outward, and it can be seen that the input of the DataCollect operator is actually taken from the output variable of the ConjunctPath operator.

The information of each operator is in the `src/executor` directory under the `nebula-graph` directory. Feel free to share your ideas with us on GitHub: [https://github.com/vesoft-inc/nebula](https://github.com/vesoft-inc/nebula) or the : [https://github.com/vesoft-inc/nebula/discussions](https://github.com/vesoft-inc/nebula/discussions)

>Hi, I’m Ming Quan, engineer at NebulaGraph. I’m interested in database storage and would like to share my experiences in this regard. Hope my post is of help to you. Please let me know if you have any ideas about this. Thanks.

This article introduces the overall structure of the Query layer and uses an nGQL statement to describe how it is processed in the four main modules of the Query layer. 

An Introduction to NebulaGraph 2.0 Query Engine


![NebulaGraph Query Engine Architecture](https://user-images.githubusercontent.com/57335825/83608282-84e80480-a531-11ea-97d1-7c6fbb66c29f.png)

The query engine is used to process the NebulaGraph Query Language (nGQL) statements. So, an architectural overview of the NebulaGraph query engine is important.

In the below illustration is an overview chart of the query engine. If you are familiar with the SQL execution engine, this should be familiar to you. The NebulaGraph query engine is very similar to the modern SQL execution engine except for the query language parser and the real actions in the execution plan.

![overview chart of the query engine](https://user-images.githubusercontent.com/56643819/72578735-e6f0f600-3911-11ea-8726-0357034b4fad.png)

# Session Manager

NebulaGraph employs the Role Based Access Control. So, when the client first connects to the Query Engine, it needs to authenticate itself. When it succeeds, the query engine creates a new session and returns the session ID to the client. All sessions are managed by the Session Manager. The session will remember the current graph space and access rights to the space. The session will also keep some session-wide configurations and be used as a temporary storage to store information across multiple requests in the same session.

The session will be dropped when the client connection is closed or is idle for a period of time. The length of the idle time is configurable. When the client sends a request to the query engine, it needs to attach the current session ID. Otherwise, the query engine will reject the request. When the query engine accesses the storage engines, it will attach the session object to every request. This is so the storage engine does not have to manage sessions.

# Parser

The first thing that the query engine will do when receiving a request is to parse the statements in the request. This is done by the parser. Most of the parser code is generated by the famous flex/bison tool set. The lexicon and syntax files for the nGQL can be found in the `src/parser` folder in the source code tree. The nGQL is designed in a way that is close enough to SQL. The idea is to lessen the learning curve as much as possible.

Graph databases currently do not have a unified international query language standard. As soon as the ISO’s GQL committee releases their first draft, NebulaGraph plans to make nGQL compatible with the proposed GQL.

The output of the parser is an Abstract Syntax Tree (AST), which will be passed on to the next module, the Execution Planner.

# Execution Planner

The Execution Planner will convert the AST from the parser into a list of actions (execution plan). An action is the smallest unit that can be executed. A typical action could be fetching all neighbors for a given vertex, getting properties for an edge, or filtering vertices or edges based on a given condition.

When converting AST to the execution plan, all IDs will be extracted. This is so the execution plan can be reused. The extracted IDs will be placed in the context for the current request. The context will also be used to store the variables and intermediate results.

# Optimization

The newly generated execution plan will then be passed to the Optimization Framework. There are multiple optimizers registered in the framework. The execution plan will be passed through all optimizers sequentially. Each optimizer can modify (optimize) the plan.

In the end, the final plan can look dramatically different from the original plan. However, the execution result should be exactly the same as the original plan.

# Execution

The last step in the query engine is to execute the optimized execution plan. It is done by the Execution Framework. Each executor will process one execution plan at a time. Actions in the plan will be executed one by one.

The executor will also do limited local optimization, such as deciding whether to run in parallel. Depending on the action, the executor will communicate with the Meta Service or the Storage Engine via their clients.

# You might also like

1. [NebulaGraph Architecture — A Bird’s View](https://nebula-graph.io/posts/nebula-graph-architecture-overview/)
1. [An Introduction to NebulaGraph's Storage Engine](https://nebula-graph.io/posts/nebula-graph-storage-engine-overview/)
1. [The Review on Graph Database](https://nebula-graph.io/posts/review-on-graph-databases/)


The query engine is used to process the NebulaGraph Query Language (nGQL) statements.

An Introduction to NebulaGraph’s Query Engine


![An Introduction to NebulaGraph's Storage Engine](https://user-images.githubusercontent.com/57335825/87172263-cf734400-c288-11ea-96d0-1bb800700d16.png)

The Storage Service of NebulaGraph is composed of two parts. One is the `Meta Service` that stores the meta data. The other is `Storage Service` that stores the data. The two services are in two independent processes. The data and deployment are separated but their architectures are almost the same.

# Architecture

---
![The Architecture of Storage Service](https://user-images.githubusercontent.com/42762957/71571213-2cd94c00-2b14-11ea-9b7f-a65067c61a63.png)

Fig.1 The Architecture of Storage Service

---

As shown in figure 1, there are three layers in the Storage Service. The bottom layer is the local storage engine, providing `get`, `put`, `scan` and `delete` operations on local data. The related interfaces are in `KVStore/KVEngine.h` and users can develop their own local store plugins based on their needs. Currently, NebulaGraph provides a store engine based on RocksDB.

Above the local storage engine is the consensus layer that implements multi group raft. Each partition corresponding to a raft group is for the [data sharding](https://www.nebula-graph.io/posts/what-is-database-sharding). Currently, NebulaGraph uses `hash` to shard data. When creating a space, users need to specify the partition number. Once set, a partition number cannot be changed. Generally, the partition number must meet the need to scale-out in the future.

Above the consensus layer is the storage interface that defines a set of APIs that are related to the graph. These API requirements are translated into a set of kv operations targeting the corresponding partition. It is this layer that makes the storage service a real graph storage. Otherwise it is just a kv storage. NebulaGraph does not separate kv as an independent service. This is because a graph query involves a lot of calculation that uses schema, which does not exist in a kv layer. Such architecture makes pushing down easier.

# Schema & Partition

NebulaGraph stores the vertices, edges, and properties. Efficient property filtering is critical for a [Graph Database](https://www.nebula-graph.io/). NebulaGraph uses tags to indicate vertices types. One vertexID can relate with multiple tags, and each tag has its own properties. In kv storage, we use `vertexID + TagID` to represent a key and the related properties are placed behind a value after encoding. The format is shown in figure 2:

---
![Vertex Key Format](https://user-images.githubusercontent.com/42762957/71571002-1252a300-2b13-11ea-915f-b3fd16920b95.png)

Fig.2 Vertex Key Format

---

- `Type`: one byte, used to indicate key type, current types are data, index, system, etc.
- `Part ID`: three bytes, used to indicate the sharding partition. This field can be used to scan the partition data based on the prefix when re-balancing the partition
- `Vertex ID`: eight bytes, used to indicate vertex ID
- `Tag ID`: four bytes, used to relate tag
- `Timestamp`: eight bytes, not available to users, used in MVCC in the future

Each edge in NebulaGraph is modeled as two independent key-values. One is stored in the same partition as the source vertex, namely out-edge. The other one is stored in the same partition as the destination vertex, namely in-edge. Generally, out-key and in-key are stored in different partitions.

There may be multiple edge types or multiple edges with the same edge type between two vertices. For example, if we define an edge type ‘transfer’, user A may transfer money to user B multiple times. Thus a field `rank` is added to distinguish the transfer records between the two. The edge key format is shown in figure three:

---
![Edge Key Format](https://user-images.githubusercontent.com/38887077/75969929-9c9bf680-5f0a-11ea-83bc-ff26e472095a.png)

Fig.3 Edge Key Format

---

- `Type`: one byte, used to indicate key type, current types are data, index, system, etc.
- `Part ID`: three bytes, used to indicate the sharding partition. This field can be used to **scan the partition data based on the prefix when re-balancing the partition**
- `Vertex ID`: eight bytes, used to indicate source vertex ID in out-edge, dest vertex ID in in-edge
- `Edge Type`: four bytes, used to indicate edge type, greater than zero means out-edge, less than zero means in-edge
- `Rank`: eight bytes, used to indicate multiple edges in one edge type. Users can set the field based on needs and store weight such as _transaction time_, _transaction number_ and _weight of a certain order_
- `Vertex ID` : eight bytes, used to indicate dest vertex ID in out-edge, source vertex ID in in-edge
- `Timestamp`: eight bytes, not available to users, used in MVCC in the future

If the value of an edge type is greater than zero, the corresponding edge key format is shown in figure four. Otherwise if the value is less than zero, the corresponding edge key format is shown in figure five.

---
![Out-key format](https://user-images.githubusercontent.com/38887077/75969938-9f96e700-5f0a-11ea-8469-027fe7ff08c3.png)

Fig.4 Out-key format

---

![In-key format](https://user-images.githubusercontent.com/38887077/75969944-a160aa80-5f0a-11ea-99ed-f4a8807b1828.png)

Fig.5 In-key format

---

The properties of vertices and edges are stored in the values of the corresponding kv pairs after being encoded. As a strong typed database, NebulaGraph needs to get the schema information in the Meta Service before decoding. In addition, when properties are encoded, the schema version is added to support online schema change.

NebulaGraph shards data through a `modulo operation` on vertex ID. All the out-keys, in-keys and tag data are placed in the same partition through the `modulo operation` on vertex ID. In this way, query efficiency is increased dramatically.

For online queries, the most common operation is to do a Breadth-First-Search (BFS) expansion from a vertex. Thus it is the basic operation to get a vertex’s in-edge or out-edge and such operation’s performance determines the traverse’s performance.

In BFS, there are cases for filtering some properties. NebulaGraph guarantees the operation efficiency by putting properties and vertices and edges together. At present, most graph databases verify their efficiency with Graph 500 or the Twitter data set, which are of no eloquence because properties are not included. While most cases use property graphs and BFS needs a lot of filtering as well.

# KVStore

NebulaGraph develops its own kv store to meet performance needs:

- **High performance** pure kv
- **Provided as a library**, as a strong typed database, the performance of pushing down is the key of the performance of **NebulaGraph**
- **Strong data consistency**, determined by the distribution system
- **Written in C++**  

For users who are not sensitive to performance or unwilling to migrate data, NebulaGraph provides plugins for the whole kv store and builds the storage service on the third party kv store. Currently, NebulaGraph provides the HBase plugin.
With RocksDB as the local storage engine, NebulaGraph supports self-management of multiple hard disks to make full use of the parallel property. All users need to do is configure multiple data directories. NebulaGraph manages the distributed kv store in a unified scheduling way with meta service. All the partition distribution data and current machine status can be found in the meta service. Users can input commands in the console to add or remove machines to generate and execute a balance plan in meta service.
NebulaGraph provides its own WAL mode so one can customize the WAL. Each partition owns its WAL to catch up data without WAL splitting to guarantee efficiency. In addition, NebulaGraph defines a Command Log class to conduct special operations. These logs have no real data and are only used to inform all replicas to execute certain operations with raft. NebulaGraph also provides a log class to conduct an atomic operation on partitions, such as with the CAS and the read-modify-write which fully uses raft serialization.
One NebulaGraph kv store cluster supports multiple spaces, and each space is set with its own partition number and replica number. Different spaces are isolated physically. Spaces in the same cluster support different storage engines and sharding strategies.

# The Raft Implementation in NebulaGraph

## Multi Raft Group

As the log IDs must be serial, almost all the implementations adapt a Multi Raft Group to solve this problem. Therefore, the partition number almost determines the performance of the Raft Group. However, it does not mean the more partitions, the better the performance.

Each Raft group stores a set of state information and has its own WAL file. Thus, more partitions require more costs. Also, when there are too many partitions, the batch operation is meaningless if the load is not high enough. For example, with a single online system having 10,000 tps, if its partition number is greater than ten thousand, the tps of each partition per second is likely only 1. So, the batch operation loses its meaning and increases CPU cost.

There are two key points to achieve a Multi Raft Group. First is to share the transport layer because each Raft Group needs to send messages to the corresponding peers. If the transport layer cannot be shared, the connection costs are huge. Second is the threading model. With it, a Multi Raft Group must share a set of thread pools. Otherwise it will end with too many threads in the system, resulting in a large amount of context switch cost.

## Batch

For each Partition, it is necessary to do a batch to improve throughput when writing WAL serially. In general, there is nothing special about a batch, but NebulaGraph designs a special type of WAL based on each part serialization. This adds some challenges.

For example, NebulaGraph uses WAL to implement lock-free CAS operations and each CAS operation will execute after all the previous WALs are committed. So, for a batch, if there are several WALs in CAS type, we need to divide this batch into several smaller serial groups.

## Learner

New machines need to “catch up” data for quite a long time, and there may be accidents during the process. If a new machine joins the raft group as a follower, it will reduce the HA capacity of the entire cluster. NebulaGraph uses the command WAL mentioned above to implement its learner. If the leader encounters the `add learner command` when writing WAL, it will add the learner to its peers and mark it as a learner, so the logs will send to them as normal. But the learners will not be involved in the leader’s election.

## Transfer Leadership

Transfer leadership is extremely important for balance. When moving a partition from one machine to another, NebulaGraph first checks if the source is a leader. If so, it should be moved to another peer. After data migration is completed, it is important to balance the leader again, so that the load on each machine can be balanced.

When transferring leadership, note that the leader abandons its leadership and the follower starts a leader election. When a transfer leadership command is committed, the original leader abandons its leadership. And as for followers, when receiving the command, it starts a leader election. This uses the same execution process with a common raft leader election. Otherwise, some corner cases will occur.

## Membership Change

To avoid split-brain, when members in a Raft Group change, an intermediate state is required. In such a state, the majority of the old group and new group always have an overlap. Thus it prevents the old or new group from making decisions unilaterally. This is the `joint consensus` mentioned in the thesis. To make it even simpler, in his doctoral thesis Diego Ongaro suggests adding or removing a peer once to ensure the overlap between the majority of the new group and the old group . NebulaGraph‘s implementation also uses this approach, except that the way to add or remove a member is different. For details, please refer to `addPeer/removePeer` in the Raft Part class.

## Snapshot

When the leader changes during sending [snapshot](https://www.nebula-graph.io/posts/database-snapshots), the follower may only receive half of the snapshot data. So, a partition data cleanup is required. Because multiple partitions share a single storage, how to clean up the data is a cumbersome problem. In addition, during the snapshot process, a large amount of IO is generated. Considering performance, you do not want this process to share an IO threadPool with the normal Raft. The process requires a large amount of memory. Thus, how you optimize the memory usage is critical for performance.

# Storage Service

- `getNeighbors`: query the in-edge or out-edge of a set of vertices, return the edges and the corresponding properties, support conditional filters
- `Insert vertex/edge`: insert a vertex or edge and its properties
- `getProps`: get the properties of a vertex or an edge

Graph semantics interfaces are translated into kv operations in this layer. To improve the performance of traversal, concurrent operations are also required.

# Meta Service

On the kv store interface, NebulaGraph encapsulates a set of meta-related interfaces. Meta service supports CRUD on schema, cluster management, and user management. Meta service also supports single-machine deployment and multiple replicas to ensure data security.

# You might also like

1. [NebulaGraph Architecture — A Bird’s View](https://www.nebula-graph.io/posts/nebula-graph-architecture-overview)
1. [An Introduction to NebulaGraph's Query Engine](https://www.nebula-graph.io/posts/nebula-graph-query-engine-overview)
1. [The Review on Graph Database](https://www.nebula-graph.io/posts/review-on-graph-databases)

This article introduces to you the storage design of NebulaGraph, an open-source distributed graph database.