Skip to content

Golang与树莓派

最近买了个树莓派3b,本来是做下载机用的,但是发现在上面写Go代码,编译,其实和在一般机器上的体验是一样的。

不过树莓派本身有其他电脑没有的玩法,那就是GPIO的支持,配合Go-gpio库,就可以控制这些接口

下面是一个简单的跑马灯+CPU温度探测程序

因为没加散热片……所以温度有点高┐( ̄ヮ ̄)┌

代码如下,根据/sys下的温度文件读数值,另一个是根据负载改变闪烁的频率。

很简单,所以我就不加注释了:)至于为啥叫jurassic,因为侏罗纪公园的电网就是蓝橙指示灯,然后写代码的胖子就被吃掉了

package main
import (
"fmt"
"io/ioutil"
"strconv"
"time"
"runtime"
"github.com/stianeikeland/go-rpio"
"github.com/shirou/gopsutil/load"
)
const (
BLUE = 20
ORANGE = 21
CORE_TEMP_PATH = "/sys/class/thermal/thermal_zone0/temp"
)
func init(){
runtime.GOMAXPROCS(1)
}
func main() {
fmt.Printf("System initial...")
if rpio.Open() == nil{
fmt.Println("[OK]")
} else {
fmt.Println("[ERROR]")
}
defer rpio.Close()
orange := rpio.Pin(ORANGE)
blue := rpio.Pin(BLUE)
orange.Output()
blue.Output()
orange.Low()
blue.High()
for {
stat, err := load.Avg()
if err != nil {
fmt.Println(err)
break
}
interval := int(stat.Load1)
if stat.Load1 < 1 {
interval = 1
}
fmt.Printf("Load1:%.2f Temp:%.2f'C", stat.Load1, loadTemp())
time.Sleep(time.Millisecond * time.Duration(interval * 900))
blue.Toggle()
orange.Toggle()
fmt.Printf("\r")
}
}
func loadTemp() float64 {
b, err := ioutil.ReadFile(CORE_TEMP_PATH)
if err != nil {
return -1000
}
raw, err := strconv.ParseFloat(string(b[:len(b)-2]), 64)
if err != nil {
fmt.Println(err)
return -1001
}
return raw/100
}

小窥Go ast库及初步使用

本文需要你有写Golang代码经验,阅读大概需要20分钟。

最近一直在研究Go的依赖注入(dependency
injection)
,方便日后写比较容易测试的代码(以便偷懒)。目前学到ast解析代码,现拿出来跟大家分享一下:)

Tokenizer 和 Lexical anaylizer

如果你知道tokenizer和lexical anaylizer是什么的话,请跳到下一章,不熟的话请看下面这个最简单的go代码

package main
func main() {
println("Hello, World!")
}

这段go代码做了什么?很简单吧,package是main,定义了个main函数,main函数里调用了println函数,参数是"Hello,
World!"。好,你是知道了,可当你运行go
run时,go怎么知道的?go先要把你的代码打散成自己可以理解的构成部分(token),这一过程就叫tokenize。例如,第一行就被拆成了package和main。
这个阶段,go就像小婴儿只会理解我、要、吃饭等词,但串不成合适句子。因为"吃饭我要"是讲不通的,所以把词按一定的语法串起来的过程就是lexical
anaylize或者parse,简单吧!和人脑不同的是,被程序理解的代码,通常会以abstract syntax
tree(AST)的形式存储起来,方便进行校验和查找。

Go的AST

那我们来看看go的ast库对代码的理解程度是不是小婴儿吧(可运行的源代码在此),其实就是token+parse刚才我们看到的上一章代码,并且按AST的方式打印出来,结果在这里

package main
import (
"go/ast"
"go/parser"
"go/token"
)
func main() {
// 这就是上一章的代码.
src := `
package main
func main() {
println("Hello, World!")
}
`
// Create the AST by parsing src.
fset := token.NewFileSet() // positions are relative to fset
f, err := parser.ParseFile(fset, "", src, 0)
if err != nil {
panic(err)
}
// Print the AST.
ast.Print(fset, f)
}

为了不吓到你,我先只打印前6行:

 0 *ast.File {
1 . Package: 2:1
2 . Name: *ast.Ident {
3 . . NamePos: 2:9
4 . . Name: "main"
5 . }
// 省略之后的50+行

可见,go
解析出了package这个关键词在文本的第二行的第一个(2:1)。“main"也解析出来了,在第二行的第9个字符,但是go的解析器还给它安了一个叫法:ast.Ident,
标示符 或者大家常说的ID,如下图所示:

Ident +------------+
|
Package +-----+ |
v v
package main

接下来我们看看那个main函数被整成了什么样。

 6 . Decls: []ast.Decl (len = 1) {
7 . . 0: *ast.FuncDecl {
8 . . . Name: *ast.Ident {
9 . . . . NamePos: 3:6
10 . . . . Name: "main"
11 . . . . Obj: *ast.Object {
12 . . . . . Kind: func
13 . . . . . Name: "main"
14 . . . . . Decl: *(obj @ 7)

此处func main被解析成ast.FuncDecl(function
declaration),而函数的参数(Params)和函数体(Body)自然也在这个FuncDecl中。Params对应的是*ast.FieldList,顾名思义就是项列表;而由大括号”{}“组成的函数体对应的是ast.BlockStmt(block
statement)。如果不清楚,可以参考下面的图:

 FuncDecl.Params +----------+
|
FuncDecl.Name +--------+ |
v v
+----------------------> func main() {
| +->
FuncDecl ++ FuncDecl.Body +-+ println("Hello, World!")
| +->
+----------------------> }

而对于main函数的函数体中,我们可以看到调用了println函数,在ast中对应的是ExprStmt(Express
Statement),调用函数的表达式对应的是CallExpr(Call
Expression),调用的参数自然不能错过,因为参数只有字符串,所以go把它归为ast.BasicLis (a literal of basic
type)。如下图所示:

+-----+ ExprStmt +---------------+
| |
| CallExpr BasicLit |
| + + |
| v v |
+---> println("Hello, World!")<--+

还有什么?

 50 . Scope: *ast.Scope {
51 . . Objects: map[string]*ast.Object (len = 1) {
52 . . . "main": *(obj @ 11)
53 . . }
54 . }
55 . Unresolved: []*ast.Ident (len = 1) {
56 . . 0: *(obj @ 29)
57 . }
58 }

我们可以看出ast还解析出了函数的作用域,以及作用域对应的对象。

小结

Go将所有可以识别的token抽象成Node,通过interface方式组织在一起,它们之间的关系如下图示意:

监控入门: 收集正确的数据

本文为Datadog《[monitoring 101:collecting the right
data](https://www.datadoghq.com/blog/monitoring-101-collecting-
data/)》的中文翻译,有部分删减。原作者:Alexis Le-Quoc

本文是关于有效地监控系统的系列文章之一。敬请关注本系列的其它文章《有关的,才告警》和《调查性能问题》(译注:后续会翻译)。

监控的数据有多种形式—-
有些系统持续地输出数据而另一些是在罕见事件发生时产出数据。有些数据对于定位问题十分有用;而另一些则在调查问题时起主导地位。(译注:分别对应错误日志,性能日志)。本文涵盖了什么数据需要收集,以及如何对数据进行分类,读完后你就能:

  1. 对于潜在的问题接受有意义的,自动化的警告
  2. 进行快速调查并追查到性能问题的根源

不管你监控的数据形式如何,不变的主题是

收集的监控数据平时是没啥用,但是如果在你需要的时候你却没收集到,那监控数据就是宝贵且昂贵的,因此你需要尽可能地插手一切系统,收集你能收集到的一切的合理的数据。

监控(Metrics)

监控捕获的是系统在特定时间点上的有关数值—-举个例子,当前登入你web应用的用户总数。因此,监控常常设定在每秒、每分或其它常规间隔时间收集一次数据。

在我们的监控框架中有两个重要的分类:工况监控(work metrics)和资源监控(resource
metrics)。每一个系统都是你软件的基础设施,对工况和资源监控都是合理的需求,请把他们都收集起来。

工况指标

工况通过有意义的输出数据,揭示了系统的顶层健康状况。当你给工况指标分类时,将它们分成4小类会相当有帮助:

  • 吞吐量(throughput) 是系统在单位时间内的工作量,常常用绝对值表示。
  • 成功(success) 显示所有工作中成功的百分比。
  • 失败(error) 捕获了失败的结果,常常是单位时间内的失败率或者是由吞吐量归一化(normalized)。失败的结果常常与成功的分别对待,因为它们是潜在的错误来源,可能是更严重的问题,而且处理起来也比成功的结果更加容易。
  • 性能(performance) 监控着组件的工作效率高不高。最常见的性能指标就是完成所有操作需要的时间—-延迟时间(latency)。延迟时间常常用平均数或百分点(percentile)表示,例如:“99%的请求在0.1秒内完成”。

下面是web服务器和数据存储应用中常见的工况指标例子。

Example work metrics: Web server (at time 2015-04-24 08:13:01 UTC)

Subtype Description Value
throughput requests per second (每秒请求数) 312
success percentage of responses that are 2xx since last measurement(距上次测量时2xx返回值的百分比) 99.1
error percentage of responses that are 5xx since last measurement 0.1
performance 90th percentile response time in seconds (90%的请求响应时间) 0.4

Example work metrics: Data store (at time 2015-04-24 08:13:01 UTC)

Subtype Description Value
throughput queries per second 949
success percentage of queries successfully executed since last measurement 100
error percentage of queries yielding exceptions since last measurement 0
error percentage of queries returning stale data since last measurement 4.2
performance 90th percentile query time in seconds 0.02

资源指标

对于其它系统来说,大部分的组件都是你软件基础设施都是它们的资源。有些资源是底层的—-
例如,一台服务器的资源包括的物理组件有CPU,内存,磁盘和网络接口。但是高层组件,如数据库或地理位置服务,也可以看成是其它系统正常工作所需的资源。

资源监控对于调查问题常常是非常有价值的。对于每个资源项,你应该尽力地收集4个关键领域:

  1. 使用率(utilization) 是资源忙/闲时的百分比或者是资源总量的使用率。
  2. 饱和量(saturation) 已经请求的、但是尚未处理的工作,通常是队列。
  3. 错误(errors) 表示的是系统运转过程中也许无法侦测到的内部错误。
  4. 可用率(availability) 表示请求返回总数中正常的百分比。这个指标仅仅在资源可被定期地检查才可以用。

下面是一个对于常见资源类型的资源监控:

Resource Utilization Saturation Errors Availability
Disk IO % time that device was busy wait queue length # device errors % time writable
Memory % of total memory capacity in use swap usage N/A (not usually observable) N/A
Microservice average % time each request-servicing thread was busy #enqueued requests # internal errors such as caught exceptions % time service is reachable
Database average % time each connection was busy # enqueued queries #internal errors, e.g. replication errors % time database is reachable

其它指标

还有一些指标既不是资源也不是工况,但是对于诊断问题根源很有用。常见的例子有缓存的命中率和数据库的锁数量。有疑问时,收集它们。

事件

对于指标的监控或多或少都是持续地进行的。有些监控系统还可以捕获事件:分离的,无规律的,对于了解什么改变了你系统的行为提供了关键的上下文。一些例子:

  • 变更:内部代码发布,构建和构建失败
  • 警告:应用内部产生的警告或者第三方通知
  • 缩扩容: 添加或者减少服务器

一个事件常常携带了足以能解释自己的信息,不像其它数据指标,只能提供一个大概的环境。合理的事件包含了,发生了什么,在什么时候,附带信息。这里有些例子:

What happened Time Additional information
Hotfix f464bfe released to production 2015-05-15 04:13:25 UTC Time elapsed: 1.2 seconds
Pull request 1630 merged 2015-05-19 14:22:20 UTC Commits: ea720d6
Nightly data rollup failed 2015-05-27 00:03:18 UTC Link to logs of failed job

事件有时用来生成警告—-像上表中第三行,有人应该收到通知,关键的任务失败了。但更通常的情况下,事件用来调查跨系统的问题。总之,把事件当指标—-
它们有价值,能收集的尽量收集。

好的监控数据长啥样

得有四个特性:

  • 易懂 你应当能快速地由数据像分析出指标或者捕获的事件。在系统不可用的时候,你估计已经不想猜测你的数据意味着什么了,所以尽量简单明了地保存这些数据,用刚才的概念来命名你的数据。
  • 粒度合适 (granular)如果你设置过长或者过短的收集窗口事件,你很有可能失去关于系统行为的重要数据。例如,平时使用量比较低的系统,在资源100%使用的时候会让你费解。以对系统没有巨大影响的情况下收集数据,否则监控系统就成了"税务"负担(详见observer effect)或者由于过短的收集间隔给数据带来噪音。
  • 按域打标签 (Tagged by scope)每一台你的服务器都是同时属于某个特定域的,你很有可能需要按域查检服务的健康情况,或者是综合起来。例如:生产环境现在的健康状况如何?北美的生产环境呢?特定的软硬件组合的情况下呢?保存数据所属的域是重要的,因为你可能会从任意域收到警告,并能按域快速展开服务不可用的调查,而不仅仅限制于特定机器。
  • 长时间保存。如果你过早地丢弃的,或者为了节省存储费用丢弃了数据,那么你就失去了关于过去的重要信息。保存一年以内的数据,你能知道系统正常情况下是什么样子的,特别是监控数据有每月、每季度、年度的波动时。

为了告警和诊断的数据

下面有张关于不同等级警告的描述和它们的紧急程度。简单来说,低等级的告警时不需要通知任何人的,只需要记录在案以便不时之需。一个通知(notification)等级的警告算是中等级的,可以通过不打断人工作的方式通知,例如邮件或者聊天室。一个Page(译注:寻呼机)等级的告警是十分紧急的,需要立即有人工参与,不管维护的人是在睡觉还是享受个人时光。

Data Alert Trigger
Work metric: Throughput Page value is much higher or lower than usual, or there is an anomalous rate of change
Work metric: Success Page the percentage of work that is successfully processed drops below a threshold
Work metric: Errors Page the error rate exceeds a threshold
Work metric: Performance Page work takes too long to complete (e.g.,performance violates internal SLA)
Resource metric: Utilization Notification approaching critical resource limit (e.g., free disk space drops below a threshold)
Resource metric: Saturation Record number of waiting processes exceeds a threshold
Resource metric: Errors Record number of errors during a fixed period exceeds a threshold
Resource metric: Availability Record the resource is unavailable for a percentage of time that exceeds a threshold
Event: Work-related Page critical work that should have been completed is reported as incomplete or failed

总结:全收了

  • 尽可能多地收集数据,包括工况、资源和各种事件。
  • 以合适的粒度收集数据,以便发现波峰或者波谷。这个粒度取决于你要监控的系统,时常变化的数据—-CPU,内存,能量消耗都是典型的要收集的。
  • 让你的数据发挥最大化的价值,包括标签,事件,完整地保留至少一年

几个Go新手易犯的错误

最近跟新同事做code review,发现组里的小朋友犯了一些几个新手错误,想想自己以前也犯过这些错,分享给大家,希望大家看完以后可不要犯咯。

  1. 跨goroutine读写不加锁
  2. 文件打开后不关闭
  3. 滥用string方法
  4. channel死锁
  5. 不用合适的方法做事
  6. 文件整个读取进内存

跨goroutine读写不加锁

这个是最常见的错误,很多小朋友并没有并发编程的思想,对于同一个内存空间进行同时读写,例如大家可以猜猜这段代码的执行结果:

func main() {
c := make(chan bool)
m := make(map[string]string)
go func() {
m["1"] = "a" // 第一次冲突访问
c <- true
}()
m["2"] = "b" // 第二次冲突访问
<-c
for k, v := range m {
fmt.Println(k, v)
}
}

代码出自Golang官方博客《Data Race
Detector
》,结果是,我也不知道!因为这是运行时(runtime)决定的,运气好时,ab都有,要是倒霉时,只有a或者b,这也就是为什么代码在这种地方需要加锁了(sync.Mutex),因为要保证同时有且只有一个goroutine能访问这个map对象。

同时推荐一本好书《七周七并发模型》,里面详细的描述了这种并发方式,锁模式,而Go推荐的CSP模式,再开一篇文章来讲了。

文件打开后不关闭

file, err := os.Open("file.go") // For read access.
if err != nil {
log.Fatal(err)
}

很多小朋友写到这,就继续写业务其他的代码,殊不知在这里埋下了一个祸根,当打开的文件过多时,很有可能触发too many open
files的系统错误。要知道,*nix系统中,一切皆文件,所以当你触发这个错误时,可能不仅仅是文件打开过多,而是整个程序陷入崩溃。那怎么改呢,很简单,Go官方还专门出了一个语句来帮助大家
—-就是defer

file, err := os.Open("file.go") // For read access.
if err != nil {
log.Fatal(err)
}
defer file.Close() //在这里添加defer语句

滥用string方法

如果要你拼接两个字符串,“foo"和"bar”,你会怎么做?常见的做法是:

a, b := "foo", "bar"
c := a + b

既然这个做法自然是错的,可是为什么呢?
因为Go的字符对象是不可变的,意味着每一个新对象都是新的内存空间,当越来越多时,gc一定会不堪重负的。那map对象怎么办?map[[]byte]interface{}这样的结构编译器是不认的,Go官方给出了一个编译器级的优化

m := map[string]string
b := []byte("hello")
m[string(b)] = "world" //注意这个string方法,只能用在这里
/*
这么做一样会分配c的内存空间
c := string(b)
m[c] = "world"
*/

channel死锁

r := make(chan int, 1)
r <- 2
r <- 3 // 代码似乎只执行到这了
<-r

很多新手都在这里问:“go不是号称轻量级纤程么,怎么卡住呢?",而且在Go 1.6
runtime会直接报出panic。那是因为这个channel已经固定数量了,如果channel内的数据不被消耗,那么这个负责输入的goroutine就会一直卡在r<-3那里,直到channel中的2被取走。

小结

前三个错误我工作中都已经碰到过4次以上,绝大多数都是编程新手犯的错误,不仅仅局限于Go,每次都要花半个小时给新人讲,这下可以丢文章给他们了。而剩下的两个我就不讲了,因为用atoi转化unix
timestamp,不是用time库的人并不多……把整个文件读到buffer中,很容易就会发现内存超量了……

希望对大家有帮助,欢迎来@mengzhuo里面的提问题或者吐槽~

一些Golang小技巧

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

  • nsq里的select写文件和socket
  • io模块里的sendfile
  • fasthttp里对header的处理

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)
}
  1. 完成判断,并直接调用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](https://github.com/astaxie/build-web-application-
with-golang/blob/master/zh/02.6.md)

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

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

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

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

排序算法笔记

最近在上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年终总结

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

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

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

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

  • 一个基于Onehop的去中心、分布式的KV数据库
  • 花了两周业余写了这个博客程序 bla
  • ucloud sdk
  • justrpc --jsonrpc v1 的python 实现

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

#年终总结

Bla — another static blog app

After 2 weeks working on my pet project, I’m glad to say that Bla is ready at
the stage of MVP(minimum viable product).

  • Fully static file serving
  • WYSIWYG (No markdown or offline editing)
  • Tag/Relation finding
  • Golang blog style template
  • Easy deploy with no php, no Mysql (only golang)

Other highlights:

  • automatically reload on content/template/config change
  • support TLS

Simple Tutorial

go get -u github.com/mengzhuo/bla/cmd/bla

bla new

edit your configure file “bla.config.json” and just run bla

Github repo:

github.com/mengzhuo/bla

某项目上线及事故总结

EW4终于在中国iOS顺利上线了,虽然我已经被调到其他项目组,但是也经历了上线加班调试到4点的情况。所用的技术栈其实在招聘页面都有,所以不算泄密。

事故总是由看似无关紧要的小错误累积而成的。

整个系统架构上是一般的二代网游架构,大问题没啥,但是登入服务赶新潮地依赖了DynamoDB这个SLA号称在线率三个9的玩意。可是偏偏在正式上线前三天us
east1的数据中心写故障!这时IT团队试图从us east1迁到us
east2,顺利的迁移完了,结果再次中了彩票,east2也故障了!这简直是可以买彩票的节奏!!反正数据还没迁完,IT团队就再次修改了配置指向east1,由于此前迁移没有进行过演练,所有配置的更改都是手动操作的,所以有台负责处理连接的节点没有更新,埋下了祸根:这个节点不停地对登入节点上报错误的地址,但由于ELB的关系,这个错误在人工测试的阶段都没有察觉到。
这时,悄然开服的消息已经传遍了骨灰玩家圈,玩家纷纷开始登入注册。

大概是下午开始,客服陆续收到玩家投诉说丢档了!但错误收集sentry并没有报告什么异常,顿时我就纳闷了,难道是DynamoDB又出了问题?但,这次,并不是,只好继续排查代码上的问题。一波未平一波又起,之前给各个安卓运营商上线之后一直正常,但是现在某运营商那边的玩家投诉无法登入,美国上线的负责人也表示自己无法登入,这时整个团队都非常沮丧,因为错误收集系统压根就没有错误报告。IT团队开始一遍又一遍地切换DynamoDB的数据库、登入服务的配置来查错,这时已经是凌晨4点了,估计因为在线人数下降了,ELB自动分配到了一台机子上,所有人又能正常登入了。王总提出让一部分人休息,明天好继续排错,所以我回家休息了。
结果第二天来时,美国团队的人通过debug
客户端,发现本来该指向US的节点,竟然给出了中国区的服务器地址!大家顿时恍然大悟,有台机子在上报错误的地址!!于是IT团队用昨晚写好的部署程序,重新部署了所有大区服务,登入问题就都解决了。
接下来就是无法下载的问题,客户端的同事发现是更新用的服务下载到了不同的数据更新包导致的,不过所幸只是一个小国的部分用户……
这次事故,其实说实话是完全可以避免的。

  • DynamoDB出故障是意外,但是我们服务器团队没有跟IT部门交代清楚配置,导致上报的密钥还是开发时的TEST_KEY是根本原因
  • 服务器并没有完整的校验机制、机器人、最后线上bug还得手动测试,浪费了很多宝贵的时间
  • 对于代码,各种需求变更过快、没有足够的人手做完UT,导致排查代码也花费了大量的时间
  • IT团队也没有及时地做好自动化部属工作、加上2日的操劳、同事们出错也是在所难免
  • 客户端团队对于数据更新包的需求也没有弄清楚就急忙开发,导致下载到了不同的数据更新包。

p.s.通过这次排查代码,我发现系统里还有不少因为加新功能而加的补丁,重构看来也是不可避免了。