分布式系统设计概要笔记-四

Posted on 01-10-2015 | In NP

分布式系统设计实践

基本的理论和策略简单介绍这么多，后面本人会从工程的角度，细化说一下”数据分布“、”副本控制”和”高可用协议”

在分布式系统中，无论是计算还是存储，处理的对象都是数据，数据不存在于一台机器或进程中，

. . .

分布式系统设计概要笔记-三

Posted on 01-07-2015 | In NP

分布式系统设计策略

重试机制

一般情况下，写一段网络交互的代码，发起rpc或者http，都会遇到请求超时而失败情况。

可能是网络抖动(暂时的网络变更导致包不可达，比如拓扑变更)或者对端挂掉。

这时一般处理逻辑是将请求包在一个重试循环块里，如下：
[cpp] view plain copy print?
int retry = 3;
while(!request() && retry–)
sched_yield(); // or usleep(100)

. . .

工厂模式

Posted on 01-07-2015 | In Misc

区别

简单工厂模式 ：

一个工厂类, 这个工厂类能创建多个具体产品类的实例。
一个抽象产品类，可以派生出多个具体产品类。

工厂方法模式 ：

一个抽象工厂类，可以派生出多个具体工厂类。
一个抽象产品类，可以派生出多个具体产品类。

每个具体工厂类只能创建一个具体产品类的实例。
抽象工厂模式 ：

一个抽象工厂类，可以派生出多个具体工厂类。
多个抽象产品类，每个抽象产品类可以派生出多个具体产品类。

每个具体工厂类可以创建多个具体产品类的实例。

区别：

工厂方法模式只有一个抽象产品类，而抽象工厂模式有多个。

工厂方法模式的具体工厂类只能创建一个具体产品类的实例，而抽象工厂模式可以创建多个。

简单工厂模式

产品类

<?php
/**
  车子系列
 
 */
abstract Class BWM{
    function construct($pa) {

    }
}
Class BWM320 extends BWM{
    function construct($pa) {

    }
}
Class BMW523 extends BWM{
   function construc($pb){

   }
}

工厂类

/**
  工厂创建车
 
 */
class Factory {


    static function  createBMW($type){
        switch ($type) {
          case 320:
             return new BWM320();
          case 523:
             return new BMW523();
        //….
   }
}

客户类

/**
  客户通过工厂获取车
 
 */
class Customer {
    private $BMW;
    function getBMW($type){
        $this¬-> BMW =  Factory::createBMW($type);
    }
}

工厂方法模式

产品类

<?php
/**
  车子系列
 
 /
abstract Class BWM{
function construct($pa) {

}
}
Class BWM320 extends BWM{
function construct($pa) {

}
}
Class BMW523 extends BWM{
   function construc($pb){

}
}

创建工厂类

/**
  创建工厂的接口
 
 */
interface FactoryBMW {
       function createBMW();
}


/**
  
  创建BWM320车
 **/
class FactoryBWM320 implements FactoryBMW {
   function  createBMW($type){
      return new BWM320();
   }

}


/**
 
  创建BWM523车
 **/
class FactoryBWM523 implements FactoryBMW {
   function  createBMW($type){
      return new BMW523();
   }
}

客户类

/**
  
  客户得到车
 */
class Customer {
   private $BMW;
   function  getBMW($type){
      switch ($type) {
        case 320:
           $BWM320 = new FactoryBWM320();
           return $BWM320->createBMW();
        case 523:
           $BWM523 = new FactoryBWM523();
           return $BWM320->createBMW();
            //….
      }

  }
}

抽象工厂模式

产品类

<?php
/**
  车子系列以及型号
 
 */
abstract class  BWM{
}

class BWM523 extends  BWM {
}
class BWM320 extends  BWM {


}

/*
  空调
 
 */
abstract class aircondition{
}
class airconditionBWM320  extends aircondition {

}
class airconditionBWM52 extends aircondition {

}

创建工厂类

/*
  创建工厂的接口
 
 */
interface FactoryBMW {
     function createBMW();
     function createAirC();
}


/**
 
  创建BWM320车
 /
class FactoryBWM320 implements FactoryBMW {
    function  createBMW(){
    return new BWM320();
}
function  createAirC(){ //空调
    return new airconditionBWM320();
}
}


/*
  
  创建BWM523车
 */
class FactoryBWM523 implements FactoryBMW {
    function  createBMW(){
    return new BWM523();
}
function  createAirC(){
    return new airconditionBWM523();
}
}

客户

/*
  
  客户得到车
 */
class Customer {
   private $BMW;
   private $airC;
   function  getBMW($type){
       $class = new ReflectionClass(‘FactoryBWM’ .$type );//建立 Person这个类的反射类
        $instance  = $class->newInstanceArgs();//相当于实例化Person 类
        $this->BMW =  $instance->createBMW();
       $this->airC =  $instance->createAirC();
   }
}

观察者模式

Posted on 01-07-2015 | In Misc

概述

一些面向对象的编程方式，提供了一种构建对象间复杂网络互连的能力。当对象们连接在一起时，它们就可以相互提供服务和信息。

通常来说，当某个对象的状态发生改变时，你仍然需要对象之间能互相通信。但是出于各种原因，你也许并不愿意因为代码环境的改变而对代码做大的修改。也许，你只想根据你的具体应用环境而改进通信代码。或者，你只想简单的重新构造通信代码来避免类和类之间的相互依赖与相互从属。

问题

当一个对象的状态发生改变时，你如何通知其他对象？是否需要一个动态方案――一个就像允许脚本的执行一样，允许自由连接的方案？

解决方案

观察者模式 ：定义对象间的一种一对多的依赖关系, 当一个对象的状态发生改变时, 所有依赖于它的对象都得到通知并被自动更新。

观察者模式允许一个对象关注其他对象的状态，并且，观察者模式还为被观测者提供了一种观测结构，或者说是一个主体和一个客体。主体，也就是被观测者，可以用来联系所有的观测它的观测者。客体，也就是观测者，用来接受主体状态的改变观测就是一个可被观测的类（也就是主题）与一个或多个观测它的类（也就是客体）的协作。不论什么时候，当被观测对象的状态变化时，所有注册过的观测者都会得到通知。

观察者模式将被观测者（主体）从观测者（客体）种分离出来。这样，每个观测者都可以根据主体的变化分别采取各自的操作。（观察者模式和 Publish/Subscribe 模式一样，也是一种有效描述对象间相互作用的模式。）观察者模式灵活而且功能强大。对于被观测者来说，那些查询哪些类需要自己的状态信息和每次使用那些状态信息的额外资源开销已经不存在了。另外，一个观测者可以在任何合适的时候进行注册和取消注册。你也可以定义多个具体的观测类，以便在实际应用中执行不同的操作。

将一个系统分割成一系列相互协作的类有一个常见的副作用：需要维护相关对象间的一致性。我们不希望为了维持一致性而使各类紧密耦合，因为这样降低了它们的可重用性。

适用性

在以下任一情况下可以使用观察者模式:

当一个抽象模型有两个方面, 其中一个方面依赖于另一方面。将这二者封装在独立的对象中以使它们可以各自独立地改变和复用。
当对一个对象的改变需要同时改变其它对象 , 而不知道具体有多少对象有待改变。
当一个对象必须通知其它对象，而它又不能假定其它对象是谁。换言之 , 你不希望这些对象是紧密耦合的。

结构

模式的组成

观察者模式包含如下角色：

目标（Subject）: 目标知道它的观察者。可以有任意多个观察者观察同一个目标。提供注册和删除观察者对象的接口。
具体目标（ConcreteSubject）: 将有关状态存入各 ConcreteObserver 对象。
观察者 (Observer): 为那些在目标发生改变时需获得通知的对象定义一个更新接口。当它的状态发生改变时, 向它的各个观察者发出通知。
具体观察者 (ConcreteObserver): 维护一个指向 ConcreteSubject 对象的引用。存储有关状态，这些状态应与目标的状态保持一致。实现 O b s e r v e r 的更新接口以使自身状态与目标的状态保持一致。

观察者模式的优缺点

Observer 模式允许你独立的改变目标和观察者。你可以单独复用目标对象而无需同时复用其观察者, 反之亦然。它也使你可以在不改动目标和其他的观察者的前提下增加观察者。

下面是观察者模式其它一些优点 :

观察者模式可以实现表示层和数据逻辑层的分离, 并定义了稳定的消息更新传递机制，抽象了更新接口，使得可以有各种各样不同的表示层作为具体观察者角色。
在观察目标和观察者之间建立一个抽象的耦合：
一个目标所知道的仅仅是它有一系列观察者 , 每个都符合抽象的 Observer 类的简单接口。目标不知道任何一个观察者属于哪一个具体的类。这样目标和观察者之间的耦合是抽象的和最小的。因为目标和观察者不是紧密耦合的, 它们可以属于一个系统中的不同抽象层次。一个处于较低层次的目标对象可与一个处于较高层次的观察者通信并通知它 , 这样就保持了系统层次的完整。如果目标和观察者混在一块 , 那么得到的对象要么横贯两个层次 (违反了层次性), 要么必须放在这两层的某一层中 (这可能会损害层次抽象)。
支持广播通信 : 不像通常的请求, 目标发送的通知不需指定它的接收者。通知被自动广播给所有已向该目标对象登记的有关对象。目标对象并不关心到底有多少对象对自己感兴趣 ; 它唯一的责任就是通知它的各观察者。这给了你在任何时刻增加和删除观察者的自由。处理还是忽略一个通知取决于观察者。
观察者模式符合 “开闭原则” 的要求。

观察者模式的缺点 :

如果一个观察目标对象有很多直接和间接的观察者的话，将所有的观察者都通知到会花费很多时间。
如果在观察者和观察目标之间有循环依赖的话，观察目标会触发它们之间进行循环调用，可能导致系统崩溃。
观察者模式没有相应的机制让观察者知道所观察的目标对象是怎么发生变化的，而仅仅只是知道观察目标发生了变化。
意外的更新因为一个观察者并不知道其它观察者的存在 , 它可能对改变目标的最终代价一无所知。在目标上一个看似无害的的操作可能会引起一系列对观察者以及依赖于这些观察者的那些对象的更新。此外 , 如果依赖准则的定义或维护不当，常常会引起错误的更新 , 这种错误通常很难捕捉。

简单的更新协议不提供具体细节说明目标中什么被改变了 , 这就使得上述问题更加严重。如果没有其他协议帮助观察者发现什么发生了改变，它们可能会被迫尽力减少改变。

实现

在 php 的 SPL 支持观察者模式，SPL 提供了 SplSubject 和 SplObserver 接口。

SplSubject 接口提供了 attach()、detach()、notify() 三个方法。而 SplObserver 接口则提供了 update() 方法。

SplSubject 派生类维护了一个状态，当状态发生变化时 - 比如属性变化等，就会调用 notify() 方法，这时，之前在 attach() 方法中注册的所有 SplObserver 实例的 update() 方法就会被调用。接口定义如下：

<?php  
/** 
* 这一模式的概念是 SplSubject 类维护了一个特定状态，当这个状态发生变化时，它就会调用 notify() 方法。 
* 调用 notify() 方法时，所有之前使用 attach() 方法注册的 SplObserver 实例的 update 方法都会被调用。 
* 
*/  
interface SplSubject{  
    public function attach(SplObserver $observer);// 注册观察者  
    public function detach(SplObserver $observer);// 释放观察者  
    public function notify();// 通知所有注册的观察者  
}  
interface SplObserver{  
    public function update(SplSubject $subject);// 观察者进行更新状态  
}

实现代码：

<?php  
/** 
* 具体目标 
* 
*/  
class ConcreteSubject implements SplSubject {  
        private $observers, $value;  
        public function __construct() {  
        $this->observers = array();  
    }  

    public function attach(SplObserver $observer) { // 注册观察者  
        $this->observers[] = $observer;  
    }  

    public function detach(SplObserver $observer) { // 释放观察者  
        if($idx = array_search($observer,$this->observers,true)) {  
        unset($this->observers[$idx]);  
    }  
    }  

    public function notify() { // 通知所有观察者  
        foreach($this->observers as $observer) {  
        $observer->update($this);  
    }  
    }  

    public function setValue($value) {  
        $this->value = $value;  
        $this->notify();  
    }  

    public function getValue() {  
        return $this->value;  
    }  

}  
/** 
* 具体观察者 
* 
*/  
class ConcreteObserver1 implements SplObserver {  

    public function update(SplSubject $subject) {  
        echo 'ConcreteObserver1  value is',$subject->getValue(), '<br>';  
    }  

}  
/** 
* 具体观察者 
* 
*/  
class ConcreteObserver2 implements SplObserver {  

    public function update(SplSubject $subject) {  
        echo 'ConcreteObserver2 value is', $subject->getValue(), '<br>';  
    }  

}  

$subject = new ConcreteSubject();  
$observer1 = new ConcreteObserver1();  
$observer2 = new ConcreteObserver2();  
$subject->attach($observer1);  
$subject->attach($observer2);  
$subject->setValue(5);  
?>

我们扩展上面的例子，根据目标状态而更新不同的观察者：

<?php    
/** 
* 具体目标  
*  
*/    

class ConcreteSubject implements SplSubject {  

    private $observers, $_state;  

    public function __construct() {  
        $this->observers = array();  
    }  
    /** 
    *  注册观察者   
    * 
    * @param SplObserver $observer 
    */  
    public function attach(SplObserver $observer) {  
        $this->observers[] = $observer;  
    }  
    /** 
    *  // 释放观察者   
    * 
    * @param SplObserver $observer 
    */  
    public function detach(SplObserver $observer) {  
        if($idx = array_search($observer,$this->observers,true)) {  
            unset($this->observers[$idx]);  
        }  
    }  
    /** 
    * 通知所有观察者   
    *  
    */  
    public function notify() {  
        /** 
        * 只要状态改变，就通知观察者 
        */  
        foreach($this->observers as $observer) {  
            if ($observer->getState() == $this->_state) {  
                $observer->update($this);  
            }  
        }  
    }  
    /** 
    * 设置状态 
    * 
    * @param unknown_type $state 
    */  
    public function setState($state) {  
        $this->_state = $state;  
        $this->notify();  
    }  

    public function getState() {  
        return $this->_state;  
    }  

}  

/** 
* 抽象观摩者 
* 
*/  
abstract class observer{  
    private $_state;  

    function __construct($state) {  
        $this->_state = $state;  
    }  

    public function setState($state) {  
        $this->_state = $state;  
        $this->notify();  
    }  

    public function getState() {  
        return $this->_state;  
    }  

}  
/** 
* 具体观察者 1 
*  
*/    
class ConcreteObserver1 extends observer  implements SplObserver {  

    function __construct($state) {  
        parent::__construct($state);  
    }  
    public function update(SplSubject $subject) {  
        echo 'ConcreteObserver1  state is',$subject->getState(), '<br>';  
    }  

}  

/** 
* 具体观察者 2 
*  
*/    
class ConcreteObserver2 extends observer   implements SplObserver {  
    function __construct($state) {  
        parent::__construct($state);  
    }  
    public function update(SplSubject $subject) {  
        echo 'ConcreteObserver2 state is', $subject->getState(), '<br>';  
    }  

}  
/** 
* 具体观察者 3 
*  
*/    
class ConcreteObserver3 extends observer   implements SplObserver {  
    function __construct($state) {  
        parent::__construct($state);  
    }  
    public function update(SplSubject $subject) {  
        echo 'ConcreteObserver3 state is', $subject->getState(), '<br>';  
    }  

}  

$subject = new ConcreteSubject();  
$observer1 = new ConcreteObserver1(1);  
$observer2 = new ConcreteObserver2(1);  
$observer3 = new ConcreteObserver3(2);  
$subject->attach($observer1);  
$subject->attach($observer2);  
$subject->attach($observer3);  
echo 'Subject state is 1', '<br>';  
$subject->setState(1);  
echo 'Subject state is 2', '<br>';  
$subject->setState(2);  
?>

与其他相关模式

终结者模式 Mediator: 通过封装复杂的更新语义 , ChangeManager 充当目标和观察者之间的中介者。
单例模式 Singleton: ChangeManager 可使用 Singleton 模式来保证它是唯一的并且是可全局访问
的。

总结与分析

通过 Observer 模式，把一对多对象之间的通知依赖关系的变得更为松散，大大地提高了程序的可维护性和可扩展性，也很好的符合了开放 - 封闭原则。

分布式系统设计概要笔记-二

Posted on 01-05-2015 | In NP

分布式系统特性

CAP是分布式系统里最著名的理论，wiki百科如下

Consistency(all nodes see the same data at the same time)
Availability (a guarantee that every request receives a response about whether it was successful or failed)
Partition tolerance (the system continues to operate despite arbitrary message loss or failure of part of the system)
```
(摘自 ：http://en.wikipedia.org/wiki/CAP_theorem)
```

. . .

分布式系统设计概要笔记-一

Posted on 01-04-2015 | In NP

分布式系统中的概念

最简单的分布式系统

分布式可繁也可以简，最简单的分布式就是大家最常用的，

在负载均衡服务器后加一堆web服务器，然后在上面搞一个缓存服务器来保存临时状态，

后面共享一个数据库，其实很多号称分布式专家的人也就停留于此，

大致结构如下图所示：

这种环境下真正进行分布式的只是web server而已，

并且web server之间没有任何联系，所以结构和实现都非常简单。

最完备的分布式体系的模块组成

有些情况下，对分布式的需求就没这么简单，

在每个环节上都有分布式的需求，

比如Load Balance、DB、Cache和文件等等，

并且当分布式节点之间有关联时，

还得考虑之间的通讯，

另外，

节点非常多的时候，

得有监控和管理来支撑。这样看起来，

分布式是一个非常庞大的体系，

只不过你可以根据具体需求进行适当地裁剪。按照最完备的分布式体系来看，

可以由以下模块组成：

分布式任务处理服务：负责具体的业务逻辑处理
分布式节点注册和查询：负责管理所有分布式节点的命名和物理信息的注册与
询，是节点之间联系的桥梁
分布式DB：分布式结构化数据存取
分布式Cache：分布式缓存数据（非持久化）存取
分布式文件：分布式文件存取
网络通信：节点之间的网络数据通信
监控管理：搜集、监控和诊断所有节点运行状态
分布式编程语言：用于分布式环境下的专有编程语言，比如Elang、Scala
分布式算法：为解决分布式环境下一些特有问题的算法，比如解决一致性问题的Paxos算法

三元组

其实，分布式系统说白了，就是很多机器组成的集群，靠彼此之间的网络通信，担当的角色可能不同，共同完成同一个事情的系统。

. . .

为什么不推荐递归以及什么是尾递归

Posted on 01-02-2015 | In Misc

为什么不推荐递归

递归的调试难度奇高，就决定了实际项目中很少用递归。

而且递归确实运行效率低，因为函数一层一层调用存在调用栈，

在切换到更深层的函数时要产生断点，为了保证回来时继续运行，

必须保存现在所处函数的各种状态，回来时恢复状态，这样一层层下去性能损失就不断增加。

大量开辟在栈区的内存，直到每一层的递归结束或整个递归结束才释放且这个内存空间可能呈几何级数增加，空间效率不佳，有可能会栈溢出

而要知道什么是尾递归，首先得指到什么是尾调用

. . .

数据结构四之链表进阶

Posted on 12-22-2014 | In Algo

只谈一下单链表, 链表实在是太重要, 是前面两篇说算法博客的基础, 了解了其应用和衍生, 再去了解其本身就有动力了

存储结构

typedef struct Node
{
	DataType data;
	struct Node *next;
}Node, *Node_Ptr;

链表中第一个结点的存储位置叫做头指针
头指针和头结点不同，头结点即第一个结点，头指针是指向第一个结点的指针。链表中可以没有头结点，但不能没有头指针。
如果链表有头结点，那么头指针就是指向头结点数据域的指针。
单链表也可以没有头结点

头结点的优点:

头结点是为了操作的统一与方便而设立的，放在第一个元素结点之前，其数据域一般无意义（当然有些情况下也可存放链表的长度、用做监视哨等等）。
有了头结点后，对在第一个元素结点前插入结点和删除第一个结点，其操作与对其它结点的操作统一了。

有头结点和无头结点的建立链表方法头插法

include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct Link {
    int  elem;
    struct Link *next;
}link;
//无头结点链表的头插法实现函数
link * creatLink(int * arc, int length) {
    int i;
    //最初状态下，头指针 H 没有任何结点，所以，插入第一个元素，就相当于是创建结点 H
    link * H =(link*)malloc(sizeof(link));
    H->elem = arc[0];
    H->next = NULL;
    //如果采用头插法插入超过 1 个元素，则可添加到第一个结点 H 之前
    for (i = 1; i<length; i++) {
        link * a = (link*)malloc(sizeof(link));
        a->elem = arc[i];
        //插入元素时，首先将插入位置后的链表链接到新结点上
        a->next = H;
        //然后再链接头指针 H
        H = a;
    }
    return H;
}
//有头结点链表的头插法实现函数
link * HcreatLink(int * arc, int length) {
    int i;
    //创建头结点 H，其链表的头指针也是 H
    link * H = (link*)malloc(sizeof(link));
    H->elem = 0;
    H->next = NULL;
    //采用头插法创建链表
    for (i = 0; i<length; i++) {
        link * a = (link*)malloc(sizeof(link));
        a->elem = arc[i];
        //首先将插入位置之后的链表链接到新结点 a 上
        a->next = H->next;
        //将新结点 a 插入到头结点之后的位置
        H->next = a;
    }
    return H;
}
//链表的输出函数
void display(link *p) {
    while (p) {
        printf("%d ", p->elem);
        p = p->next;
    }
    printf("\n");
}
int main() {
    int a[3] = { 1,2,3 };
    //采用头插法创建无头结点链表
    link * H = creatLink(a, 3);
    display(H);
    //采用头插法创建有头结点链表
    link * head = HcreatLink(a, 3);
    display(head);
    //使用完毕后，释放即可
    free(H);
    free(head);
    return 0;
}

运行结果：

3 2 1
0 3 2 1

提示：没有 0 的为无头结点的头插法输出结果，有 0 的为有头结点的头插法的输出结果

. . .

Mike

🚙 🚗 💨 💨 If you want to create a blog like this, just follow my open-source project, "hexo-theme-neo", click the GitHub button below and check it out ^_^ . It is recommended to use Chrome, Safari, or Edge to read this blog since this blog was developed on Edge (Chromium kernel version) and tested on Safari.

GitHub Spotify

分布式系统设计实践

分布式系统设计策略

重试机制

分类

区别

简单工厂模式

工厂方法模式

抽象工厂模式

概述

问题

解决方案

适用性

结构

模式的组成

观察者模式的优缺点

实现

与其他相关模式

总结与分析

分布式系统特性

分布式系统中的概念

最简单的分布式系统

最完备的分布式体系的模块组成

三元组

为什么不推荐递归

存储结构

有头结点和无头结点的建立链表方法头插法