analysis Load balancing algorithm
This project is maintained by wangfakang
nginx load balancing algorithm 的分析：
round_robin是nginx默认采用的后端peer选择的算法（在ngx_http_upstream_init_main_conf
函数中有一个函数指针peer.init_upstream若在nginx的配置文件中upstream未指定相应的算
法则设置为init_round_robin函数），然后函数init_round_robin会做一些初始化后端peer的
工作以及设置peer.init指向init_round_robin_peer函数。当每一个请求来的时候调用
ngx_http_upstream_init_request的时候就会调用init_round_robin_peer函数（主要作用是
设置peer.get peer.free函数以及开辟round_robin数据结构空间进行相应的赋值）其中get
主要是根据其算法选择后端一个server、然后进行测试后端是否可以连接、不可以则选择下一个。
其会有三个值：weight、curent_weight、effective_weight、total_weight，其中
effective_weight等于weight，curent_weight初始化0。total_weight的值是每一次
选择的过程中是各个effective_weight的总和，每一次轮训玩后置为0。每次curent_weight
的值是加上effective_weight的值。每次都是选择current_weight值最大的一个，
每次选中过后都会把curent_weight的值减去total_weight的值（间接降低权值），若
选择到的peer在进行测试连接失败的话则会把当前的effective_weight -= weight/max_fails .
当服务恢复正常的时候并且effective_weight小于weight的时候又会让effective_weight的值加1.
从而达到负载均衡的选择server。
Ip_hash 在调用init_ip_hash的时候其内部也在调用init_round_robin_peer（初始化后端peer）原因
是ip_hash的数据结构中也有一个peers结构体最后其实就是使用init_round_robin中的那个、然后设
置peer.init=init_ip_hash_peer，当每一个请求来的时候调用ngx_http_upstream_init_request的
时候就会调用init_ip_hash_peer函数（主要作用是设置peer.get peer.free函数以及开辟iphp数
据结构空间进行相应的赋值,并且设置iphp中的Get_rr_peer函数指针为get_round_robin_peer函数）
根据ip的类型设置iphp数据结构中的addr以及addrlen（IPV4中设置addr为ip的前面三个字节）。
选取规则：
首先判断根据ip_hash方法进行选取的失败次数是否超过20次或是后端只有一个peer的时候就调用
开始设置的 get_rr_peer（round_robin算法），否则的话就根据ip前3个字段进行hash，其函数是：
Hash = (hash*113 + iphp->addr[i])%6271
最后得到hash值得时候在去判断 weighted（weighted = （w != n））的值是不是0，当weighted的值是0的
时候表示weight的值是1 即虚拟节点数等于ip数，直接hash%peers->number就ok了，否则选择最先则使得
为0的那个如下：
for(I = 0 ; i<peers->numbers;i++ ) {
w -= peers->peer[i].weight;
if w < 0 break;
最后就选择peer[i] 然后进行测试连接是否可以连接。
一致性hash算法主要思想就是把后端peer全部映射到一个环上，然后当有一个请求到达的时候也根据其
请求的ip或是url或是其请求参数使用同样的hash函数去找，其中查找的算法使用的是二分法查找，比如
有A、B、C三个server形成一个环当来一个request的时候其hash到了A与B之间其就映射到B上去，当然有
一个问题就是当A与B很近的时候C就占了很大的空间于是一致性hash就引入了虚拟节点的说法，其nginx内
部的虚拟节点就是根据其weight值做的（weight的值乘以160）。假如A的weight的值是2则在这个环上就
根据hash值得大小排序成320个节点从而达到更均衡。其实nginx内部的具体做法不是这么简单的：使用
了一个叫做chash_peer_data_t 的结构体uchpd，其中有一个servers就是存放了所有的后端peer其中的顺
序是根据hash值进行从小到大排序的（内部是包括虚拟节点的，其排序算法使用的插入排序法，由于插入排
序是一个稳定的排序算法），然后还有一个real_node是一个三级指针，其中存放的是每一个真实server
所对应的虚拟peer（实际是存放的servers中的）其主要作用就是快速hash更新某一个server的状态值（
如当servers中有一个server down了 就要标志所有的server的相关虚拟节点的值也是down 但是servers
中的server顺序是hash值排序的，但是知道真实server的index所以借助这个index直接定位到real_node
中直接全部更新），然后根据client的hash值选择一个server（二分法查找）,当查找到的节点正好是down
的是时候就会把这个节点放入一个队列当中，然后在把这个节点从segment树中删除，然后借助segment树
进行去检查找一个最接近hash值得节点，然后接着进行后续处理然后下一个节点来的时候先判断这个队列
中的server是否已经恢复了若恢复了则把其节点从队列中删除，插入segment树中共后续查找。
首先hash（ip_hash、consistent_hash）与round_robin的直接区别就是:前面两种算法定位后端server
的时候与来的请求很相关，同一个client多次请求会让一台后端server处理（若次server不异常的话），
而round_robin算法则同一client的不同请求时间定位到后端的server也不同是与请求无关的（若是作
为缓存或是session机制的话就选择hash）。后面说说ip_hash与consisten_hash的比较：ip_hash（配置文件中的down特定，backup对其无效）采用的hash算法没有consistent_hash算法灵活（ip_hash一般只是根据client的请求ip，而chash可以根据client的ip、url、以及请求参数进行hash，consistent_hash会
定期的检查之前down掉的机器，若是其server正常了则恢复到环中更新down标志）
在使用中有任何问题，欢迎反馈给我，可以用以下联系方式跟我交流