CSE 486/586 Programming Assignment 3 Simple DHT solved

Description

Introduction
For this assignment you will design a simple DHT based on Chord. Although the design described here is based on Chord, it is a simplified version of Chord. You will not need to implementfingertablesorfinger-basedrouting,andyoudonotneedtohandlenodesleaving the DHT or failing. Likethepreviousassignment,yourappwillhaveanactivityandacontentprovider. However, the main activity should be used only for testing and should not implement any DHT functionality. The content provider should implement all DHT functionality and support insert and query functions on the DHT. Multiple content provider instances should form a Chord ring and serve insert and query requests in a distributed fashion according to the Chord protocol. You may use code from your previous projects in this project. Please remember to cite any code that comes from sources such as the Oracle tutorials or Android Developers. Please read this document in its entirety before you begin. It is long, but that is only because it is complicated and precise. Revisit the instructions regularly as you implement tobesureyou’reimplementingwhatisrequired. Therearenotesattheendthatmayassist you if you encounter common problems; make sure to review them as you go, as well. This assignment will require you to:
• Implement ID space partitioning and re-partitioning
• Implement ring-based routing
• Handle node joins to a DHT containing data
1 GettingStarted
We are providing a project template for you to get started. As in the previous assignments, the template configures a number of things on your behalf. It is important that you do not change settings that you do not have to change to complete your project. You will need to download the project from GitHub Classroom and open it in Android Studio. YoushouldhavereceivedtheGitHubClassroominvitationforthisprojectviaPiazza. Instructions for cloning the project and opening it in Android Studio are the same as before, except that the base repository name is SimpleDht. You can find YouTube tutorials detailing the process here.
1Thisassignmentisbased,withpermission,onanassignmentdevelopedandusedbySteveKoinhisversion of CSE 486/586. Large portions of text are used verbatim from that assignment.
1
2 TheContentProvider The graded portion of this project is a ContentProvider using DHT semantics similar to a simplified Chord to store and retrieve data across multiple devices. The provided template usesthepackagenameedu.buffalo.cse.cse486586.simpledht,anddefinesacontentprovider authority and class. Please do not change the package name, and use the content provider authority and class for your implementation. You will use SHA-1 as the hash function to generate IDs for the DHT. The following code snippettakesaJavaStringandusesittogenerateaSHA-1hashasahexadecimalstring. Use thistogenerateyourkeys. Theprojecttemplatealreadyincludesthiscode,youmustsimply use it in the appropriate places. Given two keys, you can use the standard lexicographical String comparison (i.e.,String.compareTo(String)) to determine which one is greater. import java.security.MessageDigest; import java.security.NoSuchAlgorithmException; import java.util.Formatter; private String genHash(String input) throws NoSuchAlgorithmException { MessageDigest sha1 = MessageDigest.getInstance(“SHA-1”); byte[] sha1Hash = sha1.digest(input.getBytes()); Formatter formatter = new Formatter(); for (byte b : sha1Hash) { formatter.format(“\%02x”, b); } return formatter.toString(); } For this project, you will need to run five emulators. We will be using the multi-port configuration as described in project 1. Your app will open one server socket that listens on port10000, but itwill connect to a differentport number on the IPaddress 10.0.2.2foreach emulator, as follows: emulatorserial port emulator-5554 11108 emulator-5556 11112 emulator-5558 11116 emulator-5560 11120 emulator-5562 11124
2.1 ImplementingtheContentProvider YourapplicationcontentprovidershouldimplementalloftherequiredDHTfunctionalities. For example, it should create server and client threads (if you choose to use them in your implementation),opensockets,andrespondtoincomingrequests. Itshouldalsoimplement the simplified version of the Chord routing protocol specified here. Finally, it should also handle node joins. The specific requirements for your content provider follow.
2
2.1.1 Requirements 1. The URI of your content provider must be: content://edu.buffalo.cse.cse486586.simpledht.provider 2. ThecontentprovidershouldimplementallDHTfunctionalities. Thisincludesallcommunication as well as mechanisms to handle insert and query requests from other nodes and to handle node joins.
3. EachcontentproviderinstanceshouldhaveanodeIDderivedfromitsemulatorserial number. This node ID must be obtained by applying the specified hash function (named genHash(), above) to the emulator serial number. For example, the node ID of the content provider running on emulator-5554 should benode_id = genHash(“5554″). The ID stringyoushoulduseisexactlythestringfoundinportStrinthetelephonyhack. This is necessary to place each node in the correct place in the Chord ring. 4. Your content provider must implementinsert(), query(), anddelete(). The basic interface definition is the same as in Project 2, parts A and B, which allows a client to manipulate arbitrary key-value pairs, where both the key and value are Java strings. • Fordelete(URI uri, String selection, String selectionArgs)you need only use the first two paramters, uri and selection, similar to our previous implementations ofquery(). • The key must be hashed by genHash() before being inserted in the DHT in order to determineitspositionintheChordring. 5. Forbothquery()anddelete(),youmustrecognizetwospecialstrings,”*”and”@”,for theselectionparameter. • If*(notincludingquotes;”*”shouldbetheliteralstringinyourcode)isgivenas theselectionparametertoquery(),thenyoumustreturnallkey-valuepairsstored inyourentireDHT. • Similarly,if*isgivenastheselectionparametertodelete(),thenyoumustdelete allkey-valuepairsstoredinyourentireDHT. • If@(again,notincludingquotes)isgivenastheselectionparametertoquery()on a given AVD, then you must return all key-value pairs stored on the AVD running thequery, but not any other AVDs in the DHT. • Similarly,if@isgivenastheselectionparametertodelete()onanAVD,thenyou mustdeleteallkey-valuepairsstoredontheAVDrunningthedelete,butnotonany other AVDs in the DHT.
6. Anyappusingyourcontentprovidercansubmitarbitrarykey-valuepairsofJavastrings (e.g.,<“I want to”,”store this”>). YourcontentprovidermusthashthekeyusinggenHash() (inthisexample,genHash(“I want to”))tofindthecorrectlocationintheChordringfor this datum, then store <“I want to”,”store this”> on the appropriate node.
3
7. Your content provider must implement ring-based routing (but need not implement Chord finger routing or finger tables). Following the Chord ring design, your content provider should maintain predecessor and successor pointers, then forward each requestfordatanotstoredlocallytoitssuccessoruntiltherequestarrivesatthecorrect node. WhenanodereceivesarequestforanIDthatitmaintains,itshouldprocessthe request and send the result (either directly or recursively, at your discretion) to the content provider instance initiating the request.
8. Your content provider should handle new node joins. For this functionality, the emulator instance emulator-5554 should receive all new node join requests. You should not choosearandomnodetoreceivenewnodejoinrequests,andyoushouldstartthecontent provider on emulator-5554 first to enable this. upon completing a new node join request, affected nodes should update their predecessor and successor pointers correctly.
• Your content provider need not handle concurrent node joins. You can assume that a node join will only happen after the system has completely processed any previous node joins. • Yourcontentproviderneednothandleanyinsert,query,ordeleterequestswhile a node is joining. You may assume that requests will be issued only when the system is stable. • Your content provider need not handle node leaves or failures.
9. As in the previous assignments, your content provider should have two columns.
• Thefirstcolumnshouldbenamed“key”(alllowercase,noquotationmarks). This column is used to store keys. • The second column should be named “value” (all lowercase, no quotation marks). This column is used to store the values associated with keys. • All keys and values stored by your provider should be Java strings.
10. Any app should be able to access (both read and write) your content provider. As in previous assignments, please do not require any permissions to access your content provider.
Note that each content provider must store only the key-value pairs local to its own partition oftheChordIDspace!
2.2 Writingthemainactivity The provided template code includes an activity to be used for your own testing and debugging. It will not be specifically graded or evaluated in any way. It has three buttons; one button that displays “Test”, one button that displays “LDump”, and another button that displays “GDump”. As in the previous assignment, the “Test” button is already implemented (and it is the same as “PTest” in Programming Assignment 2 part B). You can (and should) implement the other two buttons to further test your DHT.
4
• LDump
– When pressed, this button should dump and display all of the key-value pairs storedonthelocalpartitionoftheDHT. – This can be accomplished by issuing a query with @ as the selection parameter, and printing the results.
• GDump
– When pressed, this button should dump and display all of the key-value pairs in theentireDHT. – This can be accomplished by issuing a query with * as the selection parameter, and printing the results.
• Inthismanner,theLDumpbuttonwillprovidea“localdump”ofthecurrentAVD,and GDump will provide a “global dump” of the contents of the entire ring.
You may find it useful or desirable to implement additional functionality in your main activity, and that is fine.
2.3 Testing We have testing programs to help you see how your code does with our grading criteria. If youfindroughedgesinthetestingprograms,pleasereportitsotheteachingstaffcanfixit. The instructions for using the testing programs are the following:
• Downloadatestingprogramforyourplatform. Ifyourplatformdoesnotrunit,please report it.
1. Windows: Tested on 64-bit Windows 8. 2. Linux: Testedon64-bitDebian9and64-bitUbuntu17.10(seebelowforimportant information about 64-bit systems). 3. Mac OS: Tested on 64-bit Mac OS 10.9 Mavericks.
• Before you run the program, please make sure that you are running all five AVDs. You can usepython run_avd.py 5to start them. • Remember to start the emulator network by runningset_redir.py 10000. • Like the previous testing program, this test will require you to provide your APK as a command line argument, and will take care of installing and uninstalling it on the emulators.
• Run the testing program from the command line.
• It may issue some warnings or errors during execution. Some of them are normal, some may indicate errors in your program. Examine them to find out!
5
• The testing program will give you partial and final scores.
Remember during your own testing that you may see strange contents in your content provider if you do not uninstall your application between tests. In particular, updating the app from Android Studio does not uninstall the existing app first, so the content provider’s state will not be cleared. You can uninstall your app by hand with the following command: adb -s uninstall edu.buffalo.cse.cse486586.simpledht
Notesfor64-bitLinux: Thetestingprogramiscompiled32-bit. Ifyougetanerrorlikethe following, or the shell reports command not found when you run the executable, install the 32-bitlibzfor your system: ./simpledht-grading.linux: error while loading shared libraries: libz.so.1: cannot open shared object file: No such file or directory OnDebian-baseddistributions,youcanaccomplishthiswiththecommandapt-get install zlib1g:i386 as root (you may need to use sudo or su). If apt-get reports an error about the architectureorsaysthepackageisnotfound,youmayneedtoenablemultiarch. Todothis, rundpkg –add-architecture i386as root, then update your APT repositories withapt-get updateas root. Once this is done, you should be able to install the 32-bitlibz. For other distributions you will need to consult your distribution documentation.
3 Submission We use UB CSE autograder for submission. You can find autograder athttps://autograder. cse.buffalo.edu/, and log in with your UBITName and password. Once again, it is critical that you follow everything below exactly. Failure to do so willlead tonocreditforthisassignment. Zip up your entire Android Studio project source tree in a single zip file. Ensure that all of the following are true: 1. You didnot create your zip file from inside theGroupMessenger1directory. 2. The top-level directory in your zip file is SimpleDht or SimpleDht-, and it containsbuild.gradleand all of your sources. 3. Youusedaziputilityandnotanyothercompressionorarchivetool: thismeansno7-Zip, no RAR, no tar, etc.
4 Deadline
This project is due 2018-04-13 11:59:00 AM. This is one hour before our class. This is a firm deadline. If the timestamp on your submission is 11:59:01, it is a late submission. You are expected to attend class on this day!
6
Notethatthisdeadlinehasbeenpre-extended,anditwillnotbeextendedanyfurther. Extending this deadline will not leave sufficient time to both complete Programming Assignment 4 and study for Finals.
5 Grading
This assignment is 10% of your final grade. Credit for this assignment will be apportioned as follows:
• 1%: Local insert/query/delete operations work on a DHT containing a single AVD.
• 2%: The insert operation works correctly with static membership of 5 AVDs.
• 2%: The query operation works correctly with static membership of 5 AVDs.
• 2%: The insert operation works correctly with between 1 and 5 AVDs (and possibly changing membership).
• 2%: The query operation works correctly with between 1 and 5 AVDs (and possibly changing membership).
• 1%: The delete operation works correctly with between 1 and 5 AVDs (and possibly changing membership).
Thus,anapplicationprovidingalloftherequiredfeatureswouldreceieve10totalpoints, for 10% of the final course grade.
Notes
• Pleasedonotuseaseparatetimertohandlefailures,asthiswillmakedebuggingvery difficult and is likely to introduce race conditions. Use socket timeouts and handle all possible exceptions that may be thrown when there is a failure. They are: SocketTimeoutException,StreamCorruptedException,EOFException,andtheparentIOException. • PleasereuseyourTCPconnectionswithasingleremotehost,insteadofcreatinganew socket every time you send a message. You can use the same socket for both sending to and receiving from a remote AVD. Think about how you will coordinate this. • Please do not use Java object serialization (i.e., implementing Serializable). This will cause very large messages to be sent and received, with unnecessarily large message overhead.
• Please do not assume that a fixed number of DHT operations will be invoked on your system. Yourimplementationshouldnothardcodethenumberortypesofoperations in any way.
7
• Remember that there is a cap on the number of AsyncTasks that you can execute simultaneously. Plan accordingly, to keep the total number of threads that you require under this limit (which is about five).
• If the testing program cannot install your APK on one or more emulators, try each of the following steps:
1. Restart the problematic emulator. 2. Clean your build in Android Studio, then invoke the “Build APK” menu item and try again. 3. Manually install your APK usingadb installto ensure that it is installable.