笔记本

一些Golang小技巧

2016-04-22

今天给大家介绍3个我觉得比较有启发的Golang小技巧,分别是以下几个代码片段

nsq里的select读

在nsq中,需要读取之前磁盘上的,或者是从内存中直接读取,一般人都是先判断内存中有没有数据,然而,nsq另辟蹊径使用了select语句,把CSP模式用到了极致。

源文件链接:channel.go

		select {
		case msg = <-c.memoryMsgChan:  //尝试从内存中读取
		case buf = <-c.backend.ReadChan(): //如果内存中没有,直接从磁盘上读取
			msg, err = decodeMessage(buf)
			if err != nil {
				c.ctx.nsqd.logf("ERROR: failed to decode message - %s", err)
				continue
			}

io模块中的sendfile

经过精巧的io.ReadFrom interface设计,sendfile对上层的http handler完全透明,具体调用如图所示

+----------------+
| http.ServeFile |
+--------+-------+
         |
+--------+--------+      +----------------+            +---------------------------------+
|     os.File     +------>     io.Copy    |            | http.Response                   |
+--------+--------+      +--------+-------+            | +-----------------------------+ |
         |                        |                    | | net.TCPConn                 | |
         |               +--------v-------+  2. has?   | | +-------------------------+ | |
         |               |  io.CopyBuffer +--------->  | | | io.ReadFrom             | | +-----+
         |               +--------+-------+            | | | +---------------------+ | | |     |
         |                        |                    | | | | sednfile (syscall)  | | | |     |
         |                        |                    | | | +---------------------+ | | |     |
         |                        |                    | | +-------------------------+ | |     |
         |                        |                    | +-----------------------------+ |     |
         |                        |                    +---------------------------------+     |
         |   4. do it!   +--------v------+   3. YES!                                           |
         +--------------->     syscall   <-----------------------------------------------------+
                         +----------------
  1. http模块对于文件只是简单地直接打开,获取文件描述符(file descriptor)
  2. http模块调用io.Copy函数,io.Copy函数开始检查Reader Writer是否特殊的ReadFrom,WriteTo接口
    func copyBuffer(dst Writer, src Reader, buf []byte) (written int64, err error) {
    // bla....
    // Similarly, if the writer has a ReadFrom method, use it to do the copy.
       		if rt, ok := dst.(ReaderFrom); ok {
      			return rt.ReadFrom(src)
      		}
  3. 完成判断,并直接调用net.TCPConn模块下的ReadFrom接口,里面写上了sendfile
    func (c *TCPConn) ReadFrom(r io.Reader) (int64, error) {
        		if n, err, handled := sendFile(c.fd, r); handled {
        			if err != nil && err != io.EOF {
       				err = &OpError{Op: "read", Net: c.fd.net, Source: c.fd.laddr, Addr: c.fd.raddr, Err: err}
       			}
       			return n, err
       		}
    // skipped....
    

这样io.Copy的使用者其实不知道自己默默地用了sendfile,同时又保持了接口一致性和很低的耦合度。

更深入的可以移步谢大的教程- interface

fasthttp对于header的处理

fasthttp为什么会比net.http快,其中一个原因就是fasthttp并没有完全地解析所有的http请求header数据。这种做法也称作lazy loading。首先我们从header的struct开始看起吧。

type RequestHeader struct {
        //bla.....
	contentLength      int
	contentLengthBytes []byte

	method      []byte
	requestURI  []byte
	host        []byte
	contentType []byte
	userAgent   []byte

	h     []argsKV
	bufKV argsKV

	cookies []argsKV

	rawHeaders []byte
}

可能大家都很奇怪,Request里没有string,明明method、host都可以用string啊,这是由于string是不可变类型,而从Reader中读出的[]byte是可变类型,因此,从[]byte转化为string时是有copy和alloc行为的。虽然数据量小时,没有什么影响,但是构建高并发系统时,这些小的数据就会变大变多,让gc不堪重负。

request中还有一个特殊的argsKV

type argsKV struct {
	key   []byte
	value []byte
}

其实和上面的理由是一样的,net.http中使用了map[string]string来存储各种其他参数,这就需要alloc,为了达成zero alloc,fasthttp采用了遍历所有header参数来返回,其实也有一定的考虑,那就是大部分的header数量其实都不多,而每次对于短key对比只需要若干个CPU周期,因此算是合理的tradeoff(详见bytes.Equal汇编实现 )

对于[]byte alloc的优化,可以参考Dave Cheney的《Five things that make go fast

Gopher-China-2016

2016-04-17

这个周末去参加了2016的GopherChina,总体来说,两天的会议大部分都是讲各大公司用了啥架构,没有什么可直接食用的干货,这从提问的问题就可以看出来,无非就是怎么热更新、迁移数据、而且和讲师讲的题目没有什么瓜葛。大部分的讲师都是对这个问题遮遮掩掩,只有CoreOS的工程师算是回答了一次。

我就列一下我觉得有点帮助的几个议题吧:

  1. Dave Cheney How to Write high performance application
  2. 赵畅,Grabtaxi Golang项目的测试,持续集成以及部署策略
  3. 陈辉,蚂蚁金服 Go与人工智能
  4. 邓洪超,CoreOS Go在分布式系统的性能调试和优化

其他的基本不能直接食用了,因为都是架构。再说PingCAP,TiDB确实牛、我看了他们的SQL解析代码(golex yacc)实在是天书,希望有一天,我能看懂也自己写个好玩的玩具出来。 

排序算法笔记

2016-01-23

最近在上MIT的6.006算法课,重新温习了下排序算法,发现很多知识点以前并没有吃透,也没有记下来,所以这次还是写在这里了。知之为知之,不知为不知嘛。

Insertion sort

核心

取出元素比较并插入到之前已经排好序的数组中。

例子

  1. [3 5 2 1]  # 取第二位5,比较第一3
  2. [3 5 2 1]  # 5 比 3 大, 略过
  3. [3 5 2 1]  # 取第三位2, 和第二位比较,2 比 5 小,2向前
  4. [3 2 5 1]  # 继续比较2 和 3, 2 比 3小,2向前
  5. [2 3 5 1]  # 1就重复上述步骤

代码

def insert_sort(a):
    for i in xrange(1, len(a)):
        v = a.pop(i)
        p = bisect.bisect(a[:i], v)
        a.insert(p, v)
    return a

Merge sort

核心

合并已经排好序的两个数组,哪个符合条件就添加到结果里。

合并时,对两个数组头元素作出对比,又称“两指合并”

例子

  1. [3 5] [2 1]  # 拆成两个数组,并给他们排序
  2. [3 5] [1 2]  
  3. R:[1]  Stack:[3 5] [2]  #两个数组里1 最小,添加到结果里
  4. R:[1 2]  Stack:[3 5]  # 继续比较2 和 3, 2 比 3小,2添加到结果里
  5. #就重复上述步骤

代码

def merge_sort(a):

    la = len(a)
    if la == 1:
        return a
    elif la == 2 and a[0] > a[1]:
        a[0], a[1] = a[1], a[0]
        return a
    else:
        left, right = merge_sort(a[:la/2]), merge_sort(a[la/2:])
        result = []

        while left and right:
            if left[0] < right[0]:
                result.append(left.pop(0))
            else:
                result.append(right.pop(0))

        if left:
            result += left
        if right:
            result += right

    return result

Quick sort

个人最喜欢的一个算法,简单,快速!但是对栈的调用较多~

核心

和MergeSort 很像,也是合并已经排好序的两个数组,但是是哪个符合条件就放入递归的qsort里。

可以说两个是一前一后。

代码

def qsort(a):

    la = len(a)
    if la <= 1:
        return a
    elif la == 2 and a[0] > a[1]:
        a[0], a[1] = a[1], a[0]
        return a
    else:
        lt, gt = [], []
        for x in a[1:]:
            if x > a[0]:
                gt.append(x)
            else:
                lt.append(x)
        return qsort(lt) + [a[0]] + qsort(gt)

Heap sort

核心

借助Heap(堆)的特性:最大/小的元素会在数组的头部,进行排序。

知识点

heap是一种由数组构成的特殊二叉树结构,具体在下面的思维导图里。

代码

def heap_sort(a):
    la = len(a)

    def heapify(start, end):
        father = start

        while True:
            child = father * 2 + 1
            if child > end:
                break
            if child + 1 <= end and a[child] < a[child+1]:
                child += 1
            if a[father] < a[child]:
                # swap
                a[father], a[child] = a[child], a[father]
                father = child
            else:
                break

    # la/2 -> 0
    for i in xrange((la-2)//2, -1, -1):
        heapify(i, la-1)

    # la -> 0
    for end in range(la-1, 0, -1):
        a[0], a[end] = a[end], a[0]
        heapify(0, end-1)
    return a

随机输入比较图

#数据结构与算法

2015年终总结

2015-12-28

终于又到了年末自我审查的时间了……今年就不填表了,我觉得我已经不需要这种东西来督促我学习了,毕竟目标很明确了。

今年在游戏公司算是扎下了根,带了一小段时间的后端团队(虽然只有一个成员),学到了怎么给他人做职业规划,教学,发展;也学到了不少职场上的事情。Golang也算是能信手拈来的程度了,但是对于高性能系统还是有些不知所措,比如内存池规划,TCP连接优化。架构上至少接触了点分布式的东西,但是还没有上手的感觉,毕竟需求并不是那么强烈,对于CAP、Paxos都只是停留在大致知道上,明年务必要实现过一次Paxos和raft才行。算法/数据结构上,今年简直就是LRU年,之前在Game Server里有用到,写了一个,然后跑到新团队发现,又缺一个,想着LRU反正不复杂,又写了一个……LeetCode重新捡了起来,刷了40多道而已,简单地学了些图论的东西,但是边上班边生活(其实都是些琐事,比如小区换出入证什么的)真的业余时间几乎就没有了,加上还要学车,简直快要把我给累垮了。幸好女友经常安慰,疏导我,其实对我来说,能有个人说说今天的烦恼,舒缓一下压力就已经足够,然而她给予我的更多,真的要感谢她。

今年只看了一本书--《网络游戏核心技术与实战》,讲得真得很细,对于架构上也是面面俱到,可惜,大裁员时顺手把书送给了同事,要不然,还得继续精读。

东西还是造了不少,可惜没有时间整理、总结:

参加了不少分享会,不过学到的并不多,以后看来得参加更加高端点的分享会。或者报个算法班来系统补补课?

年终总结