
![Adding a Test Case for NebulaGraph](https://user-images.githubusercontent.com/57335825/128318814-def4e1f3-7eab-4dda-9f0e-aec49c7769bd.png)

# Before We Start

NebulaGraph is a product under continuous development, so the format of the returned result may be updated as required, which may cause parse errors to your applications.  

For example, after the release of NebulaGraph v2.0.0, the updated SHOW JOBS syntax caused crash of NebulaGraph Studio because it cannot parse the statement correctly. 

To avoid such errors, the NebulaGraph team have developed a new testing framework to help its users add new test cases without too much effort.

## Preparing Environment

According to [Install NebulaGraph by compiling the source code](https://docs.nebula-graph.io/2.0.1/4.deployment-and-installation/2.compile-and-install-nebula-graph/1.install-nebula-graph-by-compiling-the-source-code/), prepare the environment as follows: 

a. Get a development machine ready. Here is the minimum requirement:

- Python 3.7 or later.

```
python3 --version
``` 

b. Follow the steps described in the documentation. Create a branch from the master branch.

```
git checkout -b  dev tck
```

For further details, refer to the steps of [How to Contribute](https://docs.nebula-graph.io/2.0.1/15.contribution/how-to-contribute/) in NebulaGraph Database Manual. 

c. Install the environment for executing the test cases.

```
$ cd nebula-graph/tests/
$ make init-all
```

If an error occurs informing that the module version is too old, you should upgrade it according to the prompt. For example, run the command pip3 install `--upgrade keyrings.alt`.

d. Execute the existing cases.

```
make test
```

# Adding New Test Cases

## Learn from Existing Cases

There have been a lot of test cases in the [tests/tck/features/ directory](https://github.com/vesoft-inc/nebula-graph/tree/master/tests/tck/features) of the nebula-graph repository on GitHub.  Each feature has its own subdirectory.

Take `MATCH` as an example. Look at the [match/MatchById.feature](https://github.com/vesoft-inc/nebula-graph/blob/master/tests/tck/features/match/MatchById.feature) file.

```
Feature: Match By Id

  Background:
    Given a graph with space named "basketballplayer"     # Choose a ready graph space named basketballplayer for unit testing.

  Scenario: single node                                   # Give the new scenario (test case) a name.
    When executing query:                              # The line surrounded by three double quotes is the statement sent to NebulaGraph.
      """                                                            # This statement is to obtain a vertex with the "James Harden" ID.
      MATCH (n) WHERE id(n) == 'James Harden' RETURN n
      """                                                            # The "Then" line gives the expected result.                
    Then the result should be, in any order, with relax comparison:
      | n                |                                          # The expected result should be composed of one column named "n".
      | ("James Harden") |                                # A record with "James Harden" surrounded by parentheses, representing a vertex
    When executing query:                            # The next statement. 
      """
      MATCH (n) WHERE id(n) == 'not_exist_vertex' RETURN n
      """
    Then the result should be, in any order, with relax comparison:
      | n |
```

nebula-test is a BDD-based testing framework. All these feature files are written in Gherkin. For more information about BDD, refer to [BDD-Based Integration Testing Framework for NebulaGraph: Part I](https://nebula-graph.io/posts/bdd-testing-practice/).

Here is an introduction to the sections of a feature file:

- Feature: Gives the subject of the file.
- Background: Gives the steps that are common to all the scenarios in the same feature file. In this example, a ready graph space named "basketballplayer", with schema, indexes, and data, is selected.
- Scenario: Composed of a pair of `When` and `Then` steps. A scenario is the smallest unit of concurrent execution.
- When executing query: Sends a series of commands to NebulaGraph.
- Then the result should be: Obtains the result from NebulaGraph and compares the result with the expected result.

The returned result can be compared with the expected result with one of these methods:

- the result should be: The results must be exactly the same, which means the content of the rows, columns, and records are exactly the same.
- the result should contain: If the returned result contain the mentioned content in the expected result, it is considered valid.
- the result should be, in any order: The order of rows in the returned result is not used to determine the legality of the result.
- the result should be, in any order, with relax comparison: The returned result should comply with the given format but the order of the rows does not matter. Besides, the result must contain the specified content. For example, each record must has one or more "Tiago Splitter" strings.
- the execution should be successful: The execution is successful.
- an ExecutionError should be raised at runtime: not existed! The execution failed. The ExecutionError exception is thrown, and the error code is `not existed!`.

## Writing a Test Case

If you want to do a check of the format of the returned result of SHOW JOBS, you can add a feature file named JobCommands.feature under the directory: [nebula-graph/tests/tck/features/job/](https://github.com/vesoft-inc/nebula-graph/tree/master/tests/tck/features/job).

```
@mintest                                                         # A tag. This is for debugging.

Feature: Job compact, flush, rebuild_index

  Background:                                     # Choose a graph space with a dataset.
    Given a graph with space named "basketballplayer"

  Scenario: submit job
    When executing query:
      """
      SUBMIT JOB COMPACT;
      """
    Then the result should contain:
      | New Job Id |
      | /\d+/          |              # Write a regular expression for positive integers
    When executing query:
      """
      SUBMIT JOB FLUSH;
      """
     When executing query:
      """
      SUBMIT JOB STATS;

      SHOW JOBS;
      """
    Then the result should contain:   # Do a check of the result format
      | Job Id | Command | Status  | Start Time                               | Stop Time                 |
      | /\d+/  | "STATS"      | /\w+/  | /\d+-\d+-\d+T\d+:\d+:\d+/ | /\d+-\d+-\d+T\d+:\d+:\d+/ |
```

### Debugging a Test Case

```
nebula-graph/tests> make fmt
```

Do a check of the format and get the file format valid.

```
nebula-graph/tests>  pytest -m "mintest"
```

Run the test case. In general, the case may need some changes. You can use `#` to comment out a line or use `@skip` to skip a scenario.

```
nebula-graph/tests>  pytest -n4
```

If the memory capacity is not big enough, use -n4 to control the concurrency.

For more information, refer to the [test manual](https://github.com/vesoft-inc/nebula-graph/tree/master/tests#nebula-graph-test-manual).

# Submitting Test Case via Git

If the test case passes, remove the `@mintest` tag and submit a pull request to the NebulaGraph repository on GitHub. For more information, refer to [How to Contribute](https://docs.nebula-graph.io/2.0.1/15.contribution/how-to-contribute/).

If you are interested in learning more about NebulaGraph, welcome to join the NebulaGraph [Slack](https://join.slack.com/t/nebulagraph/shared_invite/zt-7ybejuqa-NCZBroh~PCh66d9kOQj45g) channel!


This article introduces how to add a test case to NebulaGraph easily with the BDD testing framework.

Adding a Test Case for NebulaGraph


![BDD-Based Integration Testing Framework for NebulaGraph](https://user-images.githubusercontent.com/57335825/126611829-2805b5c5-1e17-4ddc-8d7b-67376525ef1a.png)

In [BDD-Based Integration Testing Framework for NebulaGraph: Part I](https://nebula-graph.io/posts/bdd-testing-practice/), I introduced the evolution of integration testing for NebulaGraph. In this article, I will introduce how to add a test case into the test set and run all the test cases successfully. 

# Preparing Testing Environment

At the beginning of building the testing framework for NebulaGraph 2.0, we developed some tool classes to help the testing framework quickly start and stop a single-node NebulaGraph cluster, including checking for port conflicts and modifying part configurations. Here is the original execution procedure:

1. Using a Python script to start the NebulaGraph services.
2. Calling `pytest.main` to execute all the test cases concurrently.
3. Stopping the NebulaGraph services.

However, parameters need to be passed transparently to the `pytest.main` function to specify some parameters of pytest and the scripts generated by cmake is needed to execute a single test case, which makes the framework not so convenient for users.  What we want to achieve is executing a test case where it is located.

# Starting Services

During this improvement of the testing framework, besides the changes to the program entry, most of the original encapsulated logics are reused. A lot of test cases have been accumulated for NebulaGraph, so single-process operation can no longer meet the requirements of fast iteration. We have tried several parallel test executor plugins, considering compatibility requirement, we finally chose `pytest-xdist` to accelerate the testing procedure.

Pytest supports fixtures across these five scopes: session, module, class, package, and function. However, we need a global fixture to start and initialize the NebulaGraph services. Currently, for a session-scoped fixture, the highest level, each runner needs to be executed once. For example, if there are eight runners, eight NebulaGraph database services must be started, which is not what we want.

According to the [documentation of pytest-xdist](https://github.com/pytest-dev/pytest-xdist#making-session-scoped-fixtures-execute-only-once), a lock file is needed for inter-process communication between runners. To make sure that the control logic is simple enough, we separate the logic for starting and stopping the program and for preparation from the process of executing the test, that is, a single step is used to start NebulaGraph, and when errors occur to some tests, Nebula Console is connected to the NebulaGraph database that is in the process of testing for validation and debugging.

## Importing Data

Before the new framework, to import data to NebulaGraph, an entire INSERT statement in nGQL is executed, which causes the following problems:

1. When the imported dataset is large, the INSERT statement will be very long and a timeout error may occur when the client executes the query.
2. It is difficult to develop new dataset for testing, because the data of the CSV files must be converted to nGQL files first.
3. The dataset cannot be reused. For example, the data of a CSV file cannot be directly imported to graph spaces that have VIDs of different data types, because different INSERT statements are needed.

To solve these problems, referring to the implementation of [Nebula Importer](https://github.com/vesoft-inc/nebula-importer), we separate the importing logic from the dataset completely and implement a new importing module in Python. However, so far, only CSV files are supported and one CSV file can store only one tag or edge type data.

According to the new importing module, the structure of the dataset for NebulaGraph testing becomes clear.

```tree
nebula-graph/tests/data
├── basketballplayer
│   ├── bachelor.csv
│   ├── config.yaml
│   ├── like.csv
│   ├── player.csv
│   ├── serve.csv
│   ├── team.csv
│   └── teammate.csv
├── basketballplayer_int_vid
│   └── config.yaml
└── student
    ├── config.yaml
    ├── is_colleagues.csv
    ├── is_friend.csv
    ├── is_schoolmate.csv
    ├── is_teacher.csv
    ├── person.csv
    ├── student.csv
    └── teacher.csv
 
3 directories, 16 files
```

Each directory has all the CSV files for one graph space. The description of each file and the details of a graph space are configured in config.yaml in each directory. In the preceding example, the two graph spaces, "basketballplayer" and "basketballplayer_int_vid", share the same dataset. To add a new dataset, only a directory like "basketballplayer" is needed. For more information about `config.yaml`, see the [nebula-graph repository](https://github.com/vesoft-inc/nebula-graph/blob/master/tests/data/nba/config.yaml).

## Installing Dependencies

Besides pytest and nebula-python, the commonly used libraries, some plugins such as pytest-bdd and pytest-xdist are used in the testing framework. In addition, to better unify the format of the FEATURE files for adding test cases, [reformat-gherkin](https://github.com/ducminh-phan/reformat-gherkin) is introduced and [some format modifications](https://github.com/OneContainer/reformat-gherkin) are made to align the format with that of openCypher TCK FEATURE files. 

Currently, nebula-python and reformat-gherkin are installed with their source code. To simplify the installation, a makefile is provided in the `nebula-graph/tests` directory. To prepare the environment for the testing, run the following command.

```plain
$ cd nebula-graph/tests && make init-all
```

The format check procedure has been added to the GitHub Action CI process.  If your files are not compliant with the expected format, run `make fmt` to format them.

## Writing Test Cases

According to [Part I](https://nebula-graph.io/posts/bdd-testing-practice/), the BDD-based testing framework for NebulaGraph is a black box testing process, which means you do not need to know how your statements are called or which function to call is more in line with the expected result. What you only need to do is writing a FEATURE file in natural language based on the rules. Here is a test case example.

```
Feature: Variable length pattern match (m to n)
  Scenario: both direction expand with properties
    Given a graph with space named "basketballplayer"
    When executing query:
      """
      MATCH (:player{name:"Tim Duncan"})-[e:like*2..3{likeness: 90}]-(v)
      RETURN e, v
      """
    Then the result should be, in any order, with relax comparison:
      | e                                                                                  | v                  |
      | [[:like "Tim Duncan"<-"Manu Ginobili"], [:like "Manu Ginobili"<-"Tiago Splitter"]] | ("Tiago Splitter") |
```

In a FEATURE file, the `Given` section is for the initial conditions for the test. In this example, it creates a graph space named "basketballplayer". The `When` section contains the inputs for testing, that is, nGQL statements. In this example, the `Then` section gives the expected results and the expected comparing method, that is, the records of the table should be compared in a relax and unordered manner.

### FEATURE File Format

The FEATURE files are written in Gherkin language. A FEATURE file is composed of the following sections:

* Feature: It contains detailed description and/or the title of the file.
* Background: It contains the steps that are common to all the scenarios in the same FEATURE file.
* Scenario: It contains the steps necessary for a test case.
* Examples: It separates the scenario from the data further to simplify editing the Scenario section.

Each scenario has its own steps. Each step is composed of these:

* Given: Specifies the initial conditions for the test case. In the Background section, only Given steps should be used.
* When: Specifies the inputs for the scenario.
* Then: Describes the expected result when the steps inside the When section are done.
* And: Optional. It follows Given, When, or Then to further describe these steps.
* Examples: Similar with the description of the Examples above. However, it is limited to the scenario where it is located. It has no effect on the testing of other scenarios in the same FEATURE file.

### Steps

According to the preceding description, each Scenario is composed of several steps. In NebulaGraph testing framework, its format is compliant with the rules of openCypher TCK and some special steps are developed to simplify editing of the test cases:

1. `Given a graph with space named "basketballplayer"`: Using a graph space with pre-imported the "basketballplayer" dataset.
2. `creating a new space with following options`: Creating a new graph space by specifying these parameters: name, partition_num , replica_factor, vid_type, charset, and collate.
3. `load "basketballplayer" csv data to a new space`: Importing the "basketballplayer" dataset to the new graph space.
4. `profiling query`: Executing the PROFILE statement. An execution plan will be returned.
5. `wait 3 seconds`: Waiting three seconds. Time is needed for data synchronization during the schema operations, so such a step is necessary.
6. `define some list variables`: Defining some variables of the LIST type to have some lists returned as expected.
7. `the result should be, in any order, with relax comparison`: Performing a comparison in a relax and unordered manner to the result. It means that only the expected result are compared, but the unexpected result are not compared.
8. `the result should contain`: Containing the expected content in the result.
9. `the execution plan should be`: Comparing the returned execution plans.

Besides the preceding steps, more steps can be defined to speed up the development of test cases.

### Parser

[openCypher TCK](https://github.com/opencypher/openCypher/tree/master/tck#format-of-the-expected-results) defines the format of the expected results. The format of vertices and edges is borrowed from the pattern of `MATCH`, so if you are familiar with openCypher query language, you can easily understand the results of the TCK test cases. For example, the format of part graph semantics is as follows:

1. Describing a vertex: `(:L {p:1, q:"string"})`;
2. Describing an edge: `[:T {p:0, q:"string"}]`;
3. Describing a path: `<(:L)-[:T]->(:L2)>`。

However, NebulaGraph differs a little from Neo4j in their graph models. For example, in NebulaGraph, each tag can have its own properties, so according to the existing openCypher TCK rules, a vertex with multiple tags that have their own properties cannot be described. The description of edges has the similar problem. In NebulaGraph, an edge key is of four-tuples <src, type, rank, dst>, but the existing openCypher TCK rules do not support src, dst, and rank. Therefore, to solve these problems, we expand the expressions of the expected results: 

1. Describing a vertex with multiple tags that have their own properties: `("VID" :T1{p:0} :T2{q: "string"})`；
2. Describing edges with src, dst, and rank: `[:type "src"->"dst"@rank {p:0, q:"string"}]`；
3. Describing a path by adding the vertices and edges. Refer to the TCK rules.

The expanded expressions of vertices and edges are compatible with the existing TCK test cases and fit the design of NebulaGraph. In addition to the expression problem, the next one we faced was how to efficiently and accurately convert the expression into a specific data structure so that it can be compared with the actual query results. After considering solutions such as regular expression matching and parsing by a parser, we decided to construct a parser to process the strings with specific syntax rules. This solution has the following advantages:

1. According to specific syntax rules, the generated AST can have the data structure that is compliant with expected result rules. And then in the validation phase, only the specific fields in the specific structures are validated. 
2. Processing complex regular expression matching of strings can be avoided, which can reduce parsing errors.
3. Parsing other strings, such as regular expressions, lists, and collections, can be supported. 

With ply.yacc and ply.lex, we can use a small amount of code lines to implement the complex requirements described above. For more information about the implementation, see [nbv.py](https://github.com/vesoft-inc/nebula-graph/blob/master/tests/tck/utils/nbv.py).

## Testing Procedure

Currently, the testing procedure is as follows:

### 1) Edit the FEATURE files.

Currently, all the FEATURE files for NebulaGraph can be found in the [tests/tck/features](https://github.com/vesoft-inc/nebula-graph/tree/master/tests/tck/features) directory of the github.com/vesoft-inc/nebula-graph repository.

### 2) Start the NebulaGraph services.

```
$ cd /path/to/nebula-graph/tests
$ make up # Starts NebulaGraph services.
```

### 3) Execute the testing locally.

```
$ make fmt # Formats
$ make tck # Executes the TCK tests.
```

### 4) Stop the NebulaGraph services.

```
$ mak
e down
```

## Debugging

When the test cases need to be debugged, you can use some methods supported by pytest to debug them further. For example, run these commands to execute the test cases that failed in the last process.

```
$ pytest --last-failed tck/ # Executes the test cases in the TCK directory that failed in the last execution process.
$ pytest -k "match" tck/    # Executes the test cases that contain the match statements.
```

Alternatively, you can add a mark to a specific scenario in the FEATURE file and execute the marked case only. For example, run these commands:

```
# in feature file
  @testmark
  Scenario: both direction expand with properties
    Given a graph with space named "basketballplayer"
    ...
 
# in nebula-graph/tests directory
$ pytest -m "testmark" tck/ # Executes the test case with the "testmark" mark.
```

# Summary

Standing on the shoulders of our predecessors allows us to find a more suitable test solution for NebulaGraph, so we would like to thank all the open-source projects mentioned in this article.

In the process of practicing pytest-bdd, we have found some imperfections. For example, it has compatibility issues with plugins such as pytest-xdist (gherkin-reporter), and pytest does not natively provide fixtures of the global scope level. However, in general, the benefits it brings to NebulaGraph far outweigh these problems.

In [Part I](https://nebula-graph.io/posts/bdd-testing-practice/), I mentioned that the new testing framework enables no-programming. It is not a fantasy. When the mentioned mode is fixed, we can develop a scaffold for adding test cases, allowing users to "fill in the blanks" with data on pages to automatically generate corresponding FEATURE files, which can further facilitate users. If you are interested, welcome to [contribute](https://github.com/vesoft-inc/nebula-graph/issues) to this idea.


This article introduces how to add a test case into the test set and run all the test cases successfully.

BDD-Based Integration Testing Framework for NebulaGraph: Part II


![BDD-Based Integration Testing Framework for NebulaGraph: Part Ⅰ](https://user-images.githubusercontent.com/57335825/122339597-debc4080-cf73-11eb-835b-3084125c6c4e.png)

# Evolution of Testing Framework

So far, during the development of NebulaGraph, its testing framework has undergone three major changes, as shown in the following figure. In this article, I would like to introduce some experience and lessons that our team has learned from these changes.

![how the testing framework in NebulaGraph evolves over time](https://user-images.githubusercontent.com/57335825/122339745-06aba400-cf74-11eb-8eb2-b866a785692a.png)


For a database product, the importance of testing cannot be overemphasized. Therefore, no matter how the testing framework evolves, it always aims to easily and quickly accumulate test cases to assure stability of NebulaGraph functionalities, not only for developers, but also for its users, including maintenance engineers, documentation engineers, and even non-technical users. To achieve this goal, our testing framework must make codeless programming or no-programming possible for users.

Most database products have their own testing framework, and the tests submitted by developers must comply with the frameworks. We tried developing [such a testing framework](https://github.com/yixinglu/nebula-test). To develop it, our team needed to implement a lot of custom functionalities from scratch, and if it was done, our users needed to learn a new set of rules. Therefore, we did not adopt that framework. When we started supporting MATCH, an openCypher-compatible syntax, the [TCK repository](https://github.com/opencypher/openCypher/tree/master/tck) came into view. Although it is a test suite to verify conformance to openCypher, it refreshed our mind about implementing integration testing for NebulaGraph. Why the framework we originally tried was abandoned? One reason is that the result set returned by NebulaGraph is a complex data structure that may be composed of vertices, edges, and paths. It can be described in JSON, but not in an elegant and concise way. Once the amount of result sets gets large, the "content" will be overcome by the "format", which means that the description of the structure, verbose and annoying, is far more than the data that users care about. However, the set of rules for describing vertices, edges, and paths defined in TCK are simple and intuitive, and fit the pattern statement in MATCH, which can be accepted and understood by openCypher users. Of course, to apply the TCK rules to NebulaGraph, a database with strong schema, we need to extend them, but it doesn't matter. Because of these advantages, we determined to develop this BDD-based testing framework.

By comparing the complexity of the following test cases, you can see the obvious progress in each change. The following figures show test cases for:

1. GTest-based testing
2. pytest-based testing
3. BDD-based testing

![GTest-based testing](https://user-images.githubusercontent.com/57335825/122340138-7cb00b00-cf74-11eb-88dc-7f05d217480a.png)
[GTest-based testing]
![pytest-based testing](https://user-images.githubusercontent.com/57335825/122340215-96e9e900-cf74-11eb-94ce-8ae60f591b2f.png)
[pytest-based testing]
![BDD-based testing](https://user-images.githubusercontent.com/57335825/122340284-aff29a00-cf74-11eb-9ca2-3bdb3acf1f45.png)
[BDD-based testing]

It can be seen from the preceding comparisons that we are getting closer to the essence of "testing": Only the input and output, but not coding to assemble test data, are what we care about. With the help of some small automation tools, our users, even those who have no technical background, can create test cases.

# Expectations and Implementations

Before extending the TCK-based testing framework, we set the following goals for this upgrade:

1. It must be convenient  to add a test case and the expected data.
2. It must support importing other test data sets.
3. It can reuse the flexibility of the pytest-based framework, especially mechanisms such as plugins and fixture.
4. It must be compatible with the MATCH test cases in TCK.

To build a TCK-based testing framework for NebulaGraph, we must choose an "appropriate" testing framework. It must meet these requirements:

1. Completely complying with BDD-based testing.
2. Convenient, flexible, and extendable.
3. Compatibility with the existing pytest test cases would be a plus.

BDD-based testing frameworks can be implemented in various languages and in different ways, even Python has [many implementations](https://automationpanda.com/2019/04/02/python-bdd-framework-comparison/), for example, [pytest-bdd](https://pytest-bdd.readthedocs.io/en/latest/) and [behave](https://behave.readthedocs.io/en/stable/). To meet the third requirement, we decided to build a testing process based on pytest-bdd for NebulaGraph. pytest-bdd is a plug-in of pytest, so it can well support the features of BDD and the functionalities of pytest, which is more in line with our expectations.

After the testing framework was chosen, we began to design the modules of the entire testing process. They are ConnectionManager, DataLoader, Parser, Comparator, and Reporter.

## ConnectionManager

Manages connections to NebulaGraph, including retries after errors and error filtering.

## DataLoader

Reads the CSV files, parses the data types in the configurations, splices data for an INSERT statement, and so on.

## Parser

Parses the strings of vertices, edges, and paths described in TCK and converts them into the Value format defined in NebulaGraph, which makes comparisons easier.

## Comparator

Responsible for comparing the values of different Value formats, including basic data types and composite data types. Composite data types include List, Map, Set, Vertex, Edge, and Path.

## Reporter

Supports customizing features such as outputting the position and the line number in a feature file where an nGQL statement with an execution error is located.

All these modules, which are both independent and interrelated, and different scope of pytest fixture make it possible to implement the isolation and testing of different scenarios.

# What is BDD?

So far, BDD has been mentioned many times in this article. You may be familiar with TDD (Test-Driven Development) and DDD (Domain-Driven Design), but not with [BDD](https://cucumber.io/docs/bdd/). What is BDD? BDD, the abbreviation for Behavior-Driven Development, is a sort of evolution of TDD. With this methodology, developers and non-developers can write test cases in natural language to do tests, which is friendlier to non-developers and makes developers and users better understand and communicate with each other. In practice, we found that BDD is not only effective in software quality management, but also a good supplement to complicated requirement management. Besides users' complex scenarios, the feature files contain users' expected statements, steps, and conclusion of a query, which makes developers understand the feature more easily. After the feature development is done, these files turn into test cases. Well, kill two birds with one stone.

To understand BDD, we should introduce the Gherkin language firstly. It defines a set of basic syntax rules to organize the structure of plain text so that BDD-based testing tools can parse the text. The text in Gherkin is saved in a file with the FEATURE extension. A `.feature` file can be composed of several scenarios and each `Scenario` has its own steps (`Given`, `When`, `Then`, and so on). These syntax rules are simple and easy to understand, and only a few keywords need to be memorized. Therefore, reading a test case written in Gherkin is like reading an "Ask and Answer" dialogue. Easy to learn.

Our goal is to implement the BDD-based testing framework for NebulaGraph as a pure black box testing process, where developers and non-developers care about only two things: The input nGQL statements and the expected returns. Such a framework can reduce the mental burden of users to add test cases, and make it convenient for them to contribute to NebulaGraph. After we upgraded the framework, about 2,500 test cases from our team have been added within half a year. These test cases provide the strong quality assurance for NebulaGraph 2.0. You can find them in the [tests/tck/features](https://github.com/vesoft-inc/nebula-graph/tree/master/tests/tck/features) directory of the `nebula-graph` repository. You can use them as a guide to nGQL. If you have a tough scenario and don't know how to describe it in nGQL, you can refer to these test cases.

# Conclusion

In this article, I briefly described the evolution of the testing framework for NebulaGraph. In the upcoming article, I will introduce the available functionalities of the new testing framework and how to use it to test changes to the NebulaGraph source code. Stay tuned!

Interested in learning more about NebulaGraph? Join the [Slack](https://join.slack.com/t/nebulagraph/shared_invite/zt-7ybejuqa-NCZBroh~PCh66d9kOQj45g) community!


This article explains in detail how the testing framework in NebulaGraph evolves over time and why the team has decided to turn to the BDD-based integration testing framework.

BDD-Based Integration Testing Framework for NebulaGraph: Part Ⅰ


![AddressSanitizer.png](https://user-images.githubusercontent.com/56643819/74794701-d829a480-52fe-11ea-8fe7-6bd98a95dc39.png)

As a C/C++ developer, you will encounter various problems during development, the most common ones are **memory usage issues** such as **out of bounds, leakage**.

Previously the most commonly used memory error detect tool was [Valgrind](https://valgrind.org/), but the biggest problem with Valgrind is that it will greatly reduce program speed,  by 10 times by estimate.

Good news is the Google-developed memory error detect tool, [AddressSanitizer](https://github.com/google/sanitizers/wiki/AddressSanitizer) (aka ASan), has greatly improved the program slowdown to two times only on average, which is very fast.

This post gives an introduction to AddressSanitizer, covering what it is, how it works, feature comparison between AddressSanitizer and other memory detection tools, as well as some best practices utilizing AddressSanitizer.

# Introducing AddressSanitizer

AddressSanitizer is a compiler-based testing tool that detects various memory errors in C/C++ code at runtime.

Strictly speaking, AddressSanitizer is a compiler plug-in. It consists of two modules

- A compiler instrumentation module
- A run-time library that replaces malloc/free

The instrumentation module mainly deals with memory operations such as **store **and **load** at the compiler level.

The dynamic library mainly provides some complex functions at runtime such as poison/unpoison shadow memory and hooks system calling functions such as malloc/free.

## Basic Usage of AddressSanitizer

According to the official Wiki, AddressSanitizer finds:

- Use after free (dangling pointer dereference)
- Heap buffer overflow
- Stack buffer overflow
- Global buffer overflow
- Use after return
- Use after scope
- Initialization order bugs
- Memory leaks

In this post we only focus on the basic usage. For more details, please refer to the official compiler usage documents such as [Clang](https://clang.llvm.org/docs/AddressSanitizer.html).

### Example on Use After Free

The following code is a very simple example of Use after free:

```cpp
//use_after_free.cpp
#include <iostream>
int main(int argc, char **argv) {
  int *array = new int[100];
  delete [] array;
  std::cout << array[0] << std::endl;
  return 1;
}
```

Now, compile the code and run the executable. Here you only need to build with the `-fsanitize = address` option when compiling.

```shell
clang++  -O -g -fsanitize=address ./use_after_free.cpp
./a.out
```

Finally we will see the following output:

```bash
==10960==ERROR: AddressSanitizer: heap-use-after-free on address 0x614000000040 at pc 0x00010d471df0 bp 0x7ffee278e6b0 sp 0x7ffee278e6a8
READ of size 4 at 0x614000000040 thread T0
    #0 0x10d471def in main use_after_free.cpp:6
    #1 0x7fff732c17fc in start (libdyld.dylib:x86_64+0x1a7fc)

0x614000000040 is located 0 bytes inside of 400-byte region [0x614000000040,0x6140000001d0)
freed by thread T0 here:
    #0 0x10d4ccced in wrap__ZdaPv (libclang_rt.asan_osx_dynamic.dylib:x86_64h+0x51ced)
    #1 0x10d471ca1 in main use_after_free.cpp:5
    #2 0x7fff732c17fc in start (libdyld.dylib:x86_64+0x1a7fc)

previously allocated by thread T0 here:
    #0 0x10d4cc8dd in wrap__Znam (libclang_rt.asan_osx_dynamic.dylib:x86_64h+0x518dd)
    #1 0x10d471c96 in main use_after_free.cpp:4
    #2 0x7fff732c17fc in start (libdyld.dylib:x86_64+0x1a7fc)

SUMMARY: AddressSanitizer: heap-use-after-free use_after_free.cpp:6 in main
```

The output clearly shows when the memory is freed and when it's reused.

### Example on Memory leaks

In the following code, the memory that p points to is not freed.

```c
void *p;

int main() {
        p = malloc(7);
        p = 0; // The memory is leaked here.
        return 0;
}
```

Now compile and run.

```bash
clang -fsanitize=address -g  ./leak.c
./a.out
```

We can see the following outputs:

```bash
=================================================================
==17756==ERROR: LeakSanitizer: detected memory leaks

Direct leak of 7 byte(s) in 1 object(s) allocated from:
    #0 0x4ffc80 in malloc (/home/simon.liu/workspace/a.out+0x4ffc80)
    #1 0x534ab8 in main /home/simon.liu/workspace/./leak.c:4:8
    #2 0x7f127c42af42 in __libc_start_main (/usr/lib64/libc.so.6+0x23f42)

SUMMARY: AddressSanitizer: 7 byte(s) leaked in 1 allocation(s).
```

Note that **memory leak detection will only be conducted before  exiting the program**, which means that if you continuously allocate memory and then free it at run time, AddressSanitizer will not detect memory leak. At this time you need JeMalloc/TCMalloc to help.

## Fundamentals of AddressSanitizer

In this post we will give a brief introduction to AddressSanitizer's fundamentals. If you are interested in knowing the details of the algorithm behind, pleased refer to [AddressSanitizer: a fast address sanity checker](https://www.usenix.org/system/files/conference/atc12/atc12-final39.pdf).

AddressSanitizer replaces all your malloc and free, and then marks the before and after of the memory area that has been allocated (malloc) as `poisoned` (mainly to deal with overflow). And the freed memory is marked as `poisoned` (mainly to deal with `use after free`). Every memory access in your code will be translated to  the following by the compiler.

Before:

```c
*address = ...;  // or: ... = *address;
```

After:

```c
shadow_address = MemToShadow(address);
if (ShadowIsPoisoned(shadow_address)) {
  ReportError(address, kAccessSize, kIsWrite);
}
*address = ...;  // or: ... = *address;
```

First we can see   a memory address translating (MemToShadow) process, followed by determining whether the accessed memory area is poisoned. If so, the tool will  report an error and exit.

The reason why the translation process is here is that AddressSanitizer divides virtual memory into two parts:

1. Main application memory（Mem）, the memory used by the current program
1. Shadow memory, a memory that holds main memory meta information. For example, those areas of main memory that are poisoned are stored in shadow memory.

## Comparison of AddressSanitizer and Other Memory Detection Tools

The following [figure](https://github.com/google/sanitizers/wiki/AddressSanitizerComparisonOfMemoryTools#summary) is the comparison of AddressSanitizer and other memory detection tools:

![image](https://user-images.githubusercontent.com/38887077/74824227-f1544480-5342-11ea-8986-8eb88adaa1b3.png)

Parameter Description:

- _**DBI**_: dynamic binary instrumentation
- _**CTI**_: compile-time instrumentation
- _**UMR**_: uninitialized memory reads
- _**UAF**_: use-after-free (aka dangling pointer)
- _**UAR**_: use-after-return
- _**OOB**_: out-of-bounds
- _**x86**_: includes 32- and 64-bit.

We can see that AddressSanitizer only slows down the program by 2 times compared to Valgrind's 10 times.

AddressSanitizer currently supports GCC since 4.8 release and Clang since 3.1 release.

## Tips on Using AddressSanitizer

1. **Force the program to crash upon errors.** When ASan finds a memory access violation, the program does not crash automatically. This is because fuzzing tools usually detect this kind of error by checking the return code. However, we can force the program to crash by modifying the environment variable `ASAN_OPTIONS` to the following  before fuzzing test:

```bash
export ASAN_OPTIONS='abort_on_error=1'/
```

2. **Disable memory limits to solve memory limitation problems, but pay attention to the potential risks**. AddressSanitizer requires huge virtual memory (about 20 TB). But don't worry, this is just virtual memory. You can still use your program. However, fuzzing tools like american fuzzy lop will limit the memory usage of fuzzed software, you can solve this problem by disabling memory limits. The only thing to note is the risks brought by such operation: test samples may cause the program to allocate a large amount of memory, which may cause system instability or other applications crash. Thus when performing important fuzz tests, don't try to disable memory limits on the same system.

# Turn on AddressSanitizer in NebulaGraph

We used AddressSanitizer in **NebulaGraph** to help us find a lot of problems. Enabling AddressSanitizer in **NebulaGraph** is very easy. You only need to add the `ENABLE_ASAN` option in Cmake as below:

```bash
Cmake -DENABLE_ASAN=On
```

It is recommended that all developers turn on AddressSanitizer to run unit tests. By doing so, we can find many memory problems that are not easy to find and save  debugging time.

# 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. [An Introduction to NebulaGraph’s Query Engine](https://nebula-graph.io/posts/nebula-graph-query-engine-overview/)


This posts introduces to you Google’s memory error detect tool AddressSanitizer, covering what it is, how it works, and some best practices.

An Introduction to Google's Memory Error Detect Tool AddressSanitizer


​![product](https://user-images.githubusercontent.com/56643819/72118703-f6f65c00-338c-11ea-8fa2-1ecaa5b49bd5.png)

This article introduces how NebulaGraph uses Jepsen test framework to ensure system linearizability.

# Why Jepsen?
Linearizability here specifically means consistency in the CAP theory. In NebulaGraph, we guarantee strong data consistency in our key-value store.

So under such a consistency policy, we need to make sure:

- A read happens BEFORE a write operation ends must read the previous write
- A read happens AFTER a write operation ends must read the current write

Strong data consistency relies on a solid chaos testing plan which can affect a distributed system in many unplanned ways, which in turn  helps uncover corner cases that are hard to detect in development.

This is how Jepsen comes into play.

# What is Jepsen?
Jepsen is an open source software library for system testing. It is an effort to improve the safety of distributed databases, queues, consensus systems, etc.

Jepsen's author Kyle Kingsbury writes the test framework with Clojure, a functional programming language. He has then performed linearizability tests on some well known distributed systems and databases.

Currently Jepsen is still active on GitHub and it has become the actual benchmark for distributed systems.

# Jepsen Test Process
Below is a chart depicting the Jepsen test process:

![process](https://user-images.githubusercontent.com/56643819/72578065-e0617f00-390f-11ea-84e7-0c945f7ddca9.png)

By default there are six containers in the cluster, one of which is the control node and the other five are database nodes (the nodes are named n1 - n5 respectively).
As soon as  the test starts, the control node will create a group of worker threads, each contains its own client, to access the database nodes simultaneously via the SSH protocol. The generator tells the client what operations it should perform against the  system while the nemesis tells the client what fault the client should inject to the system. 

The beginning, ending, and results of each operation will be documented in Jepsen's history folder.  

When the test ends, the checker will analyze the history accuracy to verify if the results are linearizable. For the checker, you can use either the built-in validation model provided by [Jepsen knossos](https://github.com/jepsen-io/knossos), or you can define custom model per your own business requirements.

# Things to Consider Before the Test

To make sure the Jepsen test runs smoothly, please be sure to complete the following configuration before you start the test:

1. **Define operations in the DB API: download, install, start, and end**

You may delete the database log files when the test ends. Or you can specify a location for the log files and Jepsen will copy them to its own log folder for later analysis.

2. **Choose a client**

Be sure to have a client to access your database. The client can be either Clojure based such as etcd verschlimmbesserung, or JDBC and so forth. Then you need to define the client API to tell Jepsen what operations can be performed against your database.

3. **Select the test model in Checker**

For example, Jepsen will generate a chart for latency and the entire test process for performance test (checker/perf) and an html page containing timestamps of all operations for timeline test (timeline/html).

4. **Define failure types**

Specify the  types of faults you want to inject to the system in the Nemesis component. Some common ones include partition-random-halves and kill-node.

5. **Configure worker thread parameters**

Configure the operations within the worker thread in the generator process, as well as the time interval of each operation and each fault injection.

# Running Jepsen Test on NebulaGraph

NebulaGraph has three  components: meta layer, graph layer, and storage layer. The three layers work as a whole for NebulaGraph service to run normally. 

The Jepsen test is mainly on the storage layer.  

![architecture](https://user-images.githubusercontent.com/56643819/72118779-358c1680-338d-11ea-84ea-2ef07faec18d.png)

During the test against the KV storage API, we have built an eight-container cluster:

- One Jepsen control node
- One meta node
- One graph node
- Five storage nodes

The cluster is built in Docker and started by Docker-compose. Bear in mind the following two things:

1. There should be a subnet within the cluster so that the nodes can communicate with each other.
1. Install SSH service and enable passwordless login to the five storage nodes for the Jepsen control node.  


We have generated a jar package with the Java client and added it to the Clojure dependencies. Then the client can perform operations (put, get, cas, etc.) against the database. In addition, auto retry logic has been added to the Java client so that proper retry mechanism is enabled to make sure the operations have been successfully completed. 
Nebula-Jepsen, the test program developed by NebulaGraph, has three test models and three common chaos injections.

## Jepsen Test Models

### single-register

A single-register  stores only the value of one key. While the test program reads and writes the database simultaneously, each successful write  changes the value stored in the register. 

Then compare the read value from the database with the value in the register to see if they are consistent, which can validate whether the system is linearizable. 

Since it's a one-key register, the key is the same during the test and the value of the key is randomly generated upon operations.  

### multi-register

A multi-register however stores values of multiple keys. The validation process is the same as single-register, only that the keys are also randomly generated in multi-register.

Below is a sample of  read and write operations during the test:

```shell
4       :invoke :write  [[:w 9 1]]
4       :ok     :write  [[:w 9 1]]
3       :invoke :read   [[:r 5 nil]]
3       :ok     :read   [[:r 5 3]]
0       :invoke :read   [[:r 7 nil]]
0       :ok     :read   [[:r 7 2]]
0       :invoke :write  [[:w 7 1]]
0       :ok     :write  [[:w 7 1]]
1       :invoke :read   [[:r 1 nil]]
1       :ok     :read   [[:r 1 4]]
0       :invoke :read   [[:r 8 nil]]
0       :ok     :read   [[:r 8 3]]
:nemesis        :info   :start  nil
:nemesis        :info   :start  [:isolated {"n5" #{"n2" "n1" "n4" "n3"}, "n2" #{"n5"}, "n1" #{"n5"}, "n4" #{"n5"}, "n3" #{"n5"}}]
1       :invoke :write  [[:w 4 2]]
1       :ok     :write  [[:w 4 2]]
2       :invoke :read   [[:r 5 nil]]
3       :invoke :write  [[:w 1 2]]
2       :ok     :read   [[:r 5 3]]
3       :ok     :write  [[:w 1 2]]
0       :invoke :read   [[:r 4 nil]]
0       :ok     :read   [[:r 4 2]]
1       :invoke :write  [[:w 6 4]]
1       :ok     :write  [[:w 6 4]]
```

In the sample above, the number on the left indicates the worker (i.e. thread No.) which performs the operation. Every time an operation is initiated, the record is tagged as invoke and the column right next to it specifies if it's a read or a write. The info within the square brackets are the details of the operation.
Let's see some examples:

- `:invoke :read   [[:r 1 nil]]`This row records a read operation has been initiated intending to read the value of key 1. Since the operation has just started, the value of the key is unknown, hence "nil" next to 1.
- `:ok     :read   [[:r 1 4]]` This row records a successful read operation and the value of key 1 is 4.


You may also notice a nemesis operation in the sample above.

- `:nemesis   :info   :start  nil` This row records the beginning of a nemesis operation.  The next record indicates that  nemesis intends to isolate n5 from the cluster so that it's unable to communicate with other nodes within the cluster.

### cas-register

Besides the read and write, there's a cas-register  to validate cas (compare-and-set) operations. 

Below is a sample code from the test:

```shell
0		:invoke	:read		nil
0		:ok			:read		0
1		:invoke	:cas		[0 2]
1		:ok			:cas		[0 2]
4		:invoke	:read		nil
4		:ok			:read		2
0		:invoke	:read		nil
0		:ok			:read		2
2		:invoke	:write	0
2		:ok			:write	0
3		:invoke	:cas		[2 2]
:nemesis		:info		:start	nil
0		:invoke	:read		nil
0		:ok			:read		0
1		:invoke	:cas		[1 3]
:nemesis		:info		:start	{"n1" ""}
3		:fail		:cas		[2 2]
1		:fail		:cas		[1 3]
4		:invoke	:read		nil
4		:ok			:read		0
```

Just like the single-register test, the key remains the same during the entire cas operation test process. 
Let's take a look at some examples:

- `:invoke	:read  nil` This row records the initiation of a read operation. Since it's just the beginning, the result is nil.
- `:ok  	:read  0` This row records a successful read operation. The value returned is 0.
- `:invoke	:cas  [1 2]` This row records the initiation of cas operation, i.e. update the value to 2 if the read result is 1. 

## Introducing Failures in Jepsen

Below are the three types of failures NebulaGraph has injected to the cluster for chaos testing purpose.

### kill-node

The control node of Jepsen will randomly kill a certain database service on a node several times during the entire test. When a node is killed, the available nodes decreased by one in the cluster. After a certain time, the database service of the node is started and the node will rejoin the cluster.

### partition-random-node

Jepsen will randomly isolate a node from others during the test, so that there is no communication between this node and other nodes. Then Jepsen will repair this network isolation after a certain time to restore the cluster to its original state.

### partition-random-halves

In this common network partition, the Jepsen control node randomly cuts the five database nodes into two parts, one of which has two nodes and the other has three. Communication will be resumed after a certain period of time as shown below.

![partition](https://user-images.githubusercontent.com/56643819/72118867-869c0a80-338d-11ea-878d-15ea79811a8b.png)

# Test Results

Jepsen will analyze the test results according to the requirements and get the results of this test. From the following output of the console, we can see the test is passed.

```shell
2020-01-08 03:24:51,742{GMT}	INFO	[jepsen test runner] jepsen.core: {:timeline {:valid? true},
 :linear
 {:valid? true,
  :configs
  ({:model {:value 0},
    :last-op
    {:process 0,
     :type :ok,
     :f :write,
     :value 0,
     :index 597,
     :time 60143184600},
    :pending []}),
  :analyzer :linear,
  :final-paths ()},
 :valid? true}


Everything looks good! ヽ(‘ー`)ノ
```

## Auto-Generated timeline.html File

After the test is completed, you will get an auto-generated timeline.html file. The follow picture shows part of this file.

![timeline](https://user-images.githubusercontent.com/56643819/72118901-a9c6ba00-338d-11ea-9efa-045ed1914608.png)

The above picture shows the timeline of operations. Each execution block has the corresponding execution information.Jepsen verifies the linearizability based on this operation order. This also acts as Jepsen's core. We can also track faults with the HTML file.

## Performance Analysis Generated With Jepsen

Following are some performance analysis charts generated with Jepsen. This project name is basic test, please note that your project name may be different.

![latency](https://user-images.githubusercontent.com/56643819/72118934-c5ca5b80-338d-11ea-9603-ca65a36baf1b.png)

We can see the read and write latency in this chart. The above grey area incites the timing of fault injection. In this test we injected random killing node.

![rate](https://user-images.githubusercontent.com/56643819/72118989-e5fa1a80-338d-11ea-8f81-af98870621ca.png)

This chart shows the success rate of read and write. We can see the highlighted bottom red area is where failures occurred. This is because the control node stopped the partition leader's nebula service when killing a node. The cluster needs to re-elect at this time. When new leader is selected, the read and write are restored to normal.

# Conclusion

Jepsen has some short comings, such as the test can't run for a long time, because a large amount of data will cause out of memory during the verification phrase.

However, in actual scenarios, many bugs require long-term stress tests and fault simulations to discover, and the stability of the system also requires long-term running to be verified. Meanwhile, when testing NebulaGraph with Jepsen, we also found some bugs that we've never seen before, some of which may never happen in use.

Currently, we are using Jepsen to test NebulaGraph on daily basis. We release the newly-updated code to the Docker Hub every day to perform continuous tests of the latest images with the Nebula-Jepsen.

# References

- Jepsen HomePage: [https://jepsen.io/](https://jepsen.io/)
- Jepsen GitHub: [https://github.com/jepsen-io/jepsen](https://github.com/jepsen-io/jepsen)
- [Raft Understandable Distributed Consensus](http://thesecretlivesofdata.com/raft/)
- [The Raft Consensus Algorithm](https://raft.github.io/)
- NebulaGraph GitHub: [https://github.com/vesoft-inc/nebula](https://github.com/vesoft-inc/nebula)

# 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. [An Introduction to NebulaGraph’s Query Engine](https://nebula-graph.io/posts/nebula-graph-query-engine-overview/)

This article introduces how NebulaGraph, an open-source distributed graph database, uses Jepsen test framework to ensure system data consistency.

Tag