Hi~我是丸子，这篇文章是Tiny系列的第二季，Tiny系列是帮助gopher入门的项目集合
回顾第一季的内容：
概述
反向代理服务器位于用户与目标服务器之间，但是对于用户而言，反向代理服务器就相当于目标服务器，即用户直接访问反向代理服务器就可以获得目标服务器的资源。同时，用户不需要知道目标服务器的地址，也无须在用户端作任何设定。反向代理服务器通常可用来作为Web加速，即使用反向代理作为Web服务器的前置机来降低网络和服务器的负载，提高访问效率。
TinyBalancer 是基于Go语言标准库net/http/httputil扩展的反向代理负载均衡器，它支持以下特性：
- 支持http以及https协议
- 支持七种负载均衡算法，分别是：
round-robin、random、power of 2 random choice、consistent hash、consistent hash with bounded、ip-hash、least-load。 - 支持心跳检测，故障恢复
TinyBalancer 的源代码仅有一千行左右，通过学习 TinyBalancer，开发者可以得到以下收获：
- 深入理解负载均衡算法
- 代码简洁规范
- 单元测试编写技巧
- 用Go语言设计反向代理的技巧
- 工厂设计模式在go语言中的应用
net/http/httputil Demo
Go语言的标准库net/http/httputil拍摄指南为我们提供了实现反向代理的利器，为了帮助大家学习,文中先举一个简单的Demo：
packagemainimport("net/http""net/http/httputil""net/url")typeHTTPProxystruct{proxy*httputil.ReverseProxy}funcNewHTTPProxy(targetstring)(*HTTPProxy,error){u,err:=url.Parse(target)iferr!=nil{returnnil,err}return&HTTPProxy{httputil.NewSingleHostReverseProxy(u)},nil}func(h*HTTPProxy)ServeHTTP(whttp.ResponseWriter,r*http.Request){h.proxy.ServeHTTP(w,r)}funcmain(){proxy,err:=NewHTTPProxy("http:127.0.0.1:8088")iferr!=nil{}http.Handle("/",proxy)http.ListenAndServe(":8081",nil)}在上述代码中，HTTPProxy是一个包含ReverseProxy的结构体，当我们把URL解析成 *url.URL时，则可以调用httputil.NewSingleHostReverseProxy函数为目标URL创建一个反向代理，同时HTTPProxy需要实现 ServeHTTP 方法，这个方法可以将请求转发到实际代理的HTTP服务器中。
现在开始进入主题！！！
TinyBalancer的HTTPProxy
首先，我们先来看一下HTTPProxy的结构，在 HTTPProxy 的结构中，hostMap 表示主机对反向代理的映射，其中的键值表示我们需要反向代理的主机，例如192.168.1.1:8080；lb则表示负载均衡器（后面详细讲解）；alive表示反向代理的主机是否处于健康状态，读写锁是用来保护alive这个map的（因为map并发不安全）。
typeHTTPProxystruct{hostMapmap[string]*httputil.ReverseProxylbbalancer.Balancersync.RWMutex// protect alivealivemap[string]bool}接下来，让我们看一下Balancer的接口，：
typeBalancerinterface{Add(string)Remove(string)Balance(string)(string,error)Inc(string)Done(string)}其中Add、Remove是为负载均衡器添加和删除主机的操作，Balance方法会根据传入的key值（可能是远程访问的IP）挑选一个代理主机来接收请求，Inc、Done则表示对代理主机的连接数进行+1或-1操作。拍摄指南
接着我们看一下 NewHTTPProxy 函数，该函数的入参为代理主机的slice数组和负载均衡算法，该函数会为每个URL进行解析并生成一个反向代理。与此同时在反向代理时，会修改 X-Real-IP 为 客户端访问的IP，修改 X-Proxy 为 Balancer-Reverse-Proxy。
var(XRealIP=http.CanonicalHeaderKey("X-Real-IP")XProxy=http.CanonicalHeaderKey("X-Proxy")XForwardedFor=http.CanonicalHeaderKey("X-Forwarded-For"))var(ReverseProxy="Balancer-Reverse-Proxy")// HTTPProxy refers to a reverse proxy in the balancertypeHTTPProxystruct{hostMapmap[string]*httputil.ReverseProxylbbalancer.Balancersync.RWMutex// protect alivealivemap[string]bool}// NewHTTPProxy create new reverse proxy with url and balancer algorithmfuncNewHTTPProxy(targetHosts[]string,algorithmstring)(*HTTPProxy,error){hosts:=make([]string,0)hostMap:=make(map[string]*httputil.ReverseProxy)alive:=make(map[string]bool)for_,targetHost:=rangetargetHosts{url,err:=url.Parse(targetHost)// 解析urliferr!=nil{returnnil,err}proxy:=httputil.NewSingleHostReverseProxy(url)originDirector:=proxy.Director// 修改请求proxy.Director=func(req*http.Request){originDirector(req)req.Header.Set(XProxy,ReverseProxy)req.Header.Set(XRealIP,GetIP(req))}host:=GetHost(url)// 获取主机名称alive[host]=true// 默认主机存活hostMap[host]=proxyhosts=append(hosts,host)}lb,err:=balancer.Build(algo,hosts)// 根据算法构建负载均衡器iferr!=nil{returnnil,err}return&HTTPProxy{hostMap:hostMap,lb:lb,alive:alive,},nil}// 若客户端IP 为 192.168.1.1 通过代理 192.168.2.5 和 192.168.2.6// X-Forwarded-For的值可能为 [192.168.2.5 ,192.168.2.6]// X-Real-IP的值为 192.168.1.1// GetIP get client IPfuncGetIP(r*http.Request)string{clientIP,_,_:=net.SplitHostPort(r.RemoteAddr)// 试图在 X-Forwarded-For 获取客户端IPiflen(r.Header.Get(XForwardedFor))!=0{xff:=r.Header.Get(XForwardedFor)s:=strings.Index(xff,", ")ifs==-1{s=len(r.Header.Get(XForwardedFor))}clientIP=xff[:s]// 试图在X-Real-IP获取IP}elseiflen(r.Header.Get(XRealIP))!=0{clientIP=r.Header.Get(XRealIP)}returnclientIP}// GetHost get the hostname, looks like IP:PortfuncGetHost(url*url.URL)string{if_,_,err:=net.SplitHostPort(url.Host);err==nil{returnurl.Host}ifurl.Scheme=="http"{returnfmt.Sprintf("%s:%s",url.Host,"80")}elseifurl.Scheme=="https"{returnfmt.Sprintf("%s:%s",url.Host,"443")}returnurl.Host}随后，我们标记每个代理主机的存活初始状态为true，并通过balancer.Build函数把代理主机集生成一个负载均衡器。
HTTPProxy 需要实现 ServeHTTP 方法来进行反向代理，HTTPProxy会使用负载均衡器依据客户端访问的IP将其定向到其中的一台主机中，若出现错误则返回 502 BadGateway。
func(h*HTTPProxy)ServeHTTP(whttp.ResponseWriter,r*http.Request){deferfunc(){iferr:=recover();err!=nil{log.Printf("proxy causes panic :%s",err)w.WriteHeader(http.StatusBadGateway)_,_=w.Write([]byte(err.(error).Error()))}}()host,err:=h.lb.Balance(GetIP(r))// 根据 IP 选择合适的主机iferr!=nil{w.WriteHeader(http.StatusBadGateway)_,_=w.Write([]byte(fmt.Sprintf("balance error: %s",err.Error())))return}h.lb.Inc(host)deferh.lb.Done(host)h.hostMap[host].ServeHTTP(w,r)}TinyBalancer的Balancer
我们在上一节中介绍了Balancer接口，这里使用了工厂模式，通过负载均衡算法名称拍摄指南和代理主机集生成一个负载均衡器，支持七种负载均衡算法，分别是：round-robin、random、power of 2 random choice、consistent hash、consistent hash with bounded、ip-hash、least-load。
var(NoHostError=errors.New("no host")AlgorithmNotSupportedError=errors.New("algorithm not supported"))// Balancer interface is the load balancer for the reverse proxytypeBalancerinterface{Add(string)Remove(string)Balance(string)(string,error)Inc(string)Done(string)}// Factory is the factory that generates Balancer,// and the factory design pattern is used heretypeFactoryfunc([]string)Balancervarfactories=make(map[string]Factory)// Build generates the corresponding Balancer according to the algorithmfuncBuild(algorithmstring,hosts[]string)(Balancer,error){factory,ok:=factories[algorithm]if!ok{returnnil,AlgorithmNotSupportedError}returnfactory(hosts),nil}其中每个负载均衡器都在init函数中注册了工厂：
funcinit(){factories[R2Balancer]=NewRoundRobin}funcNewRoundRobin(hosts[]string)Balancer{...funcinit(){factories[P2CBalancer]=NewP2C}funcNewP2C(hosts[]string)Balancer{...Round-Robin
轮询算法是最经典的负载均衡算法之一，负载均衡器将请求依次分发到后端的每一个主机中，这里hosts表示的需要代理的主机，i可以表示为请求序号，代码：balancer/round_robin.go：
//RoundRobin will select the server in turn from the server to proxytypeRoundRobinstruct{sync.RWMutexiuint64hosts[]string}funcinit(){factories[R2Balancer]=NewRoundRobin// 注册轮询算法}// NewRoundRobin create new RoundRobin balancerfuncNewRoundRobin(hosts[]string)Balancer{return&RoundRobin{i:0,hosts:hosts}}在round-robin算法中负载平衡的算法如下，通过请求序号i % len(hosts)的方式得到代理的主机：
// Balance selects a suitable host accordingfunc(r*RoundRobin)Balance(_string)(string,error){r.RLock()deferr.RUnlock()iflen(r.hosts)==0{return"",NoHostError}host:=r.hosts[r.i%uint64(len(r.hosts))]r.i++returnhost,nil}关于round-robin算法的Add、Remove函数可以阅读代码：balancer/round_robin.go；
Random
随机算法同样也是经典的负载均衡算法，负载均衡器将请求随机分发到后端的目标主机中，拍摄指南这里hosts表示的需要代理的主机，rnd表示随机生成器，代码：balancer/random.go：
funcinit(){factories[RandomBalancer]=NewRandom// 注册随机算法}// Random will randomly select a http server from the servertypeRandomstruct{sync.RWMutexhosts[]stringrnd*rand.Rand}// NewRandom create new Random balancerfuncNewRandom(hosts[]string)Balancer{return&Random{hosts:hosts,rnd:rand.New(rand.NewSource(time.Now().UnixNano()))}}在random算法中，负载平衡的算法如下，通过随机的方式得到代理的主机：
// Balance selects a suitable host accordingfunc(r*Random)Balance(_string)(string,error){r.RLock()deferr.RUnlock()iflen(r.hosts)==0{return"",NoHostError}returnr.hosts[r.rnd.Intn(len(r.hosts))],nil}关于random算法的Add、Remove函数可以阅读代码：balancer/random.go；
IP Hash
在IP哈希算法中，负载均衡器将请求根据IP地址将其定向分发到后端的目标主机中，这里hosts表示的需要代理的主机。代码：balancer/ip_hash.go：
funcinit(){factories[IPHashBalancer]=NewIPHash// 注册IP哈希算法}// IPHash will choose a host based on the clients IP addresstypeIPHashstruct{sync.RWMutexhosts[]string}// NewIPHash create new IPHash balancerfuncNewIPHash(hosts[]string)Balancer{return&IPHash{hosts:hosts}}在IP哈希算法中，负载平衡的算法如下，通过对IP地址进行CRC32哈希计算则会得到一个32bit的值，最后对主机数量进行取模，即CRC32(IP) % len(hosts)，则可得到代理的主机：
// Balance selects a suitable host accordingfunc(r*IPHash)Balance(keystring)(string,error){r.RLock()deferr.RUnlock()iflen(r.hosts)==0{return"",NoHostError}value:=crc32.ChecksumIEEE([]byte(key))%uint32(len(r.hosts))returnr.hosts[value],nil}关于IP哈希算法的Add、Remove函数可以阅读代码balancer/ip_hash.go；
Power of 2 random choice
P2C算法是一种工业中运用较多的负载均衡算法，它的原理很简单，它有两条基本定律：
- 若请求IP为空，P2C均衡器将随机选择两个代理主机节点，最后选择其中负载量较小的节点；
- 若请求IP不为空，P2C均衡器通过对IP地址以及对IP地址加盐进行CRC32哈希计算，则会得到两个32bit的值，将其对主机数量进行取模，即CRC32(IP) % len(hosts) 、CRC32(IP + salt) % len(hosts)，最后选择其中负载量较小的节点；
在P2C算法中，负载平衡的算法balancer/p2c.go拍摄指南如下 ：
funcinit(){factories[P2CBalancer]=NewP2C// 注册P2C算法}typehoststruct{namestring// 主机名loaduint64// 负载量}// P2C refer to the power of 2 random choicetypeP2Cstruct{sync.RWMutexhosts[]*host// 代理的主机集rnd*rand.RandloadMapmap[string]*host}// NewP2C create new P2C balancerfuncNewP2C(hosts[]string)Balancer{p:=&P2C{hosts:[]*host{},loadMap:make(map[string]*host),rnd:rand.New(rand.NewSource(time.Now().UnixNano())),}for_,h:=rangehosts{p.Add(h)}returnp}// Balance selects a suitable host according to the key valuefunc(p*P2C)Balance(keystring)(string,error){p.RLock()deferp.RUnlock()iflen(p.hosts)==0{return"",NoHostError}n1,n2:=p.hash(key)host:=n2ifp.loadMap[n1].load<=p.loadMap[n2].load{// 选择负载量小的节点host=n1}returnhost,nil}constSalt="%!"// 盐值func(p*P2C)hash(keystring)(string,string){varn1,n2stringiflen(key)>0{// 请求IP为不为空的情况saltKey:=key+Salt// 类似 IP 哈希、只是做了两次哈希n1=p.hosts[crc32.ChecksumIEEE([]byte(key))%uint32(len(p.hosts))].namen2=p.hosts[crc32.ChecksumIEEE([]byte(saltKey))%uint32(len(p.hosts))].namereturnn1,n2}// 请求IP为空的情况n1=p.hosts[p.rnd.Intn(len(p.hosts))].namen2=p.hosts[p.rnd.Intn(len(p.hosts))].namereturnn1,n2}通过Inc、Done函数对主机的负载量进行加减操作：
// Inc refers to the number of connections to the server `+1`func(p*P2C)Inc(hoststring){p.Lock()deferp.Unlock()h,ok:=p.loadMap[host]if!ok{return}h.load++}// Done refers to the number of connections to the server `-1`func(p*P2C)Done(hoststring){p.Lock()deferp.Unlock()h,ok:=p.loadMap[host]if!ok{return}ifh.load>0{h.load--}}关于P2C算法的Add、Remove可以阅读代码balancer/p2c.go；
Least Load
Least Load也就是最小负载算法，也是非常经典的负载均衡算法，在最小负载算法中，负载均衡器将请求定向到负载最小的目标主机中；
对于最小负载算法而言，如果把所有主机的负载值动态存入动态数组中，寻找负载最小节点的时间复杂度为O(N)，如果把主机的负载值维护成一个红黑树，那么寻找负载最小节点的时间复杂度为O(logN)，我们这里利用的数据结构叫做斐波那契堆 ，寻找负载最小节点的时间复杂度为O(1)，感兴趣的小伙伴可以看看斐波那契堆的原理！
Least Load算法的代码:balancer/least_load.go
传统一致性哈希
一致性哈希算法是一种特殊的哈希算法，当哈希表改变大小时，平均只需要重新映射n/m个键值，其中n为哈希表键值的数量，m为哈希表槽的数量。
在一致性哈希负载均衡器中，一个集群由多个代理节点拍摄指南所组成，通过CRC32散列算法对代理主机节点的UUID或节点的IP地址进行计算，即CRC32(IP)或CRC32(UUID)，则会得到一组散列值，而这组散列值连成的环，称为哈希环。
当收到请求时，负载均衡器将请求的IP进行CRC32哈希计算进而得到一个散列值。如图所示，将代理主机节点和请求IP的哈希值映射到哈希环后，沿着哈希环顺时针方向查找，找到的第一个节点，即请求所被调度的代理节点。
通过对代理节点的哈希值按升序建立动态数组，即可在O(logN)时间复杂度的情况下通过二分搜索可以找到被调度的代理节点。
当代理节点数量越少时，越容易出现节点的哈希值在哈希环上分布不均匀的情况。而通过引入虚拟节点的方式可以解决一致性哈希算法负载不平衡的问题 。通过对代理主机的IP外加虚拟序号的形式作哈希计算。
如192.168.1.1的虚拟节点可能是192.168.1.11、192.168.1.12、192.168.1.13，我们需要把虚拟节点计算得到的CRC32值也映射到哈希环中。
下图的三个节点H1、H2、H3均匀两个虚拟节点：
有界负载一致性哈希
Google提出的有界负载一致性哈希通过限制节点负载上限拍摄指南的方式解决了工作节点负载过高的问题。当节点负载过高时，有界负载一致性哈希算法通过转移热点的方式来提升集群整体的负载平衡性。
在有界负载一致性哈希算法中R表示代理主机节点的总负载量，Tw表示代理主机节点的数量，L表示当前所有代理主机的平均负载量，即：
α表示代理主机所能执行的额外上限系数，M则表示每个代理主机所能承受的最大负载量，即：
- 当α趋于0时，有界负载一致性哈希算法将会退化成最小负载算法
- 当α趋于正无穷时，算法会退化成普通性质的一致性哈希算法。
当请求IP的哈希值所调度的代理主机节点超过所能承受的最大负载量M时，负载均衡器则会按顺时针选择第一个负载量小于M值的代理主机节点：
TinyBalancer的健康检查
varHealthCheckTimeout=5*time.Second// ReadAlive reads the alive status of the sitefunc(h*HTTPProxy)ReadAlive(urlstring)bool{h.RLock()deferh.RUnlock()returnh.alive[url]}// SetAlive sets the alive status to the sitefunc(h*HTTPProxy)SetAlive(urlstring,alivebool){h.Lock()deferh.Unlock()h.alive[url]=alive}// HealthCheck enable a health check goroutine for each agentfunc(h*HTTPProxy)HealthCheck(){forhost:=rangeh.hostMap{goh.healthCheck(host)}}func(h*HTTPProxy)healthCheck(hoststring){ticker:=time.NewTicker(time.Duration(interval)*time.Second)forrangeticker.C{if!IsBackendAlive(host)&&h.ReadAlive(host){log.Printf("Site unreachable, remove %s from load balancer.",host)h.SetAlive(host,false)h.lb.Remove(host)}elseifIsBackendAlive(host)&&!h.ReadAlive(host){log.Printf("Site reachable, add %s to load balancer.",host)h.SetAlive(host,true)h.lb.Add(host)}}}由于Map是并发不安全的，在读取alive时，我们需要给Map上读写锁。在健康检查中，我们会给每个代理启动一个goroutine用来检测代理主机是否处于健康状态，若代理主机不可到达，则从负载均衡器移除，若代理主机可到达时，则将其添加进负载均衡器中。
funcIsBackendAlive(hoststring)bool{addr,err:=net.ResolveTCPAddr("tcp",host)// 解析主机iferr!=nil{returnfalse}resolve:=fmt.Sprintf("%s:%d",addr.IP,addr.Port)conn,err:=net.DialTimeout("tcp",resolve,ConnectionTimeout)iferr!=nil{returnfalse}_=conn.Close()returntrue}我们这里使用通过建立TCP连接检测的方式来判断代理主机的健康状态。
配置
typeConfigstruct{SSLCertificateKeystring`yaml:"ssl_certificate_key"`// https时需要的密钥Location[]*Location`yaml:"location"`Schemastring`yaml:"schema"`// http或 httpsPortint`yaml:"port"`// tinybalancer暴露出来的端口SSLCertificatestring`yaml:"ssl_certificate"`// https时需要的证书HealthCheckbool`yaml:"tcp_health_check"`// 是否开启健康检测}// Location routing details of balancertypeLocationstruct{Patternstring`yaml:"pattern"`// 代理的路由ProxyPass[]string`yaml:"proxy_pass"`// 代理主机集BalanceModestring`yaml:"balance_mode"`// 负载均衡算法}tinybalancer的配置采用yaml文件进行保存和读取：
// ReadConfig read configuration from `fileName` filefuncReadConfig(fileNamestring)(*Config,error){in,err:=ioutil.ReadFile(fileName)iferr!=nil{returnnil,err}varconfigConfigerr=yaml.Unmarshal(in,&config)iferr!=nil{returnnil,err}return&config,nil}// Validation verify the configuration details of the balancerfunc(c*Config)Validation()error{ifc.Schema!="http"&&c.Schema!="https"{returnfmt.Errorf("the schema \"%s\" not supported",c.Schema)}iflen(c.Location)==0{returnerrors.New("the details of location cannot be null")}ifc.Schema=="https"&&(len(c.SSLCertificate)==0||len(c.SSLCertificateKey)==0){returnerrors.New("the https proxy requires ssl_certificate_key and ssl_certificate")}ifc.HealthCheckInterval<1{returnerrors.New("health_check_interval must be greater than 0")}returnnil}看到这里，是不是发现tinybalancer的设计小而美呢，下一篇文章，我们将着重讲解负载均衡算法！
版权声明：
本站所有资源均为站长或网友整理自互联网或站长购买自互联网，站长无法分辨资源版权出自何处，所以不承担任何版权以及其他问题带来的法律责任，如有侵权或者其他问题请联系站长删除！站长QQ754403226 谢谢。
