By

上一节中对动态规划有了一个初步的认识，现在通过更多的例子来加深印象，在网上搜索了一下关于动态规划的经典问题，其中第一个就是所谓“背包问题”，事实上它也很类似上一节中的钢条切割，稍有不同。

背包问题

给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价值最高。

不同于上节钢条切割的地方是，物品的重量不是连续的，所以事先并不能知道任意物品组成的总重会的集合。

为了便于编程实现，将问题具体化，比如使用上一节中的数据，重量价格表P：

重量：  2    3    4    5    6    7    8    9    10
价值：  5    8    9   10   17   17   20   24    30

但是上一节中我们的输入不能>10，在背包问题中，没有这种限制。

Read More

By

动态规划很像分治法，都是通过分解成子问题并结合其结果来得到原问题的解。区别在于法的子问题不相交，但是动态规划的子问题是重叠的。

动态规划通常用来求解最优解问题，即在问题的众多可行方案中找出一个（不唯一）最优解。

钢条切割问题

将长度为n的钢条切割成若干短钢条出售，切割成本不计，钢条长度与售价关系如下表，求一种售价最大的切割法（含不切割情况）。

简单的递归求解

r(n)表示规模为n问题的最优解，p(i)为长i钢条的售价：

以下为Python的代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
p=[0,1,5,8,9,10,17,17,20,24,30]
def cut_rod(n,p):
    if n == 0:
        return 0
    q=-1
    for i in range(1,n+1):
        t= p[i]+cut_rod(n-i,p)
        if t > q:
            q=t
    return q
print cut_rod(9,p)

Read More

By

　　听说在GFW之外我们又有一个大杀器GreatCannon， 好奇之下找了一篇文章翻翻，顺便部分翻译了一下。

　　看完之后的感受是，所谓GreatCannon不过是利用了独有的资源，并没啥高精尖的东西，不过，了解人家分析日志的追踪攻击的过程还挺有意思，当作一次了解运维和安全的机会吧。

利用百度来操纵百万级电脑发起DDoS

　　通过在诸如Amazon的Clound Front这样的大型CDN上部署一组在线镜像站点，GreatFire.org工程成功地解除中国国内对一些站点的屏蔽。

　　2015-3-18,项目网站报道前一天遭受了大规模的DOS攻击。这篇文档详细介绍了这次有史以来最大规模的应用层了攻击是如何实施的。

　　攻击者实现了一种隐秘机制来操作大量的合法流量，境内或境外，来发起和操纵DDOS攻击反审查项目CloundFront和GreatFire.org项目。

文档揭示了

访问中国数千网站的全球用户被随机收到恶意代码来实施攻击。

当正常用户加载以下百度服务器dup.baidustatic.com, ecomcbjs.jomodns.com, cbjs.e.shifen.com, hm.baidu.com, eclick.baidu.com, pos.baidu.com, cpro.baidu.com and hm.e.shifen.com的资源时，恶意代码以JavaScript的形式发送。

百度的分析代码h.js被替换成恶意代码触发攻击。

恶意代码被无差别地发送给全球任何用户，唯一的目的即发起到CloundFront和GreatFire的攻击

百万级的用户成为攻击目标，转而攻击Amazon的基础设施

窜改发生在来自中国以外的流量访问百度服务器时

Read More

By

用ZooKeeper构建高级结构

　　这节中讲述使用ZooKeeper构建高级功能的方法，都是一些传统的，不需要ZooKeeper特殊支持的功能。希望社区能够在client端的库中考虑这些传统来简化使用和促进标准化。

　　有意思的是虽然ZooKeeper使用异步通知，却可以用它来构造一致同步的基元，比如队列和锁。这是因为ZooKeeper实现了更新的整体有序，并有向外展示这种有序的机制。

　　所有设计遵循实用原则，特别避免了轮询，计时和任何导致“羊群效应”的事情，避免网络暴发和扩容受限。

　　还有很多可以想象的有用功能这里没有提到，比如可撤销读写优先级锁。列举的功能也可以以其它方式实现，总之本文只是为了刺激大家的想象力。

原装可用的功能

　　目录服务和配置是两大ZooKeeper直接提供的功能，另一个是组员管理，组由znode表示，成员由之下的瞬时node表示，掉线的成员被服务检测到后会自动删除。

Barrier

　　分布式系统使用Barrier来阻塞一组进程直到某条件满足。ZooKeeper设计一个barrier node来实现Barrier功能。node存在代表Barrier存在。伪代码如下：

client调用exists并设置watch

如果exists返回假，barrier不存在，进程继续

如果exists返回真，有barrier，进程阻塞等待watch事件

收到watch事件时重新调用exists……直到barrier移除

Read More

By

　　之前小节中已经写过快速入门的例程，但在进一步了解了更多的概念之后，需要更多的实践来加深印象。总之理论学习和实践穿插进行在我看来是一种不错的方式，重要的是在参照教程编写代码的同时不要只求快速跑通，而应该与之前的看过的原理结合起来。

一个简单的Watch客户端

　　watch一个znode，用启动和停止特定程序的方式作出回应。

Requirements

  1. 接收的参数:

    服务地址
    需要watch的znode
    可执行程序+参数

  2. 从zonde中取得数据并运行程序
  3. 如果znode变化，用新的数据重启程序
  4. 如果znode删除，终止程序

Read More

By

ACL 权限

ZooKeeper支持以下权限：

CREATE : you can create a child node

READ : you can get data from a node and list its children.

WRITE : you can set data for a node

DELETE : you can delete a child node

ADMIN : you can set permissions

　　创建和删除被从写的权限中抽离出来以实现更细粒度的控制.

　　因为ZooKeeper并无znode拥有者的概念，所以设计了ADMIN权限。ZooKeeper默认所有人拥有excute/lookup权限。

内建ACL策略

　　ZooKeeeper有以下内建策略。

world ： 有唯一id，anyone，表示任何人

auth ： 不使用id, 代表认证用户

digest ： 用 username:password 来生成 MD5 hash作为id. 认证使用username:password形式的明文， ACL中密码采用base64 编码的密码 的SHA1哈希.

ip ：使用client IP 作为id. expression为addr/bits形式.

Read More

By

ZooKeeper数据模型

　　ZooKeeper拥有一个层级结构的目录空间，非常类似分布式文件系统，唯一的不同是每个node可同时拥有数据和子node，即文件同时也是目录。只使用绝对路径，总的来说任何Unicode字符都可以作为路径的一部分，但遵循以下约束:

null(\u0000)不能用在path中，因为在C中会导致Binding异常。

以下字符因为不能很好显示或易让人迷惑，不可用在path中：\u0001 - \u0019 and \u007F - \u009F.

以下字符也不允许使用： \ud800 -uF8FFF, \uFFF0-uFFFF, \uXFFFE - \uXFFFF (X 代表 1 - E), \uF0000 - \uFFFFF.

.和..可用，但不能单独用来表示node, 亦即/a/b/./c” or “/a/b/../c都是非法的。

zookeeper是保留字

ZNodes

　　ZooKeeper tree中的每一个Node都指向一个znode, znode维护一个状态结构，结构中包含数据/acl 更新的版本号和时间戳，二者共同用于验证缓存和同步更新。znode每更新一次 ，版本号增加，读取数据时会得到相应的版本号，更新数据时也应提供版本号，如果版本号不符，操作失败（注：提供强制模式，会忽略版本号）。

　　Znode是应用访问最多的实体，有以下两个特性值得关注。

Read More

By

这一节中我们要对上一节中的Barrier和Queue用例进行测试和分析，填补忽略的细节，加深印象。

Barrier

首先我们来看测试main方法，为了更方便地进行Debug和日志输出，暂没有使用不是太熟悉的Junit.

测试代码

1
2
3
4
5
6
7
8
9
10
 ZKBarrier zkBarrier = new ZKBarrier("dell:2181", "/testRoot3", 3);
 
//purge the children under testrRoot
zkBarrier.name = args[0];
System.out.println("Entering the Barrier");
zkBarrier.enter();
System.out.println("Work done, leaving");
zkBarrier.leave();
return;

大致的流程如下：

等待其它进程（总数3）就绪
开始工作
等待所有Node删除，退出

Read More

By

这一节中我们演示用ZooKeeper创建一个简单的barrier和producer-consumer队列。当然首先你必须有至少一个ZooKeeper Server在运行。

基类

barrier和queue都将用到以下共同代码，构造方法会创建到Server的连接。

注意：官网教程没有提到，这个基类是要实现Watcher接口的，这样process方法才能作为回调方法收到消息

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
static ZooKeeper zk = null;
    static final Object mutex = new Object();
    String root;
    SyncPrimitive(String address)
            throws KeeperException, IOException {
        if(zk == null){
            System.out.println("Starting ZK:");
            zk = new ZooKeeper(address, 3000, (Watcher) this);
            System.out.println("Finished starting ZK: " + zk);
        }
    }
    public void process(WatcherEvent event) {
        synchronized (mutex) {
            mutex.notify();
        }
    }
    
      public void process(WatchedEvent watchedEvent) {
        synchronized (mutex) {
            mutex.notify();
        }
    }

WatchEvent包含的信息有：

1
WatchedEvent state:SyncConnected type:NodeChildrenChanged path:/testRoot1

Read More

By

ZooKeeper致力于开发一种能提供高可靠分布式协同的开源服务。

什么是ZooKeeper

Zookeeper是一个集中式的服务，提供配置信息维护、命名（目录）、分布式同步和组服务功能。上述服务在分布式系统中被广泛地以各种形式使用。这些服务通常伴随着大量不可避免的Bug和竞争条件。正因为上述服务的实施困难，应用程序通常在开始时会在此妥协，导致程序脆弱和难于维护。即使没有错误，不同的部署也会导致管理的复杂。

naming service 也称directory service.

协同一个分布式系统就像管理一个动物园。

ZooKeeper致力于将上述服务的必要部分提取成一组非常简单的集中协同服务API。服务本身就是分布式和高可靠的。一致性、组管理和presence协议将由服务提供，应用不必自己来实现。应用程序使用特定服务由ZooKeeper特定组件和应用程序特定convention组成。ZooKeeper提供的配方将表明这些简单服务可以用来构建强大的抽象。

ZooKeeper本身有C和Java的实现，并提供多种Client绑定，含Python Ruby和Go。

ZooKeepr概览

ZooKeeper允许分布式进程通过共享的层级的数据注册命令空间（类似文件系统）来相互协同。不同于文件系统的是，ZooKeeper为Client提供高吞吐量，低延时，高可用和顺序严格的znode存取。高性能全ZooKeeper可被用在大型的分布式系统。高可靠保证ZooKeeper不会成为系统的单点命门。严格的顺序使复杂的同步单元可在Client上实施。命名空间则非常类似标准的文件系统。

Read More