lb.cc

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

/* $Id: lb.cc,v 1.62 2005/08/02 19:45:32 jonathan Exp $
 * Jonathan Ledlie, Harvard University.
 * Copyright 2005.  All rights reserved.
 */

#include "lb.h"
#include "object.h"
extern map<double,Object*>mObject;
const int M=4;
int ObjectSuccessCount=0;
int ObjectFailCount=0;
int totalcount=0;
const int GOBACK=4;
double testKey;
char *usage = \
"Usage: lb, Distributions\n" \
"            -l physical server lifetime and deathtime file\n" \
"            -H average physical server lifetime\n" \
"            -c physical server capacity file (requests/round/server)\n" \
"            -C average physical server capacity\n" \
"            -w queries per round per alive node\n" \
"            -k routing key distribution\n" \
"\n" \
"           Other parameters\n"
"            -i number of ID choices when joining (default is 1, i.e., off).  Zero is opt\n" \

//各种负载均衡的方案
"            -a [t|p|k] active load balancing method\n" \

"             t: virtual server transfer:\n" \
"               (1) If overloaded and have exactly one virtual server,\n" \
"                   split virtual server into two.\n" \
"               (2) If overloaded and have more than one virtual server,\n" \
"                   attempt to transfer a virtual servers.\n" \
"               Never delete or merge virtual servers.\n" \

"             p: pure virtual servers:\n" \
"               If overloaded this round and have more than one virtual server,\n" \
"               choose the least loaded virtual server that will make us unloaded\n" \
"               and delete it.\n" \
"               If underloaded and adding an average virtual server workload\n" \
"               will not put us over capacity,\n" \
"               create a virtual server\n" \

"             k: continue to use k-choices by actively rechoosing ids\n" \
"              based on perceived workload\n" \


"             g: use Ganesan's Threshold algorithm\n" \

"            -U upper slack pct above which we are overloaded (default .90) \n" \
"            -L lower slack pct below which we are underloaded (default .10)\n" \

"            -s random seed\n" \
"            -e epsilon difference between k-choice keys to make shift\n" \

"            -o oracle mode\n" \
"               - node VSs match object distribution\n" \
"               - all nodes are up at continuously\n" \
"            -d debug\n" \
"            -f frequency of runtime summary output (once every 1000 rounds is default)\n" \
"            -v initial virtual servers per node (1 is default)\n" \
"            -S shift workload to new distribution halfway through run\n" \
"            -O output file prefix\n" \
"            -p k-choices active dampening method\n" \
"               1: limit ids\n" \
"               2: limit create and delete\n" \
"               3: limit both\n" \
"            -m kchoices (active) min capacity, below which rechoosing is dampened\n" \
"\n" \
"Distributions:\n" \
" Pareto       P/scale/shape\n" \
" Normal       N/mean/stddev\n" \
" Zipf         Z/alpha/num-elements\n" \
" Poisson      F/mean\n" \
" Uniform      U [0..1)\n" \
" Constant     C/value\n";

void printUsage () {
  printf ("%s", usage);
  exit (-1);
}

void printUsage (char* problem) {
  printf ("%s\n", problem);
  printUsage ();
}

const int object_round=30;//产生object的
const int num_block=4;//数据分块数
const int num_create=10;//每次产生的object数目

int main (int argc, char **argv) {

  char *churnFile = NULL, *capacityFile = NULL,
    *keyDistStr = NULL, *outputPrefix = NULL;//输入参数
  
  Distribution *keyDist;//产生查询目标key 的分布
  DistributionFactory *distFactory = NULL;
  
  maxVsPerNode = 128;//每个节点的最大虚拟节点数量
  idChoice = 1; //虚拟节点加入时，可供选择的id  集合大小
                      //缺省值为1，由-i 参数指定
  char activeLBmethod = '-';
  char c = 0;
  int seed = getpid();

  //slack
  lowerSlack = 0.01;//利用率的下限
  upperSlack = 0.99;//上限

 #ifdef DEBUG
  debug = false;
 #endif
 
  oracle = false;//

  int initialVsPerNode = 1;//
  int summaryFrequency = 1000;
  double queriesPerRound = -1.;//

  bool workloadShift = false;//是否需要work shift
  
  bool finished = false;//标记是否事件仿真完成
  
  FILE *runLogFP, *linksFP, *summaryFP, *nodeFP;
  
  int lifetimeAverage = -1, capacityAverage = -1;;
  int dampeningStrategy = 0;

  distFactory = new DistributionFactory ();


  
  while ( (c = getopt(argc,argv,"l:H:C:c:w:k:i:a:s:dU:L:ov:f:SO:e:p:m:")) >= 0) {
    switch (c) {//命令参数的解析
    case 'l':
      churnFile = optarg;//physical server lifetime and deathtime file
      break;
    case 'c':
      capacityFile = optarg;//physical server capacity file (requests/round/server)
      break;
    case 'w':
      queriesPerRound = atof (optarg);//queries per round per alive node
      break;
    case 'k':
      keyDistStr = optarg;//routing key distribution
      break;
    case 'i':
      idChoice = atoi (optarg);//number of ID choices when joining (default is 1, i.e., off).  Zero is opt\n
      break;

    case 'p':
      dampeningStrategy = atoi (optarg);//
      /*p方案:
      完全虚拟节点
      若本轮中某个物理节点过载，并且具有多个虚拟节点
         选择删除能降载的最轻载的虚拟节点
      若轻载且添加平均虚拟节点负载的节点而不过载，
      则创建一个虚拟节点
      If overloaded this round and have more than one virtual server,
          choose the least loaded virtual server that will make us unloaded and delete it.
      If underloaded and adding an average virtual server workload will not put us over capacity,
          create a virtual server*/
      break;
    case 'H':
      lifetimeAverage = atoi (optarg);//average physical server lifetime
      break;
    case 'C':
      capacityAverage = atoi (optarg);//average physical server capacity
      break;
    case 'a':
      activeLBmethod = *optarg;//active load balancing method
      break;
    case 'o':
      oracle = true;//oracle mode
      break;
    case 's': //random seed
      seed = atoi (optarg);
      break;
    case 'U':
      upperSlack = atof (optarg);//upper slack pct above which we are overloaded (default .90) 
      break;
    case 'L':
      lowerSlack = atof (optarg);//lower slack pct below which we are underloaded (default .10)
      break;
    case 'v'://指定每个物理节点的虚拟节点数
      initialVsPerNode = atoi (optarg);
      break;
    case 'f':
      summaryFrequency = atoi (optarg);//frequency of runtime summary output (once every 1000 rounds is default
      break;
    case 'e':
      epsilonImprovement = atof (optarg);
      break;
    case 'm':
      kchoicesActiveMinCapacity = atof (optarg);
      break;
    case 'd':
#ifdef DEBUG
      debug = true;
      break;
#endif
    case 'S':
      workloadShift = true;//work load shift
      break;
    case 'O':
      outputPrefix = optarg;//输出文件的名前缀
      break;
    default:
      printUsage ();
      break;
    }
  }

  SRand (seed);

  //non-zero need in k-choice
  switch (dampeningStrategy) {//抑制策略
  case 0://default value in others 
    break;
  case 1:
    dampeningLimitIds = true;
    break;
  case 2:
    dampeningLimitCrDel = true;
    break;
  case 3:
    dampeningLimitCrDel = true;
    dampeningLimitIds = true;
    break;
  default:
    printUsage ("Problem with dampening strategy");
    break;
  }

  //参数检查是否符合要求
  if (lifetimeAverage <= 0)
    printUsage ("Average lifetime must be greater than 0");
  if (capacityAverage <= 0)
    printUsage ("Average capacity must be greater than 0");
  
  if (upperSlack > 1. || upperSlack < 0)
    printUsage("Upper slack must be between 0 and 1");
  if (lowerSlack > upperSlack || lowerSlack > 1. || lowerSlack < 0)
    printUsage("Lower slack must be between 0 and 1 and less than or equal to upper slack");

  //各种均衡的方案
  if (activeLBmethod != '-' && activeLBmethod != 't' &&
      activeLBmethod != 'k' && activeLBmethod != 'p' &&
      activeLBmethod != 'g')
    printUsage("Unknown active LB method.");
  if (activeLBmethod == 'g' && initialVsPerNode != 1) {//在该方案下，
                                                                    //虚拟节点数量只能为1
    printUsage ("Ganesan only allows one initialVsPerNode\n");
  }
  
  if (idChoice < 0)
    printUsage("Number of IDs must be greater than zero.");
  if (churnFile == NULL)
    printUsage("Error in churn file name");
  if (capacityFile == NULL)
    printUsage("Error in capacity distribution");
  if (keyDistStr == NULL)
    printUsage("Error in key distribution");
  if (initialVsPerNode < 0)
    printUsage("v must be greater or equal to 0 (0 makes log N virtual servers)");
  if (summaryFrequency <= 0)
    printUsage("f must be greater than 0");
  if (queriesPerRound < 0.)
    printUsage("Workload rate must be greater than or equal to 0.");
  if (outputPrefix == NULL)
    printUsage("Output file prefix is required.");



  /*
   * INITIALIZE SYSTEM 系统各个参数的初始化
   */

  systemTargetCapacity = 0.;
  currentTargetCapacity = 0.;
  recordingStats = false;//

  vector<double>capacity;
  PhysicalServer *ps;//物理节点的集合
  // create PS, set capacities, and create route tables
  //物理节点能力初始化from capacity file
  psCount = initNodes (capacityFile, ps, initialVsPerNode);

  Statistics *sumStats = new Statistics ();
  Statistics *interimStats = new Statistics ();

  keyDist = distFactory->newDistribution (keyDistStr);//目标key 的分布初始化
  if (keyDist == NULL)
    printUsage ("Problem with key distribution");

  cRound = 0;//当前轮数
  psUp = 0;//当前存在的物理节点数量

  Object *object;//数据块指针

   //oracle mode
	  if (oracle) {
		    psCount /= 2;
		    if (keyDist->getName() == 'z') {
		      oracleAllocateVsZipf (keyDist,ps);
		    } else if (keyDist->getName() == 'u') {
		      oracleAllocateVsUniform (keyDist,ps);
		    } else {
		      printUsage("Oracle only handles Zipf and Uniform key distributions.");
		    }
		    for (int i = 0; i < psCount; i++) {
		      ps[i].birth (0);//
		    }
		    psUp = psCount;
	   }

  //若是g 方案
  if (activeLBmethod == 'g') {
    usingThreshold = true;
    thresholdSampleSize = (int)(rint(log2(psCount/2)));
  }

  runLogFP = openOutputFile (outputPrefix, ".run");//创建日志文件
  traceFP = openOutputFile (outputPrefix, ".trace");//创建trace 文件
  
  fprintf (runLogFP,"Earliest LB Round: %d\n", earliestLBround);
  openChurnFile (churnFile);//打开churnFP 文件
  
   while (!finished) {
		    DEBUG_P (("ROUND %d\n", cRound));
		    /*
		     * PER ROUND BIRTH AND DEATH
		     */
		    // deaths should occur before births to prevent race condition
		    char action;
		    int nodeId;

			//依次完成对每轮各种事件的处理
		    while (!finished && ((action = nextEvent (nodeId)) != ' ')) {
				// ' ' 本轮完成进入下一轮
				//未遍历完成&& 下一event 存在
				//对nodeID赋值	
		      int vsAct = 0;//
		      int myInitialVsCount = initialVsPerNode;//
		      int dtime;
		      DEBUG_P (("R %d Action: %c node %d\n", cRound, action, nodeId));

			switch (action) {//下一event的类型
				case 'b'://birth
				ASSERT(!oracle);
				if (activeLBmethod == 'p') {//pure virtual node 初始虚拟数量的确定
				  myInitialVsCount = (int)(ceil (ps[nodeId].getUpperTarget()/10.));
				  if (myInitialVsCount < 1) 
				  	myInitialVsCount = 1;
				  if (myInitialVsCount > maxVsPerNode) 
				  	myInitialVsCount = maxVsPerNode;
				}
				//g 方案的初始虚拟节点只能为1
				//其他的方案由-v 指定或者默认为1
				dtime=ps[nodeId].getDeathtime();
				if((dtime>0)&&(cRound-dtime<=GOBACK))
					vsAct=ps[nodeId].rebirth();
				else
				//printf("Birth:round:%d,id%d\n",cRound,nodeId);
					vsAct = ps[nodeId].birth (myInitialVsCount);
				interimStats->birth (vsAct);
				break;
				
			      case 'd'://dead
				ASSERT(!oracle);
				//printf("Dead:round%d,id%d\n",cRound,nodeId);
				vsAct = ps[nodeId].death ();//
				interimStats->death (vsAct);//物理节点退出时的统计记录