A Distributed Hash Table Implementation

Consider a set S of p strings: S = {s1, s2, . . . , sp} and a set N of q nodes: N = {n1, n2, . . . , nq}. Your purpose in this project is to implement a distributed hash table that will help find out efficiently whether a given string s exists in S (i.e., check if s ∈ S). In the meanwhile, insertion of new strings, and deletion of existing strings will be supported. The distributed hash table will be a composition of local hash tables maintained by each node separately. Let H denote the global (distributed) hash table and Hi (for 1 ≤ i ≤ q) denote the local hash table at node ni. The following should always hold true: s ∈ S ⇒ ∃i s.t. 1 ≤ i ≤ q, s ∈ Hi (1) ∀s ∈ S, @(i, j) s.t. 1 ≤ i ≤ q, 1 ≤ j ≤ q, i 6= j, s ∈ Hi, s ∈ Hj (2) ∀i, 1 ≤ i ≤ q, s /∈ Hi ⇒ s /∈ S (3) Equation 1 states that every string s in S should be inserted into at least one local hash table. Equation 2 gives an upper bound: a string s in S cannot be inside two distinct local hash tables. Equation 3 is implied by (1) and (2): if a string s is not in any of the local hash tables, then it cannot not be in S. A distinct node nc ∈ N is elected to be the coordinator node. Duties of the coordinator nc involve: • Distributing strings inside S to nodes of N in the setup phase (see below for details). • Managing user queries on a string s (a query is a set membership test on H): 1. Directing queries to all nodes of N (including itself). 2. Obtaining responses of the nodes on a query. 3. Calculating the final response based on local responses (s /∈ S if no ni has it). 4. Telling the final response to the user. • Keeping track of the number of strings in each Hi • Updating these counts as new strings are inserted and existing strings are deleted. • Managing insertion requests on a string s from the user: 1. Finding a node that has the minimal number of strings. 2. Sending s to that node for insertion. • Managing deletion requests on a string s from the user: 1. Finding the node that holds s (if any). 2. Asking that node to delete s. 1 Setup phase • The non-coordinator nodes start first. Each such node opens a server socket on a specific port number (passed to the program as a command-line parameter) and starts listening for a connection (from the coordinator). • The coordinator nc starts with the path to a configuration file passed as a command-line argument. The configuration file (say “[login to view URL]”) contains the following: – The number of nodes q on the first line; – One line per non-coordinator node (q − 1 lines total) listing each node’s IP address and the port number it is listening on; – The path to an input file (say “[login to view URL]”) that contains the strings (i.e., set S); – The number of strings p in S. The input file is structured such that every line contains a single string. You may assume that there are no duplicates in the input file (so that Equation 2 holds trivially). • Once started, nc establishes a socket connection with each non-coordinator node. • nc then reads the input file and sends each non-coordinator node (including itself) roughly p/q strings. Once setup phase is over, nc presents the user with 4 options: 1. Query a string s. 2. Insert a new string s. 3. Delete an existing string s. 4. Exit For each possible action, nc contacts relevant nodes as necessary. If the user wants to exit, then all socket connections will be closed properly and every node will terminate one by one. Example configuration file (“[login to view URL]”): 3 [login to view URL],4444 [login to view URL],4445 [login to view URL] 4 Example input file (“[login to view URL]”): Uzaktan egitim ne hos Ali ucaga bin Ahmet topu tut Ayse kalem al Sample command that starts the first non-coordinator node: java -cp . [login to view URL] 4444 Sample command that starts the coordinator node: java -cp . [login to view URL] [login to view URL]