notes/directory-layer-design.md - couchdb-erlfdb - Git at Google

 Directory Layer Schema-ish
 ==========================


 `'\x16...'` to `'\x1D...'` - Keys that represent contents of the directory
     tree. This is basically "all possible positive integers". The prefix
     of each key is a directory node down below.


 `'\xFE'` - Prefix for all keys related to the directory tree node
     hierarchy.


 `'\xFE\x01version\x00'` - Version of the directory tree formatted as:
     <<V1:32/little-unsigned, V2:32/little-unsigned, V3:32/little-unsigned>>


 `'\xFE\x01\xFE\x00'` - the root node of the tree


 `'\xFE\x01\xFE\x00\x01layer\x00'` - the "layer" of the given node. This
     is set at node creation time and never mutated by the directory layer.
     If a layer is provided when opening nodes it checks to see that the
     layer matches nodes that are read. When there's a mismatch an error
     is thrown. I believe the purpose of this is so that users of the
     DirectoryLayer can assert a primitive "ownership" over part of the
     directory tree with some guarantee that they won't accidentally trample
     over each other. However, if "layer" is the binary string "partition"
     then this becomes a whole new thing which I'll discuss below.


 `'\xFE\x01\xFE\x00\x16' - The prefix for all child nodes of the root node. The
     pattern here is basically `'\xFE'` + erlfdb_tupe:pack({node.key(), 0})
     although its using erlfdb_subspaces under the hood. I may ixnay subspaces
     in the directory layer because the syntax really isn't all that useful
     in Erlang.


 `'\xFE\x01\xFE\x00\x16\x02foo\x00'` -> `'\x17\x05'` - A child node named "foo"
     which has a node id of `\x17\x05`.


 `'\xFE\x17\x05\x16\x02bar\x00'` -> `'\x17\x19'` - A child of "foo" named
     "bar" with node id `'\x17\x19'`. The tree is made by recursively
     following these paths.


 `'\xFE\x17\x19\x01layer\x00'` -> `'partition'` A node id has its layer value
     set to partition which means that this node is "DirectoryPartition"
     which basically means its node id is pasted onto the front of
     every subtree node. This can be useful to do a range scan against an
     entire subtree. However, directories can not be moved across partition
     boundaries (because that would require changing all of their key
     prefixes). Also, it makes key lengths slightly longer by the length
     of the short node id string.

     Partitions are roughly equivalent to a nested directory tree re-rooted
     outside the main directory tree. All of the contents and node keys
     share the same prefix based on the node id of the partition.


 Some Names
 ==========

 A warning to future readers, this list of names is used fairly consistently
 by the `erlfdb` DirectoryLayer, however they are not all used in the
 Python implementation. So any comparison between the two requires some
 fairly decent knowledge of how things work. This is mostly because the
 Python implementation doesn't actually bother naming things and instead has
 a number of long function invocations that gloss over where we might need
 to assign something to a variable in Erlang.

   * directory name = human readable string
   * node_name = shortened binary
   * root version = node_prefix + {"version"}
   * root node = node_prefix + {node_prefix}
   * partition id = node_name + 16#FE
   * partition version = node_name + {"version"}
   * partition node = partition_id + {partition_id}
   * node_id = node_prefix + {node_name}
   * node_layer_id = node_prefix + {node_name, "layer"}
   * node_entry_id = node_prefix + {node_name, SUBDIRS, directory name}


 Algorithms
 ==========

 These are all based on the assumption that my schema is at least relatively
 close to reality and also by staring at the Python implementation. However,
 the Python implementation makes extensive use of OO inheritance as well
 as syntactical sugar via magic methods. These algorithms are my general
 reinterpretation of the Python approach in Erlang terms.

 Some common assumptions here:

   * Path is a tuple of UTF-8 encoded binaries.


 Find Node at Path
 -----------------

   * Get the root node (i.e., `\xFE\x01\xFE\x00`) (though this will
     obviously be parameterizable).
   * curr_node = RootNode
   * For part in path:
     - node_id = erlfdb:get(Tx, Root + to_string(Path))
     - if node_id == not_found: return not_found
     - curr_node = `'\xFE' + node_id`
   * return curr_node


 Open Directory at Path
 ----------------------

   * Find node at path
   * If not found, return not_found or throw an error or w/e
   * Read layer value
   * Optionally pre-fetch child keys. Would be more efficient as
     a single range scan, but super wide trees would be ungood
   * if layer != "partition": Return value representing this directory
     - root reference
     - path referecne
     - layer
     - children
   * else: Return record representing this partition
     - previous root
     - new root
     - path to partition root


 Create New Directory at Path
 ----------------------------

   * Find directory at Path[:-1]
   * If directory[Path[-1]] exists: return exists
   * Allocate new node id via HCA
   * Write `'\xFE' + node_id + '\x01layer\x00' = whatever was passed
   * return samesies as for open path


 Remove A Directory at Path
 --------------------------

   * Find node at Path
   * del_children(node_id):
   *    for name, child_id in children(node_id):
   *        del_children(child_id)
   *        clear_range for all content related to child_id
   *    clear_range for this node's layer and children nodes
   * delete node_id from Path[:-1]


 Move a Directory from PathA to PathB
 ------------------------------------

   * Bunch of error checking and partition handling
   * Insert PathA node_id to PathB[:-1]'s list of children
   * Then remove PathA's node_id from PathA[:-1]


 List Directory at Path
 ----------------------

   * Find Directory at Path
   * Return children list. Mebbe after a range read if they
     haven't been pre-loaded.


 Directory Exists
 ----------------

   * Find directory, see if it throws an error


 Tests
 -----

   * Opening a directory creates parent directories?
   * Creating parent directories does not set a label?
   * Opening nested directories does not check intermediate labels?
	Directory Layer Schema-ish
	==========================


	`'\x16...'` to `'\x1D...'` - Keys that represent contents of the directory
	tree. This is basically "all possible positive integers". The prefix
	of each key is a directory node down below.


	`'\xFE'` - Prefix for all keys related to the directory tree node
	hierarchy.


	`'\xFE\x01version\x00'` - Version of the directory tree formatted as:
	<<V1:32/little-unsigned, V2:32/little-unsigned, V3:32/little-unsigned>>


	`'\xFE\x01\xFE\x00'` - the root node of the tree


	`'\xFE\x01\xFE\x00\x01layer\x00'` - the "layer" of the given node. This
	is set at node creation time and never mutated by the directory layer.
	If a layer is provided when opening nodes it checks to see that the
	layer matches nodes that are read. When there's a mismatch an error
	is thrown. I believe the purpose of this is so that users of the
	DirectoryLayer can assert a primitive "ownership" over part of the
	directory tree with some guarantee that they won't accidentally trample
	over each other. However, if "layer" is the binary string "partition"
	then this becomes a whole new thing which I'll discuss below.


	`'\xFE\x01\xFE\x00\x16' - The prefix for all child nodes of the root node. The
	pattern here is basically `'\xFE'` + erlfdb_tupe:pack({node.key(), 0})
	although its using erlfdb_subspaces under the hood. I may ixnay subspaces
	in the directory layer because the syntax really isn't all that useful
	in Erlang.


	`'\xFE\x01\xFE\x00\x16\x02foo\x00'` -> `'\x17\x05'` - A child node named "foo"
	which has a node id of `\x17\x05`.


	`'\xFE\x17\x05\x16\x02bar\x00'` -> `'\x17\x19'` - A child of "foo" named
	"bar" with node id `'\x17\x19'`. The tree is made by recursively
	following these paths.


	`'\xFE\x17\x19\x01layer\x00'` -> `'partition'` A node id has its layer value
	set to partition which means that this node is "DirectoryPartition"
	which basically means its node id is pasted onto the front of
	every subtree node. This can be useful to do a range scan against an
	entire subtree. However, directories can not be moved across partition
	boundaries (because that would require changing all of their key
	prefixes). Also, it makes key lengths slightly longer by the length
	of the short node id string.

	Partitions are roughly equivalent to a nested directory tree re-rooted
	outside the main directory tree. All of the contents and node keys
	share the same prefix based on the node id of the partition.


	Some Names
	==========

	A warning to future readers, this list of names is used fairly consistently
	by the `erlfdb` DirectoryLayer, however they are not all used in the
	Python implementation. So any comparison between the two requires some
	fairly decent knowledge of how things work. This is mostly because the
	Python implementation doesn't actually bother naming things and instead has
	a number of long function invocations that gloss over where we might need
	to assign something to a variable in Erlang.

	* directory name = human readable string
	* node_name = shortened binary
	* root version = node_prefix + {"version"}
	* root node = node_prefix + {node_prefix}
	* partition id = node_name + 16#FE
	* partition version = node_name + {"version"}
	* partition node = partition_id + {partition_id}
	* node_id = node_prefix + {node_name}
	* node_layer_id = node_prefix + {node_name, "layer"}
	* node_entry_id = node_prefix + {node_name, SUBDIRS, directory name}



	Algorithms
	==========

	These are all based on the assumption that my schema is at least relatively
	close to reality and also by staring at the Python implementation. However,
	the Python implementation makes extensive use of OO inheritance as well
	as syntactical sugar via magic methods. These algorithms are my general
	reinterpretation of the Python approach in Erlang terms.

	Some common assumptions here:

	* Path is a tuple of UTF-8 encoded binaries.


	Find Node at Path
	-----------------

	* Get the root node (i.e., `\xFE\x01\xFE\x00`) (though this will
	obviously be parameterizable).
	* curr_node = RootNode
	* For part in path:
	- node_id = erlfdb:get(Tx, Root + to_string(Path))
	- if node_id == not_found: return not_found
	- curr_node = `'\xFE' + node_id`
	* return curr_node


	Open Directory at Path
	----------------------

	* Find node at path
	* If not found, return not_found or throw an error or w/e
	* Read layer value
	* Optionally pre-fetch child keys. Would be more efficient as
	a single range scan, but super wide trees would be ungood
	* if layer != "partition": Return value representing this directory
	- root reference
	- path referecne
	- layer
	- children
	* else: Return record representing this partition
	- previous root
	- new root
	- path to partition root


	Create New Directory at Path
	----------------------------

	* Find directory at Path[:-1]
	* If directory[Path[-1]] exists: return exists
	* Allocate new node id via HCA
	* Write `'\xFE' + node_id + '\x01layer\x00' = whatever was passed
	* return samesies as for open path


	Remove A Directory at Path
	--------------------------

	* Find node at Path
	* del_children(node_id):
	* for name, child_id in children(node_id):
	* del_children(child_id)
	* clear_range for all content related to child_id
	* clear_range for this node's layer and children nodes
	* delete node_id from Path[:-1]


	Move a Directory from PathA to PathB
	------------------------------------

	* Bunch of error checking and partition handling
	* Insert PathA node_id to PathB[:-1]'s list of children
	* Then remove PathA's node_id from PathA[:-1]


	List Directory at Path
	----------------------

	* Find Directory at Path
	* Return children list. Mebbe after a range read if they
	haven't been pre-loaded.


	Directory Exists
	----------------

	* Find directory, see if it throws an error


	Tests
	-----

	* Opening a directory creates parent directories?
	* Creating parent directories does not set a label?
	* Opening nested directories does not check intermediate labels?