DistributedHashtable

---

id: DistributedHashtable title: Distributed Hashtable permalink: /docs/manual/DemoApps/DistributedHashtable.html

Source Code on GitHub

Hashtable is among the most useful daily-used data structures. A distributed hashtable is a hashtable served by a cluster of machines. It can be accessed through network. We demonstrate how to implement a distributed hashtable on top of GE and how it can be accessed via user-defined interfaces.

Data Model

A hashtable consists of a set of buckets, each of which is collection of key-value pairs. We use string to represent both the Key and Value in this demo application. In GE, we can use a cell as a hashtable bucket. We define BucketCell in TSL for this purpose:

structKVPair{stringKey;stringValue;}cellstruct BucketCell
{List<KVPair>KVList;}

Given an arbitrary Key, we first hash it to a 64-bit cell id. Then we use this id to reference the cell bucket.

Setting A Key-Value Pair

Because we are working on a distributed hashtable, we need to define protocols to allow the clients to manipulate the hashtable. Let us first look at the protocol for setting a key-value pair.

The Set protocol is very straightforward: we just need to send a Key (string) and a Value (string) to the hashtable server. Here is the protocol specification:

structSetMessage{stringKey;stringValue;}protocolSet{Type:Syn;Request:SetMessage;Response:void;}

The implementation logic of Set operation is also straightforward:

publicoverridevoidSetHandler(SetMessageReaderrequest){longcellId=HashHelper.HashString2Int64(request.Key);using(varcell=Global.LocalStorage.UseBucketCell(cellId,CellAccessOptions.CreateNewOnCellNotFound)){intcount=cell.KVList.Count;intindex=-1;for(inti=0;i<count;i++){if(cell.KVList[i].Key==request.Key){index=i;break;}}if(index!=-1){cell.KVList[index].Value=request.Value;}elsecell.KVList.Add(newKVPair(request.Key,request.Value));}}

In the cell bucket, we search the key against the key-value pair list. If we find a match, we update the value; otherwise, we add a new value.

Getting A Key-Value Pair

Get operation is even simpler. It fetches the value by the user-specified key. This is the protocol specification:

structGetMessage{stringKey;}structGetResponse{boolIsFound;stringValue;}protocolGet{Type:Syn;Request:GetMessage;Response:GetResponse;}

This is the implementation logic:

publicoverridevoidGetHandler(GetMessageReaderrequest,GetResponseWriterresponse){longcellId=HashHelper.HashString2Int64(request.Key);response.IsFound=false;using(varcell=Global.LocalStorage.UseBucketCell(cellId,CellAccessOptions.ReturnNullOnCellNotFound)){if(cell==null)return;intcount=cell.KVList.Count;for(inti=0;i<count;i++){if(cell.KVList[i].Key==request.Key){response.IsFound=true;response.Value=cell.KVList[i].Value;break;}}}}

If we do not find a matched bucket, we return immediately. Otherwise, we search the key against the key-value pair list in the matched bucket cell.