Welcome to an exploration multi-tenant architecture - it’s all about resource utilization and data security for software. This post will provide in-depth insights into multi-tenancy, its benefits and how companies like Salesforce use it. You’ll also see how [NebulaGraph Enterprise v5.0](https://www.nebula-graph.io/posts/nebulagraph_enterprise_5.0_gql_support) has embraced this architecture in its product design.

# What is multi-tenancy?
Tenants are equivalent to the "instance" concept of traditional databases to a certain extent. Tenants are completely isolated from each other. In terms of data security, cross-tenant data access is not allowed to ensure that there is no risk of user data assets being leaked. In terms of resource usage, tenants "exclusively" occupy their resource quotas. Generally speaking, a tenant is both a container for various database objects and a container for resources (CPU, Memory, IO, etc.).

Multi-tenancy in the context of databases means a single instance of software serves multiple users or tenants. In a multi-tenant database, the data for all tenants is stored in one database which can be either a physical or virtual one. The data for each tenant is separated from the data of other tenants by a simple partitioning of the database or by more complex methods like encryption or separate schemas for each tenant.

Multi-tenant architecture is used in scenarios where multiple users or organizations need to access the same database without access to each other’s data. For example, a SaaS provider would use multi-tenant management to provide database services to multiple customers using the same underlying software and hardware.

# How Multi-Tenancy Works

Multi-tenant architecture creates separate, isolated environments within a single physical infrastructure, like a virtual machine, server or cloud platform. This is done by partitioning the data storage and processing; each tenant has their own dedicated space in the system. A tenant interacts with the app and can access their own data.

![image](https://miro.medium.com/v2/resize:fit:720/format:webp/1*dt0aQxbm0xQBqYZ4mcdaRA.jpeg)

*Image source: https://medium.com/@harish.somasundar14/database-multi-tenancy-7c8dbe848d50*

Because each multi-tenant environment is separate from each other, they can be customized to meet the needs of each individual tenant without affecting other environments. Tenants can customize features like user interface and data security settings for their environment. They can also have different rules for each domain for access control, resource allocation and feature availability.

# Benefits of Multi-tenant Architecture
Business can benefit from multi-tenant architecture in software while minimizing its challenges, including improved security, cost efficiency, and better resource utilization, etc.

- Data Security: Multi-tenant architecture with resource isolation secures data by keeping each tenant’s data separate and preventing one tenant from accessing another’s data. Plus it simplifies security management as security policies can be applied across all tenants.
- Cost Efficiency: Multi-tenancy provides cost savings as multiple tenants can share the same database infrastructure, no need for separate hardware and software for each tenant. By sharing resources and reducing the need for dedicated resources for each tenant, the company can cut down operational and maintenance costs. Plus automated operation and maintenance tools associated with multi-tenant management can reduce time and effort for routine tasks leading to more cost savings.
- Efficient Resource Utilization: In a large organization, different teams or departments may need to access and work with the same resources. With multi-tenancy a single instance of a software application can serve multiple tenants (i.e. teams or departments) thus maximizing resource utilization and reducing redundancy.
- Scalability: Multi-tenant architecture allows for easy scalability as scaling up is more efficient and less disruptive. When the company grows and more teams need access to the database new tenants can be added without the need for additional software instances.g
- Simplified Management: With multi-tenant architecture, managing updates, implementing changes, and troubleshooting issues can be done from a single point, simplifying the overall management process.

# Real-life Cases of Multi-tenant Architecture
Below are two examples for a real-life use case of multi-tenant architecture. In both examples, multi-tenant management is key to efficient resource utilization, cost savings and high data security and performance.

Salesforce leverages multi-tenant architecture to deliver its Customer Relationship Management (CRM) software as a service. This architecture allows Salesforce to provide a single instance of its application to multiple customers, which reduces costs, simplifies maintenance and upgrades, and allows for scalability as the number of clients grows.

Another industry example is the telecom sector. Telecom companies use multi-tenant architecture in their billing systems. These systems need to manage data for millions of customers, each with their own plans, usage patterns and billing cycles. By using multi-tenant architecture, these companies can isolate each customer’s data while managing resources efficiently, bill correctly and perform well.

#Examples of Databases with Multi-Tenant Architecture

Multi-tenancy is often used in Software as a Service (SaaS) applications where it can provide cost savings and scalability. For databases it’s more common in distributed databases and cloud-based systems where multiple users or tenants can share resources while keeping each other’s data private. Here are a few examples of distributed databases that support multi-tenant management and resource isolation:

- Apache Cassandra: Open-source, highly scalable and distributed NoSQL database that can handle large amounts of data across many commodity servers. It supports multi-tenancy and resource isolation, great for applications that need scalability and high availability.
- Microsoft Azure Cosmos DB: A globally distributed, multi-model database service that provides multi-tenancy and resource isolation. It's designed for applications with globally distributed users who need low latency access to data.
- NebulaGraph: Open-source, distributed graph database for super large-scale graphs with milliseconds of latency. Highly performant, horizontally scalable and fault-tolerant. Enterprise v5.0 has multi-tenant management and native GQL support.

# Multi-Tenant Architecture and NebulaGraph Enterprise v5.0
Graph databases as the underlying infrastructure have become platform oriented when integrated with real life business. This has led many tech teams to build graph based platforms to serve their business needs. Hence multi-tenant architecture has become a must have feature.

NebulaGraph Enterprise saw this trend and introduced multi-tenant architecture in its design since v5.0. This allows tenants to be managed in a single pane of glass, including support for third-party single sign on. The architecture also follows the principle of least privilege (PoLP) for authorization. This means users are given the minimum access – or permissions – they need to do their job. This reduces the risk of data breaches and unauthorized access.

The multi-tenant architecture of NebulaGraph Enterprise v5.0 also separates metadata management and data management, as well as permissions and roles. This separation aids in maintaining the integrity and security of data and user roles. Moreover, NebulaGraph architecture allows the same cluster resources to be shared, while different clusters have their own resources, permissions and data. This separation is necessary to meet performance targets and privacy and security requirements.

In summary, the multi-tenant architecture is all about resource utilization and data security and privacy. It serves the evolving needs of businesses that are building graph based platforms. If you are interested in trying NebulaGraph Enterprise, please [contact us](https://www.nebula-graph.io/contact) to try it out.


This post will provide in-depth insights into multi-tenancy, its benefits and how companies like Salesforce use it. You’ll also see how NebulaGraph Enterprise v5.0 has embraced this architecture in its product design.

Multi-Tenant Architecture: Enhancing Resource Utilization and Data Security

In the modern world of big data, graphs are undoubtedly essential data representation and visualization tools. 

Imagine navigating a city without a map. When working with complicated networks, such as social relationships, molecular structures, or recommendation systems, data analysts frequently encounter similar difficulties. Here's where graph embeddings come into play. They allow researchers and data analysts to map nodes, edges, or complete graphs to continuous vector spaces for in-depth data analysis. 

What are graph embeddings and how do they work? In this guide, we examine the fundamentals of graph embeddings, including:

* What are graph embeddings 
* How graph embeddings work
* Benefits of graph embeddings
* Trends in graph embeddings

This guide will help you uncover the mysteries contained in graphs, whether you are a data analyst, researcher, or someone just interested in learning more about the potential of network analysis. Continue reading!

# Fundamentals of graphs

A graph is a slightly abstract representation of objects that are related to each other in some way, and of these relationships. Typically, the objects in a [graph database](https://www.nebula-graph.io) are drawn as dots called vertices or nodes.  A line (or curve) connects any two vertices representing objects that are related or adjacent; such a line is called an edge.

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

It is a simplified map where lines represent relationships and dots represent items. These dots, or vertices, hold information about the entities, while the lines, or edges, represent the connections between the entities.

After learning about the vertices and edges that comprise a graph, let's investigate some of its unrealized possibilities: graph embeddings.

# What are graph embeddings? 

Graph embedding refers to the process of representing graph nodes as vectors which encode key information of the graph such as semantic and structural details, allowing machine learning algorithms and models to operate on them. In other words they are basically low-dimensional, compact graph representations that store relational and structural data in a vector space. 
Graph embeddings, as opposed to conventional graph representations, condense complicated graph structures into dense vectors while maintaining crucial graph features, potentially saving time and money in processing.

Ever wondered how your social media knows to suggest perfect friends you never knew existed? Or how your phone predicts the traffic jam before you even hit the road? The answer lies in a hidden world called graphs, networks of connections, like threads linking people, places, and things. And to understand these webs, we need a translator: graph embeddings.

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

Think of them as a magic trick that transforms intricate networks of vertices and edges into compact numerical representations. These "embeddings" capture the essence of each node (vertex) and its relationship to others, distilling the complex network into a format readily understood by machine learning algorithms.

# Benefits of graph embeddings

Being able to represent data using graph embedding offers great benefits, including: 

1. Graph embeddings allow researchers and data scientists to explore hidden patterns within large networks of data. This greatly enhances the accuracy and efficiency of machine learning algorithms 
2. By identifying hidden patterns, researchers can make informed decisions and come up with better solutions for complex problems.
3. Graph embedding distills complex graph-structured data and represents them as simple numerical figures, making computation operations on them very easy and fast. This benefit allows even the most complex algorithms to be scaled to fit all sorts of datasets.

# Techniques for generating graph embeddings

Graph embedding algorithms and node embedding techniques are the two main kinds of techniques used to construct graph embeddings.

## 1. Node embedding techniques

These techniques focus on representing individual nodes within the graph as unique vectors in a low-dimensional space. Imagine each node as a distinct character in a complex story, and these techniques aim to capture their essence and relationships through numerical encoding.

### i). DeepWalk

Inspired by language modeling, DeepWalk treats random walks on the graph as sentences and learns node representations based on their "context" within these walks. Think of it as understanding a word better by its surrounding words in a sentence.

### ii). Node2Vec

Building on DeepWalk, Node2Vec allows for flexible exploration of the graph by controlling the balance between breadth-first and depth-first searches. This "adjustable lens" allows for capturing both local and global structural information for each node.

### iii). GraphSAGE

This technique focuses on aggregating information from a node's local neighborhood to create its embedding. Imagine summarizing a person based on their close friends and associates. GraphSAGE efficiently handles large graphs by sampling fixed-size neighborhoods for each node during training.

## 2. Graph embedding algorithms

While node embedding techniques concentrate on specific nodes, graph algorithms try to capture the interactions and general structure of the entire network. Think of them as offering a thorough summary of the network that accounts for each node individually as well as its connections.

### i). Graph Convolutional Networks (GCNs)


GCNs function directly on the graph structure, executing convolutions on adjacent nodes to represent their interconnection. They were inspired by convolutional neural networks for images. Consider applying a filter to an image that takes into account not only a pixel but also the pixels surrounding it.


### ii). Graph Attention Networks (GATs)


Expanding upon GCNs, GATs incorporate an attention mechanism that enables the network to concentrate on the most pertinent neighbors for every node, perhaps resulting in more precise depictions. 

### iii). Graph Neural Networks (GNNs)


Refers to a variety of graph data processing and node representation learning frameworks. Their approach blends concepts from conventional neural networks with graph-specific processes to extract structure information as well as node attributes.

Keep in mind that the subject of graph embedding is continually changing, with new methods and improvements appearing on a regular basis.

# Applications of graph embeddings

Due to their ability to turn graph data into a computationally processable format, graph embedding is useful in graph pre-processing. 
Before we get to the use cases, let's look at the capabilities that provide the foundation that inform the use cases for graph embeddings: 
|  |  |
| --- | --- |
| **Graph Analytics** | Graph embeddings make it easy to gain insight into the structure, patterns and relationships in graphs |
| **Machine Learning and Deep Learning** | Graph embeddings make it possible to represent graph data as continuous data,  making it useful in natural language processing and training of various models such as recurrent neural networks |
| **Measuring the similarity between two vectors** | Graph embedding makes it easy to understand how users interact with items  |

Based on the above capabilities, graph embeddings find wide-ranging applications in several disciplines due to their capacity to capture intricate interactions inside graphs and represent them in low-dimensional vector spaces. 

Here are some important use cases.

## 1. Social Network Analysis

In [social network analysis](https://www.nebula-graph.io/posts/social-networks-with-graph-database-1), graph embeddings facilitate community detection, user behavior prediction, and identification of influential nodes. 

Consider Facebook as an example, where graph embeddings help uncover communities of users, [predict friendship connections](https://swetapadma449.medium.com/facebook-friend-recommendation-using-graph-mining-8d8d62153d14), and identify influential users based on their interactions and network centrality.

## 2. Recommendation Systems

Graph embeddings power [recommendation systems](https://www.nebula-graph.io/posts/use-cases-of-graph-databases-in-real-time-recommendation) by modeling user-item interactions and capturing recommendation graph structures. 

For example, systems like Netflix and YouTube use graph embeddings to recommend movies and videos based on users' past movie ratings among other metrics

## 3. Knowledge Graphs

In [knowledge graphs](https://www.nebula-graph.io/posts/how-to-build-knowledge-graph), graph embeddings enable query response, entity linking, and semantic similarity computation. 

The accessibility and interpretability of knowledge graphs are improved by integrating entities and relations.

## 4. Biological Networks and Bioinformatics

Graph embeddings are used in the analysis of biological networks, including gene regulatory networks and protein-protein interactions. 

They can be used to detect gene-disease connections, accelerate drug discovery, and predict targets and protein functions by foreseeing target-drug interactions.

## 5. Fraud Detection and Anomaly Detection

It is critical to safeguard users and financial systems against fraud. Graph embeddings play a critical role in fraud and anomaly detection systems by enabling the identification of anomalous patterns in networks such as social networks and financial transactions.

**Also Read:** [Fraud Detection With Graph Analytics](https://www.nebula-graph.io/posts/fraud-detection-with-graph-analytics) 

# Metrics for evaluating graph embeddings

It's not enough to only create strong graph embeddings; we also need instruments to evaluate them. 

Metrics for Evaluating Graph Embeddings measure how well graph embedding methods capture and maintain the relational and structural information in graphs. 

Important measurements include:

* Node Classification Accuracy: Indicates how well nodes' properties and relationships can be captured by using learned embeddings to predict their labels.
* Link Prediction Accuracy measures how well a graph's learned embeddings may be used to predict future or missing edges, demonstrating how well graph topology is captured.
* Graph Reconstruction: Measures the degree to which graph attributes can be preserved by reconstructing the original graph structure using learned embeddings.
* Downstream Task Performance: Measuring downstream task performance with learned embeddings shows how useful downstream machine learning tasks are in practical applications.
* Embedding Quality: Assesses the degree of similarity preservation, dimensionality reduction, and computing efficiency that make up learned embeddings.

All things considered, these measures offer thorough insights into the effectiveness and generalizability of graph embedding methods across a range of fields and applications.

# Challenges in generating effective graph embeddings and how to overcome them

It can be difficult to generate efficient graph embeddings since analysts have to reduce the dimensionality of the graph while maintaining its structural information. 

As a result, creating graph embeddings often encounters these primary issues:

## Scalability issues  

Accurate and efficient embeddings of graphs can be challenging to produce due to their huge size and complexity.
Scalability is an important concern, especially in the processing of real-world applications where the graphs might be of huge size and keep on changing.

## Heterogeneity issues

You can encounter challenges in representing the structural information of a network in a low-dimensional space because nodes and edges in graphs have varying types and properties.

## Sparsity issues

A large number of nodes and edges in some networks may lack connections, making them extremely sparse. Because of this, it could be challenging to represent the graph's structural information in a low-dimensional space.

To overcome these challenges, researchers have developed several techniques and algorithms for generating effective graph embeddings including sampling strategies, skip connections, inductive learning, and adversarial training.

## Future trends in graph embeddings

The future of graph embeddings is shaped by these emerging trends, mostly aimed at addressing evolving complexities. 

* Dynamic graphs require adaptive embedding techniques. 
* Interpretability is vital, with many techniques seen as opaque "black boxes." Demand will continue to grow for interpretable methods providing transparent insights.
* Efficiency will remain crucial amid growing graph complexity. Techniques must balance accuracy with computational efficiency.
* Scalable algorithms tailored to dynamic and multi-modal graphs will rise. They prioritize interpretability, offering clear explanations.

In summary, the future of graph embeddings relies on adaptive, interpretable, and efficient techniques navigating dynamic, multi-modal graph data, fostering innovation across domains.

# Conclusion

Graph embeddings have made it possible to untangle complex networks and reveal hidden connections. From social media analysis to drug discovery, their applications are vast. 

While challenges like scalability and interpretability persist, the future shines bright with dynamic and multi-modal techniques.

NebulaGraph supports graph embeddings and is  available in AWS and Azure. Get started with a [Free Trial](https://www.nebula-graph.io/choose-a-cloud-vendor) and witness the power of connections truly unveiled. 

What are graph embeddings and how do they work? In this guide, we examine the fundamentals of graph embeddings

What are graph embeddings ?

A company probably has lots of data from multiple sources. This could be internal employee data, customer data, data from public sources or even data the company pays to acquire. 

To get value from this data, it normally needs to be channeled through a pipeline that transforms it and eventually presents it in a manner that is usable. Now, for a long time, data management systems have always been in formats that are very complex. You are either plowing through thousands of rows of data or searching through multiple tables to combine different pieces of data to get a result. 

But what if it was possible to visualize all the data instead of packing it in multiple tables that make management a complex affair? This is where knowledge graphs come in. 

Knowledge graphs are instrumental in places like the search engines we use to find facts and the chatbots that are becoming popular in areas like customer support. They even power the fraud detection solutions that protect businesses from cybersecurity threats.

In this article, we explore the important steps it takes to build a vibrant knowledge graph. 

# What is a Knowledge Graph?

In simple terms, a knowledge graph is a knowledge base with a graph structure. It utilizes a [graph database](https://www.nebula-graph.io/) and graph interface for data storage and visualization, respectively. 

While the term has been around since as far back as [1972](https://dl.acm.org/doi/fullHtml/10.1145/3447772),  the knowledge graph was popularized by Google in 2012 in a bid to replace its traditional search system. It’s no wonder then that when you google the phrase “knowledge graph”,  one of the top results you will see will probably be the popular Google's knowledge graph. 

We choose to use Google’s Knowledge graph to demonstrate the mighty value of knowledge graphs for a good reason. You see, Google has utilized knowledge graphs to great effect and this could as well be one of their powerful secret cards. 

In fact, Google admits in their own blog that “The Knowledge Graph enables you to search for things, people or places that Google knows about—landmarks, celebrities, cities, sports teams…”. 

This is a great revelation of what a knowledge graph can accomplish when built right and put into serious use. In essence, what Google means by “things, people or places” that they know is hsimply data. So they basically take this data and put it in a knowledge graph, and this helps them to drive many of their successful products like the search engine. 

Rather than accessing and presenting queried data in the traditional rigid manner, knowledge graphs add meaning to queries and data. For instance, traditional search algorithms (like those used in many eCommerce stores) only present data that fits queries exactly. For example, a search query for “bag” brings all results with the “bag” keyword in them. 

Semantic algorithms, on the other hand, understand the query, give context to the query, and present dynamic results that fit the query best. A query for “bag” acquires results in the context of “what is a bag” or “different types of bags”. This is made possible thanks to Knowledge Graphs. 

**Also Read:** [Knowledge Graphs and Large Language Models](https://www.nebula-graph.io/posts/knowledge-graphs-via-natural-language)

# Why does your organization need a knowledge graph?

In the same way that Google is benefiting from the knowledge graph, you too can take all the data that your company possesses, put it into a knowledge graph and use it to drive great products for your customers or even for internal use. 

In addition to improving search, 
* Knowledge graphs can help in the storage of microdata in machine and human-readable forms
* They simplify large data sets
* They enrich the knowledge base. You don’t just define relationships but also expose hidden relationships between data. With this, complex customer needs are revealed for more effective product recommendations, and business research generally becomes easier and more comprehensive
* Knowledge graphs also help you track the flow of an element, which is useful for monitoring solutions. A financial organization, for example, will more easily track the flow of money. A cybersecurity solution can more easily identify affected systems by tracking the flow of a threat.

One key thing that a knowledge graph does is that it makes it very easy to visualize data. This is possible because of how graph databases work - through connections. If, for example, you run an eCommerce website that sells different types of phones and there is this customer known as ‘John’ who loves to buy a Samsung phone every time the company releases a new phone, you might want to discover which other products John loves to buy so that you can make recommendations. To do this, you will need to connect John to all the other products he has been buying. Once you find the other products that John is fond of buying, you might want to see if there are other customers that have the same traits as John. This requires a connection of all the customers that buy a Samsung phone every time a new one is released. Now, a knowledge graph makes it easy to visualize all these connections, unlike traditional database approaches. If you were to use a traditional database, you will probably need to join multiple tables and do some aggregation. It’s too much work.  You will have customers in one table, products in another table, their location in another table, etc. But a graph database will have all this information in one place, enabling you to build connections and derive insights. 

**Also Read:** [Using Knowledge Graph to Detect Fraud ](https://www.nebula-graph.io/posts/fraud-detection-using-knowledge-and-graph-database)

# How to build a knowledge graph: simple steps

Building your own comprehensive knowledge graph is important for two things. It ensures you meet up with competitors that already have it implemented. It then allows you to beat competitors in how you use and manage data.

Follow these steps to create one that’s effective.

## Step 1: Define the goal or purpose of the knowledge graph

The first step to building knowledge graphs is to determine what you want to use for the organization. Knowledge graphs have a wide range of applications in enterprise environments. 

For instance, you can use them to just gather, store, and organize data in a format that modernizes your use of data. In more complex applications, you can use them to support a semantic search system and eliminate hallucinations from natural language processing (NLP) operations. 
* Do you wish to awaken siloed data or reconnect with siloed data environments? 
* Are you intending to create intelligent chatbots?
* Do you want to engage in dynamic, complex research? 
* Are you looking to visualize/monitor the flow of assets and risks within the organization?

In a nutshell, you need to determine what you want to use your knowledge graph for before moving to the next steps. 

Another way to structure this step is by asking: What questions am I trying to answer? 

Let’s say you want the knowledge graph to help you dig deeper into customer habits. In this case the questions you might want answers for could include:
* How many customers signed up today and how many of those actually purchased a product?
* What is the gender of these customers?
* Where are they located? 
* What age bracket forms majority of the customers?
* What products are popular among each age bracket?

If you’re having difficulty defining the key goal (s), engaging stakeholders can point you in the right direction. Stakeholders are the individuals poised to work with, benefit from, or be affected by the graph when it is eventually launched. This initiative will help you secure buy-in and get adequate support throughout the building process.     

## Step 2: Establish your knowledge domain

Establishing a knowledge domain is all about determining the scope of data to be utilized within the graph. Of course, this scope is in turn determined by your use case, and establishing a domain is best achieved when you go from the general to the specific. You use the general use case to determine specific entities and their characteristics within the use case.

If you wish to build a semantic search system for eCommerce products, for example, your graph should use data that is relevant to this scope. This will be specific data like the product name, product specification, product category, product price, and product vendor, among others. Establishing the domain helps you understand the type of data to collect so your knowledge graph satisfies the intended use case/goals. 

## Step 3: Gather, clean, and organize relevant data

Now, it’s time to collect relevant data from different sources. You gather data from either private sources within the organization or public sources like [OpenAIRE](https://www.openaire.eu/) and [Wikidata](https://www.wikidata.org/wiki/Wikidata:Main_Page). Wikidata is a database specifically designed to store data in a format that both humans and computers can read. 

Once you gather this data, you carefully analyze it and eliminate any form of redundancy within the data set. You want your knowledge base to be as succinct as possible — you want to be able to parse through data and answer questions as fast as you can. Deduplicate data, check for irrelevant data, and expand data types for more relevant ingestion.   

## Step 4: Choose a semantic data model

Semantic models define how you want to store and display data in the knowledge graph. They can be said to be formalized templates that define the structure of the knowledge graph. Your semantic model determines how you map and link different data together. 

Although you can create your semantic data model yourself, some organizations prefer to use existing semantic formalisms to hasten the process. A few of these include the [Resource Description Framework](https://www.w3.org/RDF/) (RDF), [SPARQL](https://www.w3.org/TR/rdf-sparql-query/), and the expandable [Web Ontology Language](https://www.w3.org/OWL/) (OWL). RDF presents data in basic triples, while OWL seeks to provide more expansive and specific semantics to data. The concept of triples will be explained later on. 

The baseline is to use a semantic model into which your data best fits. 

## Step 5: Choose a graph Database Management System (DBMS)

Once you have determined the semantic model, you choose a graph database management system (DBMS) that will best house and handle the knowledge graph for the identified use case. 

When making a choice here, you want to ensure the graph DBMS is compatible with existing business operations. You don’t just choose one that supports your semantic model, but you choose one that also scales with your business needs as projected.

Ingesting data into your graph DBMS is a huge step in bringing your knowledge graph to life. This is where your graph begins to take shape and show just how data-to-data relationships will be represented. Some good graph DBMSs include NebulaGraph, Neo4j, Memgraph, etc.   

## Step 6: Ingest data using ETL-enabled tools

To simplify data ingestion into your graph DBMS, you should utilize ETL tools. ETL (Extract, Transform, and Load) tools are programs that help with the conversion of data to formats that fit into your graph and graph DBMS. 

Thanks to automation, ETLs are more efficient than manual data loading. They aid data cleaning and permit easily customizable data loading processes. Examples of ETL tools for knowledge graphs include [Graph.Build Transformers](https://graph.build/graph-build-transformers) and [Graphable](https://www.graphable.ai/blog/graph-etl-neo4j-etl-best-practices/).  

## Step 7: Establish Ontology in Triples

Your taxonomy refers to general classifications and your ontology is the vocabulary you use to specifically define your data relationships. It is through ontology that you make general semantic models more personalized for your use case. 

This is where business goals reconcile with semantic models. Generally, we define ontologies in triples where there is a subject, predicate, and object. Here, there are two entities (subject and object) linked together by a predicate relationship. 

More specifically, three parts make up a knowledge graph ontology: 
* Node
* Edge
* Label

A node is an entity, while the edge defines the kind of relationship to exist between entities. A label specifically states this relationship based on the edge. For example, let’s look at an adult-infant environment.

The adult and infant are the nodes (entities). The edge can be to define a teaching relationship, and the label (according to the network direction) specifically identifies who teaches whom. We can, for example, say that  Adult 1 (node 1) teaches (label)  infant 1 (node 2) in a teaching environment (edge). You create ontologies like this for your specific use case. 

One thing to note when creating an ontology, however, is that you need to keep it extensible and reusable across the graph. The [D2KG Ontology](https://www.semantic-web-journal.net/content/d2kg-integrated-ontology-knowledge-graph-based-representation-government-decisions-and-0) is a good example of how to establish one for your business. It uses data from “Diavage”, a platform for recording government decisions, to create a vocabulary for the knowledge graph relevant to its use case (retrieving information on government actions).

## Step 8: Start small, with a small sample 

Now, it’s time to start experimenting with your ontology. You develop your knowledge graph through iterative steps — starting with small data and gradually scaling up. 

This is the step where you practically combine all you have learned so far. You combine semantic models with relevant vocabularies to develop your knowledge graph. Here, you start populating your knowledge graph to answer business-related questions. 

## Step 9: Test and adjust the knowledge graph 

This step is all about optimizing the knowledge graph to make it more effective and extract more value from data. 

Test the knowledge graph against its use case, analyze its performance, and improve on its defective attributes. 

One important operation to note in this testing phase is “inference”.  In the context of knowledge graphs, to inference means to find new relationships between data entities. It is one of the unique properties that  knowledge graphs have over relational data management systems and one advantage you have to utilize for your business. 

To spot these hidden relationships, you feed your prototype knowledge graph into an inference engine. This engine utilizes AI to understand and implement logical semantics within the graph and generate new relevant relationships. 

Test the post-inference knowledge graph for accuracy by running it through queries and semantic solutions you wish to use it with. Use it to answer business questions, check for consistencies, pit it against industry standards, and optimize it where you find it lacking.  

**Also Read:** [Difference Between Graph Database and Relational Database](https://www.nebula-graph.io/posts/graph-database-vs-relational-database)

## Step 10:   Develop and publish expanded graph for enterprise use

Once you have found the business-effective mix of modeling, ontology, and inference connection, it’s time to develop the prototype into a fully enterprise knowledge graph. 

Create the full-scale knowledge graph, integrating it with all data sources through ETL tools and utilizing all data to populate the visual knowledge base.

## Step 11: Revisit the business goals and check if they have been met 

In the real-world environment, your knowledge graph may behave differently from its prototype in the test environment. To validate its usability, accuracy, and value, you need to compare its results against the business goals drafted in Step One. 
* Are query results fitting the context?
* Are recommendations powered by the knowledge graph working better for customers? 
* Is your chatbot giving satisfactory answers to all customer queries?

In short, check the results against why you needed the knowledge graph in the first place. 
**Demo:** [How to build and query a knowledge by using natural language with NebulaGraph  ](https://www.nebula-graph.io/posts/build-knowledgegraph-via-natural-language-demo)

# Perfecting your Knowledge Graph

So, now you understand how to get knowledge graphs built to serve you perfectly both in the test and real-world environment. You know that you need to check it for business effectiveness. Guess how you can make it better?

You can make your enterprise knowledge graph better by keeping it easy to update and optimize for more accuracy and semantic expansion. 

In other words when building a knowledge graph, leave room for change. Ensure you can optimize it post-launch, integrate solutions to new business discoveries, and grow the database as the business and data grows. 

A great knowledge graph is one that is capable of scaling over time. It is only through this that you can meet or beat competitors in your organization’s search for more market share. 

NebulaGraph is highly scalable and you can use it to build robust knowledge graphs for different use cases, from fraud detection to product recommendations and many more. It’s available both in [Azure](https://azuremarketplace.microsoft.com/en-us/marketplace/apps/vesoftcompanylimited1625556994617.nebulagraph_enterprise?tab=Overview) and [AWS](https://aws.amazon.com/solutions/partners/vesoft-nebula-graph/). Get started with your [free trial](https://www.nebula-graph.io/choose-a-cloud-vendor) and deploy the fastest graph database in just one click.



NebulaGraph is highly scalable and you can use it to build robust knowledge graphs for different use cases, from fraud detection to product recommendations and many more

How to Build a Knowledge Graph

Databases are useful in many ways besides their core function of storing and serving data. For example, databases are useful in areas like reporting and auditing, just to mention a few.

When you want to use some data set from a database for something like reporting or analysis, it would be easier if you were to be able to go to the specific period you are interested in and get the data set as it were for the period of interest. Database snapshots become useful in such moments.

In this simple guide, we explore database snapshots with a focus on how they work.

**IMPORTANT NOTE:** Please note that database snapshots are not only a preserve of SQL databases as this is the common notion. No, the concept applies across all types of databases such as a [graph database](https://nebula-graph.io/) and others. 

**Also Read:** [What is a Graph Database? ](https://www.nebula-graph.io/posts/why-use-graph-databases)

# What is a database snapshot?

A database snapshot is essentially a static, read only view of the source database. The key principle is that the snapshot will always be consistent with the source database, as at the moment the snapshot was created. 

The snapshot will always be domiciled in the same server instance where the source database resides. As more changes are made to the source database, the size of the snapshot file increases.

Database snapshots are the closest we’ve come to time travel in data operations. They offer a powerful complement to backups, playing a crucial role without compromising the integrity of the source database. 

Picture this as an example - you are in charge of a website for an e-commerce store that relies heavily on a database for customer and product information, orders, and inventory management. 

While installing new storefront features such as a new shopping cart plugin, disaster strikes, an incorrect setting in the plugin installation clip causes a misconfiguration. 

Panic sets in as your database spirals into chaos. Product images and descriptions are nowhere to be found, and customer complaints start pouring in. 

To quickly restore order, you turn to database snapshots. Database snapshots will help you to:

1. Restore any accidental deletion of product images and descriptions
2. Revert the database to a snapshot taken just before the update, effectively restoring the site to a stable state
3. Use the snapshot to identify the incorrect setting on the plugin script
4. Give you the option to use a different snapshot to test the update before deploying it to the live store.

From this example, it’s clear that database snapshots are extremely important. So, how do they work? 

**Also Read:** [Snapshots in NebulaGraph - An Introduction](https://www.nebula-graph.io/posts/nebula-graph-snapshot-introduction)

# How database snapshots work

A snapshot captures the state of the database at a specific moment without duplicating the entire dataset. 

For a simplistic demonstration, let’s say it’s now 2:00 PM. Some updates need to be made to a certain data set within the database. Before the changes are implemented, a snapshot of the dataset is taken as it is at 2:00 PM. Once the snapshot is taken, the changes are done and completed at 3:00 PM. Come 4:00 PM, another change is due. Again, another snapshot is taken which shows the state of the data as at 4:00 PM. So now there are two snapshots. If other changes are needed at 6:00 PM, the same procedure is followed.  

To simplify it further, we can say that  database snapshots work in a similar manner to how version control works. The focus is on taking a ‘snap’ of the current changes, and not the entire thing.

There are two main techniques at the center of the workings of database snapshots:

1. Copy-on-write
2. Redirect-on-write


## Copy-on-write

In this technique, the original data blocks that are due for modification are copied into a snapshot area. This is done before the blocks are overwritten. This way, the original data will be retained in the snapshot even as changes take place in the source database.

## Redirect-on-write

At the start of the write operation, the new data is written to a different block (location) while the original data remains in place. After the write operation is completed and recorded, the original data is retained in the snapshot while the newly written data is retained in the source.  

The key difference between these two mechanisms is in the process, right from the start to the end. In copy-on-write, the process starts by first ‘copying’ the original blocks to the snapshots. In redirect-on-write, the process starts by writing the new data to a different block i.e redirecting.

But in both methods, the newly written data eventually ends up in the master while the old one ends up in the snapshot. So the result is the same but the processes differ slightly.

Besides these two standard approaches, the following techniques can also be employed to create a database snapshot.

* **Differential snapshots:** This technique captures the data changes that have been made since the last snapshot was taken. In other words, the focus is on storing the difference between the current state and the last snapshot. This mechanism also reduces the storage space requirements. 
* **Clone snapshots:**  A clone of the existing data blocks is made at the time of making changes. The original data is preserved in the snapshot.
* **Thin provisioning:** Here, snapshots are created without the need to consume more space. The storage space is allocated in the course of making changes. This ensures optimum utilization of space.
* **Chain snapshots:** In this mechanism, snapshots are organized into a series of chains. Each snapshot is created based on the previous snapshot. This method makes it easy to track changes in the course of time and thus preserve the consistency of data.
* **Log snapshots:** In this method, the data blocks are not copied. Instead, the snapshot will capture the changes by making records of the operations that make modifications to the data.

# Key takeaways about how database snapshots work

* Copy-on-write and Redirect-on-write are the two main techniques that are used to create database snapshots
* A read-only static view of the database file of interest is created, instead of a duplicate data set.
* Reading data from the snapshot is essentially equivalent to reading from the primary data source.

**Also Read:** [How to Backup and Restore Data With Snapshots in NebulaGraph](https://docs.nebula-graph.io/3.6.0/backup-and-restore/3.manage-snapshot/)

# Benefits of database snapshots

The core advantage of database snapshots is that they are great for projects that always need modifications in real-time i.e when an application is still running. 

Here are the advantages in detail:

## Speed

Since the snapshots only capture the state of the database at a specific moment , they are quick to implement. This means they can be utilized in scenarios where speed is of utmost importance, and this is why they are highly recommended for real-time implementations.

## Efficient space usage

As snapshots only require space that is equivalent to the modifications created, they come with the advantage of not requiring too much space at a go. This saves a lot of the expenses that would have gone to storage resources.

## Database snapshots contribute to consistent performance

Since database snapshots do not come with the need to have the data set of interest duplicated, it means that system disruption is minimal . As a result, performance remains largely consistent even in the course of updates. 


## Database snapshots enhance analysis

This is possible thanks to the ability to create snapshots that cover a period of time. Such snapshots make it possible to query results that cover the given period. The results provide an opportunity to analyze aspects such as customer growth during a given period.

**Also Read:** [Graph Query Language ](https://www.nebula-graph.io/posts/graph-query-languages-you-should-know)

## Database snapshots can act as safeguards against errors

It's normal to experience errors in databases. Luckily, snapshots create the opportunity to revert to the previous state of the database before a snapshot was made. This minimizes data loss. In such cases the snapshot acts as a recovery option, and this is far much faster than having to restore from a backup. However, they should not be mistaken to be a substitute for backups. You still need to do backups - they are very important with a distinct and irreplaceable role. 

# Drawbacks of database snapshots

Database snapshots are great but not without drawbacks, just like any other type of technology out here. 

Here are some of the drawbacks or limitations of database snapshots:

* System overload: You can easily end up overloading the system if you create so many snapshots. This normally happens when there is no clear strategy on when to create, why and how to manage the snapshots.
* Overreliance: Some risks can crop up if there is going to be too much reliance on snapshots. We advise that they are utilized in moderation.
* Dependence on source database: Since database snapshots depend on the original source database, this renders them a non-redundant storage. So you cannot expect them to offer protection against corruption resulting from causes such as disk errors. In other words if the source files get lost or compromised, it would be impossible to make a restoration from snapshots. 
* Read-only: Snapshots cannot be upgraded since they are read-only.

**Also Read:** [Amazon Neptune vs NebulaGraph](https://www.nebula-graph.io/posts/amazon-neptune-vs-nebulagraph), plus [Memgraph vs NebulaGraph ](https://www.nebula-graph.io/posts/memgraph-vs-nebulaGraph)

# Scenarios where database snapshots are useful

Snapshots become useful mainly in the following functions:

* Auditing
* Reporting
* Analysis

In terms of auditing, auditors can easily go to specific snapshots and audit the state of the database at that particular moment. This makes work easier especially when certain parts of the audit demand focus on a particular period.

**Also Read:** [NebulaGraph Audit Logs
](https://docs.nebula-graph.io/3.5.0/5.configurations-and-logs/2.log-management/audit-log/)

Snapshots also become instrumental when preparing reports for different purposes. You can easily jump between different periods and extract relevant information, saving lots of time that would have been spent rummaging through the entire database or backup.

Same to analysis. If you want to analyze a specific period, you simply go to past snapshots and narrow to the snapshot that corresponds to the period in time.

# Key differences between database snapshots and database backups
 
| Database Snapshots| Database Backups |
| --- | --- |
| A database snapshot is a read-only static view of the source data set | A database backup is a readable copy of the source data set |
| A database snapshot always resides on the same server as the source database | A database backup can be kept in different locations including local storage, the cloud, or be sharable within the network |
| A database snapshot can only be restored to same location as the source database | A backup can be restored to a different location |

**Also Read:** [How NebulaGraph Supports Incremental Backup](https://www.nebula-graph.io/posts/nebulagraph-visualization-tools-v3.4.0)

# Conclusion

For best results, we advise that you review the snapshots on a regular basis and make sure you are only keeping snapshots that will be needed. This way you don't have to consume a lot of storage resources. Meticulous organization and management are key to getting the most value from snapshots.

Remember the ultimate goal of database snapshots is to enable efficient changes to the database, save on space utilization, sustain high levels of performance, and aid in activities such as reporting, auditing , and analysis. So, regardless of the mechanism or database you are going to use, keep your eye on these eventual goals of a typical snapshot operation.

NebulaGraph supports database snapshots and is 100% flexible in deployment. You can deploy it anywhere you prefer including on-premise, public cloud, hybrid, Windows, macOS. It's available on AWS and Azure marketplaces. [Start your free trial.](https://www.nebula-graph.io/choose-a-cloud-vendor)



In this simple guide, we explore database snapshots with a focus on how they work.

What is a Database Snapshot?

This article provides the performance test report for NebulaGraph Community Edition v3.5.0.

NebulaGraph Database v3.5.0 Benchmark Report

Memory management in databases is an important module in database kernel design, and measurable and controllable memory is an important guarantee for the stability of the database. Similarly, memory management is also crucial for [NebulaGraph Database](https://www.nebula-graph.io).
The multi-degree association query feature of graph databases often leads to a huge demand for memory in the execution layer of graph databases. This article mainly introduces the new feature Memory Tracker in NebulaGraph v3.4, aiming to achieve fine-grained control of memory usage by the Memory Tracker module, reduce the risk of system OOM kill for graphd and storaged, and improve the kernel stability of NebulaGraph database.


# Available Memory


Before diving into Memory Tracker, let's introduce some relevant background knowledge: available memory.

## Process Available Memory

Here, we briefly introduce how the system determines available memory under various modes.

**Physical Machine Mode**

The database kernel reads the system directory /proc/meminfo to determine the actual memory and available memory in the current environment. Memory Tracker takes "actual physical memory" as the "maximum memory that the process can use".

**Container/cgroup Mode**

In the `nebula-graphd.conf` file, there is a configuration item `FLAG_containerized` to determine whether the database is running in a container. After setting `FLAG_containerized` (false by default) to `true`, the kernel reads the files under the relevant `cgroup path` to determine how much memory the current process can use. There are two versions of `cgroup` - v1 and v2, and v2 is used as an example here.

| FLAG                               | Default Value                       | Explanation                           |
| :--------------------------------- | :---------------------------- | :----------------------------- |
| FLAG_cgroup_v2_memory_max_path     | /sys/fs/cgroup/memory.max     | Determine the maximum memory usage by reading the path |
| FLAG_cgroup_v2_memory_current_path | /sys/fs/cgroup/memory.current | Determine the current memory usage by reading the path |

For example, to control the memory quota for graphd and storaged on a single machine separately, follow these steps:：

Step 1：Set `FLAG_containerized=true`；

Step 2：Create `/sys/fs/cgroup/graphd/`，`/sys/fs/cgroup/storaged/`，and configure `memory.max` under their respective directories；

Step 3：Add relevant configuration in `etc/nebula-graphd.conf`，and `etc/nebula-storaged.conf`

```
--containerized=true
--cgroup_v2_controllers=/sys/fs/cgroup/graphd/cgroup.controllers
--cgroup_v2_memory_stat_path=/sys/fs/cgroup/graphd/memory.stat
--cgroup_v2_memory_max_path=/sys/fs/cgroup/graphd/memory.max
--cgroup_v2_memory_current_path=/sys/fs/cgroup/graphd/memory.current
```

## Memory Tracker Available Memory

After obtaining the "process available memory", the system needs to convert it into memory that Memory Tracker can track. There is a conversion formula between "process available memory" and "Memory Tracker available memory".

```
memtracker_limit = ( total - FLAGS_memory_tracker_untracked_reserved_memory_mb ) *  FLAGS_memory_tracker_limit_ratio
```
![usable_memory](https://www-cdn.nebula-graph.io/nebula-website-5.0/images/blogs/usable_memory.png)

| **FLAG**                                    | **Default Value** | **Explanation**                                                     | **Dynamic Change** |
| :------------------------------------------ | ---------- | ------------------------------------------------------------ | -------------- |
| memory_tracker_untracked_reserved_memory_mb | 50 M        | Memory Tracker manages memory allocated through new/delete, but there may be other ways a process consumes memory besides this method; for example, by calling low-level malloc/free. Memory not tracked by this flag is subtracted during calculations. | Yes            |
| memory_tracker_limit_ratio                  | 0.8        | Memory Tracker allows you to specify the proportion of memory it can use. In some scenarios, we may need to reduce this value to prevent out-of-memory (OOM) issues. | Yes            |

Here we'll elaborate on the usage of `memory_tracker_limit_ratio`:

- In a mixed deployment environment where multiple graphd or storaged instances are deployed together, it needs to be reduced. For example, if graphd only occupies 50% of the memory, you need to manually change it to 0.5 in `nebula-graphd.conf`;
- Value range: In addition to the (0,1] value range for `memory_tracker_limit_ratio`, there are two special values defined:
   - `2`：Dynamically adjusts available memory based on the current system runtime environment as perceived by the database kernel. This method is not real-time and may have some degree of inaccuracy;
   - `3`：The limit will be set to an extremely large value, effectively disabling Memory Tracker;

# How Memory Tracker is Designed and Implemented

Next, let's discuss the design and implementation of Memory Tracker. The overall Memory Tracker design consists of several sub-modules, including **Global new/delete operator**, **MemoryStats**, **system malloc**, and **Limiter**. In this section, we'll focus on the Global new/delete operator and MemoryStats modules.


![memory_tracker](https://www-cdn.nebula-graph.io/nebula-website-5.0/images/blogs/memory_tracker.png)

## Global new/delete operator

Memory Tracker overloads the global new/delete operator, taking control of memory allocation and deallocation, allowing memory quota allocation management before actual memory allocation takes place. This process is broken down into two steps:

- Step 1: Report memory allocation through MemoryStats；
- Step 2: Invoke jemalloc for actual memory allocation behavior；

> **jemalloc**：Memory Tracker does not change the underlying malloc mechanism, still using jemalloc for memory allocation and deallocation.

## MemoryStats

Global memory usage statistics are managed through GlobalMemoryStats and ThreadMemoryStats for global memory and thread-internal memory, respectively;

## ThreadMemoryStats

`thread_local`  variable, execution engine threads maintain their MemoryStats in their ThreadMemoryStats, including "memory Reservation information" and "whether to allow exceptions to be thrown on memory exceeded";

- **Reservation**

Each thread reserves a 1 MB memory quota to avoid frequent requests to GlobalMemoryStats for quota. When applying or returning, ThreadMemoryStats will use a larger memory block as the exchange unit with the global scope. 

- **alloc**：

Only when the locally reserved 1 MB memory is used up, will it ask the global scope for the next 1 MB. This approach is used to minimize the frequency of requesting memory quota from the global scope;


- **dealloc**：

The returned memory is first added to the thread's reserved memory, and when the reserve quota exceeds 1 MB, 1 MB is returned, and the rest is kept;

```
 // Memory stats for each thread.
 struct ThreadMemoryStats {
   ThreadMemoryStats();
   ~ThreadMemoryStats();
 
   // reserved bytes size in current thread
   int64_t reserved;
   bool throwOnMemoryExceeded{false};
 };
```

- **throwOnMemoryExceeded**  

Whether to throw an exception when the thread exceeds the memory quota. Only when `throwOnMemoryExceeded` is set to true will `throw std::bad_alloc` occur. See the `Catch std::bac_alloc` section for scenarios where `throw std::bad_alloc` needs to be disabled.

### GlobalMemoryStats

Global memory quota, maintaining limit and used variables.

- **limit**：limit: Calculated from the runtime environment and configuration information, it represents the maximum memory Memory Tracker can manage. Limit serves the same purpose as the Limiter module. For detailed memory conversion, see the "Memory Tracker Available Memory" section above;

- **used**：Atomic variable, summarizing all reported used memory from threads (including reserved portions). If used + try_to_alloc > limit, and when `throw OnMemoryExceeded` is set to true, `std::bad_alloc` exception will be thrown.


## Catch std::bac_alloc

Since Memory Tracker overloads new/delete and affects all threads, including third-party threads, throwing `bad_alloc` may cause unintended behavior in some third-party threads. To prevent such issues, we use an active memory detection approach in the code path, enabling memory detection in operators, RPC modules, etc.

## Memory detection in operators

In graph/storage operators, add `try...catch` (performing calculations/allocating memory in the current thread) and `thenError` (asynchronously submitting calculation tasks via `folly::Executor`) to detect Memory Tracker throwing `std::bad_alloc`. 

The database then returns an error code through Status, causing the query to fail;
When debugging memory, you can enable the `FLAGS_memory_tracker_detail_log` configuration item in the `nebula-graphd.conf` file and reduce the `memory_tracker_detail_log_interval_ms` to observe memory usage before and after the query;

**folly::future asynchronous execution**

```c++
thenValue([this](StorageRpcResponse<GetNeighborsResponse>&& resp) {
    memory::MemoryCheckGuard guard;
    // memory tracker turned on code scope
    return handleResponse(resp);
})
.thenError(folly::tag_t<std::bad_alloc>{},
    [](const std::bad_alloc&) {
    // handle memory exceed
})
```

**Synchronous execution**

```c++
memory::MemoryCheckGuard guard; \
try {
    // ...
} catch (std::bad_alloc & e) { \
    // handle memory exceed
}
```

## Memory detection in RPC

RPC mainly addresses memory quota control issues during the serialization/deserialization of Request/Response objects. Since storaged responses are all encapsulated in the DataSet structure, the problem is transformed into memory detection during DataSet serialization and deserialization.

**Serialization**： DataSet object construction is in the NebulaGraph operator result return logic, and by default, memory detection is enabled;

**Deserialization**：Explicitly enabled through `MemoryCheckGuard`, exceptions can be caught in `StorageClientBase::getResponse's onError`;

## Error Codes

To help identify which module has issues, NebulaGraph has added relevant error codes, indicating memory exceeded exceptions in graphd and storaged respectively:

```
E_GRAPH_MEMORY_EXCEEDED = -2600, // Graph memory exceeded
E_STORAGE_MEMORY_EXCEEDED = -3600, // Storage memory exceeded
```

# How NebulaGraph Works
1. [NebulaGraph Architecture — A Bird’s Eye View](https://www.nebula-graph.io/posts/nebula-graph-architecture-overview)
2. [Benchmark: NebulaGraph vs Dgraph vs JanusGraph](https://www.nebula-graph.io/posts/benchmarking-mainstraim-graph-databases-dgraph-nebula-graph-janusgraph)
3. [Comparison: Neo4j vs NebulaGraph vs JanusGraph](https://www.nebula-graph.io/posts/performance-comparison-neo4j-janusgraph-nebula-graph)
4. [Deploy the Graph Database on Kubernetes](https://www.nebula-graph.io/posts/how-to-deploy-nebula-graph-in-kubernetes)


This article mainly introduces the new feature Memory Tracker in NebulaGraph v3.4, aiming to achieve fine-grained control of memory usage by the Memory Tracker module, reduce the risk of system OOM kill for graphd and storaged, and improve the kernel stability of NebulaGraph graph database.

Memory Tracker:  Memory Management Practice in NebulaGraph Database

With the rapid development of network information technology, data is gradually developing towards multi-source heterogeneity. Inside the multi-source heterogeneous data lies countless inextricable relations. And this kind of relations, together with the the network structure, are sure essential for data analysis. Unfortunately, when it comes to large scale data analysis, the traditional relational databases are poor in association detection and expressions. Therefore, graph data has attracted great attention for its powerful ability in expressions. Graph computing uses a graph model to express and solve the problem. Graphs can integrate with multi-source data types. In addition to displaying the static basic features for data, graph computing also finds its chance to display the graph structure and relationships hidden in the data. Thus graph becomes an important analysis tool in social network, recommendation system, knowledge graph, financial risk control, network security and text retrieval.

# Practical Algorithms

In order to support the business needs of large-scale graph computing, [Nebula Graph](https://github.com/vesoft-inc/nebula) provides [PageRank](https://en.wikipedia.org/wiki/PageRank) and [Louvain](https://en.wikipedia.org/wiki/Louvain_method) community-discovered graph computing algorithms based on [GraphX](https://github.com/apache/spark/tree/master/graphx). Users can execute these algorithm applications by submitting Spark tasks. In addition, users can also write Spark programs by using Spark Connector to call other built-in graph algorithms in GraphX, such as LabelPropagation, ConnectedComponent, etc.

## PageRank

PageRank is an algorithm raised by Google to rank web pages in their search engine results. PageRank is a way of measuring the importance of website pages.

### Introduction to PageRank

PageRank was named after Larry Page and Sergey Brin from Stanford in the United States. PageRank works by counting the number and quality of links to a page to determine a rough estimate of how important the website is. The underlying assumption is that more important websites are likely to receive more links from other websites.

### Applications of PageRank

#### Content recommendation based on similarity

With the help of the PageRank, you can recommend similar content to users based on their browse history and view time when analyzing social applications such as Twitter and Facebook.

#### Analyze the social influence of users

You can analyze the social influence of users according to their PageRank values in social network analysis.

#### Importance research for papers

Judge a paper's quality according to its PageRank value. Actually the PageRank algorithm comes from the idea of judging the quality of the papers. In addition, PageRank also finds its usage in data analysis and mining.

### Implementation PageRank

PageRank in GraphX is implemented based on the Pregel computing model. The algorithm contains three procedures:

1. Set a same initial PageRank value for every vertex (web page) in the graph;
1. The first iteration: Send a message along the edge. Each vertex receives all the vertices information along its related edges and gets a new PageRank value;
1. The second iteration: Put the PageRank values you get in the first iteration to the formulas corresponding to different algorithm models and get the new PageRank values.

## Louvain method

The Louvain method for community detection is a method to extract communities from large networks. The method is an aggregation algorithm for graphs.

### Introduction to Louvain

The inspiration for Louvain is the optimization of modularity as the algorithm progresses. If a node joins a certain community and maximizes the modularity of the community compared to other communities, then the node belongs to the community. If a node doesn't increase the modularity after joining other communities, it should stay in the current community.

#### Modularity

##### Modularity formula

The modularity Q measures the density of links inside communities compared to links between communities. Modularity is defined as:

$$Q = \frac{1}{2m} \times \sum_{i,j}[A_{ij} - \frac{k_ik_j}{2m}]\delta(c_i,c_j)  \\
 conditions: \delta(u,v) = \begin{cases}
                 1 &\text{when u == v} \\
                 0 &\text {}else
                 \end{cases}
$$                 

where

- $A_{ij}$ represents the edge weight between nodes $i$ and $j$.
- $K_i$ reprsents the sum of the weights of the edges attached to nodes $i$.
- $C_i$ is the community of the node $i$.
- $m$ is the sum of all of the edge weights in the graph.

**Deformation for the modularity formula**

In this formula, the formula is only meaningful when node i and node j belong to the same community. Therefore the formula measures the closeness within a certain community. The simplified deformation of this formula is as follows:

$ Q = \frac{1}{2m} \times \sum{i,j}[A{i,j} - \frac{k_ik_j}{2m}]\delta(c_i,c_j) \\
= \frac{1}{2m}[\sum{i,j}A{i,j} - \frac{\sum_ik_i \sum_jk_j}{2m}]\delta(c_i,c_j) \\
= \frac{1}{2m} \sum_c[\sum{in} - \frac{{\sum{tot}}^{2}}{2m}] $

where

- $\Sigma_{in}$ represents the sum of the weights of the edges in community c.
- $\Sigma_{k_n}$ represents the sum of the weighs of the edges connected with the nodes in community c (because $i$ belongs to community c), including the edges inside and outside the community attached to the node $i$.
- $\Sigma_{k_j}$ represents the sum of the weighs of the edges connected with the nodes in community c (because $j$ belongs to community c), including the edges inside and outside the community attached to the node $j$.
- $\Sigma{tot}$ replaces $\Sigma{k_i}$ and $\Sigma_{k_j}$. (Namely the sum of the weights of the edges in community c plus the sum of the weights of the edges in other community attached to community c. )

**Calculate the modularity change**

In the Louvain method, there is no need to calculate the specific modularity for each community. You only need to compare the modularity changes after adding a certain node to the community. That is to say you only need to calculate △Q.

When inserting node i to a certain community, the modularity change is:

$$\Delta{Q} = [\frac{\sum{in} + k{i,in}}{2m} -({\frac{\sum{tot} + k_i}{2m}})^{2}] - [\frac{\sum{in}}{2m} - (\frac{\sum_{tot}}{2m})^{2} - (\frac{k_i}{2m})^{2}] \\
= [\frac{k{i,in}}{2m} - \frac{\sum{tot}k_i}{2m^2}]$$

where

- $k_{i,in}$ is the sum of the weights of the edges between $i$ and other nodes in the community (This is 2 times of the actual weight in the new community, because all the edges attached to node i in the community are calculated twice).
- $K_i$ is the weighted degree of $i$. Thus when implementing the algorithm, you only need to calculate the $[k{i,in} - \sum{tot} \times \frac{k_i}{m}]$.

### Applications of Louvain

- Financial risk control

In financial risk control scenarios, you can use the method to identify fraud gangs based on the users behaviors.

- Social network

Louvain divides the social network based on the breadth and strength of nodes association in a graph. Louvain also analyzes complex networks and the closeness among a group of people.

- Recommendation system

Community detection based on the users’ interests. More accurate and effective customized recommendation can be implemented based on the community and collaborative filtering algorithm.

### Implement Louvain

The Louvain method contains two stages. The procedure is actually the iteration of the two stages.

**Stage 1:** Continuously traverse the nodes in the graph, and compare the modularity changes introduced by nodes in each neighbor community. Then add a single node to the community that can maximize the modularity. (For example, node v is added to communities A, B, and C respectively. The modularity increments of the three communities are -1, 1, 2. Then node v should be added to community C.)

**Stage 2:** Process based on the first stage. The nodes belonging to the same community are merged into a super node to reconstruct the graph. That is,  the community is regarded as a new node in the graph. At this time, the weight of the edges between the two super nodes are the sum of the weight of the edges attached to the original nodes in the two super nodes. That is, the sum of the weight of the edges in the two communities.

Following are details for the two stages.

![Louvain](https://user-images.githubusercontent.com/57335825/99624951-03ebcf00-29e4-11eb-9000-911efdf519d1.png)

In the first stage, the nodes are traversed and then added to the communities they belong to. In this way, we get the middle graph and the four communities.

In the second stage, the nodes in the community are merged into a super node. The community nodes have self-connected edges whose weight is twice the sum of the weights of the edges connected between all nodes in the community. The edge weight between the communities is the sum of the weights of the edges connecting the two communities. For example, the red community and the light green community are connected by (8,11), (10,11), (10,13). So the weight of the edges between the two communities is 3.

> Note: The weight inside the community is twice the weight of the edges between all internal nodes, because the concept of Kin is the sum of the edges of all nodes in the community and node i. When calculating the Kin for a certain community, each edge is actually counted twice.

The Louvain method continuously iterates stage 1 and stage 2 until the algorithm is stable (the modularity for the graph does not change) or the iterations reach the maximum.

# Practice the proceeding algorithms

## Demo environment

- Three virtual machines:
   - Cpu name: Intel(R) Xeon(R) Platinum 8260M CPU @ 2.30GHz
   - Processors: 32
   - CPU Cores: 16
   - Memory Size: 128G
- Software environment:
   - Spark: spark-2.4.6-bin-hadoop2.7 a cluster with three nodes
   - yarn V2.10.0: a cluster with three nodes
   - NebulaGraph V1.1.0: distributed deployed, used the default configurations

## Dataset for testing

1. Create graph space

```shell
CREATE SPACE algoTest(partition_num=100, replica_factor=1);
```

2. Create schema

```shell
CREATE TAG PERSON()
CREATE EDGE FRIEND(likeness double);
```

3. Import data

Use Spark Writer to import data offline into NebulaGraph.

4. Test results

The resource allocation fot the Spark job is `--driver-memory=20G --executor-memory=100G --executor-cores=3`.

- PageRank algorithm execution time on a dataset with hundred million nodes is 21 minutes.
- Louvain algorithm execution time on a dataset with hundred million nodes is 1.3 hours.

## How to use NebulaGraph algorithm

1. Download and pack the nebula-algorithm project to a jar package.

```shell
$ git clone git@github.com:vesoft-inc/nebula-java.git
$ cd nebula-java/tools/nebula-algorithm
$ mvn package -DskipTests
```

2. Configure the file `src/main/resources/application.conf`.

```xml
{
  # Spark relation config
  spark: {
    app: {
        # not required, default name is the algorithm that you are going to execute.
        name: PageRank

        # not required
        partitionNum: 12
    }

    master: local

    # not required
    conf: {
        driver-memory: 8g
        executor-memory: 8g
        executor-cores: 1g
        cores-max:6
    }
  }

  # NebulaGraph relation config
  nebula: {
    # metadata server address
    addresses: "127.0.0.1:45500"
    user: root
    pswd: nebula
    space: algoTest
    # partition specified while creating nebula space, if you didn't specified the partition, then it's 100.
    partitionNumber: 100
    # nebula edge type
    labels: ["FRIEND"]

    hasWeight: true
    # if hasWeight is true，then weightCols is required， and weghtCols' order must be corresponding with labels.
    # Noted: the graph algorithm only supports isomorphic graphs,
    #        so the data type of each col in weightCols must be consistent and all numeric types.
    weightCols: [“likeness”]
  }

  algorithm: {
    # the algorithm that you are going to execute，pick one from [pagerank, louvain]
    executeAlgo: louvain
    # algorithm result path
    path: /tmp

    # pagerank parameter
    pagerank: {
        maxIter: 20
        resetProb: 0.15  # default 0.15

    }

    # louvain parameter
    louvain: {
        maxIter: 20
        internalIter: 10
        tol: 0.5
   }
  }
}
```

3. Make sure that you have installed and started the Spark service on your machine.
4. Submit the nebula algorithm application:

```shell
spark-submit --master xxx --class com.vesoft.nebula.tools.algorithm.Main /your-jar-path/nebula-algorithm-1.0.1.jar -p /your-application.conf-path/application.conf
```

If you are interested in the content, welcome to try nebula-algorithm.

# References

- NebulaGraph: [https://github.com/vesoft-inc/nebula](https://github.com/vesoft-inc/nebula)
- GraphX: [https://github.com/apache/spark/tree/master/graphx](https://github.com/apache/spark/tree/master/graphx)
- nebula-algorithm: [https://github.com/vesoft-inc/nebula-java/tree/v1.0/tools/nebula-algorithm](https://github.com/vesoft-inc/nebula-java/tree/v1.0/tools/nebula-algorithm)

> Hi, I’m Nicole, the software engineer in NebulaGraph. Let me know if you have any thoughts and suggestions on this article. Welcome to talk to me on our [forum](https://discuss.nebula-graph.io/). Thanks!

# You Might Also Like

- [Exploring the S&P 100 Index Stocks Using Graph Machine Learning](https://nebula-graph.io/posts/stock-interrelation-analysis-nebula-graph-machine-learning/)
- [Analyzing Relationships in Game of Thrones With NetworkX, Gephi, and NebulaGraph (Part Two)](https://nebula-graph.io/posts/game-of-thrones-relationship-networkx-gephi-nebula-graph-part-two/)


In order to support the business needs of large-scale graph computing, NebulaGraph provides PageRank and Louvain community-discovered graph computing algorithms based on GraphX. Users can execute these algorithm applications by submitting Spark tasks. In addition, users can also write Spark programs by using Spark Connector to call other built-in graph algorithms in GraphX, such as LabelPropagation, ConnectedComponent, etc.

Practicing Graph Computation with GraphX in NebulaGraph

# Dag Controller Introduction

Dag Controller is a component of NebulaGraph Explorer, which was released after several tests and tunings. It mainly solves the problem of integration of OLTP and OLAP, and the problem of graph algorithms in complex scenarios. To learn more, see [https://docs.nebula-graph.io/master/nebula-explorer/deploy-connect/ex-ug-deploy/#dag_controller](https://docs.nebula-graph.io/master/nebula-explorer/deploy-connect/ex-ug-deploy/#dag_controller).

Below is some information I would like to share about Dag Controller. Feel free to leave a comment and let's discuss it together.

I'm sure you're no stranger to OLTP and OLAP, but let me briefly introduce them again here: OLTP is a fast-response, real-time online data processing method. OLAP is an offline, data algorithm method for complex scenarios. For NebulaGraph, OLTP has a variety of query statements, such as GO, MATCH, etc. OLAP has a variety of graph algorithms, such as Pagerank, Louvain, WCC (Weakly Connected Components), K-Core, and Jaccard.

OLTP and OLAP do not exist independently. For example, we can use the subgraph returned by a MATCH statement as input to the PageRank algorithm, and the result of the PageRank can be written to NebulaGraph to continue executing a MATCH statement or other algorithms. Like building blocks, various [OLTP and OLAP](https://www.nebula-graph.io/posts/OLTP-vs-OLAP-what-are-the-differences) can be assembled to form a data processing method for complex scenarios.

The Dag Controller is a system that handles scenarios where OLTP and OLAP need to be linked and executed. 

![oltp-vs-olap](https://www-cdn.nebula-graph.io/nebula-website-5.0/images/blogs/olap-and-oltp/1.png)

## Architecture

![dag-architecture](https://www-cdn.nebula-graph.io/nebula-website-5.0/images/blogs/olap-and-oltp/2.png)

The responsibilities of Dag Controller:

1. It provides an HTTP interface for external communication and access.

It is used for job submission, stopping, deleting and other operations, as well as the configuration of the system environment.

2. Execution of DAG.

When Dag Controller executes DAG, the OLAP will call NebulaGraph Analytics, and the OLTP will call graphd to complete the execution of nGQL.

NebulaGraph Analytics is our graph computing system, supporting Pagerank, Louvain, WCC, Jaccard, and other graph algorithms, supporting HDFS and NebulaGraph data sources.

Graphd, metad, and storaged are components in NebulaGraph. Graphd is mainly responsible for nGQL parsing, storaged is responsible for data storage, and metad is responsible for metadata storage.

# Cases

## Case 1

![dag-use-case](https://www-cdn.nebula-graph.io/nebula-website-5.0/images/blogs/olap-and-oltp/4.png)

The above figure shows a DAG model that runs the pagerank algorithm on a subgraph. First, we get a subgraph using an nGQL statement, and then we run the pagerank algorithm on this subgraph.

This method can be used when our graph size is particularly large and we only want to run the algorithm on part of the graph data.

## Case 2

![olap-and-oltp-use-case](https://www-cdn.nebula-graph.io/nebula-website-5.0/images/blogs/olap-and-oltp/3.png)

The above figure shows a model to compute the shortest paths for two classes of vertices.

First, the vertex IDs of the two classes are obtained separately by using nGQL, and then the vertex IDs of the two classes are passed to the shortestpath algorithm, which computes the paths between the two classes in the full graph.

Each algorithm can be set up to run the algorithm based on the full graph or subgraph.

There are various DAG models, and different DAG models can be built according to different business scenarios.

# Technical implementation

## DAG model

The DAG refers to a directed graph without loops, and an instance of DAG is considered as a job, and a job has multiple task.

The task in Dag Controller can be an nGQL or a graph algorithm such as PageRank, Louvain, SSSP, etc.

When a job is executed, it needs to sort the task first, there is a lot of related code on the internet, so I won't repeat it here.

## Parallel execution

To ensure the execution efficiency of DAG, multiple DAGs need to be executed in parallel. At the same time, within a DAG, the task without upstream and downstream dependencies also needs to be executed in parallel.

How can multiple DAGs and tasks be executed in parallel? In simple terms, the DAGs and tasks are handled by two thread pools respectively.

The details are as follows:

1. When the system starts, allocate the job thread pool and task thread pool to handle the execution of job and task respectively.

2. Unexecuted jobs are periodically obtained from the database and transferred to the job thread pool.

3. When a job is executed, the task is sorted according to its upstream and downstream dependencies, and then it determines whether the execution of all upstreams of each task is completed, and then the task is handed over to the task thread pool for execution when the upstream execution is completed, or waits if the upstream execution is not completed.

4. If the job thread pool is full during job execution, you need to wait to obtain unexecuted jobs at regular intervals. The same is done when the task thread pool is full.

## Type check

Note that the data type verification problem exists between the data input and output of tasks. For example, task2 is the downstream of task1. The input of task2 must be of type int, and the output of task1 must be of type int.

## DAG stop

When you stop a job, you need to stop multiple task that are running in parallel. A task has a preparation phase, a running phase, and in the running phase there are cross-machine, multi-process situations. Stopping a job requires avoiding the orphan process problem.

## Custom algorithm support

We support treating a customer's algorithm as a task for DAG building. First, configure the algorithm-related parameter information in the system. When executing a job, the system is responsible for running the algorithm that corresponds to the task.

# How NebulaGraph Works
1. [NebulaGraph Architecture — A Bird’s Eye View](https://www.nebula-graph.io/posts/nebula-graph-architecture-overview)
2. [Benchmark: NebulaGraph vs Dgraph vs JanusGraph](https://www.nebula-graph.io/posts/benchmarking-mainstraim-graph-databases-dgraph-nebula-graph-janusgraph)
3. [Comparison: Neo4j vs NebulaGraph vs JanusGraph](https://www.nebula-graph.io/posts/performance-comparison-neo4j-janusgraph-nebula-graph)
4. [Deploy the Graph Database on Kubernetes](https://www.nebula-graph.io/posts/how-to-deploy-nebula-graph-in-kubernetes)


Dag controller mainly solves the problem of integration of OLTP and OLAP, and the problem of graph algorithms in complex scenarios. 

Integration  Practice of OLTP and OLAP


# What is geospatial data?

Geospatial data is information related to geospatial entities, such as points, lines, and polygons.

NebulaGraph 2.6 supports geospatial data. You can store, compute, and retrieve geospatial data in NebulaGraph. Geography is a data type supported in NebulaGraph. It is composed of latitude and longitude that represents geospatial data.

## How to use geospatial data in NebulaGraph?

**Create Schema**

The following example shows how to create tags. You can create edge types in the same way.

NebulaGraph currently supports three types of geospatial data: Point, LineString, and Polygon. The following shows how to create geography types and how to insert geospatial data.

```ngql
CREATE TAG any_shape(geo geography);
CREATE TAG only_point(geo geography(point));
CREATE TAG only_linestring(geo geography(linestring));
CREATE TAG only_polygon(geo geography(polygon));
```

When no geography type is specified, it means that you can store data of any type; when a type is specified, it means that only geospatial data of that type can be stored, such as `geography (point)`, which means that you can only store spatial information of points.

**Insert Data**

Insert data in the `geo` column of the `any_shape` tag.

```ngql
INSERT VERTEX any_shape(geo) VALUES "101":(ST_GeogFromText("POINT(120.12 30.16)"));
INSERT VERTEX any_shape(geo) VALUES "102":(ST_GeogFromText("LINESTRING(3 8, 4.7 73.23)"));
INSERT VERTEX any_shape(geo) VALUES "103":(ST_GeogFromText("POLYGON((75.3 45.4, 112.5 53.6, 122.7 25.5, 93.9 28.6, 75.3 45.4))"));
```

Insert data in the `geo` column of the `only_point` tag.

```ngql
INSERT VERTEX only_point(geo) VALUES "201":(ST_Point(120.12，30.16)"));;
```

Insert data in the `geo` column of the `only_linestring` tag.

```ngql
INSERT VERTEX only_linestring(geo) VALUES "302":(ST_GeogFromText("LINESTRING(3 8, 4.7 73.23)"));
```

Insert data in the `geo` column of the `only_polygon` tag.

```ngql
INSERT VERTEX only_polygon(geo) VALUES "403":(ST_GeogFromText("POLYGON((75.3 45.4, 112.5 53.6, 122.7 25.5, 93.9 28.6, 75.3 45.4))"));
```

When the data inserted does not meet the requirements of the specified type, the data insertion fails.

```ngql
(root@nebula) [geo]> INSERT VERTEX only_polygon(geo) VALUES "404":(ST_GeogFromText("POINT((75.3 45.4))"));
[ERROR (-1005)]: Wrong value type: ST_GeogFromText("POINT((75.3 45.4))")
```

We can see that the geospatial data insertion method is rather peculiar, and is very different from the insertion of basic types such as `int`, `string`, and `bool`.

Let's take `ST_GeogFromText("POINT(120.12 30.16)")` as an example, `ST_GeogFromText` is a geographic location information parsing function, which accepts a string type of geographic location data in WKT (Well-Known Text) standard format.

`POINT(120.12 30.16)` represents a geographic point with longitude 120°12′E and latitude 30°16′N; the `ST_GeogFromText` function parses and constructs a geography data object from the WKT parameter, and then the `INSERT` statement stores it in the NebulaGraph in WKB (Well-Known Binary) standard.

## Geospatial functions

The geospatial functions supported by NebulaGraph can be divided into the following main categories:

- Constructing functions

  - `ST_Point(longitude, latitude)`: Constructs a `geography point` object based on a latitude and longitude pair.

- Parsing functions

  - `ST_GeogFromText(wkt_string)`: Parses `geography` objects from the WKT text.

  - `ST_GeogFromWKB(wkb_string)`: Parses `geography` objects from the WKB text. # Not yet supported, because NebulaGraph does not yet support binary strings.

- Format setting functions

  - `ST_AsText(geography)`: Outputs the `geography` object in the WKT text format.

  - `ST_AsBinary(geography)`: Outputs the `geography` object in the WKB text format. # Not yet supported, because NebulaGraph does not yet support binary strings.

- Conversion functions

  - `ST_Centroid(geography)`: Calculates the center of gravity of a `geography` object, which is a `geography point` object.

- The predicate function

  - `ST_Intersects(geography_1, geography_2)`: Determines whether two `geography` objects intersect.

  - `ST_Covers(geography_1, geography_2)`: Determines if the first `geography` object completely covers the second.

  - `ST_CoveredBy(geography_1, geography_2)`: The inverse of ST_Covers.

  - `ST_DWithin(geography_1, geography_2, distance_in_meters)`: Determines if the shortest distance between two `geography` objects is less than the given distance.

- The metric function

  - `ST_Distance(geography_1, geography_2)`: Calculates the distance between two `geography` objects.

These function interfaces follow the OpenGIS Simple Feature Access and ISO SQL/MM standards. For details, see [NebulaGraph doc](https://docs.nebula-graph.io/3.3.0/3.ngql-guide/6.functions-and-expressions/14.geo/).

## Geospatial Index

**What is a geospatial index?**

Geospatial indexes are indexes that can be used to quickly filter data based on the predicate `ST_Intersects` and `ST_Covers` functions. 

NebulaGraph uses the Google S2 library as the geospatial index. 

The S2 library projects the Earth's surface into a tangent square, then recursively quadruples each square surface of the square n times, and uses a space-filling curve, the Hilbert curve, to connect the centers of these small square lattices.

When n is infinitely large, this Hilbert curve almost fills the square.

The S2 library uses a Hilbert curve of order 30.

![](https://www-cdn.nebula-graph.io/nebula-website-5.0/images/blogs/Exploring-Geospatial-Data-with-NebulaGraph/1.jpeg)

The following figure shows that the Earth is filled with Hilbert curves.

![](https://www-cdn.nebula-graph.io/nebula-website-5.0/images/blogs/Exploring-Geospatial-Data-with-NebulaGraph/2.jpeg)


It can be seen that the Earth's surface is divided into cells by these Hilbert curves. For any geographic shape on the earth's surface, such as a city, a river, or a person's location, we can use several of these cells to completely cover the geographic shape.

Each cell is identified by a unique int64 CellID. Thus, the spatial index of a geographic object is the set of S2 cells that are constructed to completely cover the geographic shape.

When constructing an index of a geospatial object, a collection of different S2 cells that completely cover the indexed object is constructed. The indexing query based on spatial predicate functions quickly filters out a large number of irrelevant geographic objects by finding the intersection between the set of S2 cells that cover the queried object and the S2 cells that cover the indexed object.


**Create a geography index**

```ngql
CREATE TAG any_shape_geo_index on any_shape(geo)
```

For geospatial data with the type `point`, it can be represented by an S2 cell of order 30, so a point corresponds to one index entry; for geospatial data with the type `inestring` and `polygon`, we use multiple S2 cells of different levels to cover it, so it will correspond to multiple index entries.

Spatial indexing is used to speed up the lookup of all geo predicates, for example:

```ngql
LOOKUP ON any_shape WHERE ST_Intersects(any_shape.geo, ST_GeogFromText("LINESTRING(3 8, 4.7 73.23)"));
```

When there is no spatial index on the `geo` column of `any_shape`, this statement will first read all the data of `any_shape` into memory and then use it to calculate whether it intersects with the point (3.0, 8.0), which is generally more expensive. When the amount of data in `any_shape` is large, the computation overhead will be unacceptable.

When the `geo` column of `any_shape` has a spatial index, the statement will first use the spatial index to filter out most of the data that intersected by the line, but there will still be some that may be intersected when read into memory, so there is still one more calculation to be done. In this way, the spatial index quickly filters out most of the data that is not likely to intersect at a small cost, and a small percentage is filtered, greatly reducing the computational overhead.

You can store, compute, and retrieve geospatial data in NebulaGraph. Geography is a data type supported in NebulaGraph.

Exploring Geospatial Data with NebulaGraph

Based on the actual demand and subsequent scalability, the NebulaGraph database is used for technical selection. The batch import performance in the actual business scenarios of NebulaGraph needs to be first verified.

This article shares the best practice of using NebulaGraph Spark Connector by performing import jobs via Spark on Yarn distributed tasks and with CSV files on HDFS as the data source.

# About NebulaGraph Spark Connector

The following figure shows the use cases and advantages of NebulaGraph Spark Connector. For more details, see [NebulaGraph Spark Connector](https://docs.nebula-graph.io/3.0.1/nebula-spark-connector/).

<pic>


# Environment Information

- Hardware environment 

| **Name**     |  **Value**  | **Recommend** |
| :----------- | :------: | -------: |
| Local Disk (SSD) |   2 T    | At least 2 T |
| CPU          | 16 C * 4 |    128 C |
| Memory         |  128 GB  |    128 GB |

- Software environment

| **Name**               | **Version**  |
| :--------------------- | :---------: |
| NebulaGraph           |    3.0.0    |
| NebulaGraph Spark Connector |    3.0.0    |
| Hadoop                 | 2.7.2U17-10 |
| Spark                  |   2.4.5U5   |

- Data size

| **Name**     | **Value** |
| :----------- | :----: |
| Data size      | 200 GB  |
| Vertex | 930 million |
| Edge   | 970 million |

# Deployment Plan

- Method: Distributed, 3 nodes
- See [Deploy a NebulaGraph cluster with RPM/DEB package on multiple servers](https://docs.nebula-graph.com.cn/3.0.1/4.deployment-and-installation/2.compile-and-install-nebula-graph/deploy-nebula-graph-cluster/)

There are roughly three steps for the deployment.

1. Download the RPM package of NebulaGraph and install it.
2. Modify configuration files in batch.
3. Start the cluster service.

The above-mentioned three steps are performed with the `root` user. For non-root users, use `sudo` to execute the commands.

## Download and Install the NebulaGraph RPM Package

Execute the following commands:

```bash
wget https://os-cdn.nebula-graph.com.cn/package/3.0.0/nebula-graph-3.0.0.el7.x86_64.rpm
wget https://oss-cdn.nebula-graph.com.cn/package/3.0.0/nebula-graph-3.0.0.el7.x86_64.rpm.sha256sum.txt
rpm -ivh nebula-graph-3.0.0.el7.x86_64.rpm
```

Note: The default installation path is `/usr/local/nebula`. Make sure the memory resources are sufficient.

## Modify Configuration Files in Batch

```bash
sed -i 's?--meta_server_addrs=127.0.0.1:9559?--meta_server_addrs=172.1x.x.15:9559,172.1x.x.176:9559,172.1x.1x.149:9559?g' *.conf
sed -i 's?--local_ip=127.0.0.1?--local_ip=172.1x.1x.149?g' *.conf
sed -i 's?--meta_server_addrs=127.0.0.1:9559?--meta_server_addrs=172.1x.x.15:9559,172.1x.x.176:9559,172.1x.1x.149:9559?g' *.conf
sed -i 's?--local_ip=127.0.0.1?--local_ip=172.1x.x.15?g' *.conf
sed -i 's?--meta_server_addrs=127.0.0.1:9559?--meta_server_addrs=172.1x.x.15:9559,172.1x.x.176:9559,172.1x.1x.149:9559?g' *.conf
sed -i 's?--local_ip=127.0.0.1?--local_ip=172.1x.x.176?g' *.conf
```

Note: The IP addresses in the above commands are internal IP addresses, used for communication between nodes. 


## Start the NebulaGraph Cluster Service

```bash
/usr/local/nebula/scripts/nebula.service start all
```

The above command is to start the cluster service, the following is to check the status of the cluster service.

```bash
ps aux|grep nebula
```

The returned result shows 3 processes for each service.

```bash
/usr/local/nebula/bin/nebula-metad --flagfile /usr/local/nebula/etc/nebula-metad.conf
/usr/local/nebula/bin/nebula-graphd --flagfile /usr/local/nebula/etc/nebula-graphd.conf
/usr/local/nebula/bin/nebula-storaged --flagfile /usr/local/nebula/etc/nebula-storaged.conf
```

Note: If the returned result shows less than 3 processes, run `/usr/local/nebula/scripts/nebula.service start all` several times or run `/usr/local/nebula/scripts/nebula.service restart all` to restart the service.


# Visualization Service

The NebulaGraph Studio is used as the visualize the NebulaGraph cluster service. Visit `http://n01v:7001` to log into the NebulaGraph Studio. (This is my network environment which is not accessible from the Internet.)

<pic>

- Login: 10.x.x.1 (The IP of any node):9669
- Username/Password: `root`/`nebula`

Refer to [Use nGQL (CRUD)](https://docs.nebula-graph.com.cn/3.0.1/2.quick-start/4.nebula-graph-crud) for common-used nGQL statements.


## Use NebulaGraph

Add the Storage nodes to the cluster.

```nebula
ADD HOSTS 172.x.x.121:9779, 172.16.11.218:9779,172.16.12.12:9779;
```

List all nodes and check whether the status of the cluster is `ONLINE by running `SHOW HOSTS` or `SHOW HOSTS META`.
Create a graph space, equivalent to a database in relational databases.
```nebula
CREATE SPACE mylove (partition_num = 15, replica_factor = 3, vid_type = FIXED_STRING(256));//The number of partitions is recommended to be 5 times the number of nodes; the number of replicas is an odd number, generally set to 3; if the data type of vids is string, make the length as long as a reasonable value, otherwise, it takes up too much disk space.
```

Create a Tag, equivalent to an entity.: 

```nebula
CREATE TAG entity (name string NULL, version string NULL);
```  

Create an edge, equivalent to a relationship.

```nebula
CREATE EDGE relation (name string NULL);  
```

Add `limit` when querying data, otherwise, the query may take a long time.

```nebula
match (v) return v limit 100;
```

# Read and Import CSV Files with Spark Connector 

References:

- [NebulaSparkWriterExample (Scala Json) from the official](https://github.com/vesoft-inc/nebula-spark-utils/blob/master/example/src/main/scala/com/vesoft/nebula/examples/connector/NebulaSparkWriterExample.scala)
- [NebulaSparkWriterExample (Java Json) from an ace](https://www.jianshu.com/p/930e0343a28c)

Code example of NebulaSparkWriterExample

```
import com.facebook.thrift.protocol.TCompactProtocol
import com.vesoft.nebula.connector.{
  NebulaConnectionConfig,
  WriteMode,
  WriteNebulaEdgeConfig,
  WriteNebulaVertexConfig
}
import org.apache.spark.SparkConf
import org.apache.spark.sql.SparkSession
import org.slf4j.LoggerFactory
object NebulaSparkWriter {
  private val LOG = LoggerFactory.getLogger(this.getClass)
  var ip = ""
  def main(args: Array[String]): Unit = {
    val part = args(0)
    ip = args(1)
    val sparkConf = new SparkConf
    sparkConf
      .set("spark.serializer", "org.apache.spark.serializer.KryoSerializer")
      .registerKryoClasses(Array[Class[_]](classOf[TCompactProtocol]))
    val spark = SparkSession
      .builder()
      .master("local")
      .config(sparkConf)
      .getOrCreate()
    spark.sparkContext.setLogLevel("WARN")
    if("1".equalsIgnoreCase(part)) writeVertex(spark)
    if("2".equalsIgnoreCase(part)) writeEdge(spark)
    spark.close()
  }
  def getNebulaConnectionConfig(): NebulaConnectionConfig = {
    val config =
      NebulaConnectionConfig
        .builder()
        .withMetaAddress(ip + ":9559")
        .withGraphAddress(ip + ":9669")
        .withTimeout(Integer.MAX_VALUE)
        .withConenctionRetry(5)
        .build()
    config
  }
  def writeVertex(spark: SparkSession): Unit = {
    LOG.info("start to write nebula vertices: 1 entity")
    val df = spark.read.option("sep", "\t").csv("/home/2022/project/origin_file/csv/tag/entity/").toDF("id", "name", "version")
    val config = getNebulaConnectionConfig()
    val nebulaWriteVertexConfig: WriteNebulaVertexConfig = WriteNebulaVertexConfig
      .builder()
      .withSpace("mywtt")
      .withTag("entity")
      .withVidField("id")
      .withVidAsProp(false)
      .withUser("root")
      .withPasswd("nebula")
      .withBatch(1800)
      .build()
    df.coalesce(1400).write.nebula(config, nebulaWriteVertexConfig).writeVertices()
  }
  def writeEdge(spark: SparkSession): Unit = {
    LOG.info("start to write nebula edges: 2 entityRel")
    val df = spark.read.option("sep", "\t").csv("/home/2022/project/origin_file/csv/out/rel/relation/").toDF("src", "dst", "name")
    val config = getNebulaConnectionConfig()
    val nebulaWriteEdgeConfig: WriteNebulaEdgeConfig = WriteNebulaEdgeConfig
      .builder()
      .withSpace("mywtt")
      .withEdge("relation")
      .withSrcIdField("src")
      .withDstIdField("dst")
      .withSrcAsProperty(false)
      .withDstAsProperty(false)
      .withUser("root")
      .withPasswd("nebula")
      .withBatch(1800)
      .build()
    df.coalesce(1400).write.nebula(config, nebulaWriteEdgeConfig).writeEdges()
  }
}
```
## Details on NebulaSparkWriterExample 

The following are the details of the functions.

- `spark.sparkContext.setLogLevel("WARN")`: Sets the log print level and prevents the INFO log. 


- `withTimeout(Integer.MAX_VALUE)`: Sets the connection timeout. The timeout can be set as large as possible. The default value is 1 minute. When the number of timeouts is greater than that of retries, the Spark task fails.

- `option("sep", "\t")`: Specifies the separator of CSV files, otherwise, it defaults to 1 column.

- `toDF("src", "dst", "name")`: The schema of the dataset, i.e., converting `Dataset<Row>` to `DataFrame`, otherwise, the `VidField` cannot be specified.

- `withVidField("id")`: This function only works when the column name is set, so a schema must be specified.

- `withVidAsProp(false)`: When the ID is set as the VID by default, data will not be written repeatedly as a property that will not take up disk space.

- `withSrcIdField("src")`: Sets the `IdField` of the source vertex.

- `withDstIdField("dst")`: Sets the `IdField` of the destination vertex.

- `withSrcAsProperty(false)`: Saves disk space.

- `withDstAsProperty(false)`: Saves disk space.

- `withBatch(1000)`: The number of rows of data imported in batch. `WriteMode.UPDATE` is <=512 by default. The value of `WriteMode.INSERT` can be larger (Gigabit NIC/Bandwidth 5Gbps /Local SSD = 1500)

- `coalesce(1500)`: Adjustable according to the number of concurrent tasks. Too much data on a single partition can easily cause executor OOM exceptions.

# Submit Tasks to the Spark Cluster

```spark
nohup spark-submit  --master yarn --deploy-mode client --class com.xxx.nebula.connector.NebulaSparkWriter --conf spark.dynamicAllocation.enabled=false --conf spark.executor.memoryOverhead=10g  --conf spark.blacklist.enabled=false --conf spark.default.parallelism=1000 --driver-memory 10G --executor-memory 12G --executor-cores 4 --num-executors 180 ./example-3.0-SNAPSHOT.jar >  run-csv-nebula.log 2>&1 &
```

## Monitoring with `iotop`

The `iotop` command can be used to monitor the disk IO of the Spark cluster.

```bash
Total DISK READ :      26.61 K/s | Total DISK WRITE :     383.77 M/s
Actual DISK READ:      26.61 K/s | Actual DISK WRITE:     431.75 M/s
```
## Monitoring with `top` 

The `top` command can be used to monitor the CPU and memory of the Spark cluster.

```bash
top - 16:03:01 up 8 days, 28 min,  1 user,  load average: 6.16, 6.53, 4.58
Tasks: 205 total,   1 running, 204 sleeping,   0 stopped,   0 zombie
%Cpu(s): 28.3 us, 14.2 sy,  0.0 ni, 56.0 id,  0.6 wa,  0.0 hi,  0.4 si,  0.5 st
KiB Mem : 13186284+total,  1135004 free, 31321240 used, 99406592 buff/cache
KiB Swap:        0 total,        0 free,        0 used. 99641296 avail Mem 
  PID USER      PR  NI    VIRT    RES    SHR S  %CPU %MEM     TIME+ COMMAND                                                                         
27979 root      20   0 39.071g 0.026t   9936 S 564.6 20.8  83:22.03 nebula-storaged                                                                 
27920 root      20   0 2187476 804036   7672 S 128.2  0.6  17:13.75 nebula-graphd                                                                   
27875 root      20   0 6484644 1.990g   8588 S  58.5  1.6  14:14.22 nebula-metad     
```
## Other Resource Monitoring

<pic>

# Service Optimization

## Configuration Optimization of `nebula-storaged.conf`

Here, I modified the value of parameters in the `nebula-storaged.conf` file.

```bash
# Default reserved bytes for a batch operation.
--rocksdb_batch_size=4096
# Default block cache size used in BlockBasedTable.
# The unit is MB. It is usually set to one third of the memory value. The memory is 128 GB.
--rocksdb_block_cache=44024
############## rocksdb Options ##############
--rocksdb_disable_wal=true
# In JSON, the name and value of each option of rocksdb DBOptions is a string. Such as “option_name”:“option_value”. Use a comma to separate each option.
--rocksdb_db_options={"max_subcompactions":"3","max_background_jobs":"3"}
# In JSON, the name and value of each option of rocksdb ColumnFamilyOptions is a string. Such as “option_name”:“option_value”. Use a comma to separate each option.
--rocksdb_column_family_options={"disable_auto_compactions":"false","write_buffer_size":"67108864","max_write_buffer_number":"4","max_bytes_for_level_base":"268435456"}
# In JSON, the name and value of each option of rocksdb BlockBasedTableOptions is a string. Such as “option_name”:“option_value”. Use a comma to separate each option.
--rocksdb_block_based_table_options={"block_size":"8192"}
# The number of processors per request.
--max_handlers_per_req=10
# The interval time between clusters.
--heartbeat_interval_secs=10
--raft_rpc_timeout_ms=5000
--raft_heartbeat_interval_secs=10
--wal_ttl=14400
# The max value for batch import.
--max_batch_size=1800
# Reduces memory usage when the value is true.
--enable_partitioned_index_filter=true
# The data is indirectly filtered at the bottom storage layer to prevent encountering the super node in the production environment.
--max_edge_returned_per_vertex=10000
```
## Optimizations of the Linux System

```bash
ulimit -c unlimited
ulimit -n 130000
sysctl -w net.ipv4.tcp_slow_start_after_idle=0
sysctl -w net.core.somaxconn=2048
sysctl -w net.ipv4.tcp_max_syn_backlog=2048
sysctl -w net.core.netdev_max_backlog=3000
sysctl -w kernel.core_uses_pid=1
```

# Verify Import Results

```nebula
SUBMIT JOB STATS;
SHOW JOB ${ID}
SHOW STATS;
```
- The entity insertion rate is approximately 27,837 items/s (for this import performance calculation only).

- The relationship insertion rate is about 26,276 items/s (for this import performance calculation only).

- The import performance will be better if the server is better configured. In addition, bandwidth, cross-datacenter or not, disk IO, and even network fluctuations are also factors that affect performance.

# Performance Tests

- Query for the specified entities based on properties.

  ```nebula
  MATCH (v:entity) WHERE v.entity.name == 'Lifespan' RETURN v;
  ```

  It takes 0.002558 (s).

- One-hop queries.

  ```nebula
  MATCH (v1:entity)-[e:propertiesRel]->(v2:attribute) WHERE id(v1) == '70da43c5e46f56c634547c7aded3639aa8a1565975303218e2a92af677a7ee3a' RETURN v2 limit 100;  
  ```
  It takes 0.003571 (s)

- Two-hop queries.

  ```nebula
  MATCH p=(v1:entity)-[e:propertiesRel*1..2]->(v2) WHERE id(v1) == '70da43c5e46f56c634547c7aded3639aa8a1565975303218e2a92af677a7ee3a' RETURN p;
  ```
  It takes 0.005143 (s)

- Query for all the properties of an edge.

  ```nebula
  FETCH PROP ON propertiesRel '70da43c5e46f56c634547c7aded3639aa8a1565975303218e2a92af677a7ee3a' -> '0000002d2e88d7ba6659db83893dedf3b8678f3f80de4ffe3f8683694b63a256' YIELD properties(edge); 
  ```  
  It takes 0.001304 (s)

  ```nebula
  match p=(v:entity{name:"张三"})-[e:entityRel|propertiesRel*1]->(v2) return p;
  ```
  å
  It takes 0.02986 (s)

  ```nebula
  match p=(v:entity{name:"张三"})-[e:entityRel|propertiesRel*2]->(v2) return p; 
  ```

  It takes 0.07937 (s)

  ```nebula
  match p=(v:entity{name:"张三"})-[e:entityRel|propertiesRel*3]->(v2) return p; 
  ```

  It takes 0.269 (s)

  ```nebula
  match p=(v:entity{name:"张三"})-[e:entityRel|propertiesRel*4]->(v2) return p;
  ```

  It takes 3.524859 (s)

  ```nebula 
  match p=(v:entity{name:"张三"})-[e:entityRel|propertiesRel*1..2]->(v2) return p; 
  ```

  It takes 0.072367 (s)

  ```nebula 
  match p=(v:entity{name:"张三"})-[e:entityRel|propertiesRel*1..3]->(v2) return p;
  ```

  It takes 0.279011 (s)

  ```nebula 
  match p=(v:entity{name:"张三"})-[e:entityRel|propertiesRel*1..4]->(v2) return p; 
  It takes 3.728018 (s)
  ```

 - Query for the properties of vertices and the edge in the shortest path in bilateral directions between `A_vid` and `B_vid`.

  ```nebula
  FIND SHORTEST PATH WITH PROP FROM "70da43c5e46f56c634547c7aded3639aa8a1565975303218e2a92af677a7ee3a" TO "0000002d2e88d7ba6659db83893dedf3b8678f3f80de4ffe3f8683694b63a256" OVER * BIDIRECT YIELD path AS p; 
  ```
  It takes 0.003096 (s)

  ```nebula
  FIND ALL PATH FROM "70da43c5e46f56c634547c7aded3639aa8a1565975303218e2a92af677a7ee3a" TO "0000002d2e88d7ba6659db83893dedf3b8678f3f80de4ffe3f8683694b63a256" OVER * WHERE propertiesRel.name is not EMPTY or propertiesRel.name >=0 YIELD path AS p;
  ```

  It takes 0.003656 (s)

# Problems Encountered

## Guava version conflict

```
Caused by: java.lang.NoSuchMethodError: com.google.common.base.Stopwatch.createStarted()Lcom/google/common/base/Stopwatch;
```

After troubleshooting, I found that one of the dependent modules used Guava version 22.0, while the Spark cluster came with 14.0, resulting in a conflict, and it did not work properly. For tasks running on Spark clusters, Spark loads Guava packages with higher priority than its packages.

The package we depend on uses methods that are newer in Guava version 22.0 and not available in version 14.0. Without being able to modify each other's code, the following options are available:

1. The Spark cluster package can be upgraded, which is risky and can cause unknown problems.

2. Rename your Guava package using the Maven plugin.

The second way is used here, using the Maven plugin shade (link: https://maven.apache.org/plugins/maven-shade-plugin/) to rename the package to solve the problem.

```java
<plugin>
    <groupId>org.apache.maven.plugins</groupId>
    <artifactId>maven-shade-plugin</artifactId>
    <version>3.2.4</version>
    <executions>
        <execution>
            <phase>package</phase>
            <goals>
                <goal>shade</goal>
            </goals>
            <configuration>
                <relocations>
                    <relocation>
                        <pattern>com.google.common</pattern>
                        <shadedPattern>my_guava.common</shadedPattern>
                    </relocation>
                </relocations>
                <filters>
                    <filter>
                        <artifact>*:*</artifact>
                        <excludes>
                            <exclude>META-INF/maven/**</exclude>
                            <exclude>META-INF/*.SF</exclude>
                            <exclude>META-INF/*.DSA</exclude>
                            <exclude>META-INF/*.RSA</exclude>
                        </excludes>
                    </filter>
                </filters>
            </configuration>
        </execution>
    </executions>
</plugin>
```
## Spark Blacklist Mechanism
```
Blacklisting behavior can be configured via spark.blacklist.*.
```
The default value of `spark.blacklist.enabled` is `false`. If the value is set to `true`, Spark will no longer schedule tasks to the blacklisted executors. The blacklisting algorithm can be further configured by setting `spark.blacklist`.
  
*This article was written by Enqiu Jia and first published on the WeChat Official Account *只要5分钟不要996*. This article is translated and published with permission.

This is a best practice of using NebulaGraph Spark Connector by performing import jobs via Spark on Yarn distributed tasks and with CSV files on HDFS as the data source.

Offline CSV Import of Billions of Data | Best Practice Using NebulaGraph Spark Connector


![nebula-graph-index-explained-featured](https://user-images.githubusercontent.com/57335825/167098195-bde39149-3b4a-4d52-843d-0b56a2309a97.jpg)

The term Index in NebulaGraph is quite similar to the same term in relational databases, but they are not exactly the same. I noticed that some NebulaGraph users are often confused when getting started with NebulaGraph. Typically, people want to know what exactly NebulaGraph Index is, when should they use it, and how it impacts the performance of NebulaGraph.

Today I'm going to walk you through the Index concept in NebulaGraph and hopefully, this article will answer these questions.

Let's get started!

## What exactly NebulaGraph Index is

To put it short, NebulaGraph Index is only used when the vertextID is not specified, or only when **properties** of vertices or edges are defined in the query conditions. 

Index is only used in a starting entry of a graph query. If a query is in the pattern: (a->b->c, where c is with the condition "foobar"), since the only filter `condition-foobar` is on `c`, this query under the hood will start to look for `c`, and then it walks reversely through the `->` to `b`, and finally to `a`. Thus, the NebulaGraph Index will be used and only be possibly used when locating c.

### Index is used only to seek starting points

We know that in RDBMS, indexing is to create a duplicate of sorted data to enable QUERY with conditional filtering on the sorted data, in order to **accelerate the query in reads** and it also brings additional data writes.

> Note: in RDBMS/Tabular DB, indexing some columns means to create extra data that are sorted on those columns to make a query with those columns' conditions to be scanned faster, rather than scanning from the original table data sorted based on the key only.

In NebulaGraph, the index is to create a duplicate of sorted **Vertex/Edge PROP DATA** to **locate the starting point of a QUERY**.

Not all of queries relied on the index, here are some example queries, where the starting points are only defined using conditions, rather than VertextIDs. Let's call them `pure property condition starting queries`:

```cypher
#### Queries relying on NebulaGraph Index

# query 0 pure-property-condition-start query
LOOKUP ON tag1 WHERE col1 > 1 AND col2 == "foo" \
    YIELD tag1.col1 as col1, tag1.col3 as col3;

# query 1 pure-property-condition-start query
MATCH (v:player { name: 'Tim Duncan' })-->(v2:player) \
        RETURN v2.player.name AS Name;
```

In both `query 0` and `query 1`, the pattern is to "Find VID/EDGE only based on given property conditions". 

On the contrary, the starting point is VertexID based instead in `query 2` and `query 3`:

```cypher
#### Queries not based on NebulaGraph Index

# query 2, walk query starting from given vertex VID: "player100"

GO FROM "player100" OVER follow REVERSELY \
        YIELD src(edge) AS id | \
    GO FROM $-.id OVER serve \
        WHERE properties($^).age > 20 \
        YIELD properties($^).name AS FriendOf, properties($$).name AS Team;

# query 3, walk query starting from given vertex VID: "player101" or "player102"

MATCH (v:player { name: 'Tim Duncan' })--(v2) \
        WHERE id(v2) IN ["player101", "player102"] \
        RETURN v2.player.name AS Name;
```

If we look into `query 1` and `query 3`, which shared the same condition on vertices on `tag:player`, which are both `{ name: 'Tim Duncan' }`, they are differentiated in starting points:

For `query 3`, the index is not required as the query will start from the known vertex ID in `["player101", "player102"]` and thus:
- It'll directly fetch vertex data from `v2`'s vertex IDs
- then to GetNeighbors(): walk through edges of `v2`, GetVertices() for the next hop: `v` and filter based on the property: `name`

For `query 1`, the query has to start from `v` due to no known vertex IDs were provided:
- It'll do IndexScan() first to find all vertices only with the property condition of `{ name: 'Tim Duncan' }`
- Then, GetNeighbors(): walk through edges of `v`, GetVertices() for the next hop: `v2` 

Now, we know the whole point that matters here is on **whether we know the vertexID**. And the above differences could be shown in their execution plans with PROFILE or EXPLAIN like the following:

| `query 1`, requires index(on tag: player), pure property condition query as starting point | `query 3`, no index required, query starting from known vertex IDs |
| ------------------------------------------------------------ | ------------------------------------------------------------ |
| ![query-based-on-index](https://user-images.githubusercontent.com/57335825/167237932-effed472-6390-460c-89b5-c759644dc674.png)         | ![query-requires-no-index](https://user-images.githubusercontent.com/57335825/167237957-14981b0b-61c2-4ea9-ab60-02ee49c4843b.png)   |

### Why NebulaGraph index is an enabler rather than an accelerator

Can't those queries be done without indexes?

It's possible in theory with a full scan, but disabled without an index.

The reason is that NebulaGraph stores data in a distributed and graph-oriented way, the full scan of data was considered too expensive to be allowed.

> Note: from v3.0, it's possible to do TopN Scan without index, where the `LIMIT <n>` is used, this is different from the full scan case(index is a must), which will be explained later.
>
> ```cypher
> MATCH (v:player { name: 'Tim Duncan' })-->(v2:player) \
>         RETURN v2.player.name AS Name LIMIT 3;
> ```

### Why starting point only

Index data is not used in the traversal. It could confuse us to think of index as sorting data based on properties, does it accelerate the traversal with property condition filtering? The answer is no.

In NebulaGraph, the data is structured in a way to enable fast graph-traversal, which is already indexed/sorted on vertex ID(for both vertex and edge) in the raw data, where traversal(underlying in storage, it's calling GetNeighbors interface) of the given vertex is cheap and fast due to the persistent storage.

So in summary:

> NebulaGraph Index is sorted property data to find the starting vertex or edge on given pure property conditions.

## Facts on NebulaGraph Index

To understand more details/limitations/cost of Nebula, let's reveal more about its design. Here are some facts in short:

- Index Data is stored and shared together with Vertex Data

- It's **Left Match** based only: It's RocksDB Prefix Scan under the hood

- Effect on write and read path(to see its cost):

  - Write Path: Extra Data written + Extra Read request introduced
  - Read Path: RBO(Rule-based optimization), Fan Out(to all shards)

- Data Full Scan LIMIT Sample(not full scan) is supported without index
  - `LOOKUP ON t YIELD t.name | LIMIT 1`

  - ```cypher
    MATCH (v:player { name: 'Tim Duncan' })-->(v2:player) \
            RETURN v2.player.name AS Name LIMIT 3;
    ```

The key info can be seen in one of my [sketch notes](https://www.siwei.io/en/sketch-notes/):

![nebula-graph-index-sketch](https://user-images.githubusercontent.com/57335825/167237972-507c1344-636e-48f5-9b3f-fc8ba5dbaa69.png)

> We should notice that only the left match is supported in pure-property-condition-start queries. For queries like wildcard or regular expression, Full-text Index/Search is to be used, where an external elastic search is integrated with Nebula: please check [NebulaGraph Full text index](https://docs.nebula-graph.io/3.1.0/4.deployment-and-installation/6.deploy-text-based-index/2.deploy-es/) for more.

Within this sketch note, more highlights are:

- It's a Local Index Design
  - The index is stored and shared locally together with the graph data.
  - It's sorting based on property value, and the index search is underlying a RocksDB prefix scan, that's why only left match is supported.

- There are costs in the writing path
  - The index enables the RDBMS-like property Condition Based Query with cost in the write path including not only the extra write but also, random read, to ensure the data consistency.
  - Index Data writing is done in a synchronous way

- For the reading path:
  - In pure-property-condition-start queries, in GraphD, the index will be selected with Rule-based-optimization like this example, where, in a rule, the col2 to be sorted first is considered optimal with the condition: col2 equals 'foo'.
  - After the index was chosen, the index-scan request will be fanout to storageD instances, and in the case of filters like LIMIT N, it will be pushed down to the storage side to reduce data payload.
    - Note: it was not shown in the sketch but actually from v3.0, the nebula graph allows LIMIT N Sample Property condition query like this w/o index, which is underlying pushing down the LIMIT filter to storage side.


Takeaways:

- Use index only when we have to, as it's costly in write cases and if the limit N sample is the only needed case and it's fast enough, we can use that instead.
- Index is left to match
  - composite index order matters, and should be created carefully.
  - for full-text search use case, use [full-text index](https://docs.nebula-graph.io/3.1.0/4.deployment-and-installation/6.deploy-text-based-index/2.deploy-es/) instead.

## How to use the index

We should always refer to the [documentation](https://docs.nebula-graph.io/3.1.0/3.ngql-guide/14.native-index-statements/), and I just put some highlights on this here:

- To create an index on a tag or edge type to specify a list of props in the order that we need.

  - `CREATE INDEX`

- If an index was created after existing data was inserted, we need to trigger an index asynchronously to rebuild the job, as the index data will be written in a synchronous way only when the index is created.

  - `REBUILD INDEX`

- We can see the index status after `REBUILD INDEX` is issued.

  - `SHOW INDEX STATUS`

- Queries levering index could be LOOKUP, and with the pipeline, in most cases, we will do follow-up graph-walk queries like:

  ```sql
  LOOKUP ON player \
    WHERE player.name == "Kobe Bryant"\
    YIELD id(vertex) AS VertexID, properties(vertex).name AS name |\
    GO FROM $-.VertexID OVER serve \
    YIELD $-.name, properties(edge).start_year, properties(edge).end_year, properties($$).name;
  ```

- Or in MATCH query like this, under the hood, v will be searched on index and v2 will be walked by default graph data structure without involving index.

  ```cypher
  MATCH (v:player{name:"Tim Duncan"})-->(v2:player) \
    RETURN v2.player.name AS Name;
  ```

## Recap

Finally, Let's Recap

- Index is to sort Property DATA to enable finding starting point on a given Pure Property Condition(no VertexID provided)
- Index is **not** for traversal
- Index is left match, **not** for full-text search
- Index has cost on WRITE
- Remember to REBUILD after `CREATE INDEX` on existing data

Happy Graphing!

## About the author
Wey Gu is the Developer Advocate of NebulaGraph. He is passionate about spreading the graph technology to the developer community and trying his best to make distributed graph database more accessible. Follow him on [Twitter](https://twitter.com/wey_gu) or visit his [blog](https://www.siwei.io/en/) for more fun stuff.


This article explains what NebulaGraph's native index is, and when and how to use index.

Everything you need to know about NebulaGraph Index

In this article, I will try to walk you through four different ways that you can make NebulaGraph and Apache Spark work together: Spark Connector, Nebula Exchange, Nebula Algorithm, and PySpark.