NAME: Tat Leung Chung
CS551 Final project
Date: 5/10/2004
A Peer-to-Peer File Sharing System
--------------------------------------
Introduction
------------
This is a distributed file sharing system using peer-to-peer technology
called SERVANT. It is composed of a collection of nodes. A user of
each node can store, search, retrived and delete file on the SERVANT
network. The whole source code consists of 8000 lines of code in
55 files written in C++. The whole program is carefully check for
out of memory in new() and perform cleanup on memory and
temporary file upon shutdown. There is a global debug flag in
sv_node.cpp that you can turn on for diagnostic.
There are 2 types of nodes, beacon and non-beacon. Beacon
nodes will always retrying to reconnect each other to form
full mesh. They known each other address when startup from a
configuration file. Non-beacon node will connect to beacon
node when startup and flood a join message through beacon node
to get distance to all neighbors, then disconnect from beacon
node and select a few peer to make connection.
Architecture
------------
Each nodes will create one thread for each connection to other
node. This connection thread is used for both sending and receiving
message. Basically the thread will wait for either timeout or
data coming from socket using select(). If timeout a keepalive
message is send to the peer to see if connection still valid. When some other
threads has messages for this thread to send. They will put the
message in a queue belong to this thread, the do a signal on it.
So the thread will quit from blocking select() and send
the messages in queue if not empty.
The main thread is used for accepting connection from peer
and spawn new connection thread. There is also 2 other threads
for each node - the timer thread and the user thread.
The timer thread will waitup every second and decrement
message lifetime of messages in a table it has seen before.
If the lefetime is zero the message is parse from the table.
The thread also used for autoshutdown features and timeout
when user command 'get' does not return file.
The UOIDs of message it seen before are save in a binary tree
for efficiently lookup.
The main loop of program to process message is as follows:
while (running) {
while (reconnect) {
// try to reconnect in case of beacon or quit
}
r = select() read socket
if (r == 0) {
sendKeepAlive message();
continue;
}
if (r < 0) {
// signal by other thread
if (!running) {
break; // signal by SIGINT
}
if there is message m on write queue // signal by SIGCONT
m->send() for each one.
continue;
}
m = readMessage();
if (m == NULL) {
// handle error or
// set reconnect = true for beacon
continue;
}
if (m->duplicate) {
// drop the message
continue;
}
m->handleMessage();
if (m->timeToLive > 0) {
m->forwadMessage();
}
}
Each message is a class of its own (e.g. JoinMessage.cpp,
JoinResMessage.cpp, CheckMessage.cpp, SearchMessage.cpp...)
with base class Message.cpp.
Openssl Environment
--------------------
User has to set path to openssl, otherwise program will
not work. I don't want to hardcode the path to
/usr/usc/openssl/default/bin/openssl
so the program can use in other system.
Connection Initialization
--------------------------
When non-beacon node startup it will connect to beacon. If there is
simultanously connection the server will wait for the hello message
to come back. After node have BOTH Hello message from simultaneous
connection it will break tie by closing one connection depending on
node ID.
Check Message
-------------
When one of the peer's connection in a node disconnect, the
thread for that peer will ask other connection threads to
send out check message using with timeToLive = TTL in
config file. After sleep for joinTimeout it check if
there is Check response message back from beacon.
If not all peer connection is closed and system will restart.
Mini-File System
-----------------
The implementation is in class MiniFileSys. There
is a vector of FilenoNode table which contains
the following fields
(i) File no use in current file system
(ii) FileID
(iii) file size
(iv) isCached
(v) Nonce
(vi) SHA1
(vii) Filename
(v), (vi) and (vii) are used for
a) Delete message to figure out which fileno to delete
b) Store and GetResponse Message to check
if file is duplicated before cached.
(iv) is used to distinguish whether the file is
permanent or just cache.
LRU algorithm is used for cache replacement. When
there is new file need to cache. If the file size
is less than cacheSize the FilenoNode table
is search in order of insertion and remove file
mark as cache using (iv) until there is enough room
for new file.
The field (iii) is used to compute currently permanent
file usage and cached file usage. So when the system
startup and load this FilenoNode table we know
current file size and use it to check quota.
The fieldID field (ii) is a globally unique File ID
that return response to 'search' and 'get' request.
To assist filename, sha1 and keywords searching,
there are 3 other indices for them.
(a) A binary tree of FilenameNode index by filename.
It has 1 field contains a list of fileno.
(b) A binary tree of SHANode index by SHA1.
It has 1 field contains a list of fileno.
(c) A vector of BitVectorNode.
It has 2 fields: 1024 bit vector and
a list of fileno.
The above 3 indices and FilenoTable are stored in
each node homeDir as name_index, sha1_index,
kwrd_index and fileno_index respectively. They
are saved when node shutdown.
Since search result has to return FileID instead of
file no, we need a way to quickly locate FileID
based on file no. One way is to search the FilenoTable
linearly which is O(n). In my implementation an
additional hash map data structure is used to map
file no to pointer of FilenoNode structure in
FilenoNode table. This hash map operation is O(1) and
is built when loading FilenoNode table and will not store in disk.
As a result search can be done in O(log n) for n files.
The BinaryTree implementation from :
http://www.cs.fiu.edu/~weiss/dsaa_c++/code
is employed. However it does not have code to load/save
a binary tree in linear time. So I modify to perform
an O(n) load/save operation. For save it use in order
traveral of tree to get a sorted list. For load it
get the middle element of a sorted list and pass the
left/right array to construct left/right side of tree
recursively.
Store Command
-------------
Syntax: store <filename> <ttl> [tag1=\"value1\" tag2=\"value2\" ...]
The file is stored locally and then
send out store message to all its peer
based on NeighborStoreProb. Error message will
output if store fail.
The timeToLive is set using the input from
user shell. If timeToLive = 0 store message
will not send out to its peer.
When the peer get the message it pass StoreProb
test it will check if file already exists or not.
If not and cacheSize is big enough then peer will
put it in cache (possibly remove of other cached
file based on LRU). SHA1 is computed and check with
file metaData before store to provide integrity of file.
The file in the message is store in a temporary file
when message is received or forward. When the message is
destroy this temporary file is removed. In this case there
is no limit to the file size we can transfer and forward.
Search Command
--------------
Syntax: search [filename|sha1hash|keywords]=<query>
The file system locally is search first.
Then the node is send out message to all peers using
timeToLive = TTL in config. file.
The user shell is wait until it press Ctrl-C.
For keyword search, if the bitVector from Bloom filter
match, the program will actually open the metaData
file, extract the keywords and compare it one by one.
Keywords are not store in FilenoNode since it can be
big potentially (vs the other fields which is
pretty much fix size).
Get Command
-------------
Syntax: get <fileIdx>
If file index (from search result) is a local file
the program will output file already exists.
Otherwise it will send out GetMessage to peer
and output 'Success' in user thread and control
resume to user.
If for some reason (e.g. the only node that
has the request FileID down) there is no
Get Reponse Message back for time = 3*joinTimeout
the user thread will resume control with message
'Fail to get File !'.
When Peer node get the response file, it may cache
it based on cacheProb before forward. It there is
enough room to cache (after remove old cache file
based on LRU), SHA1 is computed and check with
file metaData before store to provide integrity of file.
Status Command
---------------
Syntax: status [neighbors|files] <ttl> <extfile>
This is used for grading purpose. For neighbors it will draw
the connection graph (up to specific ttl) in nam format
with duplication link removed.
For files it will output all files store in neighbors (up to
specific ttl) in the format
[host:port]
FileID=...
[metadata]
FileName=...
FileSize=...
...
FileID=...
[metadata]
FileName=...
FileSize=...
...
[host:port]
FileID=...
[metadata]
...
Delete Command
--------------
Syntax: delete FileName=<filename> SHA1=<sha1> Nonce=<nonce>
Local file system is search for the file to delete.
If there is a match and signature verify successfully the
user shell will output 'Success'. If signature verification
fail the user shell will output '
To search the file system for deletion. Instead of using
linear search on FilenoTable, the program search using
SHANode Index Tree and Filename Index Tree. Then perform
an intersection of 2 fileno vectors. The resulting list is
either 0 or 1 element since we have check for duplication
before storing in file system using nonce, sha1 and filename.
The time complexity for search is O(log N)
If there is a match we use the hash map to map the fileno
to FilenoNode. Thus we can get the nonce and compare. If
it matches the digitally sign metaData is verify with
fileno.cert for that file. In the peer side, there is no
feedback to the user shell so the use will not know if
delete success or not in peer side until using status or
search command.
Shutdown Command
----------------
Syntax: shutdown
The user thread will send a signal to wakeup all connection
threads, then quit. Then main thread will close all
connections and wait for N+2 thread to join. All resources
are cleanup either in C++ destructor or explicitly. The
index(s) file are saved.