Wednesday, January 11, 2012

Python 不常见的实用技巧

在stackoverflow上看到有人讨论一些python的hidden feature,发现其中有几个确实还是蛮实用的。
特此摘了几个,翻译过来。

原文见http://stackoverflow.com/questions/101268/hidden-features-of-python

1 参数解包(argument unpacking)
传递list、tuple或dict对象给函数,用*或者**(字典),会自动将容器解开。例如
def show(a,b):
    print a,b
L=[1,2]

show(*L)

2 链比较
python支持链比较,例如
1<a<2

3 Decorator
通过@符号自动将一个函数封装起来,作为参数传递给另一个函数直接使用。类似宏的概念。例如

def func2(fun):
      def new_func1():
          do_sth...
          fun()
     return new_func1
@func2
def func1():
     do_sth...
在这个例子中,func1被传给func2,然后被func2的结果替换掉(即执行的是func2中的new_func1)。

4 Property
指定在某些对属性进行操作时候的触发函数,包括设置、读取和删除属性等。
property(fget=None, fset=None, fdel=None, doc=None) -> property attribute
例如
class C(object):
    def getx(self): return self.__x
    def setx(self, value): self.__x = value
    def delx(self): del self.__x
    x = property(getx, setx, delx, "I'm the 'x' property.")

5 字典的get()函数
dict类型有get()函数,跟直接用索引值取值基本用法一致,但存在如下区别,在某些时候用get()会方便。
当key不存在的时候,用索引会导致异常退出;而get则会返回None,还可已给定一个失败时的默认值。
例如
sum[value] = sum.get(value,0) + 1

6 doctest模块
该模块会自动读取各个函数doc中的命令和对应执行结果,自动化进行用例测试。例如
def factorial(n):
    """Return the factorial of n, an exact integer >= 0.

    If the result is small enough to fit in an int, return an int.
    Else return a long.

    >>> [factorial(n) for n in range(6)]
    [1, 1, 2, 6, 24, 120]
    >>> factorial(-1)
    Traceback (most recent call last):
        ...
    ValueError: n must be >= 0

    Factorials of floats are OK, but the float must be an exact integer:
    """

    import math
    if not n >= 0:
        raise ValueError("n must be >= 0")
    if math.floor(n) != n:
        raise ValueError("n must be exact integer")
    if n+1 == n:  # catch a value like 1e300
        raise OverflowError("n too large")
    result = 1
    factor = 2
    while factor <= n:
        result *= factor
        factor += 1
    return result

def _test():
    import doctest
    doctest.testmod()    

if __name__ == "__main__":
    _test()

7 省略号(Ellipsis)
一般用于高维数组中的切片,用省略号的维上表示全部。
例如
a=array([[ 1,  2,  3,  4],
       [ 5,  6,  7,  8],
       [ 9, 10, 11, 12],
       [13, 14, 15, 16]])
a[...,2]
等价于a[:,2]

8 Enumerate 
封装可迭代类型,每个元素对应到index。例如
>>> a = ['a', 'b', 'c', 'd', 'e']
>>> for index, item in enumerate(a): print index, item
...
0 a
1 b
2 c
3 d
4 e

9 for else结构
for中测试的循环正常结束后执行else。除非之前执行了break,则不执行else。例如
for i in foo:
    if i == 0:
        break
else:
    print("i was never 0")

10 iter
iter(callable, until_value)迭代调用callable,生成迭代器,一直到until_value被callable返回。

11 字典格式自动输出解析
 >>>print("The {foo} is {bar}".format(foo='answer', bar=42))
The answer is 42.

12 with语法
with open('foo.txt', 'w') as f:
    f.write('hello!')










Wednesday, December 28, 2011

云计算数据中心中的关键问题和核心技术

面向云计算的数据中心发展正是如火如荼。
在实践应用中,各个企业和云服务提供商都碰到了若干类似的问题,简单总结一下。
1 带宽保证
保证数据中心中点对点的无阻塞大容量的带宽。特别是横向流量。传统的以太网采用STP技术,极大限制了带宽资源的供应。这方面目前的解决方案,主要是融合3层的多路经技术,包括Cisco主推的TRILL标准(FabricPath核心技术),和IEEE主推的802.1aq标准(SPB)。
2 低延迟
保证任意两点之间低延迟的互通。这往往跟高带宽矛盾,因为如果采用了3层路由来实现多路经转发,自然会加大网包转发处理的复杂度(包括加减包头,计算等),造成延迟增大。因此,要在保证高带宽的前提下,还能实现低延迟,需要通盘的设计考虑。这方面的技术方案主要有Juniper主推的QFabric,号称实现点到点只有1跳转发,延迟低于5us。
3 虚拟化
包括计算资源虚拟化,存储资源虚拟化和网络资源虚拟化。前两者有大量的成熟方案,包括VMware、EMC和IBM等。对于网络资源虚拟化,目前还处在探讨和摸索阶段。主要有两个问题,一个是如何让vm接入网络,即让网络感知到vm的存在。这方面的工作包括Cisco Nexus 1000v中采用的VN-link技术,Vmware的Vcenter,Xen的Xenserver等。基本都是各家处于自身考虑,设计的私有机制。
另一个问题是如何实现网络在各层,特别是2层的虚拟化。传统Vlan仅仅支持最多4094个segment,而且扩展性差。今年8月份由Vmware和Cisco等提出的VXLAN草案,采用在3层以上搭建overley2层网络的方案,支持2^24个segment,在某种程度上能缓解vlan的缺陷。
4 管理性
数据中心中的资源复杂,特别网络架构与传统的网络不同。在引入大量的虚拟化和其他机制后,通过网络资源来协调整合计算和存储资源,对外统一提供虚拟的云资源,其复杂度要远远超越普通企业网的管理复杂度。无法管理,则意味着云计算只能是纸上谈。这方面包括Xenserver、Openstack都在做一些有意的尝试,但目前还远未到成熟可用的时候。

Monday, December 26, 2011

也谈谈TRILL

TRILL最近很火。
最早在09年的时候,就有rfc提出来,要设计一个新的协议,改进现有STP的种种问题。11年小半年时间更是连发了5个rfc出来讨论TRILL的设计和应用(6325-6327,6361,6439)。

可能有对网络不太熟悉的同学,先来介绍下STP。
STP是Spanning Tree Protocol的缩写。我们知道对于现在的局域网(LAN)来说,交换机是实现多个节点互相通信的基础。而想要连接多个LAN,就需要交换机之间能有一定的机制来互通。如果交换机拓扑中含有环,那么就可能会出现循环转发,整个网络也就容易挂掉。因此,被称为“互联网之母”的Radia Perlman大妈就跳出来设计了个STP,还因此开心的写了一首小诗。

I think that I shall never see
A graph more lovely than a tree.

A tree whose crucial property
Is loop-free connectivity.

A tree that must be sure to span
So packets can reach every LAN.

First, the root must be selected.
By ID, it is elected.

Least-cost paths from root are traced.
In the tree, these paths are placed.

A mesh is made by folks like me,
Then bridges find a spanning tree.

其实STP的理念十分简单,拓扑中有环存在不是么?我禁掉其中的某些链路,自然就没有环了(当然要具体实现还需要很多的机制和协议)。STP因为其简洁有效,成为了事实上二层网络互通的标准。当然,凡事都会有利有弊,STP的问题主要有两点,一个是仅仅用了某些链路,很可能降低网络的性能;另一个是一旦出现链路故障,重新计算STP收敛不够快。

也正是为了解决这两个问题,Radia Perlman和其他的一些专家一同又提出了TRILL。
TRILL的设计理念也十分明确,把二层和三层各自的优点都结合起来,设计一个新的2.5层的协议出来。总的想法是在每个二层网络内部用传统的二层,而在各个交换机之间采用类似三层路由的机制,来实现多路径和快速收敛等。

TRILL的提出,为实现大规模的二层网络和保持高性能的互通带来了曙光。而现代云计算数据中心的发展,更是在这两方面提出了很强的需求,这也是为何TRILL在近些年讨论的越来越多,并被Cisco等支持,还作为其面向下一代数据中心核心网络技术FabricPath中的核心技术。

话说在TRILL的rfc6325中,Radia大妈又写了一首小诗。

I hope that we shall one day see
A graph more lovely than a tree.

A graph to boost efficiency
While still configuration-free.

A network where RBridges can
Route packets to their target LAN.

The paths they find, to our elation,
Are least cost paths to destination!

With packet hop counts we now see,
The network need not be loop-free!

RBridges work transparently,
Without a common spanning tree.

让人不得不赞叹,大妈真是个人才(随便搜搜大妈的简历,就知道大妈功力之深厚)。

附:Radia大妈照



Sunday, December 11, 2011

关于SDN和未来云计算数据中心的报告

昨天,在首届SDN和数据中心技术研讨会上,我做了一个报告,给与会的各位专家介绍SDN相关技术和其在新一代数据中心中的应用,以及我对未来云计算发展方向的展望。
在报告中主要提出两个核心的理念。
一是关于信息技术从性能阶段往智能阶段的转变。
人类文明的发展,基础是对各种新技术的应用。而对任何新技术的应用大体可以分为两个阶段。第一阶段是简单依赖新技术变革带来的生产力飞跃,是一种粗放式的增长模式,可以称为性能主导阶段。而这种粗放式的模式必定会碰到瓶颈。一方面是对技术自身潜力的挖掘总有限制,在性能主导阶段,性能提升的代价必然是越来越大的,到了后面,这种代价可能已经超越了性能提升本身带来的收益。再一方面是人对新技术的需求,是越来越多的,简单的性能增长并不能满足所有需求。因此,过了性能主导阶段,必然会寻求一种更为精细化的阶段,可以称为智能主导阶段。以印刷术为例,开始是整版印刷,工人不断提升刻板速度,改进版面质量,但很快就变得难以继续提升了。这个时候就需要向智能化方向发展——活字印刷也就出现了。往往,在智能化阶段,孕育着更新一代技术的种子。此前的时期石器时代到电气时代,无不如此。而现在的信息时代,实际上已经到了性能主导阶段的后期,社会对智能化的需求也来越强烈。从生活中,我们也可以慢慢体会到这点。nokia破落,iphone大卖;汇编绝迹,C#盛行;pc收缩,平板兴起;甚至手动档已经越来越少见,自动档越来越流行,都证明了这点。这些年云计算的流行、社交网络、移动应用的兴起,也都是因为这个原因。所以,我预言,智能相关技术,特别是人工智能,春天已经到来了。而SDN的相关技术,恰好是智能化网络的一个很好的例子。
另外一个观点就是对于未来云计算数据中心的发展方向。
这个问题我也多次想过,这次算是有了个比较清晰的想法。我认为,未来的数据中心至少要具备两个基本特征。一是必须是性能(带宽、延迟)与智能(绿色、管理、配置、可靠、安全)需求都要能满足。二是必须是实现真正的完全虚拟化。当前的数据中心,其实并没有实现完全的虚拟化,无论提供的是iaas,paas,还是saas,都是针对用户的需求进行了深度的定制。一个提供saas的datacenter,很难同时服务需要其他xaas的用户。这个问题出在哪里?就出现在网络上,因为datacenter中的三个基本元素,计算、存储、网络,前两者的虚拟化都已经实现,唯独网络的虚拟化,最近几年才开始相关研究。未来的datacenter中,所有的资源,不论是什么类型,都应该统一的虚拟化,为“虚资源”。用户需要什么样的服务,就用这些“虚资源”组织起来,满足成能满足用户需求的形式。
以上两点想法,不知道是否是由我最早提出来的,但我坚信,都会被逐渐证实。

Wednesday, November 23, 2011

从数楼层问题到最大熵原理

先来看一道智力题目。
有2个鸡蛋和100层楼。可以站在某层往下扔鸡蛋,问尝试多少次,可以一定能获知在哪一层的时候刚好让鸡蛋碎。

——————分割线,请先自行思考30s————————

初看此题,可能认为答案是100。很自然,挨着试呗。
我们假设第k层(k=1...100)的时候鸡蛋刚好碎,那么从第一层开始依次往上是最保险的。因为一旦一开始某次尝试的楼层>k,则鸡蛋碎掉。
当我们手头只有一个鸡蛋的时候,确实只能采取这种方法,因为我们不知道k,不能去冒险。但是,现在有2个鸡蛋,能否减少尝试的次数?
毫无疑问,肯定是可以减少的,比如我们在第50层扔下来第一个鸡蛋,如果碎了,说明k<=50,然后从1...49挨着试第二个即可,最多需要50次(1次第一个,49次第二个)。如果第一个鸡蛋没碎,说明k>50,再用这两个鸡蛋尝试剩下的51...100楼层即可。
那么最优解是多少呢?
仔细思考这个问题,我们尝试扔鸡蛋有两种方法,一种是可以冒险猜一层,一种是挨着保险的线性尝试。对于第一个鸡蛋来说,冒险或者保险都可以。问题在于,一旦第一个鸡蛋碎了,则我们手头就只剩下一个鸡蛋了,这个时候就不能冒险了,只能采取保险的线性方法。因此,关键在于第一个鸡蛋应该采取什么样的策略?冒险还是保险?

——————分割线,请再自行思考30s————————

先暂时把刚才的问题放到一边,我们来看“最大熵原理”。
“最大熵原理是在1957 年由E.T.Jaynes 提出的,其主要思想是,在只掌握关于未知分布的部分知识时,应该选取符合这些知识但熵值最大的概率分布。”
这段话来自百度百科,未必是最准确的定义,但意思已经讲透了。熟悉信息论的同仁相比已经理解了。
用大白话解释这段话,就是说,如果我们不知道足够多的信息,那么对于不知道的部分应该采取最保守的策略,不能添加任何的先验预测。
或者更直白点,如果不知道,千万不要蒙。
一个很平凡的例子就是掷骰子。假如实现你对这个骰子一无所知,请问它掷的结果该是什么样子的?很显然,大家都会说,六个面概率一样,肯定都是1/6.
那么现在告诉你它掷出来1的概率是1/2,那么结果是啥?因为我们只知道1的概率,对其他面依然一无所知,所以,六个面的概率只能是(1/2,1/10,1/10,1/10,1/10,1/10),即剩下的五个面应该是彼此均匀等价的。
回到我们的问题,我们在扔第一个鸡蛋的时候,假如我们选择了第N层作为第一次扔的层数,则有两个可能:
N >= k: 鸡蛋1碎,鸡蛋2可以线性查找1...N-1层,一共需要1+N-1=N次。
N<k: 鸡蛋2没有碎,我们在N+1...100层中解决同一个问题,但是扔的次数少了1.
按照最大熵原理,因为我们不知道任何事先的信息,这两种选择的概率都是等价的,我们要求得最优,就只能让它俩带来的代价一致,也即我们应当选择N,使得无论那种情形发生,我们最终的尝试次数都是一致的。
对于N >= k的情况,一共需要N次,所以对于N<k的情况一共也必须是N次才成。则我们在N+1...100中解决问题,所尝试的次数应当为N-1,此时我们已经成功排除了N层.
可以观察到类似的决策中,从第一次到第N次,我们依次排除了N, N-1, ...1层。
所以我们有
N+N-1+...+1 = 100,或者
N(N+1)/2 =100
容易求得N=14

就是按照这样一个平凡的基本原理,我们求出了这个问题的最优解。实际上,从最大熵原理出发,可以推出近现代信息学上一堆著名的公式和方法,比如大名鼎鼎的卡尔曼滤波器,比如人工智能中的语义分析。或许,越是简单自然的东西,越能反映出这个世界终极的秘密吧。

备注:
这道问题是一个朋友出给我的,我想了大约一分钟,就想透了其中的关键。问题本身并不难,但其解决思路却蕴含了一个基本的原理——最大熵。这或多或少让我感到意外和惊喜。

扩展思考,
一般的,如果我们手头有m个鸡蛋,去尝试n层楼,需要试多少次?