PHP常见算法 排序冒泡排序依次比较相邻的两个数，将比较小的数放在前面，比较大的数放在后面。$arr = [8,1,10,9,5,7]; function bubbleSort($arr){ // 外层 for 循环控制循环次数 for ($i=0; $i<count($arr) ; $i++) { //内层 for 循环进行两数交换，找每次的最大数，排到最后 for ($j=0; $j < count($arr)-1; $j++) { //数组里第一个和第二个对比，如果1>2，执行数值互换 if($arr[$j] >$arr[$j+1]){ $x = $arr[$j]; //第一赋给一个变量 $arr[$j] = $arr[$j+1]; //第二赋给第一 $arr[$j+1] = $x; //把变量给第二，结果就是1，2的数值互换 // $a=10; // $b=20; // $x=$a; $x=10 // $a=$b; $a=20 // $b=$X; $b=10 } } } return $arr; } print_r(bubbleSort($arr));快速排序快速排序是对冒泡排序的一种改进。设置一个基准元素，通过排序将需要排序的数据分割成两个部分，其中一部分的所有数据比基准元素小，另一部分的所有数据比基准元素大，然后对这两部分数据分别进行递归快速排序，最后将得到的数据和基准元素进行合并，就得到了所需数据。$arr = [8,1,10,9,5,7]; function quickSort($arr){ $lenth = count($arr);//获取数组个数 if($lenth <= 1){//小于等于一个不用往下走了 return $arr; } //选择基准元素。一般选第一个或最后一个 $first = $arr[0]; $left = array();//接收小于基准元素的值 $right = array();//接收大于基准元素的值 //循环从1开始，因为基准元素是0 for($i=1;$i<$lenth;$i++){ if($arr[$i]<$first){//小于基准元素的值 $left[] = $arr[$i]; }else{//大于基准元素的值 $right[] = $arr[$i]; } } //递归排序 $left = quickSort($left); $right = quickSort($right); //合并返回数组 return array_merge($left,array($first),$right); } print_r(quickSort($arr));选择排序1.找到数组中最小的元素，拎出来，将它和数组的第一个元素交换位置； 2.在剩下的元素中继续寻找最小的元素，拎出来，和数组的第二个元素交换位置; 3.如此循环，直到整个数组排序完成。$arr = [8,1,10,9,5,7]; function selectSort($arr){ //实现思路 双重循环完成，外层控制轮数，当前的最小值。内层 控制的比较次数，$i 当前最小值的位置， 需要参与比较的元素 for($i=0, $len=count($arr); $i<$len-1; $i++){ //先假设最小的值的位置 $p = $i; //$j 当前都需要和哪些元素比较，$i 后边的。 for($j=$i+1; $j<$len; $j++) { //$arr[$p] 是 当前已知的最小值 if($arr[$p] > $arr[$j]){ //比较，发现更小的,记录下最小值的位置；并且在下次比较时，应该采用已知的最小值进行比较。 $p = $j; } } //已经确定了当前的最小值的位置，保存到$p中。如果发现 最小值的位置与当前假设的位置$i不同，则位置互换即可。 if($p != $i){ $tmp = $arr[$p]; $arr[$p] = $arr[$i]; $arr[$i] = $tmp; } } return $arr; } print_r(selectSort($arr));插入排序每次将一个待排序的数据元素，插入到前面已经排好序的数列中的适当位置，使数列依然有序；直到待排序数据元素全部插入完为止。$arr = [8,1,10,9,5,7]; function insertSort($arr){ $count = count($arr); for($i=1; $i<$count; $i++){ $tmp = $arr[$i]; $j = $i - 1; while(isset($arr[$j]) && $arr[$j] > $tmp){ $arr[$j+1] = $arr[$j]; $arr[$j] = $tmp; $j--; } } return $arr; } print_r(insertSort($arr));希尔排序希尔排序(Shell Sort)是插入排序的一种，它是针对直接插入排序算法的改进。该方法又称缩小增量排序，因DL．Shell于1959年提出而得名。希尔排序实质上是一种分组插入方法。它的基本思想是：对于n个待排序的数列，取一个小于n的整数gap(gap被称为步长)将待排序元素分成若干个组子序列，所有距离为gap的倍数的记录放在同一个组中；然后，对各组内的元素进行直接插入排序。 这一趟排序完成之后，每一个组的元素都是有序的。然后减小gap的值，并重复执行上述的分组和排序。重复这样的操作，当gap=1时，整个数列就是有序的。$arr = [8,1,10,9,5,7]; function shellSort(&$arr){ if(!is_array($arr))return;$n=count($arr); for($gap=floor($n/2);$gap>0;$gap=floor($gap/=2)){ for($i=$gap;$i<$n;++$i){ for($j=$i-$gap;$j>=0&&$arr[$j+$gap]<$arr[$j];$j-=$gap){ $temp=$arr[$j]; $arr[$j]=$arr[$j+$gap]; $arr[$j+$gap]=$temp; } } } return $arr; } print_r(shellSort($arr));查找二分查找二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。/** * 二分查找（Binary Search）算法，也叫折半查找算法。二分查找的思想非常简单，有点类似分治的思想。 * 二分查找针对的是一个有序的数据集合，每次都通过跟区间的中间元素对比， * 将待查找的区间缩小为之前的一半，直到找到要查找的元素，或者区间被缩小为 0。 * * 循环写法 * @param array $array 待查找的数组 * @param int $findVal 要查找的值 * @return int 返回找到的数组键 */ function binarySearch($array, $findVal) { // 非数组或者数组为空，直接返回-1 if (!is_array($array) || empty($array)) { return -1; } // 查找区间，起点和终点 $start = 0; $end = count($array) - 1; while ($start <= $end) { // 以中间点作为参照点比较，取整数 $middle = intval(($start + $end) / 2); if ($array[$middle] > $findVal) { // 查找数比参照点小，则要查找的数在左半边 // 因为 $middle 已经比较过了，这里需要减1 $end = $middle - 1; } elseif ($array[$middle] < $findVal) { // 查找数比参照点大，则要查找的数在右半边 // 因为 $middle 已经比较过了，这里需要加1 $start = $middle + 1; } else { // 查找数与参照点相等，则找到返回 return $middle; } } // 未找到，返回-1 return -1; } // 调用 $array = [10,12,16,19,20,34,56,78,84,95,100]; echo binarySearch($array, 84); /** * 递归写法 * @param array $array 待查找的数组 * @param int $findVal 要查找的值 * @param int $start 查找区间，起点 * @param int $end 查找区间，终点 * @return int 返回找到的数组键 */ function binSearch($array, $findVal, $start, $end) { // 以中间点作为参照点比较，取整数 $middle = intval(($start + $end) / 2); if ($start > $end) { return -1; } if ($findVal > $array[$middle]) { // 查找数比参照点大，则要查找的数在右半边 return binSearch($array, $findVal, $middle + 1, $end); } elseif ($findVal < $array[$middle]) { // 查找数比参照点小，则要查找的数在左半边 return binSearch($array, $findVal, $start, $middle - 1); } else { return $middle; } } // 调用 $arr = [10,12,16,19,20,34,56,78,84,95,100]; var_dump(binSearch($arr, 95, 0, count($arr)-1));

PHP常用六大设计模式 PHP常用六大设计模式单例模式特点三私一公 ：私有的静态变量（存放实例），私有的构造方法（防止创建实例），私有的克隆方法(防止克隆对象)，公有的静态方法（对外界提供实例）应用场景程序应用中，涉及到数据库操作时，如果每次操作的时候连接数据库，会带来大量的资源消耗。可以通过单例模式，创建唯一的数据库连接对象。<?php class Singleton { private static $_instance; private function __construct(){} private function __clone(){} public static function getInstance() { if(self::$_instance instanceof Singleton){//instanceof 判断一个实例是否是某个类的对象 self::$_instance = new Singleton(); } return self::$_instance; } }工厂模式特点将调用对象与创建对象分离 ，调用者直接向工厂请求，减少代码的耦合，提高系统的可维护性与可扩展性。应用场景提供一种类，具有为您创建对象的某些方法，这样就可以使用工厂类创建对象，而不直接使用new。这样如果想更改创建的对象类型，只需更改该工厂即可。//假设3个待实例化的类 class Aclass { } class Bclass { } class Cclass { } class Factory { //定义每个类的类名 const ACLASS = 'Aclass'; const BCLASS = 'Bclass'; const CCLASS = 'Cclass'; public static function getInstance($newclass) { $class = $newclass;//真实项目中这里常常是用来解析路由，加载文件。 return new $class; } } //调用方法： Factory::getInstance(Factory::ACLASS);注册树模式特点注册树模式通过 将对象实例注册到一棵全局的对象树上，需要的时候从对象树上采摘 的模式设计方法。应用场景不管你是通过单例模式还是工厂模式还是二者结合生成的对象，都统统给我“插到”注册树上。我用某个对象的时候，直接从注册树上取一下就好。这和我们使用全局变量一样的方便实用。而且注册树模式还为其他模式提供了一种非常好的想法。 (如下实例是单例，工厂，注册树的联合使用)//创建单例 class Single{ public $hash; static protected $ins=null; final protected function __construct(){ $this->hash=rand(1,9999); } static public function getInstance(){ if (self::$ins instanceof self) { return self::$ins; } self::$ins=new self(); return self::$ins; } } //工厂模式 class RandFactory{ public static function factory(){ return Single::getInstance(); } } //注册树 class Register{ protected static $objects; public static function set($alias,$object){ self::$objects[$alias]=$object; } public static function get($alias){ return self::$objects[$alias]; } public static function _unset($alias){ unset(self::$objects[$alias]); } } //调用 Register::set('rand',RandFactory::factory()); $object=Register::get('rand'); print_r($object);策略模式定义定义一系列算法，将每一个算法封装起来，并让它们可以相互替换。策略模式让算法独立于使用它的客户而变化。特点策略模式提供了 管理相关的算法族 的办法策略模式提供了 可以替换继承关系 的办法使用策略模式可以 避免使用多重条件转移语句应用场景多个类只区别在表现行为不同，可以使用Strategy模式，在运行时动态选择具体要执行的行为。比如上学，有多种策略：走路，公交，地铁…abstract class Strategy { abstract function goSchoole(); } class Run extends Strategy { public function goSchoole() { // TODO: Implement goSchool() method. echo "Run to school <br/>"; } } class Subway extends Strategy { public function goSchoole() { // TODO: Implement goSchool() method. echo "Take the subway to school <br/>"; } } class Bike extends Strategy { public function goSchoole() { // TODO: Implement goSchool() method. echo "Go to school by bike <br/>"; } } class Context { protected $_stratege;//存储传过来的策略对象 public function goSchoole() { $this->_stratege->goSchoole(); } public function setBehavior(Strategy $behavior){//设置策略对象 $this->_stratege = $behavior; } } //调用： $contenx = new Context(); //坐地铁去学校 $contenx->setBehavior(new Subway()); $contenx->goSchoole(); //骑自行车去学校 $contenx->setBehavior(new Bike()); $contenx->goSchoole();适配器模式特点将各种截然不同的函数接口封装成统一的API。应用场景PHP中的数据库操作有MySQL,MySQLi,PDO三种，可以用适配器模式统一成一致，使不同的数据库操作，统一成一样的API。类似的场景还有cache适配器，可以将memcache,redis,file,apc等不同的缓存函数，统一成一致。abstract class Toy { public abstract function openMouth(); public abstract function closeMouth(); } class Dog extends Toy { public function openMouth() { echo "Dog open Mouth<br/>"; } public function closeMouth() { echo "Dog close Mouth<br/>"; } } class Cat extends Toy { public function openMouth() { echo "Cat open Mouth<br/>"; } public function closeMouth() { echo "Cat close Mouth<br/>"; } } //目标角色（红） interface RedTarget { public function doMouthOpen(); public function doMouthClose(); } //目标角色（绿） interface GreenTarget { public function operateMouth($type = 0); } //类适配器角色（红） class RedAdapter implements RedTarget { private $adaptee; function __construct(Toy $adaptee) { $this->adaptee = $adaptee; } //委派调用Adaptee的sampleMethod1方法 public function doMouthOpen() { $this->adaptee->openMouth(); } public function doMouthClose() { $this->adaptee->closeMouth(); } } //类适配器角色（绿） class GreenAdapter implements GreenTarget { private $adaptee; function __construct(Toy $adaptee) { $this->adaptee = $adaptee; } //委派调用Adaptee：GreenTarget的operateMouth方法 public function operateMouth($type = 0) { if ($type) { $this->adaptee->openMouth(); } else { $this->adaptee->closeMouth(); } } } class testDriver { public function run() { //实例化一只狗玩具 $adaptee_dog = new Dog(); echo "给狗套上红枣适配器<br/>"; $adapter_red = new RedAdapter($adaptee_dog); //张嘴 $adapter_red->doMouthOpen(); //闭嘴 $adapter_red->doMouthClose(); echo "给狗套上绿枣适配器<br/>"; $adapter_green = new GreenAdapter($adaptee_dog); //张嘴 $adapter_green->operateMouth(1); //闭嘴 $adapter_green->operateMouth(0); } } //调用 $test = new testDriver(); $test->run();观察者模式特点观察者模式(Observer)， 当一个对象状态发生变化时，依赖它的对象全部会收到通知，并自动更新。 观察者模式实现了低耦合，非侵入式的通知与更新机制。应用场景一个事件发生后，要执行一连串更新操作。传统的编程方式，就是在事件的代码之后直接加入处理的逻辑。当更新的逻辑增多之后，代码会变得难以维护。这种方式是耦合的，侵入式的，增加新的逻辑需要修改事件的主体代码。// 主题接口 interface Subject{ public function register(Observer $observer); public function notify(); } // 观察者接口 interface Observer{ public function watch(); } // 主题 class Action implements Subject{ public $_observers=[]; public function register(Observer $observer){ $this->_observers[]=$observer; } public function notify(){ foreach ($this->_observers as $observer) { $observer->watch(); } } } // 观察者 class Cat1 implements Observer{ public function watch(){ echo "Cat1 watches TV<hr/>"; } } class Dog1 implements Observer{ public function watch(){ echo "Dog1 watches TV<hr/>"; } } class People implements Observer{ public function watch(){ echo "People watches TV<hr/>"; } } // 调用实例 $action=new Action(); $action->register(new Cat1()); $action->register(new People()); $action->register(new Dog1()); $action->notify();

动静分离架构 动静分离架构一、静态页面静态页面，是指互联网架构中，几乎不变的页面(或者变化频率很低)静态页面例如首页等html页面js/css等样式文件jpg/apk等资源文件与之匹配的技术架构来加速静态页面，有与之匹配的技术架构来加速，例如：CDNnginxsquid/varnish二、动态页面动态页面，是指互联网架构中，不同用户不同场景访问，都不一样的页面动态页面例如百度搜索结果页淘宝商品列表页速运个人订单中心页这些页面，不同用户，不同场景访问，大都会动态生成不同的页面。与之匹配的技术架构动态页面，有与之匹配的技术架构，例如：分层架构服务化架构数据库，缓存架构三、互联网动静分离架构动静分离是指，静态页面与动态页面分开不同系统访问的架构设计方法。一般来说：静态页面访问路径短，访问速度快，几毫秒动态页面访问路径长，访问速度相对较慢(数据库的访问，网络传输，业务逻辑计算)，几十毫秒甚至几百毫秒，对架构扩展性的要求更高静态页面与动态页面以不同域名区分四、页面静态化既然静态页面访问快，动态页面生成慢，有没有可能，将原本需要动态生成的站点提前生成好，使用静态页面加速技术来访问呢？这就是互联网架构中的“页面静态化”优化技术。举例，如下图，58同城的帖子详情页，原本是需要动态生成的：浏览器发起http请求，访问/detail/12348888x.shtml 详情页web-server层从RESTful接口中，解析出帖子id是12348888service层通过DAO层拼装SQL语句，访问数据库最终获取数据，拼装html返回浏览器而“页面静态化”是指，将帖子ID为12348888的帖子12348888x.shtml提前生成好，由静态页面相关加速技术来加速：这样的话，将极大提升访问速度，减少访问时间，提高用户体验。五、页面静态化的适用场景页面静态化优化后速度会加快，那能不能所有的场景都使用这个优化呢？哪些业务场景适合使用这个架构优化方案呢？一切脱离业务的架构设计都是耍流氓，页面静态化，适用于：总数据量不大，生成静态页面数量不多的业务。例如：58速运的城市页只有几百个，就可以用这个优化，只需提前生成几百个城市的“静态化页面”即可一些二手车业务，只有几万量二手车库存，也可以提前生成这几万量二手车的静态页面像58同城这样的信息模式业务，有几十亿的帖子量，就不太适合于静态化（碎片文件多，反而访问慢）六、总结“页面静态化”是一种将原本需要动态生成的站点提前生成静态站点的优化技术。 总数据量不大，生成静态页面数量不多的业务，非常适合于“页面静态化”优化。

一分钟了解负载均衡的一切 一分钟了解负载均衡的一切什么是负载均衡负载均衡(Load Balance) 是分布式系统架构设计中必须考虑的因素之一，它通常是指， 将请求/数据【均匀】分摊到多个操作单元上执行，负载均衡的关键在于【均匀】。常见的负载均衡方案常见互联网分布式架构如上，分为 客户端层、反向代理nginx层、站点层、服务层、数据层 。可以看到，每一个下游都有多个上游调用，只需要做到，每一个上游都均匀访问每一个下游，就能实现“将请求/数据【均匀】分摊到多个操作单元上执行”。【客户端层->反向代理层】的负载均衡【客户端层】到【反向代理层】的负载均衡，是通过“DNS轮询”实现的：DNS-server对于一个域名配置了多个解析ip，每次DNS解析请求来访问DNS-server，会轮询返回这些ip，保证每个ip的解析概率是相同的。这些ip就是nginx的外网ip，以做到每台nginx的请求分配也是均衡的。【反向代理层->站点层】的负载均衡【反向代理层】到【站点层】的负载均衡，是通过“nginx”实现的。通过修改nginx.conf，可以实现多种负载均衡策略：1)请求轮询：和DNS轮询类似，请求依次路由到各个web-server2)最少连接路由：哪个web-server的连接少，路由到哪个web-server3)ip哈希：按照访问用户的ip哈希值来路由web-server，只要用户的ip分布是均匀的，请求理论上也是均匀的，ip哈希均衡方法可以做到，同一个用户的请求固定落到同一台web-server上，此策略适合有状态服务，例如session(58沈剑备注：可以这么做，但强烈不建议这么做，站点层无状态是分布式架构设计的基本原则之一，session*放到数据层存储)4)…【站点层->服务层】的负载均衡【站点层】到【服务层】的负载均衡，是通过“服务连接池”实现的。上游连接池会建立与下游服务多个连接，每次请求会“随机”选取连接来访问下游服务。上一篇文章《RPC-client实现细节》中有详细的负载均衡、故障转移、超时处理的细节描述，欢迎点击link查阅，此处不再展开。【数据层】的负载均衡在数据量很大的情况下，由于数据层(db，cache)涉及数据的水平切分，所以数据层的负载均衡更为复杂一些，它 分为“数据的均衡”，与“请求的均衡” 。数据的均衡是指：水平切分后的每个服务(db，cache)，数据量是差不多的。请求的均衡是指：水平切分后的每个服务(db，cache)，请求量是差不多的。常见的水平切分方式业内常见的水平切分方式有这么几种：一、按照range水平切分每一个数据服务，存储一定范围的数据，上图为例：user0服务，存储uid范围1-1kwuser1服务，存储uid范围1kw-2kw好处这个方案的好处是：(1)规则简单，service只需判断一下uid范围就能路由到对应的存储服务(2)数据均衡性较好(3)比较容易扩展，可以随时加一个uid[2kw,3kw]的数据服务不足不足是：(1)请求的负载不一定均衡，一般来说，新注册的用户会比老用户更活跃，大range的服务请求压力会更大二、按照id哈希水平切分每一个数据服务，存储某个key值hash后的部分数据，上图为例：user0服务，存储偶数uid数据user1服务，存储奇数uid数据好处这个方案的好处是：(1)规则简单，service只需对uid进行hash能路由到对应的存储服务(2)数据均衡性较好(3)请求均匀性较好不足不足是：(1)不容易扩展，扩展一个数据服务，hash方法改变时候，可能需要进行数据迁移总结负载均衡(Load Balance)是分布式系统架构设计中必须考虑的因素之一，它通常是指，将请求/数据【均匀】分摊到多个操作单元上执行，负载均衡的关键在于【均匀】。(1)【客户端层】到【反向代理层】的负载均衡，是通过“DNS轮询”实现的(2)【反向代理层】到【站点层】的负载均衡，是通过“nginx”实现的(3)【站点层】到【服务层】的负载均衡，是通过“服务连接池”实现的(4)【数据层】的负载均衡，要考虑“数据的均衡”与“请求的均衡”两个点，常见的方式有“按照范围水平切分”与“hash水平切分”

关于负载均衡的一切：总结与思考 关于负载均衡的一切：总结与思考 概述　　古人云，不患寡而患不均。　　在计算机的世界，这就是大家耳熟能详的 负载均衡（load balancing） ，所谓负载均衡，就是说如果一组计算机节点（或者一组进程）提供相同的（同质的）服务，那么对服务的请求就应该均匀的分摊到这些节点上。负载均衡的前提一定是“provide a single Internet service from multiple servers”， 这些提供服务的节点被称之为server farm、server pool或者backend servers。　　这里的服务是广义的，可以是简单的计算，也可能是数据的读取或者存储。负载均衡也不是新事物，这种思想在多核CPU时代就有了，只不过在分布式系统中，负载均衡更是无处不在，这是分布式系统的天然特性决定的，分布式就是利用大量计算机节点完成单个计算机无法完成的计算、存储服务，既然有大量计算机节点，那么均衡的调度就非常重要。　　 负载均衡的意义在于，让所有节点以最小的代价、最好的状态对外提供服务，这样系统吞吐量最大，性能更高，对于用户而言请求的时间也更小。而且，负载均衡增强了系统的可靠性，最大化降低了单个节点过载、甚至crash的概率。不难想象，如果一个系统绝大部分请求都落在同一个节点上，那么这些请求响应时间都很慢，而且万一节点降级或者崩溃，那么所有请求又会转移到下一个节点，造成雪崩。 　　事实上，网上有很多文章介绍负载均衡的算法，大多都是大同小异。本文更多的是自己对这些算法的总结与思考。一分钟了解负载均衡的一切　　本章节的标题和内容都来自 一分钟了解负载均衡的一切 这一篇文章。当然，原文的标题是夸张了点，不过文中列出了在一个大型web网站中各层是如何用到负载均衡的，一目了然。　　　　常见互联网分布式架构如上，分为客户端层、反向代理nginx层、站点层、服务层、数据层。可以看到，每一个下游都有多个上游调用，只需要做到，每一个上游都均匀访问每一个下游，就能实现“将请求/数据【均匀】分摊到多个操作单元上执行”。　　(1)【客户端层】到【反向代理层】的负载均衡，是通过“DNS轮询”实现的　　(2)【反向代理层】到【站点层】的负载均衡，是通过“nginx”实现的　　(3)【站点层】到【服务层】的负载均衡，是通过“服务连接池”实现的　　(4)【数据层】的负载均衡，要考虑“数据的均衡”与“请求的均衡”两个点，常见的方式有“按照范围水平切分”与“hash水平切分”。　　数据层的负载均衡，在我之前的《带着问题学习分布式系统之数据分片》 中有详细介绍。算法衡量　　在我看来，当我们提到一个负载均衡算法，或者具体的应用场景时，应该考虑以下问题　　第一，是否意识到不同节点的服务能力是不一样的，比如CPU、内存、网络、地理位置　　第二，是否意识到节点的服务能力是动态变化的，高配的机器也有可能由于一些突发原因导致处理速度变得很慢　　第三，是否考虑将同一个客户端，或者说同样的请求分发到同一个处理节点，这对于“有状态”的服务非常重要，比如session，比如分布式存储　　第四，谁来负责负载均衡，即谁充当负载均衡器（load balancer），balancer本身是否会成为瓶颈　　下面会结合具体的算法来考虑这些问题负载均衡算法轮询算法（round-robin）　　思想很简单，就是提供同质服务的节点逐个对外提供服务，这样能做到绝对的均衡。Python示例代码如下 SERVER_LIST = [ '10.246.10.1', '10.246.10.2', '10.246.10.3', ] def round_robin(server_lst, cur = [0]): length = len(server_lst) ret = server_lst[cur[0] % length] cur[0] = (cur[0] + 1) % length return ret　　可以看到，所有的节点都是以同样的概率提供服务，即没有考虑到节点的差异，也许同样数目的请求，高配的机器CPU才20%，低配的机器CPU已经80%了加权轮询算法（weight round-robin）　　加权轮训算法就是在轮训算法的基础上，考虑到机器的差异性，分配给机器不同的权重，能者多劳。注意，这个权重的分配依赖于请求的类型，比如计算密集型，那就考虑CPU、内存；如果是IO密集型，那就考虑磁盘性能。Python示例代码如下 WEIGHT_SERVER_LIST = { '10.246.10.1': 1, '10.246.10.2': 3, '10.246.10.3': 2, } def weight_round_robin(servers, cur = [0]): weighted_list = [] for k, v in servers.iteritems(): weighted_list.extend([k] * v) length = len(weighted_list) ret = weighted_list[cur[0] % length] cur[0] = (cur[0] + 1) % length return ret随机算法（random）　　这个就更好理解了，随机选择一个节点服务，按照概率，只要请求数量足够多，那么也能达到绝对均衡的效果。而且实现简单很多 def random_choose(server_lst): import random random.seed() return random.choice(server_lst)加权随机算法（random）　　如同加权轮训算法至于轮训算法一样，也是在随机的时候引入不同节点的权重，实现也很类似。def weight_random_choose(servers): import random random.seed() weighted_list = [] for k, v in servers.iteritems(): weighted_list.extend([k] * v) return random.choice(weighted_list)　　当然，如果节点列表以及权重变化不大，那么也可以对所有节点归一化，然后按概率区间选择 def normalize_servers(servers): normalized_servers = {} total = sum(servers.values()) cur_sum = 0 for k, v in servers.iteritems(): normalized_servers[k] = 1.0 * (cur_sum + v) / total cur_sum += v return normalized_servers def weight_random_choose_ex(normalized_servers): import random, operator random.seed() rand = random.random() for k, v in sorted(normalized_servers.iteritems(), key = operator.itemgetter(1)): if v >= rand: return k else: assert False, 'Error normalized_servers with rand %s ' % rand 哈希法（hash）　　根据客户端的IP，或者请求的“Key”，计算出一个hash值，然后对节点数目取模。好处就是，同一个请求能够分配到同样的服务节点，这对于“有状态”的服务很有必要 def hash_choose(request_info, server_lst): hashed_request_info = hash(request_info) return server_lst[hashed_request_info % len(server_lst)]　　只要hash结果足够分散，也是能做到绝对均衡的。一致性哈希　　哈希算法的缺陷也很明显，当节点的数目发生变化的时候，请求会大概率分配到其他的节点，引发到一系列问题，比如sticky session。而且在某些情况，比如分布式存储，是绝对的不允许的。　　为了解决这个哈希算法的问题，又引入了一致性哈希算法，简单来说，一个物理节点与多个虚拟节点映射，在hash的时候，使用虚拟节点数目而不是物理节点数目。当物理节点变化的时候，虚拟节点的数目无需变化，只涉及到虚拟节点的重新分配。而且，调整每个物理节点对应的虚拟节点数目，也就相当于每个物理节点有不同的权重最少连接算法（least connection）　　以上的诸多算法，要么没有考虑到节点间的差异（轮训、随机、哈希），要么节点间的权重是静态分配的（加权轮训、加权随机、一致性hash）。　　考虑这么一种情况，某台机器出现故障，无法及时处理请求，但新的请求还是会以一定的概率源源不断的分配到这个节点，造成请求的积压。因此，根据节点的真实负载，动态地调整节点的权重就非常重要。当然，要获得接节点的真实负载也不是一概而论的事情，如何定义负载，负载的收集是否及时，这都是需要考虑的问题。　　每个节点当前的连接数目是一个非常容易收集的指标，因此lease connection是最常被人提到的算法。也有一些侧重不同或者更复杂、更客观的指标，比如最小响应时间（least response time）、最小活跃数（least active）等等。一点思考有状态的请求　　　　首先来看看“算法衡量”中提到的第三个问题：同一个请求是否分发到同样的服务节点，同一个请求指的是同一个用户或者同样的唯一标示。什么时候同一请求最好（必须）分发到同样的服务节点呢？那就是有状态 -- 请求依赖某些存在于内存或者磁盘的数据，比如web请求的session，比如分布式存储。怎么实现呢，有以下几种办法：　　（1）请求分发的时候，保证同一个请求分发到同样的服务节点。　　这个依赖于负载均衡算法，比如简单的轮训，随机肯定是不行的，哈希法在节点增删的时候也会失效。可行的是一致性hash，以及分布式存储中的按范围分段（即记录哪些请求由哪个服务节点提供服务），代价是需要在load balancer中维护额外的数据。　　（2）状态数据在backend servers之间共享　　保证同一个请求分发到同样的服务节点，这个只是手段，目的是请求能使用到对应的状态数据。如果状态数据能够在服务节点之间共享，那么也能达到这个目的。比如服务节点连接到共享数据库，或者内存数据库如memcached　　（3）状态数据维护在客户端　　这个在web请求中也有使用，即cookie，不过要考虑安全性，需要加密。关于load balancer　　接下来回答第四个问题：关于load balancer，其实就是说，在哪里做负载均衡，是客户端还是服务端，是请求的发起者还是请求的3。具体而言，要么是在客户端，根据服务节点的信息自行选择，然后将请求直接发送到选中的服务节点；要么是在服务节点集群之前放一个集中式代理（proxy），由代理负责请求求分发。不管哪一种，至少都需要知道当前的服务节点列表这一基础信息。　　如果在客户端实现负载均衡，客户端首先得知道服务器列表，要么是静态配置，要么有简单接口查询，但backend server的详细负载信息，就不适用通过客户端来查询。因此，客户端的负载均衡算法要么是比较简单的，比如轮训（加权轮训）、随机（加权随机）、哈希这几种算法，只要每个客户端足够随机，按照大数定理，服务节点的负载也是均衡的。要在客户端使用较为复杂的算法，比如根据backend的实际负载，那么就需要去额外的负载均衡服务（external load balancing service）查询到这些信息，在grpc中，就是使用的这种办法　　　　可以看到，load balancer与grpc server通信，获得grpc server的负载等具体详细，然后grpc client从load balancer获取这些信息，最终grpc client直连到被选择的grpc server。　　而基于Proxy的方式是更为常见的，比如7层的Nginx，四层的F5、LVS，既有硬件路由，也有软件分发。集中式的特点在于方便控制，而且能容易实现一些更精密，更复杂的算法。但缺点也很明显，一来负载均衡器本身可能成为性能瓶颈；二来可能引入额外的延迟，请求一定先发到达负载均衡器，然后到达真正的服务节点。　　load balance proxy对于请求的响应（response），要么不经过proxy(三角传输模式)，如LVS；要么经过Proxy，如Nginx。下图是LVS示意图（来源见水印）　　　　而如果response也是走load balancer proxy的话，那么整个服务过程对客户端而言就是完全透明的，也防止了客户端去尝试连接后台服务器，提供了一层安全保障！　　值得注意的是，load balancer proxy不能成为单点故障（single point of failure），因此一般会设计为高可用的主从结构# 其他　　在这篇文章中提到，负载均衡是一种推模型，一定会选出一个服务节点，然后把请求推送过来。而换一种思路，使用消息队列，就变成了拉模型：空闲的服务节点主动去拉取请求进行处理，各个节点的负载自然也是均衡的。消息队列相比负载均衡好处在于，服务节点不会被大量请求冲垮，同时增加服务节点更加容易；缺点也很明显，请求不是事实处理的。　　想到另外一个例子，比如在gunicorn这种pre-fork模型中，master（gunicorn 中Arbiter）会fork出指定数量的worker进程，worker进程在同样的端口上监听，谁先监听到网络连接请求，谁就提供服务，这也是worker进程之间的负载均衡。