Wendy Chen
CPSC 426 Distributed Systems, Fall 2016
The following service description is adapted from the lab specification:
Service description
The first iteration of the graph store is a simple single-node in-memory service. A server hosts the graph and handles client requests to modify or query the graph. The graph is erased from memory when the server stops.
The user should be able to invoke the graph server by specifying the port in the command line: ./cs426_graph_server <port>
The service expects simple HTTP requests with a Content-Length header, and arguments specified in JSON. Requests should be in the form:
HTTP/1.1 <status_code> <status_message>
Content-Length: <length>
Content-Type: application/json
{
<JSON_arguments>
}
All requests will be POST requests. The following functions can be handled by the graph server:
| Function | Arguments | Return |
|---|---|---|
| add_node | u64 node_id | 200 on success 204 if the node already exists |
| add_edge | u64 node_a_id, u64 node_b_id | 200 on success 204 if the edge already exists 400 if either node doesn't exist, or if node_a_id is the same as node_b_id |
| remove_node | u64 node_id | 200 on success 400 if the node does not exist |
| remove_edge | u64 node_a_id, u64 node_b_id | 200 on success 400 if the edge does not exist |
| get_node | u64 node_id | 200 and a boolean JSON field in_graph indicating whether the node is in the graph |
| get_edge | u64 node_a_id, u64 node_b_id | 200 and a boolean JSON field in_graph indicating whether the edge is in the graph 400 of at least one of the vertices does not exist |
| get_neighbors | u64 node_id | 200 and a list of neighbors or 400 if the node does not exist |
| shortest_path | u64 node_a_id, u64 node_b_id | u64 and a field distance containing the length of shortest path between the two nodes or 204 if there is no path 400 if either node does not exist |
Compilation Details
The current Makefile is for MacOSX. The functions needed from Mongoose are included in mongoose.c, so no installation is required.
Implementation Details
The implementation is split into three areas: the graph, the server, and the http request handling. These three areas are handled by the following files, respectively: graph.cpp, cs426_graph_server.cpp, and api.cpp.
The Graph class is defined in graph.h. As requested by the specification, all graph mutation and query functions are defined as class methods in graph.cpp. When the graph service is running, an instance of the Graph class is constructed, and this instance is not preserved when the service terminates.
The server is set up in cs426_graph_server.cpp. Mongoose is used for setting up the server, and parsing JSON attached to http requests. When the server is running, it listens at the specified port for incoming events. Each defined event corresponds to one of the functions from the lab specification. When handling an event, the server calls a function from api.cpp.
The functions from api.cpp are wrappers for calling Graph methods in addition to emitting an http response. Mongoose is used for emitting JSON.
Test script and Examples
The test script I have provided (test.sh) builds a simple graph of six nodes and calls all the allowed functions. Besides using the test script, http requests can also be sent using curl:
curl -H "Content-Type: application/json" -X POST -d '{"node_id":1}' http://127.0.0.1:8000/api/v1/add_node
Links:
Home: Demo video and Abstract
First iteration: Local in-memory graph
Second iteration: Durable on-disk graph
Third iteration: Chain-replicated graph
Fourth iteration: Partitioned graph
Source code: Each graph is stored under its appropriate branch (lab1, lab2, lab3, lab4)