server.h

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

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

#ifndef SERVER_H
#define SERVER_H

#include <map>
#include <set>
#include <vector>
#include <deque>
#include <iostream>

const double EWMA_LAMBDA = .1;//统计虚拟节点的历史负载的参数

class PhysicalServer;
class VirtualServer;

class Finger {
 private:
  double key;
  int lastHeartbeat;
  
 public:
  Finger ();
  ~Finger ();
  void setFinger (double key);
  void invalidate ();
  bool isValid ();
  bool isAlive ();
  void heartbeat ();
  double getKey () { return key; }
  int getLastHeartbeat () { return lastHeartbeat; }
};

class Fingers {
 private:
  void invalidate ();
  int fixFingers (double myKey, bool fixAllFingers);

 public:
  Fingers ();
  ~Fingers ();
  int fixFingers (double myKey);
  double findFinger (double myKey, double dstKey, int &fingerIndex,
                     double dstVsKeyCache);
  void heartbeat (int fingerIndex);
  Finger *finger;
};

class OptKeyDesc {
 public:
  double key;
  double succ;
  double pred;
  double predicted_work;
  double cost;  
  double gap;
  OptKeyDesc (double key, double succ, double pred, double predicted_work,
              double cost, double gap);
  ~OptKeyDesc ();
};

class VirtualServer {
 private:
  double key;//virtual server id
  double previousKey;//not used
  VirtualServer *predCache;//not used
  
  int birthTime;
  
  int workCurrent;//该虚拟节点的当前负载值
  double workHistory;//历史负载
 public:
  set<double> mBlock;

  
 public:
  PhysicalServer *rootPs;
  VirtualServer (double k, PhysicalServer *ps);//
  ~VirtualServer ();
  Fingers* fingers;

  bool sendMsg (int senderId, bool isQuery);
  bool sendMsg (VirtualServer *sender, bool isQuery);
  
  bool proute (double dstKey, vector<double> &hops, vector<int> &fingersUsed, bool isQuery);
  bool proute(double dstKey, vector<double> &hops, vector<int> &fingersUsed, bool isQuery, double dstVsKeyCache);

  bool route (double dstKey, vector<double> &hops, vector<int> &fingersUsed, bool isQuery);
  bool route (double dstKey, vector<double> &hops, vector<int> &fingersUsed, bool isQuery, double dstVsKeyCache);

  bool findHopDistance (double dstKey, vector<double> &hops, vector<int> &fingersUsed, double dstVsKeyCache);

  //调整修复该虚拟节点的fingers
  int fixFingers () { return fingers->fixFingers(key); }

 //not used
  double getPreviousKey () { return previousKey; }
  void setPreviousKey (double pKey) { previousKey = pKey; }

  double getKey () {return key;}
  void setKey (double k);


  //root physical node set and get methods
  void setRootPs (PhysicalServer *p) {rootPs = p;}
  PhysicalServer* getRootPs () {return rootPs;}

  //get worklord per round (history work)
  double getWorkPerRound ();
  
  //get current worklord
  int getWorkCurrent () { return workCurrent; }

  //virtual node join time
  int getBirth () { return birthTime; }

  
  void merge (VirtualServer *oldGuy);

  void endOfRound ();

  double getArcLength ();

  void putBlock(double block);
};

extern map<double,VirtualServer*> vServers;

class PhysicalServer {
 private:
  int id;//顺序号
  double capacity;    //节点能力值
  
  int capacityIndex;
  double upperTarget;//负载的下限值
  double lowerTarget;//负载的上限值

  bool alive;//死掉标记  
  int birthTime;//加入时间
  int deathTime;//死掉时间
  set<double> mBlock;
  int work;//物理节点当前轮的负载值

  int rechooseAttempts;
  bool thresholdShift;
  int thresholdLevel;

  set<VirtualServer*> localVs;//该物理节点的所有虚拟节点集合
  
  double util;		//物理节点的当前利用率
  double maxUtil;	//物理节点到目前为止最大利用率

  int nextLBactionTime;
  void setNextLBactionTime ();
  
  vector<double> keys;
  set<double> usedKeys;
  bool haveDeletedVS;
  void printLocalVs ();

  int nodeStatUptime;//节点存在时间
  
  int nodeStatRoundsOverloaded;//过载时间记录
  int nodeStatTotalWork;
  
  int nodeStatVsAct;
  double nodeStatArc;

  //该物理节点的所有的虚拟节点计数
  //删除虚拟节点时计数
  int nodeStatVsCount;

  int nodeStatCreate;
  int nodeStatDelete;

  int nodeStatRechooseCreate;
  int nodeStatRechooseDelete;
  int nodeStatRechooseChangeId;

  int nodeStatSplit;
  int nodeStatTransferAttempt;
  int nodeStatTransferSuccess;

  int nodeStatQueryIn;
  int nodeStatQueryOut;
  int nodeStatMaintIn;
  int nodeStatMaintOut;

 public:
  PhysicalServer ();
  void setNode (int id, double capacity);
  double getCapacity () { return capacity; }
  int getWork () { return work; }
  int getThresholdLevel () { return thresholdLevel; }
  int getId () { return id;}
  ~PhysicalServer ();
  int endOfRound ();
  bool canTakeLBaction ();

  double getRandomKey ();
  vector<double> getSampleKeys ();

  bool sendMsg (int senderId, bool isQuery);
  bool sendMaintMsg (double dstKey);

  int birth (int initialVsPerNode);
  int rebirth();
  int foreverdeath();
  int death ();
  int getDeathtime();
  bool isAlive ();
  void print (FILE *fp);

  bool isOverloaded ();
  bool isUnderloaded ();
  
  int getVsCount ();
  double getPctRoundsOverloaded ();

  void incrMaintMsgOut (int mCount);
  void incrMaintMsgIn (int mCount);
  void incrQueryMsgOut (int mCount);
  void incrQueryMsgIn (int mCount);
  
  bool createVs (int vsCreateCount, double desiredWork, double &predictedWork);
  void deleteVs (int &vsDelta);

  void deleteLocalVs (map<double,VirtualServer*>::iterator p, int &vsDelta);
  int deleteLocalVServers (bool forever);

  bool splitVs ();
  bool transferVs (int &vsDelta);
  void takeVs (VirtualServer *vs, int &vsDelta);

  VirtualServer* getRandomVs ();
  int rechooseVs (int &vsDelta);
  int thresholdVs (int &vsDelta);
  int neighborAdjust (VirtualServer *ourVs);
  bool reorder (VirtualServer *ourVs);

  double chooseKey (vector<double> keyList, double desiredWork, 
		    double &predictedWork, double skipKey, double &cost,
		    double &distanceFromCenter);
  VirtualServer* addVs (double key);
  void removeVs (map<double,VirtualServer*>::iterator p, int &vsDelta);
  void removeLocalVs (VirtualServer *vs);

  double getUpperTarget () { return upperTarget; }
  double getLowerTarget () { return lowerTarget; }
  int getCapacityIndex () { return capacityIndex; }
  double getWorkPerRound ();
  double getExtraCapacity ();
  double getUtil ();
  double getMaxUtil ();
  bool canAddVs (int maxVsPerNode);
  set<VirtualServer*> getLocalVsCopy () { return localVs; }

  double findDepartureCost (double ourKey, double &gap);
  double findScore (double ourKey, double ourDesiredWork,
		double &ourFutureWork, double &distanceFromCenter);
  double findOptCost (double a, double s,
		  double w, double &min_r, double &max_r);
  double findOptKey (double desiredWork, double &predictedWork, double &cost, double &gap);
  double getArcLength ();
};

VirtualServer* findDst (double key);
VirtualServer* findPred (double key);

void initStep (int vsEstimateCount);
int util2thresholdLevel (double util);

extern double systemTargetCapacity;
extern double currentTargetCapacity;
double keyDistance (double a, double b);
extern void mergeVServers ();
extern double lowerSlack;
extern double upperSlack;
extern int cRound;
extern int psUp;
extern int psCount;
extern bool recordingStats;
extern bool shuttingDown;
extern set<double> deadVServers;
extern set<double> gracefulRelocateVServers;
extern const int earliestLBround;
extern bool usingThreshold;
extern int thresholdSampleSize;
extern int idChoice;
extern int maxVsPerNode;
extern void printFingerStats (FILE *fp);
extern void printServerStats (FILE *fp,PhysicalServer *ps);
extern bool oracle;
extern void printUtilHistogram (FILE *fp,PhysicalServer *ps);
extern double epsilonImprovement;
extern vector<double> deadVServersCountVector;
extern vector<double> gracefulVServersCountVector;
extern FILE *traceFP;
extern bool dampeningLimitCrDel;
extern bool dampeningLimitIds;
extern double kchoicesActiveMinCapacity;
extern double findPctRingUnderCapacity (PhysicalServer *ps);
extern void initializePreviousQuerySuccess (deque<bool> &previousQuerySuccess);
extern void addToPreviousQuerySuccess (deque<bool> &previousQuerySuccess,
                                       bool routeSuccess);
extern double avgOfPreviousQuerySuccess (deque<bool> &previousQuerySuccess,
                                         int sizeOfAvg);
#endif