stevedekorte/vertex.js

ABOUT
-----

vertex.js is a graph database inspired by filesystems that supports automatic garbage collection and is built on node.js and tokyocabinet. It uses HTTP as its communication protocol and JSON as its request and response data format. It is MIT licensed and was written by Rich Collins and Steve Dekorte.


ADVANTAGES
----------

Flexibility

Vertex.js is schemaless allowing it to naturally model arbitrary graphs and irregular data.

Uptime

Fine grain migrations. The database is not locked during migrations or index creation.

Extensibility

Vertex.js supports addons. You can extend and modify the API to implement complex queries or other protocols (e.g. memcache, Facebook graph API, etc), all using javascript.

Simplicity

All vertices in the database are accessible via paths. This provides natural mapping between URLs and DB objects.

Scalability

vertex.js is currently single server based, but before discounting it as not scalable, it's worth considering what your performance requirements are and if vertex.js can meet them. It can handle thousands of requests per second and a single modern machine server can have 512GB of RAM (more than enough room to cache most databases entirely in memory) and with an SSD and proper use of vertex's feature of allowing write requests to specify the max time they can stay volatile (thereby minimizing hard syncs) you may find that it outperforms cluster solutions for most tasks.

Security

Unix style permissions on nodes are supported. This allows web clients to directly access the database without the need for an intermediary server that handles login and security issues. It also makes vertex convenient for use as a primary user database.


INSTALL AND RUN
---------------

1) install node.js 
2) install tokyocabinet
3) in the vertex.js folder, run:

		node server.js 

   For a list of command line options:

		node server.js -help


DATABASE STRUCTURE
------------------

The database is composed of nodes each of which have a lexically ordered list of named slots whose values point to other nodes and a separate list of meta slots whose values contain data. These lists are indexed (log(n) lookups) and support cursor-like operations so they can be use for most database applications.

This is similar to a typical filesystem except directories (the equivalent of vertex's "nodes") contain separate namespaces for sub-directories ("slots") and files ("meta slots").


REQUESTS AND RESPONSES
----------------------
API requests are sent as HTTP POST messages with the content type of "application/json-request". The JSON request is a list of actions and each action is a dictionary. Responses are a list with an item (containing the results) for each of the actions in the request. Actions that have no responses typically return null. 

API requests are sent as HTTP POST messages with the content type of "application/json-request". The JSON request is a list of actions and each action is a list containing the name of the action and its arguments. Responses are a list with an item (containing the results) for each of the actions in the request. Actions that have no responses typically return null. 


PATHS
-----

All paths in requests are passed a JSON array of the path components. 
e.g. the string path of:

	"/a/b/c"

should be passed as:

	["a", "b", "c"]

This eliminates the need to encode slashes within the strings, so normal JSON string encodings can be used.
Also, all paths in requests are absolute paths.


SAMPLE REQUEST
--------------

	POST /
	Content-Type: application/json-request
	Content-Length: X

	[
		{ 
			'path': ['customers', 'John Doe', 'street'], 
			'do': 'mk',    
			'meta': { 'type': 'String', 'value': '203 Oak' }
		},
		{ 
			'path': ['customers', 'John Doe', 'street'],
			'do': 'mread',
	]	}


SUCCESS RESPONSE
----------------

	Content-Type: application/json
	Content-Length: X
	Status-Code: 200

	[
		null,
		{ 'type': 'String', 'value': '203 Oak' }
	]


ERROR RESPONSE
--------------

	Content-Type: application/json
	Content-Length: X
	Status-Code: 500

	{
		action: { 'do': 'mwrite', 'path': ['customers', 'Joe Shmoe', 'first name'] },
		message: "invalid path"
	}


ERROR CONDITIONS
----------------

Errors are only raised when the database would be left in an undesired state. So removes never raise errors and reads return null if the path is absent, while writes and links do raise an error if the path does not exists.

If any action in a request produces an error, no further actions are processed and any writes that were made within the request are aborted (not committed to the database). The HTTP response will have a 500 status and a description of the action that caused the error and the reason for the error.


META-SLOT CONVENTIONS
---------------------

By convention the meta slots "type" and "data" are used to indicate the node's type and to store raw data associated with it. Only primitive nodes types (such as String, Number, etc) should contain data values. The meta slot names "_user", "_group" and "_mode" are reserved for  permissions.


PERMISSIONS
-----------

Permissions follow normal unix filesystem conventions. The _user meta slot on a node can be used to specify the owner (by username) of the file. The _group meta slot specify a group that has access permissions on the file. The _mode slot can contain a string describing the permissions in the following format "rwxrwxrwx", where the first three characters determine read, write and execute permissions for the user, the next three apply to the group and the last three to other (all users). If a character contains a "-" that access permission is denied. e.g. a mode of "rwx------" would only allow the user to read, write or execute the node.

The user info is contained in the database itself in the path _internal/users/[username]. A user's password is contained on the node _internal/users/[username]/password in the data metaslot. When a request is processed, the HTTP cookie send with the request can contain "username" and "password" fields used to specify the login. It's recommended that this only be used with HTTPS. 


GARBAGE COLLECTION
------------------

Nodes are never removed directly in Vertex, only slots are. When the database grows above its highwater mark (currently, 10% larger than when it was started) a garbage collection cycle begins which uses server idle time to do incremental collection of unreferenced nodes.


TRANSACTIONS AND DATABASE INTEGRITY
-----------------------------------

The "sync" action can be used to commit the write ahead log to the database. This action takes a argument specifying the maximum amount of time the database is allowed to keep the data in a volatile state (not hard synced). If this time is 0, the sync is done before the response is sent, which is effectively the same as a traditional transaction. By making this time greater than 0, the database can group writes together into a single transaction and greatly increase write throughput (by minimizing waits on hard syncs and allowing the OS to optimize write ordering), so it's best to set this time to the maximum amount that meets the needs of the individual requests. Note: in this system, all actions within a request are guaranteed to be completely written or not written at all, there will be no partially completed requests.


API ACTIONS
-----------

	{ do:'mk', path:, meta:)
	{ do:'link', dest:, slot:, source: }
	{ do:'ls', path:, options: { start:, reverse:, max:, justCount:, inline: } }
	{ do:'rm, path:, slot: }
	{ do:'rename', path:, old:, new:)
	{ do:'mwrite', path:, slot:, value: }
	{ do:'mread', path:, slot: }
	{ do:'mls', path: }
	{ do:'mrm', path:, slot: }
	{ do:'mrename', path:, old:, new:)
	{ do:'sync', dt: }


API ACTION DESCRIPTIONS
-----------------------

Where not otherwise stated, all arguments are assumed to be strings. 
Boolean values treat null for false and non-null (1 is recommended) for true.

{ do:'mk', path:, meta:aDict)

	Writes: Create a node at path (creating any necessary path components 
		to that path). No change is made if the node is already present.
	Options:
		meta: the node's meta slots are set to match the dictionary. All dictionary values must be strings.
	Errors: none
	Returns: null


{ do:'link', dest: destPath, slot:slotName, source: sourcePath }

	Writes: At destPath, add a slot with named slotName that points to the node at sourcePath.
	Errors: An error occurs if either node does not already exist.
	Returns: null


{ do:'ls', path:, options: { start:, reverse:, max:, justCount:, inline: } }

	Writes: none
	Returns: a list of slot names at path.
	Options:
		start: if given, the list starts at the first (or last, if 
			optionalReverse is not null) key matching or after the optionalStart string. 
		reverse: if not null, the enumeration occurs in reverse order.
		max: if specified, limits the max number of returned results.
		justCount: Return only the count of the result list, and not the items themselves.
		inline: [not yet implemented] if non-null, instead of each item 
			being a slot name, it will be a list containing the slot name and a json 
			object with the inlined values for primitive types such as strings and numbers.

			Inline example. The Database node (meta slot names here are denoted with underscores):

			{ 
				"first name": { "type": "String", "data": "John" }, 
				"age":  { "type": "Number", "data": "30" }, 
			}

			Would be inlined as:

			{
				["John Doe", { "first name": "John", "age": 30 }]
			}

	Errors: none



{ do:'rm, path:, slot: }

	Writes: Removes the specified slot name on the node at path.
	Errors: none
	Returns: null
	

{ do:'rename', path:, old:oldSlot, new:newSlot)

	Writes: Renames the slot with specified oldSlot name to the specified newSlot name. Overrights if slot already exits.
	Errors: none
	Returns: null

{ do:'mwrite', path:, slot:, value: }

	Writes: At path, set/overwrite the specified meta slot to value.
	Errors: Raises error if the path does not exist.
	Returns: null


{ do:'mread', path:, slot: }

	Writes: none
	Errors: none
	Returns: a string containing the value of specified meta slot at path 
		or null if the path does not exist or slot is not present.
	

{ do:'mls', path: }

	Writes: none
	Errors: Raises error if path does not exists.
	Returns: a list of the meta slot names at path.


{ do:'mlsread', path: }

	Writes: none
	Errors: Raises error if path does not exists.
	Returns: a dictionary containing all meta slot names and values at path.	


{ do:'mrm', path:, slot: }

	Writes: Removes the meta slot at path. 
	Errors: none
	Returns: null


{ do: 'mrename', path:, old:oldName, new:newName: }

	Writes: Renames the meta slot with oldName to newName. Overrights if slot already exits.
	Errors: none
	Returns: null


{ do:'sync', in:dt }

	Writes: Tells vertex to do a hard sync within dt seconds. 
		If dt is 0 or unspecified, a hard sync will be done before the response is sent.
	Errors: none
	Returns: null
	
TODO 
----

- complete tests for all action options


FEEDBACK & COLLABORATION 
------------------------

Steve Dekorte
email: [email protected]
aim: stevedekorte

Rich Collins
email: [email protected]
aim: richwcollins