object.cc

这是关于覆盖网的各种负载均衡算法的程序。好好研究

#include "math_util.h"
#include "object.h"

set<double> okeys;//已使用object keys
set<double> bkeys;//已使用block keys

map<double,Object*> mObject;//所有的虚拟节点集合
set<double> mBlock;//块数居
const double range_width=0.04;
const int M=3;
const int N=2;
extern double testKey;

int getRange(double id,double  &start ,double &end)
{
	if(range_width==0)
	{
		start=id;
		end=id;
		return 0;
	}
	int s=int(id/range_width);
	start=s*range_width;
	end=(s+1)*range_width;
	return s;
}


bool updateBlock(map<double,VirtualServer*> vServers,set<double>mBlock)
{
	int num=int(1/range_width);
	int *flag=new int[num];
	memset(flag,0,sizeof(int)*num);
	double start,end;
	int index;
	 for (map<double,VirtualServer*>::iterator p = vServers.begin();p != vServers.end(); p++) 
	 {
		index=getRange(p->second->getKey(),start,end);
		flag[index]=1;
	 }
	 for(set<double>::iterator q = mBlock.begin();q != mBlock.end(); q++)
	 {
	 	index=getRange(*q,start,end);
		if(flag[index]==0)
			mBlock.erase(q);
	 }			
			
}

bool between(double id,double start,double end)
{
	return (id>=start)&&(id<end);
}

//产生一个尚未使用的key (id)
double getRandomUnusedKey (set<double> keys) {
  bool goodId = false;
  double id;
  while (!goodId) {
    goodId = true;
    id = randPct();
    if (keys.find(id) != keys.end())
      goodId = false;
  }
  return id;
}

Object::Object(int n)
{
	okey=getRandomUnusedKey(okeys);
	okeys.insert(okey);
	//testKey=okey;
	bkey=new double[n];
	bnum=n;
	for(int i=0;i<n;i++)
	{
		bkey[i]=getRandomUnusedKey(bkeys);
		bkeys.insert(bkey[i]);
	}
	
}

Object::~Object(){

	delete []bkey;
}

void Object::randselect(double *key)
{
	int j;
	double temp;
	for(int i=0;i<bnum;i++)
		key[i]=i;
	for(int i=1;i<bnum;i++)
		{
			srand(time(NULL));
			j=rand()%i;
			temp=key[j];
			key[j]=key[i];
			key[i]=temp;
		}
}

void Object::putObject()
{

	mObject.insert(pair<double,Object*>(okey,this));
	putBlock();
}

//找到相应的区间，将数据移动到区间内所有的节点
void Object::putBlock()
{
	for(int i=0;i<bnum;i++)
		{
			mBlock.insert(bkey[i]);		
		}
}

//源节点vs 将block 发布到网络
void Object::publish(VirtualServer*  vs,Statistics *interimStats)
{
	vector<double> hops;//记录经过的虚拟节点
	vector<int> fingersUsed;//
	int routeSuccess;
	for(int i=0;i<bnum;i++)
		{

			//插入到对应的VirtualServer
			map<double,VirtualServer*>::iterator p;
			VirtualServer* vp;
			if(range_width==0)
			{
				p= vServers.upper_bound (bkey[i]);
				vp=p->second;
				vp->putBlock(bkey[i]);
			}
			else
			{
				double start,end;
				getRange(bkey[i], start, end);
				for(p=vServers.upper_bound(start);p!=vServers.upper_bound(end);p++)
				{
					vp=p->second;
					vp->putBlock(bkey[i]);
				}
			}
			
			vs->route(bkey[i], hops, fingersUsed, true);
			//记录
		      int hopCount = hops.size()-1;
		      if (hopCount < 0) hopCount = 0;
		      if (routeSuccess) {//路由成功
			DEBUG_P (("R %d query success for key %f in hops %d\n",
				  cRound, bkey[i], hopCount));
			  interimStats->query (true, hopCount);
		        //querySuccessCount++;
		      } else {//路由失败
			DEBUG_P (("R %d query fail for key %f\n",cRound,bkey[i]));
			interimStats->query (false, hopCount);
		      }
		      interimStats->queryMsg (hopCount);

			hops.clear();
			fingersUsed.clear();
		}
}

bool Object::search(VirtualServer* vs,int m,Statistics *interimStats)
{
	double *bbuf=new double[bnum];
	randselect(bbuf);//
	//printf("select\n");
	int succ=0;//成功block数目
	int i=0;
	int result=0;//查询结果

	vector<double> hops;//记录经过的虚拟节点
	vector<int> fingersUsed;//
	double dstKey;
	int routeSuccess;
	while(i<bnum)
		{
		 	int isExist;
			isExist=mBlock.count(bkey[i]);

			//double start,end;
			//getRange(bkey[i], start, end);
			//dstKey=findDst(start)->getKey();
			result=vs->proute(bkey[i], hops, fingersUsed, true);
			
			//等待记录
		      int hopCount = hops.size()-1;
		      if (hopCount < 0) hopCount = 0;
		      if (result) {//路由成功
			DEBUG_P (("R %d query success for key %f in hops %d\n",
				  cRound, dstKey, hopCount));
			  interimStats->query (true, hopCount);
		        //querySuccessCount++;
		      } else {//路由失败
			DEBUG_P (("R %d query fail for key %f\n",cRound,dstKey));
			interimStats->query (false, hopCount);
		      }
		      interimStats->queryMsg (hopCount);
			
			hops.clear();
			fingersUsed.clear();
			//result=1;
			//isExist=1;
			if(result)
				succ++;
			if(succ>=333)
				return true;
			i++;
		}
	return false;
}