基于 JWT + Refresh Token 的用户认证实践

HTTP 是一个无状态的协议,一次请求结束后,下次在发送服务器就不知道这个请求是谁发来的了(同一个 IP 不代表同一个用户),在 Web 应用中,用户的认证和鉴权是非常重要的一环,实践中有多种可用方案,并且各有千秋。

基于 Session 的会话管理

在 Web 应用发展的初期,大部分采用基于 Session 的会话管理方式,逻辑如下。

  • 客户端使用用户名密码进行认证
  • 服务端生成并存储 Session,将 SessionID 通过 Cookie 返回给客户端
  • 客户端访问需要认证的接口时在 Cookie 中携带 SessionID
  • 服务端通过 SessionID 查找 Session 并进行鉴权,返回给客户端需要的数据

基于 Session 的方式存在多种问题。

  • 服务端需要存储 Session,并且由于 Session 需要经常快速查找,通常存储在内存或内存数据库中,同时在线用户较多时需要占用大量的服务器资源。
  • 当需要扩展时,创建 Session 的服务器可能不是验证 Session 的服务器,所以还需要将所有 Session 单独存储并共享。
  • 由于客户端使用 Cookie 存储 SessionID,在跨域场景下需要进行兼容性处理,同时这种方式也难以防范 CSRF 攻击。

基于 Token 的会话管理

鉴于基于 Session 的会话管理方式存在上述多个缺点,无状态的基于 Token 的会话管理方式诞生了,所谓无状态,就是服务端不再存储信息,甚至是不再存储 Session,逻辑如下。

  • 客户端使用用户名密码进行认证
  • 服务端验证用户名密码,通过后生成 Token 返回给客户端
  • 客户端保存 Token,访问需要认证的接口时在 URL 参数或 HTTP Header 中加入 Token
  • 服务端通过解码 Token 进行鉴权,返回给客户端需要的数据

基于 Token 的会话管理方式有效解决了基于 Session 的会话管理方式带来的问题。

  • 服务端不需要存储和用户鉴权有关的信息,鉴权信息会被加密到 Token 中,服务端只需要读取 Token 中包含的鉴权信息即可
  • 避免了共享 Session 导致的不易扩展问题
  • 不需要依赖 Cookie,有效避免 Cookie 带来的 CSRF 攻击问题
  • 使用 CORS 可以快速解决跨域问题

JWT 介绍

JWT 是 JSON Web Token 的缩写,JWT 本身没有定义任何技术实现,它只是定义了一种基于 Token 的会话管理的规则,涵盖 Token 需要包含的标准内容和 Token 的生成过程。

一个 JWT Token 长这样。

1
eyJhbGciOiJIUzI1NiIsInR5cCI6IkpXVCJ9.eyJleHAiOjE1NDQ1MTE3NDMsImp0aSI6IjYxYmVmNjkyLTE4M2ItNGYxYy1hZjE1LWUwMDM0MTczNzkxOSJ9.CZzB2-JI1oPRFxNMaoFz9-9cKGTYVXkOC2INMoEYNNA

仔细辨别会发现它由 A.B.C 三部分组成,这三部分依次是头部(Header)、负载(Payload)、签名(Signature),头部和负载以 JSON 形式存在,这就是 JWT 中的 JSON,三部分的内容都分别单独经过了 Base64 编码,以 . 拼接成一个 JWT Token。

JWT 的 Header 中存储了所使用的加密算法和 Token 类型。

1
2
3
4
{
"alg": "HS256",
"typ": "JWT"
}

Payload 是负载,JWT 规范规定了一些字段,并推荐使用,开发者也可以自己指定字段和内容,例如下面的内容。

1
2
3
4
5
6
{
username: 'yage',
email: 'sa@simpleapples.com',
role: 'user',
exp: 1544602234
}

需要注意的是,Payload的内容只经过了 Base64 编码,对客户端来说当于明文存储,所以不要放置敏感信息。

Signature 部分用来验证 JWT Token 是否被篡改,所以这部分会使用一个 Secret 将前两部分加密,逻辑如下。

1
HMACSHA256(base64UrlEncode(header) + "." + base64UrlEncode(payload), secret)

JWT 优势 & 问题

JWT 拥有基于 Token 的会话管理方式所拥有的一切优势,不依赖 Cookie,使得其可以防止 CSRF 攻击,也能在禁用 Cookie 的浏览器环境中正常运行。

而 JWT 的最大优势是服务端不再需要存储 Session,使得服务端认证鉴权业务可以方便扩展,避免存储 Session 所需要引入的 Redis 等组件,降低了系统架构复杂度。但这也是 JWT 最大的劣势,由于有效期存储在 Token 中,JWT Token 一旦签发,就会在有效期内一直可用,无法在服务端废止,当用户进行登出操作,只能依赖客户端删除掉本地存储的 JWT Token,如果需要禁用用户,单纯使用 JWT 就无法做到了。

基于 JWT 的实践

既然 JWT 依然存在诸多问题,甚至无法满足一些业务上的需求,但是我们依然可以基于 JWT 在实践中进行一些改进,来形成一个折中的方案,毕竟,在用户会话管理场景下,没有银弹。

前面讲的 Token,都是 Access Token,也就是访问资源接口时所需要的 Token,还有另外一种 Token,Refresh Token,通常情况下,Refresh Token 的有效期会比较长,而 Access Token 的有效期比较短,当 Access Token 由于过期而失效时,使用 Refresh Token 就可以获取到新的 Access Token,如果 Refresh Token 也失效了,用户就只能重新登录了。

在 JWT 的实践中,引入 Refresh Token,将会话管理流程改进如下。

  • 客户端使用用户名密码进行认证
  • 服务端生成有效时间较短的 Access Token(例如 10 分钟),和有效时间较长的 Refresh Token(例如 7 天)
  • 客户端访问需要认证的接口时,携带 Access Token
  • 如果 Access Token 没有过期,服务端鉴权后返回给客户端需要的数据
  • 如果携带 Access Token 访问需要认证的接口时鉴权失败(例如返回 401 错误),则客户端使用 Refresh Token 向刷新接口申请新的 Access Token
  • 如果 Refresh Token 没有过期,服务端向客户端下发新的 Access Token
  • 客户端使用新的 Access Token 访问需要认证的接口

将生成的 Refresh Token 以及过期时间存储在服务端的数据库中,由于 Refresh Token 不会在客户端请求业务接口时验证,只有在申请新的 Access Token 时才会验证,所以将 Refresh Token 存储在数据库中,不会对业务接口的响应时间造成影响,也不需要像 Session 一样一直保持在内存中以应对大量的请求。

上述的架构,提供了服务端禁用用户 Token 的方式,当用户需要登出或禁用用户时,只需要将服务端的 Refresh Token 禁用或删除,用户就会在 Access Token 过期后,由于无法获取到新的 Access Token 而再也无法访问需要认证的接口。这样的方式虽然会有一定的窗口期(取决于 Access Token 的失效时间),但是结合用户登出时客户端删除 Access Token 的操作,基本上可以适应常规情况下对用户认证鉴权的精度要求。

总结

JWT 的使用,提高了开发者开发用户认证鉴权功能的效率,降低了系统架构复杂度,避免了大量的数据库和缓存查询,降低了业务接口的响应延迟。然而 JWT 的这些优点也增加了 Token 管理上的难度,通过引入 Refresh Token,既能继续使用 JWT 所带来的优势,又能使得 Token 管理的精度符合业务的需求。

关注Python私房菜

通过 ngrok 实现 ssh 内网穿透

ngrok

用 ssh 访问一台主机,如果和主机在一个局域网中或者主机拥有公网 IP,就可以使用 ssh 命令直接连接主机的 IP 地址,但是大部分公司和家庭内部都是局域网,并不能给局域网内的每一台主机都分配一个公网 IP,这时候就需要进行内网穿透,才能从外部连接到局域网内的主机。

ngrok 是一个反向代理工具,可以实现将内网的端口暴露到公网,通过 ngrok,也能将 ssh 使用的端口暴露出去,以此实现 ssh 的内网穿透。

注册并下载 ngrok

访问 https://ngrok.com/ 注册 ngrok 账号并下载 ngrok 客户端。

查看 ngrok 的 token

访问 https://dashboard.ngrok.com/auth 查看 token并复制。

在内网机器上启动 ngrok

连接 ngrok 账号

1
ngrok authtoken 5TqUhMnum6ntDE8Z5HkNb_49F9ffzzcV9V7pKLVdDYc

启动 ngrok 并打开 22 端口转发

1
ngrok tcp 22 --log=stdout > "$HOME/ngrok.log" --region ap &

其中 region 的 ap 代表 ngrok 新加坡节点,访问速度相比美国节点会快一些。访问 https://ngrok.com/docs#config-options 可以查看支持的所有区域。

访问 http://127.0.0.1:4040

可以看到一个tcp开头的地址,通过访问这个地址,就可以转发到本机的 22 端口上。

通过 ssh 访问内网机器

查看到转发地址后,就可以在外网通过 ssh 命令访问内网机器来。以上图为例,ssh 访问的命令是:

1
ssh -p 10502 username@0.tcp.ap.ngrok.io

需要注意的问题

由于所有流量都要经过 ngrok 服务器,而 ngrok 的服务节点又只有美国、新加坡等地,所以速度上还是比较慢的。另外,如果 ngrok 的服务节点存在安全隐患的话,存在敏感内容的泄漏的可能性。

关注Python私房菜

Unicode 和 UTF-8

Unicode 和 UTF-8 的概念是一个非常基础和重要,但是却容易被忽略的问题。

字符集

在计算机系统中,所有的数据都以二进制存储,所有的运算也以二进制表示,人类语言和符号也需要转化成二进制的形式,才能存储在计算机中,于是需要有一个从人类语言到二进制编码的映射表。这个映射表就叫做字符集。

ASCII

最早的字符集叫 American Standard Code for Information Interchange(美国信息交换标准代码),简称 ASCII,由 American National Standard Institute(美国国家标准协会)制定。在ASCII 字符集中,字母 A 对应的字符编码是 65,转换成二进制是 0100 0001,由于二进制表示比较长,通常使用十六进制 41

GB2312、GBK

ASCII 字符集总共规定了 128 种字符规范,但是并没有涵盖西文字母之外的字符,当需要计算机显示存储中文的时候,就需要一种对中文进行编码的字符集,GB 2312 就是解决中文编码的字符集,由国家标准委员会发布。同时考虑到中文语境中往往也需要使用西文字母,GB 2312 也实现了对 ASCII 的向下兼容,原理是西文字母使用和 ASCII 中相同的代码,但是 GB 2312 只涵盖了 6000 多个汉字,还有很多没有包含在其中,所以又出现了 GBK 和 GB 18030,两种字符集都是在 GB 2312 的基础上进行了扩展。

Unicode

可以看到,光是简体中文,就先后出现了至少三种字符集,繁体中文方面也有 BIG5 等字符集,几乎每种语言都需要有一个自己的字符集,每个字符集使用了自己的编码规则,往往互不兼容。同一个字符在不同字符集下的字符代码不同,这使得跨语言交流的过程中双方必须要使用相同的字符编码才能不出现乱码的情况。为了解决传统字符编码的局限性,Unicode 诞生了,Unicoide 的全称是 Universal Multiple-Octet Coded Character Set(通用多八位字符集,简称 UCS)。Unicode 在一个字符集中包含了世界上所有文字和符号,统一编码,来终结不同编码产生乱码的问题。

字符编码 UTF-8

Unicode 统一了所有字符的编码,是一个 Character Set,也就是字符集,字符集只是给所有的字符一个唯一编号,但是却没有规定如何存储,一个编号为 65 的字符,只需要一个字节就可以存下,但是编号 40657 的字符需要两个字节的空间才可以装下,而更靠后的字符可能会需要三个甚至四个字节的空间。

这时,用什么规则存储 Unicode 字符就成了关键,我们可以规定,一个字符使用四个字节存储,也就是 32 位,这样就能涵盖现有 Unicode 包含的所有字符,这种编码方式叫做 UTF-32(UTF 是 UCS Transformation Format 的缩写)。UTF-32 的规则虽然简单,但是缺陷也很明显,假设使用 UTF-32 和 ASCII 分别对一个只有西文字母的文档编码,前者需要花费的空间是后者的四倍(ASCII 每个字符只需要一个字节存储)。

在存储和网络传输中,通常使用更为节省空间的变长编码方式 UTF-8,UTF-8 代表 8 位一组表示 Unicode 字符的格式,使用 1 - 4 个字节来表示字符。

UTF-8 的编码规则如下(U+ 后面的数字代表 Unicode 字符代码):

1
2
3
4
U+ 0000 ~ U+ 007F: 0XXXXXXX
U+ 0080 ~ U+ 07FF: 110XXXXX 10XXXXXX
U+ 0800 ~ U+ FFFF: 1110XXXX 10XXXXXX 10XXXXXX
U+10000 ~ U+1FFFF: 11110XXX 10XXXXXX 10XXXXXX 10XXXXXX

可以看到,UTF-8 通过开头的标志位位数实现了变长。对于单字节字符,只占用一个字节,实现了向下兼容 ASCII,并且能和 UTF-32 一样,包含 Unicode 中的所有字符,又能有效减少存储传输过程中占用的空间。

关注Python私房菜

理解Golang的Time结构

在golang中创建并打印一个时间对象,会看到如下输出

1
2018-10-26 14:15:50.306558969 +0800 CST m=+0.000401093

前面表示的意义好理解,分别是年月日和时间时区,最后的m=+xxxx这部分代表什么呢?

Monotonic Clocks 和 Wall Clocks

根据golang的time包的文档可以知道,golang的time结构中存储了两种时钟,一种是Wall Clocks,一种是Monotonic Clocks。

Wall Clocks,顾名思义,表示墙上挂的钟,在这里表示我们平时理解的时间,存储的形式是自 1970 年 1 月 1 日 0 时 0 分 0 秒以来的时间戳,当系统和授时服务器进行校准时间时间操作时,有可能造成这一秒是2018-1-1 00:00:00,而下一秒变成了2017-12-31 23:59:59的情况。Monotonic Clocks,意思是单调时间的,所谓单调,就是只会不停的往前增长,不受校时操作的影响,这个时间是自进程启动以来的秒数。

如果每隔一秒生成一个Time并打印出来,就会看到如下输出。

1
2
3
4
5
6
7
8
9
10
11
2018-10-26 14:15:50.306558969 +0800 CST m=+0.000401093
2018-10-26 14:15:51.310559881 +0800 CST m=+1.004425285
2018-10-26 14:15:52.311822486 +0800 CST m=+2.005711106
2018-10-26 14:15:53.314599457 +0800 CST m=+3.008511329
2018-10-26 14:15:54.31882248 +0800 CST m=+4.012757636
2018-10-26 14:15:55.320059921 +0800 CST m=+5.014018292
2018-10-26 14:15:56.323814998 +0800 CST m=+6.017796644
2018-10-26 14:15:57.324858749 +0800 CST m=+7.018863606
2018-10-26 14:15:58.325164174 +0800 CST m=+8.019192224
2018-10-26 14:15:59.329058535 +0800 CST m=+9.023109863
2018-10-26 14:16:00.329591268 +0800 CST m=+10.023665796

可以看到m=+后面所显示的数字,就是文档中所说的Monotonic Clocks。

Time结构

那么Monotonic Clock和Wall Clock在Time中是怎么存储的呢?来看一下Time结构体。

1
2
3
4
5
type Time struct {
wall uint64
ext int64
loc *Location
}

Time结构体中由三部分组成,loc比较明了,表示时区,wall和ext所存储的信息规则相对复杂,根据文档的介绍总结成了下图:

golang中的Time结构,不像很多语言保存Unix时间戳(也就是最早只能表示到1970年1月1日),而是至少可以安全的表示1885年以来的时间。

1
2
t, _ := time.Parse(time.RFC3339, "1890-01-02T15:04:05Z")
fmt.Println(t) // 1890-01-02 15:04:05 +0000 UTC

实践中需要注意的问题

既然Time结构所表示的时间,有可能有Monotonic Clock也可能没有,那么在使用中就有可能遇到一些问题,例如下面这种情况。

1
2
3
4
5
6
7
8
now := time.Now()
encodeNow, _ := json.Marshal(now)

decodeNow := time.Time{}
json.Unmarshal(encodeNow, &decodeNow)

fmt.Println(now) // 2018-10-26 16:04:55.230121766 +0800 CST m=+0.000520419
fmt.Println(decodeNow) // 2018-10-26 16:04:55.230121766 +0800 CST

可以看到,经过JSON转码之后,Time结构体会被表示成不带Monotonic Clock的字符串,丢失了Monotonic Clock信息,而将字符串转码回Time结构时,自然也就和转码之前的不一样了。同样的情况,也发生在数据库存储中,存储到数据库里的Time结构和从数据库取出来的也是不一样的。

当调用Equal比较两个Time时,只有两个Time都含有Monotonic Clock时,才会根据Monotonic Clock比较大小,其他情况只比较Wall Clock部分。

1
2
3
4
5
6
7
8
timeA := time.Now()
timeB := time.Unix(0, timeA.UnixNano())

fmt.Println(timeA) // 2018-10-26 16:37:02.216165074 +0800 CST m=+0.000363156
fmt.Println(timeB) // 2018-10-26 16:37:02.216165074 +0800 CST

r := timeA.Equal(timeB)
fmt.Println(r) // true

上面两个时间的Wall Clock部分相同,一个有Monotonic Clock一个没有,但是比较的结果是两个时间是相同的。

1
2
3
4
5
6
7
8
timeA := time.Now()
timeB := time.Unix(timeA.Unix(), 0)

fmt.Println(timeA) // 2018-10-26 16:38:25.653953438 +0800 CST m=+0.000364851
fmt.Println(timeB) // 2018-10-26 16:38:25 +0800 CST

r := timeA.Equal(timeB)
fmt.Println(r) // false

需要注意的是Wall Clock并不是秒之前的部分,Wall Clock本身也可以精确到纳秒级别,所以一个精确到纳秒的时间和一个精确到秒的时间也是不同的。

对于Time中的Monotonic Clock,我们可以使用time.Round(0)方法将其消除掉,以实现和其他语言一致的行为。

1
2
3
4
5
timeA := time.Now()
timeB := timeA.Round(0)

fmt.Println(timeA) // 2018-10-26 16:43:03.799263739 +0800 CST m=+0.000357758
fmt.Println(timeB) // 2018-10-26 16:43:03.799263739 +0800 CST

参考文章

https://golang.org/pkg/time/

点击关注知乎专栏Golang私房菜

翻译 | 更快的Python(二)

更快的Python(Python Faster Way)使用代码示例来说明如何书写Python代码能带来更高的性能。本文对代码进行了讲解,从性能和可读性等角度来选择出最适合的写法。

例子11:字符串连接

  • 最差/最优时间比:1.15
  • 使用建议:一次性连接多个(3个以上)的字符串的时候,使用join,其他情况使用加号或f-string。
  • 说明:又是一个字符串连接的问题,不过这个例子举的不好,join适用的场景是一次连接多个字符串,会比加号连接多个字符串要快很多(加号相当于一个一个连接)。

例子12:数字的格式化

  • 最差/最优时间比:1.29
  • 使用建议:需要复杂格式,推荐使用format方法;将数字转换为字符串,直接使用str方法。
  • 说明:将数字转为字符串,使用str方法要快于format方法,因为format方法支持在转换过程中增加规则,例如将数字转为货币形式(每三位加一个逗号分隔符)。

例子13:获取内置列表类型的长度

  • 最差/最优时间比:1.20
  • 使用建议:使用len()方法。
  • 说明:当调用len()方法时,系统实际上是调用了对象内置的len方法,从这个层面理解,直接调用len应该比len()方法更快。但是当len()内置的列表方法时,Python解释器做了优化,直接返回了列表对象中存储长度信息的变量,并不会调用len

例子14:整数类型的运算

  • 最差/最优时间比:2.63
  • 使用建议:不要直接调用add等魔术方法。
  • 说明:对于整数类型,调用魔术方法完成运算的速度远远慢于直接使用运算符,使用运算符时,Python解释器直接调用C实现的operaotr包中的运算方法,所以速度很快;而使用调用魔术方法,在Python层面多出了调用add等魔术方法的额外操作。

例子15:自定义类型的运算符重载

  • 最差/最优时间比:1.06
  • 使用建议:不要直接调用add等魔术方法。
  • 说明:对于重载了运算符的对象,没有对应的C实现运算方法,所以直接直接调用魔术方法速度会更快。

例子16:对range结果求和

  • 最差/最优时间比:2.95
  • 使用建议:推荐使用第一种。
  • 说明:和第一种相比,第三种会遍历range先生成一个列表,然后将列表传给sum,速度最慢,而第一种直接传递迭代器给sum,省去了遍历生成列表的过程;第二种和第一种相比则是在Python层面实现了求和,而sum是C层面实现的求和,所以也没有第一种块。

例子17:for循环和表达式构建列表的区别

  • 最差/最优时间比:2.05
  • 使用建议:推荐使用表达式构建。
  • 说明:两种方式看上去逻辑一样,都是把range迭代器遍历,生成一个列表,但是表达式是在字节码层面构建了一个循环来生成,而第二种则是在Python层面创建列表,并不断Append,性能上要差于第一种。

例子18:for循环和表达式构建字典的区别

  • 最差/最优时间比:1.49
  • 使用建议:推荐使用表达式。
  • 说明:dict的update方法适用于合并两个字典的情况,也就是说可以一次合并多个key,所以相比于直接访问key速度要慢;根据图中的测试,在100这个量级上,表达式生成的速度要慢一些,但是在更大的量级上,表达式的优势就体现出来了,并且更加Pythonic。首先表达式方法是在字节码层面生成循环的,所以理论上比Python层面生成循环构建字典要快的,那么为什么在小量级的场景下,字节码反倒没有优势呢?根据dis出的字节码可以看到,表达式构建首先会MAKE_FUNCTION然后再CALL_FUNCTION,这里会有一些基本的消耗,量级小的时候,这些基本消耗占比高,量级越大,这些基本消耗所占比例就越低,表达式方法的优势也就越明显。

例子19:for循环和表达式构建字典的区别

  • 最差/最优时间比:2.89
  • 使用建议:推荐使用表达式构建。
  • 说明:理由同上一个例子。

例子20:转换为bool值

  • 最差/最优时间比:N/A
  • 使用建议:根据具体情况选择。
  • 说明:这个比较似乎没有什么好说的,时间的区别主要原因是构建a对象的成本不同。

参考文章

关注公众号【Python私房菜】

Go的栈空间管理

栈空间管理的基本逻辑

go语言通过goroutine提供了并发编程支持,goroutine是go运行库的功能,而不是操作系统线程实现的,goroutine可以被理解成一个用户态的线程。

既然goroutine是由go运行库管理的,那么go运行库也需要为每个goroutine创建并管理相应的栈空间,为每个goroutine分配的栈空间不能太大,goroutine开多时会浪费大量空间,也不能太小,会导致栈溢出。go语言选择栈的栈空间管理的方式是,一开始给一个比较小的空间,随着需要自动增长。当goroutine不需要那么大的空间时,栈空间也要自动缩小。

分段栈 Segment Stacks

在go 1.3之前,go使用分段栈。

分段栈实现了一种不连续但是可以持续增长的栈,开始时,栈只有一个段,当需要更多的栈空间时,会分配一个新的段,和上一个栈双向链接。这样,一个栈就是由多个双向链接的段所组成的。当新分配的段使用完毕后,新段会被释放掉。

分段栈实现了栈的按需收缩,在增加新分段时也不需要对原有分段中的数据进行拷贝,使得goroutine的使用代价非常低廉。

分段栈的好处是可以按需增长,空间利用率比较高,然而分段栈在某些情况下也存在一定的瑕疵。当一个段即将用尽,这时使用for循环执行一个比较耗空间的函数,会导致函数执行时goroutine进行段的分配,而执行完成返回时,进行段的销毁,这样就会导致在循环中出现多次栈的扩容和收缩,造成很大的性能损失,这种情况被称作栈分裂(Stack Split)。

连续栈 Contiguous Stacks

go 1.3推出了连续栈,连续栈使用了另外一种策略,不再把栈分成一段一段的,当栈空间不够时,直接new一个2倍大的栈空间,并将原先栈空间中的数据拷贝到新的栈空间中,而后销毁旧栈。这样当出现栈空间触及边界时,不会产生栈分裂的情况。

继续假设当前栈空间即将用尽,并且需要在for循环中执行一个比较消耗空间的函数。当该函数执行时,栈空间发生了扩容,变成原先2倍大小,函数执行完成一次后,栈空间的使用量缩小回执行前的大小,但是栈空间的使用量并没有小于栈大小的1/4,不会触发栈收缩,所以在整个for循环执行过程中,不会反复触发栈空间的收缩扩容。

总结

相比于分段栈,连续栈避免了某些场景下栈空间的的频繁伸缩。有一点需要注意的是,连续栈的收缩也是需要重新申请一段空间(原先的1/2大小),并进行栈拷贝操作的。

点击关注知乎专栏Golang私房菜

翻译 | 更快的Python(一)

更快的Python(Python Faster Way)使用代码示例来说明如何书写Python代码能带来更高的性能。本文对代码进行了讲解,从性能和可读性等角度来选择出最适合的写法。

例子1:字符串格式化

  • 最差/最优时间比:1.95
  • 使用建议:Python 3.7或以上推荐使用f-string,其他版本推荐使用format方法。
  • 说明:字符串格式化是代码中最常遇到的情况,虽然在连接少量字符串的情景中,使用+号的性能最优,但是使用+号的代码可读性最差。如果使用Python 3.7或优以上版本,可以使用f-string来解决这个问题,f-string的性能比format方法和%操作符的性能都要高,可读性也比+号好。

例子2:字典的初始化

  • 最差/最优时间比:1.83
  • 使用建议:使用字面量初始化字典(以及其他集合类型)。
  • 说明:Python中初始化集合类型时使用字面量的方式,解释器会直接调用BUILD_MAP等字节码来创建,如果用构造函数的方式来创建,则需要先查询构造方法,再执行构造方法。使用字面量初始化,Python代码也更简洁。

例子3:内置排序方法

  • 最差/最优时间比:1.26
  • 使用建议:根据是否需要修改原始值来决定使用哪个方法。
  • 说明:sorted和list.sort方法是Python中内置的排序方法,sorted方法不会修改原始值,list.sort方法在原始值上直接排序,会修改原始值。比较这两个方法的性能差异,意义不大。

例子4:初始化多个变量

  • 最差/最优时间比:1.01
  • 使用建议:推荐使用第二种。
  • 说明:从字节码中可以看出两种方式出了执行顺序之外,基本一致,所以性能上也非常接近。

例子5:多个变量的比较

  • 最差/最优时间比:1.11
  • 使用建议:推荐使用第二种。
  • 说明:使用第一种方法能带来一定的性能提升,但是提升有限,在实际情况中也很少出现多个变量连续比较大小的情况,并且第一种方法非常不Pythonic,所以推荐使用第二种。

例子6:if true的条件判断

  • 最差/最优时间比:1.17
  • 使用建议:推荐使用第一种。
  • 说明:从字节码上看,第一种方法的性能最高,并且语法上也更加简洁。

例子7:if false的条件判断

  • 最差/最优时间比:1.10
  • 使用建议:推荐使用第一种。
  • 说明:从字节码上看,第一种方法的性能最高,语法角度上,if not写成第二种和第三种都是不推荐的。

例子8:判断list是否为空

  • 最差/最优时间比:1.55
  • 使用建议:根据具体需求,优先使用前两种。
  • 说明:前两种代码性能更高,代码更简洁。同时,空列表a并不等于None,所以使用if a is None无法实现对空列表的判断。

例子9:判断object是否为空

  • 最差/最优时间比:1.00
  • 使用建议:根据具体需求,优先使用前两种。
  • 说明:理由同上一个例子。

例子10:遍历可迭代对象

  • 最差/最优时间比:1.12
  • 使用建议:根据具体情况选择。
  • 说明:两者性能差别不大,使用enumerate方法,可以不需要取对象的长度,可以直接获取到对象的index。

参考文章

关注公众号【Python私房菜】

Go语言中defer的一些坑

defer语句是Go中一个非常有用的特性,可以将一个方法延迟到包裹该方法的方法返回时执行,在实际应用中,defer语句可以充当其他语言中try…catch…的角色,也可以用来处理关闭文件句柄等收尾操作。

defer触发时机

A “defer” statement invokes a function whose execution is deferred to the moment the surrounding function returns, either because the surrounding function executed a return statement, reached the end of its function body, or because the corresponding goroutine is panicking.

Go官方文档中对defer的执行时机做了阐述,分别是。

  • 包裹defer的函数返回时
  • 包裹defer的函数执行到末尾时
  • 所在的goroutine发生panic时

defer执行顺序

当一个方法中有多个defer时, defer会将要延迟执行的方法“压栈”,当defer被触发时,将所有“压栈”的方法“出栈”并执行。所以defer的执行顺序是LIFO的。

所以下面这段代码的输出不是1 2 3,而是3 2 1。

1
2
3
4
5
6
7
8
9
10
11
func stackingDefers() {
defer func() {
fmt.Println("1")
}()
defer func() {
fmt.Println("2")
}()
defer func() {
fmt.Println("3")
}()
}

坑1:defer在匿名返回值和命名返回值函数中的不同表现

先看下面两个方法执行的结果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func returnValues() int {
var result int
defer func() {
result++
fmt.Println("defer")
}()
return result
}

func namedReturnValues() (result int) {
defer func() {
result++
fmt.Println("defer")
}()
return result
}

上面的方法会输出0,下面的方法输出1。上面的方法使用了匿名返回值,下面的使用了命名返回值,除此之外其他的逻辑均相同,为什么输出的结果会有区别呢?

要搞清这个问题首先需要了解defer的执行逻辑,文档中说defer语句在方法返回“时”触发,也就是说return和defer是“同时”执行的。以匿名返回值方法举例,过程如下。

  • 将result赋值给返回值(可以理解成Go自动创建了一个返回值retValue,相当于执行retValue = result)
  • 然后检查是否有defer,如果有则执行
  • 返回刚才创建的返回值(retValue)

在这种情况下,defer中的修改是对result执行的,而不是retValue,所以defer返回的依然是retValue。在命名返回值方法中,由于返回值在方法定义时已经被定义,所以没有创建retValue的过程,result就是retValue,defer对于result的修改也会被直接返回。

坑2:在for循环中使用defer可能导致的性能问题

看下面的代码

1
2
3
4
5
6
func deferInLoops() {
for i := 0; i < 100; i++ {
f, _ := os.Open("/etc/hosts")
defer f.Close()
}
}

defer在紧邻创建资源的语句后生命力,看上去逻辑没有什么问题。但是和直接调用相比,defer的执行存在着额外的开销,例如defer会对其后需要的参数进行内存拷贝,还需要对defer结构进行压栈出栈操作。所以在循环中定义defer可能导致大量的资源开销,在本例中,可以将f.Close()语句前的defer去掉,来减少大量defer导致的额外资源消耗。

坑3:判断执行没有err之后,再defer释放资源

一些获取资源的操作可能会返回err参数,我们可以选择忽略返回的err参数,但是如果要使用defer进行延迟释放的的话,需要在使用defer之前先判断是否存在err,如果资源没有获取成功,即没有必要也不应该再对资源执行释放操作。如果不判断获取资源是否成功就执行释放操作的话,还有可能导致释放方法执行错误。

正确写法如下。

1
2
3
4
5
6
7
resp, err := http.Get(url)
// 先判断操作是否成功
if err != nil {
return err
}
// 如果操作成功,再进行Close操作
defer resp.Body.Close()

坑4:调用os.Exit时defer不会被执行

当发生panic时,所在goroutine的所有defer会被执行,但是当调用os.Exit()方法退出程序时,defer并不会被执行。

1
2
3
4
5
6
func deferExit() {
defer func() {
fmt.Println("defer")
}()
os.Exit(0)
}

上面的defer并不会输出。

点击关注知乎专栏Golang私房菜

用Python写算法 | 蓄水池算法实现随机抽样

现在有一组数,不知道这组数的总量有多少,请描述一种算法能够在这组数据中随机抽取k个数,使得每个数被取出来的概率相等。

如果这组数有n个,那么每个数字取到的概率就是k/n,但是这个问题的难点在于不知道这组数的总数,也就是不知道n,那么该怎么计算每个数取到的概率呢?

蓄水池算法

游泳池(蓄水池)大家都不陌生,有些游泳池中的水是活的,有入水管也有出水管,那么和泳池体积相当的水流过之后,是不是泳池中所有的水都会被替换呢?当然不是,有的水在泳池中可能会存留很久,有的可能刚进去就流走了。仿照这种现象,蓄水池抽样算法诞生了,蓄水池算法的关键在于保证流入蓄水池的水和已经在池中的水以相同的概率留存在蓄水池中。并且蓄水池算法可以在不预先知道总量的情况下,在时间复杂度O(N)的情况下,来解决这类采样问题。

核心原理

这一部分涉及公式,为了保证效果直接贴了图过来。

Python实现

接下来尝试用Python实现一下蓄水池算法,由于蓄水池算法是在事先不知道总量的情况下抽样的,所以定义一个方法来接收单个元素,并且把这个方法放在类中,以持有采样后的数据。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import random


class ReservoirSample(object):

def __init__(self, size):
self._size = size
self._counter = 0
self._sample = []

def feed(self, item):
self._counter += 1
# 第i个元素(i <= k),直接进入池中
if len(self._sample) < self._size:
self._sample.append(item)
return self._sample
# 第i个元素(i > k),以k / i的概率进入池中
rand_int = random.randint(1, self._counter)
if rand_int <= self._size:
self._sample[rand_int - 1] = item
return self._sample

测试代码

接下来实现一个测试用例验证实现的算法是否正确,既然是随机抽样,无法通过单词测试来验证是否正确,所以通过多次执行的方式来验证,比如从1-10里随机取样3个数,然后执行10000次取样,如果算法正确,最后结果中1-10被取样的次数应该是相同的,都是3000上下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import unittest
from collections import Counter

from reservoir_sample import ReservoirSample


class TestMain(unittest.TestCase):

def test_reservoir_sample(self):
samples = []
for i in range(10000):
sample = []
rs = ReservoirSample(3)
for item in range(1, 11):
sample = rs.feed(item)
samples.extend(sample)
r = Counter(samples)
print(r)

if __name__ == '__main__':
unittest.main()

输出的结果如下

1
Counter({7: 3084, 6: 3042, 10: 3033, 3: 3020, 8: 3016, 5: 2997, 4: 2986, 2: 2972, 9: 2932, 1: 2918})

上面输出了每个数字被取样到的次数,通过图表可以清晰的看到分布情况

可以看出蓄水池算法对于随机抽样还是非常适合的,每个元素的抽样概率都相同。

代码

上述的算法和测试代码已经放在Github,可以直接下载使用。

关注公众号【Python私房菜】

使用gofmt格式化代码

对于一门编程语言来说,代码格式化是最容易引起争议的一个问题,不同的开发者可能会有不同的编码风格和习惯,但是如果所有开发者都能使用同一种格式来编写代码,开发者就可以将宝贵的时间专注在语言要解决的问题上。

gofmt介绍

Golang的开发团队制定了统一的官方代码风格,并且推出了gofmt工具(gofmt或go fmt)来帮助开发者格式化他们的代码到统一的风格。gofmt是一个cli程序,会优先读取标准输入,如果传入了文件路径的话,会格式化这个文件,如果传入一个目录,会格式化目录中所有.go文件,如果不传参数,会格式化当前目录下的所有.go文件。

gofmt默认不对代码进行简化,使用-s参数可以开启简化代码功能,具体来说会进行如下的转换:

  • 去除数组、切片、Map初始化时不必要的类型声明:
1
2
3
4
如下形式的切片表达式:
    []T{T{}, T{}}
将被简化为:
    []T{{}, {}}
  • 去除数组切片操作时不必要的索引指定
1
2
3
4
如下形式的切片表达式:
    s[a:len(s)]
将被简化为:
    s[a:]
  • 去除迭代时非必要的变量赋值
1
2
3
4
5
6
7
8
如下形式的迭代:
    for x, _ = range v {...}
将被简化为:
    for x = range v {...}
如下形式的迭代:
    for _ = range v {...}
将被简化为:
    for range v {...}

gofmt命令参数列表如下:

1
2
3
4
5
6
7
8
9
10
usage: gofmt [flags] [path ...]
  -cpuprofile string
        write cpu profile to this file
  -d    display diffs instead of rewriting files
  -e    report all errors (not just the first 10 on different lines)
  -l    list files whose formatting differs from gofmt's
  -r string
        rewrite rule (e.g., 'a[b:len(a)] -> a[b:]')
  -s    simplify code
  -w    write result to (source) file instead of stdout

可以看到,gofmt命令还支持自定义的重写规则,使用-r参数,按照pattern -> replacement的格式传入规则。

有如下内容的Golang程序,存储在main.go文件中。

1
2
3
4
5
6
7
8
9
10
package main

import "fmt"

func main() {
   a := 1
   b := 2
   c := a + b
   fmt.Println(c)
}

用以下规则来格式化上面的代码。

1
gofmt -r "a + b -> b + a"

格式化的结果如下。

1
2
3
4
5
6
7
8
9
10
package main

import "fmt"

func main() {
   a := 1
   b := 2
   c := b + a
   fmt.Println(c)
}

*注意:Gofmt使用tab来表示缩进,并且对行宽度无限制,如果手动对代码进行了换行,gofmt也不会强制把代码格式化回一行。

go fmt和gofmt

gofmt是一个独立的cli程序,而go中还有一个go fmt命令,go fmt命令是gofmt的简单封装。

1
2
3
4
5
6
7
8
9
10
11
usage: go fmt [-n] [-x] [packages]

Fmt runs the command 'gofmt -l -w' on the packages named
by the import paths. It prints the names of the files that are modified.
For more about gofmt, see 'go doc cmd/gofmt'.
For more about specifying packages, see 'go help packages'.
The -n flag prints commands that would be executed.
The -x flag prints commands as they are executed.
To run gofmt with specific options, run gofmt itself.

See also: go fix, go vet.

go fmt命令本身只有两个可选参数-n和-x,-n仅打印出内部要执行的go fmt的命令,-x命令既打印出go fmt命令又执行它,如果需要更细化的配置,需要直接执行gofmt命令。

go fmt在调用gofmt时添加了-l -w参数,相当于执行了gofmt -l -w

goland中配置gofmt

Goland是JetBrains公司推出的Go语言IDE,是一款功能强大,使用便捷的产品。

在Goland中,可以通过添加一个File Watcher来在文件发生变化的时候调用gofmt进行代码格式化,具体方法是,点击Preferences -> Tools -> File Watchers,点加号添加一个go fmt模版,Goland中预置的go fmt模版使用的是go fmt命令,将其替换为gofmt,然后在参数中增加-l -w -s参数,启用代码简化功能。添加配置后,保存源码时,goland就会执行代码格式化了。

参考文章

https://golang.org/cmd/gofmt/

https://golang.org/doc/effective_go.html

https://openhome.cc/Gossip/Go/gofmt.html

https://github.com/hyper0x/go_command_tutorial/blob/master/0.9.md

点击关注知乎专栏Golang私房菜