fingers.cc

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

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

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include "math_util.h"
#include "error.h"
#include "server.h"
#include "lb.h"

vector<double> deadVServersCountVector;
vector<double> gracefulVServersCountVector;
vector<double> timeToExpirationVector;

int setDeadStat = 0;
int isNullStat = 0;
int setInvalidateStat = 0;
int fingerHBCountStat = 0;
int fixCauseVSnull = 0, fixCauseHBexpired = 0;

int fingerCount = 0;//每个虚拟节点的fingers 的大小

int fingerStabilizeInterval = 30;//平均每隔30s 进行finger 修复

//int minFingerStabilizeInterval = 5;
//int maxFingerStabilizeInterval = 120;

int minFingerStabilizeInterval = 30;
int maxFingerStabilizeInterval = 30;

double maxNullFrac = .02;
double minNullFrac = .005;

double* step = NULL;
const int PREDECESSOR_INDEX = -10;//???

int setFingerAttemptStat = 0;//finger 的尝试修复计数
int setFingerSuccessStat = 0;//成功设置finger 的计数

int findFingerFixCall = 0;
int findFingerCall = 0;
int findFingerFallbackSuccessor = 0;

vector<double> fingersPerCall;//每次修复时，发送的维护消息

// step 0 should be 0;
void initStep (int vsEstimateCount) {
//ceil  求不小于参数的最小整数，返回float型
  fingerCount = (int)(ceil(log2 (vsEstimateCount)));//
  if (fingerCount < 1) fingerCount = 1;//

  //
  double stepAmt = 0.5 / pow (2., (double)fingerCount-1);//?????
  fingerCount++;

  step = new double [fingerCount];
  step[0] = 0.;
  
  for (int i = 1; i < fingerCount; i++) {
    step[i] = stepAmt;
    stepAmt *= 2.;    
  }  
}

Fingers::Fingers () {
  ASSERT (fingerCount > 0);
  finger = new Finger[fingerCount];
}

Fingers::~Fingers () {
  delete [] finger;
}

//修复fingers
//Returns the number of fingers fixed (for maint messages incurred)
int Fingers::fixFingers (double myKey) {
  return fixFingers (myKey, true);
}



// 若fixAllFingers 参数为false，仅仅修复后继节点，即finger[0]

int Fingers::fixFingers (double myKey, bool fixAllFingers) {
  int fixedFingerCount = 0;//已经修复的finger 数量

  //取得相应的虚拟节点
  DEBUG_P (("VS %f fixing fingers\n", myKey));
  map<double,VirtualServer*>::iterator us = vServers.find (myKey);
  VirtualServer *ourVs = us->second;//欲修复的虚拟节点
  ASSERT (ourVs->rootPs->isAlive());

  //找到该虚拟节点的后继
  VirtualServer *succVs = findDst (myKey);
  if (succVs->getKey() != finger[0].getKey()) {
    finger[0].setFinger (succVs->getKey());//finger[0] 的设定，从vservers 查找的
    fixedFingerCount++;
  }
  //若参数为false，则仅仅修复后继
  if (!fixAllFingers) return fixedFingerCount;

  //修复剩下的各个finger
  for (int i = 1; i < fingerCount; i++) {
    ASSERT (finger[i].getLastHeartbeat() >= 0);
     //从当前调整的虚拟节点集合中，若查到则说明
     //该finger 指向的虚拟节点无效了
    if (gracefulRelocateVServers.find(finger[i].getKey()) != gracefulRelocateVServers.end()) {
      DEBUG_P (("R %d VS %f finger %d step %f invalidating %f\n",
		cRound, myKey, i, step[i], finger[i].getKey()));
      setInvalidateStat++;
      finger[i].invalidate ();
    }

    //该finger 是无效的填充或者下次探测时间过期
    if ( (!finger[i].isValid()) || finger[i].getLastHeartbeat() < cRound) {
      if (finger[i].getLastHeartbeat() < cRound) {//该finger的下次探测过期
        int diff = cRound - finger[i].getLastHeartbeat();
        timeToExpirationVector.push_back ((double)diff);
        fixCauseHBexpired++;
      } 
	else {
        fixCauseVSnull++;
      }

      //生成欲修复的finger  的key
      double fingerKey = myKey + step[i];
      if (fingerKey > 1.) fingerKey -= 1.;//

	//找到finger  key 的后继虚拟节点
      VirtualServer *dstVs = findDst (fingerKey);
      ASSERT (dstVs->rootPs->isAlive());

      setFingerAttemptStat++;//finger 的尝试修复计数
      if (dstVs->sendMsg (ourVs, false)) {//向该虚拟节点发送维护消息
        finger[i].setFinger (dstVs->getKey());//修复填充该finger
        setFingerSuccessStat++; //成功填充finger 的计数
      }
      fixedFingerCount++; //修复计数

      DEBUG_P (("R %d VS %f set finger-%d for %f is %f\n", 
		cRound, myKey, i, fingerKey,
		finger[i].getKey()));
    }

  }
  fingersPerCall.push_back ((double)fixedFingerCount);//

  return fixedFingerCount;
}

//清空所有的finger
void Fingers::invalidate () {
  for (int i = 0; i < fingerCount; i++) {
    finger[i].invalidate ();
  }
}

// 
//Note that this may return the key of a VS that doesn't exist (anymore)
double Fingers::findFinger (double myKey, double dstKey, int &fingerIndex,
                            double dstVsKeyCache) {
  findFingerCall++;

  if (!finger[0].isValid() ||
      !finger[0].isAlive()) {
    findFingerFixCall++;
    fixFingers (myKey,false);
  }

  if (dstVsKeyCache == finger[0].getKey()) {
    fingerIndex = 0;
    return dstVsKeyCache;
  }

  // assume pred sends domain on its heartbeats
  if (dstVsKeyCache == findPred (myKey)->getKey()) {
    fingerIndex = PREDECESSOR_INDEX;
    return dstVsKeyCache;
  }

  double hopDistance = keyDistance (myKey, dstKey);
  ASSERT (hopDistance > 0. && hopDistance < 1.);
  for (fingerIndex = fingerCount-1; fingerIndex >= 0; fingerIndex--) {
    if (finger[fingerIndex].isValid()) {
      double fingerDistance = keyDistance (myKey, finger[fingerIndex].getKey());
      if (hopDistance > fingerDistance) {
        return finger[fingerIndex].getKey();
      }
    }
  }

  findFingerFallbackSuccessor++;
  fingerIndex = 0;
  return finger[0].getKey();
}

void Fingers::heartbeat (int fingerIndex) {
  ASSERT (fingerIndex >= 0 && fingerIndex < fingerCount || fingerIndex == PREDECESSOR_INDEX);
  if (fingerIndex != PREDECESSOR_INDEX) 
    finger[fingerIndex].heartbeat();
}

//finger 的初始化
Finger::Finger () {
  key = -1.;
  lastHeartbeat = 0;
}

Finger::~Finger () {
}

//清空该finger
void Finger::invalidate () {
  key = -1.;
  lastHeartbeat = 0;
}

//填充该finger
void Finger::setFinger (double thisKey) {
  key = thisKey;
  lastHeartbeat = cRound + poisson (fingerStabilizeInterval);
}

int nextPoissonCount = 0, nextPoissonTotal = 0;

//探测该finger 的虚拟节点
//安排下次探测的时间
void Finger::heartbeat () {
  if (lastHeartbeat <= 0) 
  	lastHeartbeat = 0;
  fingerHBCountStat++;
  
  //下次探测的时间安排
  int nextPoisson = poisson (fingerStabilizeInterval);
  nextPoissonTotal += nextPoisson;
  nextPoissonCount++;
  int nextHB = cRound + nextPoisson;
  lastHeartbeat = nextHB;
}

//该finger 是否填充了
bool Finger::isValid () {
  if (key >= 0. && key < 1.) return true;
  return false;
}

//该虚拟节点是否存在
bool Finger::isAlive () {
  map<double,VirtualServer*>::iterator us = vServers.find (key);
  if (us == vServers.end()) return false;
  return true;
}

void printFingerStats (FILE *fp) {

  bool fingerStdout = false;

  double m = mean (fingersPerCall);
  double s = stddev (fingersPerCall,m);

  double dm = mean (deadVServersCountVector);
  double ds = stddev (deadVServersCountVector,dm);

  double gm = 0.;
  double gs = 0.;

  if (gracefulVServersCountVector.size() > 0) {
    gm = mean (gracefulVServersCountVector);
    gs = stddev (gracefulVServersCountVector,dm);
  }

  double exm = 0, exs = 0;
 
  if (timeToExpirationVector.size() > 0) {
    exm = mean (timeToExpirationVector);
    exs = stddev (timeToExpirationVector, exm);
  }

  fingersPerCall.clear();
  deadVServersCountVector.clear();    
  gracefulVServersCountVector.clear();    
  timeToExpirationVector.clear();

  fprintf (fp,"R %d Fix fingers per call %f (%f) cause: null %d expired %d, timeToExpire %f (%f) Dead VServers: %f (%f)\n",
	   cRound, m, s, fixCauseVSnull,fixCauseHBexpired,
           exm, exs, dm, ds);
  if (fingerStdout) {
    printf ("R %d Fix fingers per call %f (%f) cause: null %d expired %d, timeToExpire %f (%f) Dead VServers: %f (%f)\n",
            cRound, m, s, fixCauseVSnull,fixCauseHBexpired,
            exm, exs, dm, ds);
  }

  int totalFingerCount = 0;
  int nullCount = 0;
  int deadCount = 0;
  int fingerOKCount = 0;

  for (map<double,VirtualServer*>::iterator vsIter = vServers.begin ();
       vsIter != vServers.end(); vsIter++) {
    VirtualServer *vs = vsIter->second;
    Fingers *fingers = vs->fingers;
    
    for (int i = 0; i < fingerCount; i++) {
      totalFingerCount++;
      if (!(fingers->finger[i].isValid())) {
        nullCount++;
      }
      if (!fingers->finger[i].isAlive()) {
        deadCount++;
      }
      if (fingers->finger[i].isAlive())
        fingerOKCount++;
    }
  }


  double nullFrac = nullCount/(double)totalFingerCount;
  double deadFrac = deadCount/(double)totalFingerCount;
  double okFrac = fingerOKCount/(double)totalFingerCount;

  // Real-time adjustment of finger stabilization
  // Would have to assume that nodes are passing around this kind of information
  if (deadFrac > maxNullFrac) {
    fingerStabilizeInterval--;
    if (fingerStabilizeInterval < minFingerStabilizeInterval)
      fingerStabilizeInterval = minFingerStabilizeInterval;
  } else if (deadFrac < minNullFrac) {
    fingerStabilizeInterval++;
    if (fingerStabilizeInterval > maxFingerStabilizeInterval)
      fingerStabilizeInterval = maxFingerStabilizeInterval;
  }

  double setFingerOKPct = 0;
  if (setFingerAttemptStat > 0) {
    setFingerOKPct = setFingerSuccessStat/(double)setFingerAttemptStat;
  }
  setFingerSuccessStat = 0;
  setFingerAttemptStat = 0;
  double succFallbackPct = 0.;
  if (findFingerCall > 0) {
    succFallbackPct = findFingerFallbackSuccessor/(double)findFingerCall;
    findFingerFallbackSuccessor = 0;
    findFingerCall = 0;
  }

  fprintf (fp,"R %d FingerState: null %f dead %f OK %f interval %d setOK %f total %d, setDead %d setInvalid %d isNull %d HBCount %d succ-fallback %f\n",
           cRound, nullFrac, deadFrac, okFrac, fingerStabilizeInterval, setFingerOKPct, totalFingerCount, 
           setDeadStat, setInvalidateStat, isNullStat, fingerHBCountStat, succFallbackPct);

  if (fingerStdout) {
    printf ("R %d FingerState: null %f dead %f OK %f interval %d setOK %f total %d, setDead %d setInvalid %d isNull %d HBCount %d\n",
	    cRound, nullFrac, deadFrac, okFrac, fingerStabilizeInterval, setFingerOKPct, totalFingerCount, 
	    setDeadStat, setInvalidateStat, isNullStat, fingerHBCountStat);
  }
  setDeadStat = 0;
  setInvalidateStat = 0;
  isNullStat = 0;
  fingerHBCountStat = 0;


}