Sol Boucher and lane Lawley
#hashtable Software/Protocol Documentation and RFC

INTRODUCTION
	#hashtable is a Hadoop Filesystem--style quasi-distributed, redundant key-value data store.
	The system consists of a single master node that maintains all metadata and handles all requests and one or more slave systems.
	Clients connect to the master to retrieve the values of existing keys and store new data.
	Each slave holds a number of key/value pairs in RAM for fast access.
	The master is responsible for getting data from the slave that holds it and currently has the shortest waiting line.
	When given a brand new key, it chooses a set of slaves that keeps the data distribution as even as possible.
	Finally, it attempts to maintain the redundancy level as slaves are added and removed by copying data from those that still hold it.

USAGE INSTRUCTIONS
	BUILDING
	$ make

	BRINGUP
	1. On the master system: $ ./master
	2. On one or more slave systems: $ ./slave <hostname or address of master>
	3. On any client system(s): $ ./client <hostname or address of master>
	4. Run commands on those clients

	CLIENT OPERATIONS
	- put <key> <value> : store the specified (one-word) value under the given key
	- send <key> <filename> : store the contents of the file under the given key
	- get <key> : print the value associated with the key to standard output
	- get <key> <filename> : clobber the file given by filename with the value associated with the key

	MASTER OPERATIONS
	- slaves : show the living slaves and their loads
	- files : list the files and the slaves that hold each

	CHANGING REDUNDANCY LEVEL
	The common.h header contains a constant MIN_STOR_REDUN that specifies the number of copies of each file to keep in flight.
	This only affects the master, leading one to question why it is defined in that particular header.
	That issue asside, after changing it, one must do: $ make wipe && make master
	Please don't set it to anything unreasonable (i.e. anything le 0)!

	ANDROID SLAVE (experimental, but cool)
	1. Download the Android SDK and NDK from http://developer.android.com/sdk
	2. Put the extracted SDK's bin/ subdirectory and the extracted NDK itself in your $PATH (after which `$ which adb` and `$ which ndk-build` should work.)
	3. Connect an Andriod device via USB or networked ADB, then run $ ./deploy.sh
	4. Provide your terminal emulator app's package (e.g. jackpal.androidterm) and the hostname or address of the master node.
	5. On the device, open that same terminal emulator and run $ sh /sdcard/runslave.sh

OPERATION MODES
	(The system has a requested redundancy level REDUND.)
	(Requests to retrieve data are always served by the slave with the shortest waiting queue.)
	(Modifications to existing data occur on every one of the nodes responsible for the old value.)

	LOAD BALANCED (lighter load on slaves, full redundancy guarantee)
		Occurs when the number of online slaves is gt REDUND.
		There are exactly REDUND copies of any given file, each on a separate slave.
		Because there are extra slaves, the slaves are not identical:
			New data to be stored is sent to the slaves currently holding the least data.
		If new slaves join, they are only used for storing newly-received data.
		If a slave fails, every pair that would have been lost with it is recopied to another node.

	MIRROR MODE (all slaves identical, full redundancy guarantee)
		Occurs when the number of online slaves is eq REDUND.
		There are exactly REDUND copies of any given file, one on each of the slaves.
		Because there are just enough slaves, each is identical to the others.
		If new slaves join, they are only used for storing newly-received data.
		If a slave fails, all references to it are redacted from the relevant key table entries.

	DEGRADED MODE (all slaves identical, redundancy guarantee unmet)
		Occurs when the number of online slaves is lt REDUND.
		There are as many copies of each slave as there are usable slaves.
		Because there are so few slaves, they are all mirrors of one another.
		If new slaves join, all existing data is replicated onto it until it becomes a perfect clone.
		If a slave fails, all references to it are redacted from the relevant key table entries.

PACKET FORMAT
	All communications happen over a TCP stream for reliability, but transmissions are interpreted one high-level pseudo-packet at a time.
	(all packet types are capped at a total length of 512 B)
	* = denotes an unsigned 8-bit integer
	** = denotes an unsigned 16-bit integer
	^ = denotes a non--null terminated string, possibly containing binary data

			0		 2
	+--------------------+
	|  length**	opcode*  | (HEY, BYE, THX, FKU, SUP)
	+--------------------+

			0		 2	  3
	+-------------------------+
	|  length**	opcode*	key^  | (PLZ, HRZ)
	+-------------------------+

			0		 2		3
	+---------------------------+
	|  length** opcode*	value^  | (STF)
	+---------------------------+

OPCODES
	  1 PLZ (read request)						requires: key
	  2 HRZ (write request)						requires: key, followed by 1+ STFs
	  4 STF (data packet)						requires: more STFs following if length nonzero
	  8 HEY (slave joins master)				doesn't require: shit
	 16 BYE (slave deserts master)				doesn't require: shit (DEPRECATED)
	 32 THX (master plays along)				doesn't require: shit (DEPRECATED)
	 64 FKU (master has problem with slave)		doesn't require: shit
	128 SUP (slave hearbeat)					doesn't require: shit

PORTS
	CLIENT
		ephemeral port for communications

	MASTER
		client-facing port (1030)
		registration port (1031)
		heartbeat port (1032)
		ephemeral port for each slave

	SLAVE
		control port (1033)
		ephemeral port for heartbeats

PROCEDURES
	SLAVE REGISTRATION
		1. Slave sends HEY from its main port to master's registration port
		2. Master establishes new ephemeral port and opens TCP connection to slave's main port
		3. Slave establishes new ephemeral port and opens TCP conection to master's heartbeat port

	SLAVE HEARTBEAT
		1. Slave periodically sends SUP from its heartbeat port to master's heartbeat port
		2. If master fails to receive a certain slave's heartbeat, it stops using it
		3. If disowned slaves attempt to do anything, including keepalive, they receive an FKU

	CLIENT REQUEST
		1. Client sends PLZ.
		2. Master says HRZ.
		3. Master starts sending STF.
		4. Master concludes with an empty STF.

	CLIENT TRANSMISSION
		1. Client says HRZ.
		2. Client starts sending STF.
		3. Client concludes with an empty STF.

KNOWN LIMITATIONS
	Only a single instance of the slave can be run on any given system (although one slave can run on the same system as the master).
	Because the maximum length of a packet is fixed at 512 B and 3 of those octets are reserved for length and opcode, the maximum length of a key---excluding its null terminator---is currently 509 B.

ERRATA
	No comments are actually desired. In fact, any comments submitted will be despised. Commentors will be deposed.