浅谈负载均衡

ips: [
  "192.168.0.1",
  "192.168.0.2",
  "192.168.0.3",
  "192.168.0.4",
],

const resMap = {};
//执行100次
for (let i = 0; i < 100; i++) {
  const ip = getServer();
  console.log(ip);
  if (!resMap[ip]) {
    resMap[ip] = 1;
  } else {
    resMap[ip]++
  }
}
console.log(resMap);

function getServer() {
  return ips[Math.floor(Math.random() * (ips.length))];
}

weightMap: {
  "192.168.0.1": 1,
  "192.168.0.2": 1,
  "192.168.0.3": 3,
  "192.168.0.4": 5,
}

function getServerWithWeight() {
  const newIps = [];
  for (const k in weightMap) {
    const weight = weightMap[k];
    for (let i = 0; i < weight; i++) {
      newIps.push(k);
    }
  }
  return newIps[Math.floor(Math.random() * (newIps.length))];
}

function getServerWithWeight2() {
  const totalWeight = Object.values(weightMap).reduce((p, c) => p + c);
  //在 0-totalWeight 范围内取随机数
  let index = Math.floor(Math.random() * (totalWeight));
  for (const ip in weightMap) {
    const weight = weightMap[ip];
    if (index < weight) {
      return ip;
    }
    index -= weight;
  }

  return ips[index];
}

//模拟简单轮询，不考虑并发
let index = 0;
function getServer() {
  if (index >= ips.length) {
    index = 0;
  }
  let ip = ips[index];
  index++;
  return ip;
}

//模拟调用编号
let sequenceNum = 0;
function getSequence() {
  return ++sequenceNum;
}

function getServerWithRobin() {
  const currentSequence = getSequence()
  const totalWeight = Object.values(weightMap).reduce((p, c) => p + c);
  let pos = currentSequence % totalWeight;
  if (pos === 0) {
    pos = totalWeight;
  }
  for (const ip in weightMap) {
    const weight = weightMap[ip];
    if (pos <= weight) {
      return ip;
    }
    pos -= weight;
  }
}

const totalWeight = Object.values(weightMap).reduce((p, c) => p + c);
//把currentWeight数组初始赋值为weight
let currentWeight = ips.map(v => weightMap[v] ? weightMap[v] : 0);

function getServerWithRobin2() {
  //找currentWeight中的最大值所对应的服务器
  const MaxPos = currentWeight.indexOf(Math.max(...currentWeight));
  const ip = ips[MaxPos];
  //currentWeight中的最大值减去总权重
  currentWeight[MaxPos] -= totalWeight;
  //所有的ip的currentWeight统一加上原始权重
  currentWeight = currentWeight.map((v, i) => v + weightMap[ips[i]]);

  return ip;
}

const VIRTUAL_NODE_NUM = 160;
const VIRTUAL_NODES = new Map();
// 对每个真实节点添加虚拟节点，虚拟节点会根据哈希算法进行散列
for (const ip of ips) {
  for (let i = 0; i < VIRTUAL_NODE_NUM; i++) {
    const hash = getHash(`${ip}VN${i}`);
    VIRTUAL_NODES.set(hash, ip);
  }
}

function getServer(client) {
  const hash = getHash(client);
  const arr = Array.from(VIRTUAL_NODES);
  // 得到大于该Hash值的Map，且按key升序
  let subArr = arr.filter(item => item[0] > hash);
  subArr = subArr.sort((a, b) => a[0] - b[0]);
  // 大于该hash值的第一个元素的位置，若不存在，返回第一个虚拟节点
  const nodeIndex = subArr[0] ? subArr[0] : VIRTUAL_NODES[0];
  const subMap = new Map(subArr);
  return subMap.get(nodeIndex[0]);
}

/**
 * 改进的32位FNV算法1
 * @param {String} str 字符串
 * @returns {Number}
 */
function getHash(str) {
  const p = 16777619
  let hash = Number("2166136261L");
  for (let i = 0; i < str.length; i++) {
    hash = (hash ^ str.charAt(i)) * p;
  }
  hash += hash << 13;
  hash ^= hash >> 7;
  hash += hash << 3;
  hash ^= hash >> 17;
  hash += hash << 5;
  return hash < 0 ? Math.abs(hash) : hash;
}

//模拟当前服务器的活跃数
const ACTIVICY_LIST = {
  "192.168.0.1": 5,
  "192.168.0.2": 4,
  "192.168.0.3": 3,
  "192.168.0.4": 3
};

function getServer() {
  //获取最小活跃数
  const minActivityIps = [];
  const minValue = Math.min(...Object.values(ACTIVICY_LIST));
  for (const ip of Object.keys(ACTIVICY_LIST)) {
    if (ACTIVICY_LIST[ip] === minValue) {
      minActivityIps.push(ip);
    }
  }
  // 最小活跃数的ip有多个，则根据权重来选，权重大的优先
  if (minActivityIps.length > 1) {
    // 过滤出对应的ip和权重
    const weightList = [];
    for (const ip in weightMap) {
      if (minActivityIps.includes(ip)) {
        weightList.push(weightMap[ip]);
      }
    }
    const totalWeight = weightList.reduce((p, c) => p + c);
    //在 0-totalWeight 范围内取随机数
    let index = Math.floor(Math.random() * (totalWeight));
    for (const ip of minActivityIps) {
      const weight = weightMap[ip];
      if (index < weight) {
        return ip;
      }
      index -= weight;
    }
  } else {
    return minActivityIps[0];
  }
}