Mar 29
原发于我的公众号:felix021

在乔纳森·斯威夫特的著名讽刺小说《格列夫游记》中,小人国内部分裂成 Big-endian 和 Little-endian 两派,区别在于一派要求从鸡蛋的大头把鸡蛋打破,另一派要求从鸡蛋的小头把鸡蛋打破。

然后忘了这个故事,咱们开始吧。

== 坑 ==
Charles 同学这周又踩了个坑,数据插入 MySQL 时报错:

引用
1366 Incorrect string value: '\xF0\x90\x8D\x83...' for column 'content' at row 1


按惯例搜一下,据说是因为 mysql 用的 utf8 不支持 emoji,需要修改配置文件,将字符集改成 utf8mb4:

引用
[mysqld]
character-set-server = utf8mb4
stackoverflow.com/questions/10957238


但是 Charles 已经给 MySQL 加上了这个配置,仍然报错。

实际上,MySQL 还有另外一个配置,用于指定客户端和服务器之间连接时使用的字符集:

引用
[mysqld]
character-set-client-handshake = utf8mb4


当然,也可以在 MySQL Client 中指定,具体需要参考 client 的文档,或者简单粗暴地在连接成功以后执行(但不推荐):

引用
SET NAMES utf8mb4;


== utf8 和 utf8mb4 ==

那么,什么是 utf8mb4 ?和 utf8 有啥区别呢?

根据 MySQL 的 manual:

引用
The utfmb4 character set has these characteristics:
- Supports BMP and supplementary characters.
- Requires a maximum of four bytes per multibyte character.
https://dev.mysql.com/doc/refman/8.0/en/charset-unicode-utf8mb4.html

(文档中 utf8mb4 打错了,我是原样复制的)

翻译过来就是,utf8mb4 支持 BMP ( Unicode Basic Multilingual Plane )和补充字符,每个字符最多 4 字节(这里 “mb4” 大概就是 multi byte 4 的简写了)。

冷知识:Unicode 编码一共有 17 个 "Plane"( 0~16 ),其中 Plane 0 就是 BMP,包含绝大多数常用字符,比如希腊、希伯来、阿拉伯、CJK ( Chinese-Japanese-Korean )字符等。Plane 1~16 被称为 "supplementary planes",包含不常用的其他字符,例如 emoji 和某些特殊的 CJK 字符。所以目前 Unicode 字符的最大编码为 0x10FFFF 。

至于 utf8,MySQL 文档里也有说明:

引用
utf8 is an alias for the utf8mb3 character set.

Note
The utf8mb3 character set is deprecated and will be removed in a future MySQL release. Please use utf8mb4 instead
https://dev.mysql.com/doc/refman/8.0/en/charset-unicode-utf8.html

简单说就是挂羊头卖狗肉了,看到的是 utf8,实际用的是 utf8mb3

utf8mb3 的文档就不贴了(懒),和 ut8mb4 的区别就在于最多只支持 3 个字节,因此不支持 Unicode 的补充字符集。

也就是说,MySQL 里的 utf8,实际上是一个阉割版的 utf8 。

MySQL 从 5.5.3 才开始支持完整版的 utf8 ( utf8mb4 ),并且后续计划移除 utf8mb3,utf8 未来在 mysql 中也会变成 utf8mb4 的别名,所以以后默认都使用 utf8mb4 就对了。

话说回来,MySQL 为什么会有这种奇怪的设定呢?

其实最初是从性能上考虑的,这个精简版的 utf8 在运行的时候可以更快一点点。

要知道 MySQL 已经是一个 24 岁的老项目了,在 1995 年诞生时,Intel 才只推出了 Pentium Pro,对比现在的 CPU,性能可以说是非常差了。

冷知识:差到什么程度呢?举个例子,早期的 Windows Beta 版,桌面右下角时间是可以显示秒数的,但由于当时硬件的性能问题,微软在发布 Windows 95 之前就移除了该功能,直到 Windows 7 ( 2009 年)才允许通过修改注册表开启。

== 真正的 utf8 ==

那么真正的 utf8 长什么样呢?

在查文档之前,不妨先动手创建一个文档看一下

$ echo '0Aa 你好' > utf-8.txt

$ file utf-8.txt
utf-8.txt: UTF-8 Unicode text

$ xxd utf-8.txt #用 16 进制的方式查看
0000: 3041 61e4 bda0 e5a5 bd0a      0Aa.......

可以看到,开头"0Aa" 对应 3 个字节 0x30 、0x41 、0x61 (十进制 48 、65 、97,大写 A < 小写 a 就是这么来的)。

最后一个字符 0x0a 是 echo 默认输出的换行。

冷知识:可以加上 -n 参数让 echo 不输出换行符。换行符在不同 OS 下不同,在 Linux/Unix 下是 "\n" ( 0x0a ),在 Windows 下是 "\r\n"( 0x0d 0x0a ),在早期 Mac 下是 "\r" ( 0x0d ),从 Mac OS 10.0 ( 2001 )开始也和 Unix 一样用 "\n" 了。在 C/Python 等语言下,fopen/open 默认使用“文本模式”打开文件,读取时会统一转换成 "\n",写入时将"\n"转换为按 os 的默认值。还有一些其他场景可能需要注意,例如 http 协议中 header 使用 "\r\n" 换行。

中间的 "e4bda0e5a5bd" 这 6 个字节对应的就是 “你好” 了,每个字符 3 个字节。

那到底如何确定一个 utf8 字符是几个字节呢?

这里贴一个 wikipedia 的表格 Number

引用
字节数 | 比特数 | Unicode 区间 开始~结束 | 字节 1~4
1  7  U+0000  U+00007F  0xxxxxxx     
2  11  U+0080  U+0007FF  110xxxxx 10xxxxxx   
3  16  U+0800  U+00FFFF  1110xxxx 10xxxxxx 10xxxxxx
4  21  U+10000  U+10FFFF  11110xxx 10xxxxxx 10xxxxxx 10xxxxxx

简单解释一下:

1. 第一个字节中,开头 1 的数量表明了这个 utf8 字符包含几个字节
2. 0 开头,表示只需要 1 个字节,剩余 7 bit 可以表示 unicode 中的 0~127,正好和 ascii 编码兼容。
3. 110 开头,表示需要 2 个字节,包含 11 bit,可以表示大部分非 CJK 字符(希腊、阿拉伯等字符)
4. 1110 开头,表示需要 3 个字节,包含 16 bit,正好可以表示所有 BMP 的字符,比如 “你好”都在 这个 Plane 里面,所以一共需要 6 个字节。
5. 11110 开头,表示需要 4 个字节,包含 21 bit,最多可以包含 32 个 Plane,超过了当前 17 个 Plane 的
6. 后续字符都是 10 开头,不会和首字符混淆,因此在解析的时候很容易识别,就算遇到了错误的编码字符(例如按字节截断到字符中间),也可以简单跳过,定位下一个字符。

前面展示了 ASCII 字符和中文,咱们顺便再看看 emoji 的 utf-8 编码长什么样:

$ echo -n  > 1.txt
$ xxd 1.txt
0000: f09f 9880    ....


根据上面的表格,我们可以算出,这个 GRIN FACE (露齿笑)的 Unicode 码点是 0x1F600,在 Unicode 的 Plain 1 中,因此 utf-8 编码需要 4 个字节。

== 字符集和编码规范 ==

上文提到了 Unicode 和 utf-8 这两个名词,但是很多同学其实没搞明白他俩的区别是啥。

一般我们提到 Unicode 时指的是字符集( Character Set ),其中包含了一系列字符,并为每一个字符指定了码点( Code Point,即该字符的编号)。

Unicode 标准里包含了很多编码规范,utf-8 是其中一种,指定了一个 Unicode 字符的码点应该如何存储,例如 ASCII 用一个字节,超过一个字节的根据需要的 bit 数量,分别存储到多个字节中。

除了 utf-8 之外,Unicode 还有多种不同的编码规范,例如

1. ucs-2,就是简单地一一对应 BMP 的编码,每个字符使用 2 个字节,因此不支持补充字符。
2. ucs-4,用 4 个字节来存储 unicode 编码,因此支持 Unicode 中的所有 plain 。Unicode 后续的修订也会保证添加的码点都在 31bit 范围内。
3. utf-16,BMP 内的字符等于 ucs-2,其他 plane 用 4 个字节表示; windows 和 ecma 规范( javascript )使用 utf-16 作为其内部编码。
4. utf-32,ucs-4 的子集,一般可以认为就是 ucs-4 。

然鹅 utf-8 几乎统治了互联网,超过 93%的网页是用 UTF-8 编码的,以至于 IETF 要求所有网络协议都需要标明内容的编码,并且必须支持 UTF-8 。

至于原因么,还记得开头的那个故事吗? utf-8 避免了上述编码中的字节序( big endian 、little endian )的问题。

当然这只是一个原因,我认为更重要的是,utf-8 保持了对 ascii 的兼容,路径依赖的强大惯性,会导致上述 4 种编码在实际推广中带来很高的迁移成本(按理应该在这里讲讲马屁股宽度的故事,不过跑题太远了)。

utf-8 在保持后向兼容的前提下,能支持所有 Unicode 字符,相比 ucs4 还能节省大量存储空间、数据传输量,因此统治了互联网,也就在情理之中了。

除了 Unicode 之外,还有很多其他字符集,例如最经典的 ASCII,由于字符少,其编码规范也相当简单。

在中国,比较常见的字符集还有 GB2312 ( 1980 年)、GBK ( 1993 年)、GB18030 ( 2000 年),这些标准都规定了对应的编码规范,所以这些名字既可以表示字符集,也可以表示编码规范。

其中 GB2312 只包含 7445 个字符,其中汉字 6763 个(只包含常用汉字,很多生僻字都不支持),编码规范也兼容 ASCII 。GBK ( GB13000 )兼容 GB2312,添加了更多字符,GB18030 是进一步的补充。

冷知识:我们可以使用 iconv 命令行工具来修改文件的字符编码

$ iconv -f gb18030 -t utf-8 < gb18030.txt
0Aa 你好

也可以在 vim 中这干
:set fileencoding=gb18030


此外,使用 windows 的同学可能还见到过一个奇怪的代号 "cp936"(在上述 iconv 命令、vim 中都可以使用),这是微软对 GB2312 的实现,在 Win95 以后实际上也支持了大部分 GBK 字符。

== 总结 ==

1.  Unicode 是一个字符集,包含 17 个 Plane,每个 Plane 65536 个码点,Plane0 是 BMP,其他 Plane 是补充字符
2. UTF-8 是一种编码规范,用 1~4 个字节编码 Unicode 字符,兼容 ASCII,中文 3 字节,补充字符如 emoji 需要 4 字节)
3. MySQL 中的 utf8 是阉割版的、只支持 BMP 的编码,以后记得都使用 utf8mb4 ;除了 server 编码,记得也要修改连接的编码(客户端编码)。
4. 除了 utf-8 之外,还有好几个没什么卵用的字符集 /编码。
5. 我在网盟广告业务线(穿山甲),由于业务持续高速发展,长期缺人、不限 HC 。关于字节跳动面试的详情,可参考我之前写的《程序员面试指北:面试官视角》: https://mp.weixin.qq.com/s/Byvu-w7kyby-L7FBCE24Uw

~ 投递链接 ~

后端开发(上海) https://job.toutiao.com/s/sBAvKe

后端开发(北京) https://job.toutiao.com/s/sBMyxk

广告策略研发(上海) https://job.toutiao.com/s/sBDMAK

其他地区、职能线 https://job.toutiao.com/s/sB9Jq

----

再补充一个冷知识。

可能有些 PHP 程序员还踩过一个坑 :

用windows的 notepad 编辑utf-8编码的php文件并保存以后,代码执行不正常了。

这是因为 notepad 给文件开头打了个标记 (你可以用 xxd 或者 ultraedit 打开试试看)。

这个标记被称为 UTF-8 BOM,具体值为 0xEF 0xBB 0xBF,用来告诉文件的读取方,这个文件是使用 UTF-8 编码的。

比如说,你的csv是使用utf-8编码的,如果没有这个BOM,使用微软的Excel打开就会出现乱码。

至于PHP的问题,由于它在code tag(<?php)之前,PHP的解释器会把它当成 html 文件的一部分,可能就会导致 session 相关函数启动之前,就输出了http body。

最后,再学习一下移除 BOM 的方法吧:

vim:不要炸弹
引用
:set nobomb

sed:inplace
引用
$ sed -i '1s/^\xEF\xBB\xBF//' bom.txt
Mar 23

关于 RSA 的一些趣事 不指定

felix021 @ 2020-3-23 20:54 [IT » 其他] 评论(0) , 引用(0) , 阅读(1637) | Via 本站原创
文章有点长(一共 2300 字), 但最后一个故事最有意思, 看不完的话可以直接拉到底

== 1 ==

从面试题说起好了。

在考察到网络这一块的时候,可能会问问 http 协议,聊安全相关问题时,就顺便聊聊 https 。

大多数候选人知道非对称加密,了解客户端会用 RSA 公钥进行加密。

那么,服务器在返回响应报文之前,会用什么来进行加密呢?

有些候选人回答:“用服务器私钥进行加密”。

内心呵呵一笑

接着问,那服务器返回的信息岂不是可以被中间人拦截并解密吗?

候选人一般就放弃挣扎,只能强颜欢笑了。

有进一步了解过 https 的同学,能够说出在 SSL/TLS 握手以后,会生成一个对称加密密钥。

那么,既然有非对称加密,为什么还需要使用对称加密呢?

有些候选人就回答不上来了,只能强颜欢笑+1 。

实际上这是因为非对称加密的性能通常比对称加密算法差几个数量级。

以 RSA 为例,在加解密的时候,需要对大整数(典型值是 2048bit,256 字节)做大量乘法、取模等运算;相比之下如 AES 这样的对称加密算法会简单很多,一些 XOR 、移位,以及在 4x4 的矩阵上做些变换,还可以通过查表来加速。

此外,由于 AES 的广泛应用,主流 CPU ( Intel, AMD, ARM )都有相应的扩展指令集,可以将性能提升一个数量级,实际每秒能处理的数据在数百 MB 这个量级上。

有些硬盘号称有全盘加密功能,实际上就是硬盘的主控芯片在写入前通过 AES 进行加密,在电脑启动时 BIOS 会要求输入密码。这样即使电脑丢了,或者硬盘被人拆下挂到其他机器上也不用担心数据泄露。

关于 RSA 算法的实现细节,推荐阮一峰写的《 RSA 算法原理》

https://www.ruanyifeng.com/blog/2013/06/rsa_algorithm_part_one.html

== 2 ==

另一个有趣的事情是 2017 年,当时在钱厂,对接某银行系统的时候,在通信协议的加密这块,对方给了一个 jar 包(不给源码),以及不知什么编码的公钥、私钥文件,既不是 PEM 也不是 X509,是个奇怪的二进制文件。

然鹅,钱厂用的是 PHP,这就有点尴尬了。

幸好这个 jar 包没有经过混淆,用安卓开发小伙伴提供的反编译工具,得到了源码,并经过一番努力重写成了 PHP 的源码。

然后发现那个公私钥是 java object 序列化后得到的字节码。

更有趣的还在后面。

为了方便测试,我们按银行给的 API 写了一套 mock 系统,这样就可以在不依赖银行在内部完成全流程自测,大幅提高了开发效率。

在部署 mock 系统的时候,没想太多,就用银行提供的这对公私钥,然后竟然调通了

也就是说,银行给的公钥和私钥文件竟然是一对,把他们的私钥直接给我们了……

我猜,应该是银行的安全审计部门在项目需求中要求用非对称加密,但是又没有对最终代码进行审查吧

顺便一提,正式上线时,对方给的 API url 是 https 的,但是 url 中的域名是 IP,钱厂在代码中只能把 CURLOPT_SSL_VERIFYHOST 设为 false 。

过了一段时间,他们决定用个正式的域名,才给安上了 https 证书。

又过了一段时间,他们的证书过期了。

并且在故障期间不允许我们忽略证书进行访问。

== 3 ==

故事 2 里提到,把那段 java 代码“经过一番努力”重写成了 PHP,其实中间还是遇到了个不大不小的麻烦。

Java 代码里用了一个叫 bouncycastle 的库来进行 RSA 的加解密,而我用 PHP 的 openssl_private_encrypt 加密的文本,并不能被他们提供的 java 代码正常解密。

经过多次尝试,我发现了一个现象:对同一个消息,java 代码加密生成的密文,每次都一样,而 PHP 生成的密文,则总是在变化。

作为一个信息安全专业的毕业生,我竟然不知道这是为什么,真是愧对国家愧对党,只好默默点开桌面上的小飞机,在一些不存在的网站上摸索。

根据这个现象,我在 stackoverflow 找到了 "data encrypted with openssl_public_encrypt is different every time?" 这个问题,答案中给了个线索:

The PKCS#1 encryption algorithm uses some random seed to make the cipher-text different every time. This protects the cipher-text against several attacks, like frequency analysis, ciphertext matching.

FROM stackoverflow.com/questions/36627518

经过进一步的搜索,终于找到了如何在 PHP 中解决这个问题。

具体解决办法后面说,这里先介绍一些背景知识。

RSA 加密的基本流程是:将一个和密钥长度相同的输入(明文),通过一系列运算(加密),得到一个和密钥长度相同的输出(密文)。

以 1024 bit 的 RSA 密钥为例,每次输入 128 字节,输出 128 字节。

对于超过 128 字节的情况,就需要将原始数据切成 128 字节的块,分别加密后再拼起来;解密时,按 128 字节拆开解密。

但是不足 128 字节的情况,比如像密码这种短数据,或者长数据也并不总是 128 的倍数,会留下小尾巴,这就有点尴尬。

因此我们还需要用某种方法,将不足 128 字节的数据拼( padding )到 128 字节,再进行加密;解密得到的数据,需要把 padding 的数据去掉,才能得原始数据。

真是让人头秃。

继续。

对于普通文本,一个简单的做法是用 ASCII 0 进行填充。

但这会带来 2 个问题:

如果原文中包含了 ASCII 0,就无法有效识别

对于相同的输入,总是能得到相同的密文。

问题 2 可能招致某些类型的攻击,例如前面引用中提到的 "frequency analysis",以一个简化的场景为例,假设每个单词是单独加密的,在英文中单词 a 出现的次数最多,通过统计密文出现的频率,可以破译对应的明文。

一个改进的方案是,使用一些随机数进行填充,这样可以保证相同明文每次加密得到不同的密文。

基于这个思路,RFC 2313 制定了 RSA 的加密标准 PKCS #1: RSA Encryption Version 1.5,通过在 128 字节中的前 11 个字节里加入一些随机数,保证每次加密得到的密文不同。

回到最初的问题,通过查看 PHP 的 openssl_public_encrypt 文档,可以发现它有一个 $padding 参数,默认值是 OPENSSL_PKCS1_PADDING 。

而银行给的 Java 代码是 Cipher.getInstance("RSA", new BouncyCastleProvider()); 按照官方文档的说明,这里的 RSA 等于 "RSA/NONE/NoPadding"。

最后,通过在 PHP 代码中给数据手动填充前导 ASCII 0,并指定 OPENSSL_NO_PADDING,终于和 Java 代码兼容了。

问题圆满解决。

等等……

银行用的是 NoPadding ?

== THE END ==

其实关于 RSA 还有一些其他有趣的事情,这次就先写到这里,下次(如果我还记得的话),可以聊聊 RSA 和币圈的一点小八卦。

按照前几篇的套路,文末还是要贴一下招聘广告:

我在网盟广告业务线(穿山甲),由于业务持续高速发展,长期缺人、不限 HC 。关于字节跳动面试的详情,可参考我之前写的《程序员面试指北:面试官视角》

https://mp.weixin.qq.com/s/Byvu-w7kyby-L7FBCE24Uw

~ 投递链接 ~

后端开发(上海) https://job.toutiao.com/s/sBAvKe

后端开发(北京) https://job.toutiao.com/s/sBMyxk

广告策略研发(上海) https://job.toutiao.com/s/sBDMAK

其他地区、职能线 https://job.toutiao.com/s/sB9Jqk

Mar 22

PYTHON RSA加解密 不指定

felix021 @ 2020-3-22 00:31 [IT » 其他] 评论(0) , 引用(0) , 阅读(1968) | Via 本站原创
和某厂通信需要按其要求用rsa加密某段数据,该厂给了个Example.java,和一个X509 Certificate。

之前是把java编译好,然后在python里用system来调用它,有点丑。

最近需要复用这段代码,希望代码干净点,所以在Python里重新实现一遍。

# 1. 将 x509cer 转成  PEM 格式
import java.io.*;
import java.util.Base64;
import java.security.PublicKey;
import java.security.cert.CertificateFactory;
import java.security.cert.X509Certificate;

public class Test2
{
    public static PublicKey getPublicKeyByX509Cer(String cerFilePath) throws Exception
    {
        InputStream x509Is = new FileInputStream(cerFilePath);
        CertificateFactory certificatefactory = CertificateFactory.getInstance("X.509");
        X509Certificate cert = (X509Certificate)certificatefactory.generateCertificate(x509Is);
        x509Is.close();
        return cert.getPublicKey();
    }

    public static void main(String[] args) throws Exception {
        PublicKey pubKey = getPublicKeyByX509Cer("public.cer");
        System.out.println(Base64.getEncoder().encodeToString(pubKey.getEncoded()));
    }
}


输出PEM编码的公钥,类似:MIGfMA0GCSqGSIb3DQ...(中间省略)...rAvxiOfQIDAQAB


# 2. 在Python中加密

#!/usr/bin/python
#coding:utf-8
import base64
import binascii
import Crypto
from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_v1_5

PUBLIC_KEY = "MIGfMA0GCSqGSIb3DQ...(中间省略)...rAvxiOfQIDAQAB"

#返回base64编码后的密文
def RSAEncrypt(message, pubkey):
    binary = base64.b64decode(pubkey)
    key = RSA.importKey(binary)
    #PKCS#1建议的padding需要占用11个字节
    length = (key.size() + 1) / 8 - 11

    cipher = PKCS1_v1_5.new(key)
    res = []
    for i in range(0, len(message), length):
        res.append(cipher.encrypt(message[i:i+length]))
    result = ''.join(res)
    return binascii.hexlify(result)

print RSAEncrypt("123456", PUBLIC_KEY)


由于该厂在Java代码中使用 "RSA/NONE/PKCS1Padding",和PKCS1_v1_5的默认padding一致,因此不需要特殊处理。

注:
如果希望使用 NoPadding,看起来Python的Crypto没有直接提供支持,可能需要用PKCS1_OAEP并自己填充ASCII 0(但不确定,好像OAEP也包含了某种padding,encrypt的文档里说"长度需要 - 2 - 2倍hashcode长度"),几年前用PHP的时候踩过坑,详见
  https://www.felix021.com/blog/read.php?2169
  RSA: Java bouncy castle 与 PHP openssl_public_encrypt 兼容的那点事儿

# 3. 解密

反向处理就好,先base64 decode,分段解密再拼起来

PRIVATE_KEY = "MIICXQIBAAKBgQ....."

# 输入是base64编码的密文
def RSADecrypt(message, prikey):
    binary = base64.b64decode(prikey)
    key = RSA.importKey(binary)
    length = (key.size() + 1) / 8
    cipher = PKCS1_v1_5.new(key)
    message = binascii.unhexlify(message)
    res = []
    for i in range(0, len(message), length):
        res.append(cipher.decrypt(message[i:i+length], 'sentinel: random message'))
    result = ''.join(res)
    return result


注:decrypt方法的文档里说,"sentinel" 应当是一个无意义的字符串,并且尽量应当和典型的明文长度相似(这里偷懒了)。因为PKCS1_v1_5没有完善的完整性校验,某个构造的输入可能可以被正确解码,虽然看起来是一串没有意义的随机文字。加上sentinel以后,当解密出错的时候,会返回指定的 sentinel 继续后续处理流程,从而可以躲避选择密文攻击的检测。

关于这个选择密文攻击的细节可参考这篇文章:SSL.TLS协议安全系列:SSL的Padding Oracle攻击


# 4. 其他

可以用这个命令来生成RSA的公私钥对
引用
$ openssl genrsa -out test.pem 1024
$ openssl rsa -in test.pem -pubout -out test_public.pem


RSA.importKey(key) 方法的 key 也可以直接使用 PEM 文件的内容,也可以用 base64 decode 以后的 binary data。
Feb 15
== 结构化面试 ==

在字节跳动,我们使用结构化面试法来考查应聘者的技能。

所谓结构化,指的是将各种知识技能做好划分,例如编程语言,操作系统,数据库,网络,算法,工程/架构设计,并通过几个面试官之间的多轮交叉面试来考查掌握程度。

这样的面试方法,可以避免某个面试官考察太偏,并充分挖掘候选人的亮点。

== 技能 ==

在具体的面试中,每一个方向都会由浅入深去考查。

以编程语言为例,比如某个应聘者常用语言是Python,我会先考查一些语言的基础特性,例如什么是magic function,__repr__ 和 __str__ 的区别等。

确认候选人对语言的使用掌握符合预期后,再考查候选人对python底层实现的理解,例如展开聊聊python的gc相关知识。

更进一步,可以结合一些具体的应用场景来考查候选人对语言的综合应用能力,例如使用Python的多线程,需要考虑什么,如何提高某些任务中的效率等。

通过这样的综合考察,我避开了所有学过下面这本书的程序员。

点击在新窗口中浏览此图片


== 算法 ==

值得一提的是算法/数据结构,这是字节跳动面试的一大特点,也是网上各面经都会提(tu)到(cao)的。

点击在新窗口中浏览此图片

通常来说每一轮面试都会要求候选人完成一道算法题,现场面试就直接在纸上写,远程面试则是在在线共享编辑的IDE环境里完成。

可能早期常有面试官让候选人手写红黑树,以至于"手写红黑树"已经成为一个内部梗。

点击在新窗口中浏览此图片

实际上难度没有太夸张,通常来说15分钟内完成 Leetcode Medium 级别的题目,就能满足面试要求了(划重点)。

我更倾向于考查操作基础数据结构的题目,关注点放在对代码的掌控力,而不是某个具体的算法。

不过,对于有ACM经历的同学,面试官可能会尝试用 Hard 级别题目来challenge。比如我内推的某同学被问了 manacher's algorithm,可能是和面试官八字不合。

但也不用太担心,毕竟不是谁都像他一样拿了ACM金牌。

点击在新窗口中浏览此图片

== 沟通 ==

候选人的沟通能力也是考查的重点。

例如,在面试中的工程设计题通常是开放式问题,题面往往不是精确的,问题的规模,可能存在的问题,或者可以忽略的一些细节,都可以在前期的沟通中确认,然后再开始设计。

点击在新窗口中浏览此图片

还有,在面试过程中的知识盲点,要注意避免不懂装懂的强行作答,但利用已有知识做出的合理推测则是加分项。两种行为的边界可能有点模糊,这就考验候选人的沟通技巧了。

== 总结 ==

我想要招什么样的候选人?概括而言就是:聪明,勤奋,有潜力。

更具体的,大佬早就讲过了,推荐阅读字节跳动创始人张一鸣的演讲《我面了两千个年轻人,发现混得好的都有这5种特质》:https://www.toutiao.com/i6681549238490366472

== 硬广 ==

最后,我目前在字节跳动的网盟广告业务线(穿山甲),由于业务持续高速发展,长期缺人、不限HC,欢迎踊跃投递:

后端开发(上海):https://job.toutiao.com/s/sBAvKe

后端开发(北京):https://job.toutiao.com/s/sBMyxk

广告策略研发(上海):https://job.toutiao.com/s/sBDMAK

测试开发(上海):https://job.toutiao.com/s/sBUKuh

其他地区、职能线:https://job.toutiao.com/s/sB9Jqk
Sep 21
最近线上服务压力很大,api的p99有点扛不住。

广告业务对延时的要求普遍比较严格,有些adx设置的超时时间低至100ms,因此亟需找出性能热点。

根据对目前系统情况的估计(和metrics埋点数据),大致估计问题出在广告的正排环节。

使用 pprof  也证明了这一块确实是热点:

引用
$ go tool pprof http://$IP:$PORT/debug/pprof/profile
...
(pprof) top 10
Showing nodes accounting for 25.50s, 32.63% of 78.14s total
Dropped 1533 nodes (cum <= 0.39s)
Showing top 10 nodes out of 284
      flat  flat%  sum%        cum  cum%
    4.56s  5.84%  5.84%      4.87s  6.23%  syscall.Syscall
    4.03s  5.16% 10.99%      4.03s  5.16%  runtime.aeshashbody
    3.50s  4.48% 15.47%      6.01s  7.69%  git.xxx.org/xxx/target.NewFilter
    2.78s  3.56% 19.03%      3.73s  4.77%  runtime.mapaccess2_fast64
    2.63s  3.37% 22.40%      4.52s  5.78%  runtime.mapiternext
    2.08s  2.66% 25.06%      2.16s  2.76%  runtime.heapBitsForObject
    1.65s  2.11% 27.17%      1.93s  2.47%  runtime.mapaccess1_fast64
    1.57s  2.01% 29.18%      2.96s  3.79%  runtime.mapaccess2
    1.43s  1.83% 31.01%      2.06s  2.64%  runtime.runqgrab
    1.27s  1.63% 32.63%      1.27s  1.63%  runtime.epollwait
(pprof) png
Generating report in profile001.png (使用生成的线框图查看耗时)


其中第三行 NewFilter 就是正排过滤函数。因为一些历史原因,系统里不是所有定向条件都使用了倒排,正排实现起来毕竟简单、容易理解,而一旦开了这个口子,就会有越来越多正排加进来,推测是这个原因导致了性能的逐渐衰退。

经过讨论,D同学花了一周多的时间,逐个梳理重写。在Libra(字节跳动内部的ABTest平台,参考谷歌分层实验框架方案)上开实验,平均耗时 -9%,从统计数据上来说,实验组比对照组有了显著的改进,但从最终结果上,整体的p95、p99超时都出现了进一步恶化。

这说明真正的问题不在于正排的计算,优化的思路出现了偏差。

考虑到晚高峰期间的cpu占用率也只是刚超过50%,也就是说有可能性能问题在于锁,但pprof的 block 和 mutex 都是空的,没有线索。

猜测问题有可能在日志,代码里确实用得不少。日志用的是 github.com/ngaut/logging 库,每一次调用都会用到两个全局mutex。但通过调整log level 为error级别,大幅减少了日志量,并没有看到性能的改善。

经过搜索,发现 uber 基于 pprof 开发了一个神器 go-torch,可以生成火焰图。安装好 go-torch 及依赖 FlameGraph 以后执行

引用
$ go-torch  -u http://$IP:$PORT -f cpu.svg
INFO[14:52:23] Run pprof command: go tool pprof -raw -seconds 30 http://$IP:$PORT/debug/pprof/profile
INFO[14:52:54] Writing svg to cpu.svg


用 Chrome 打开 cpu.svg,人肉排查:

点击在新窗口中浏览此图片

可以看到,在NewFilter旁边竟然还有一个耗时接近的 runtime.growslice ,结合实际代码(略作简化),可以推测是 slice 的初始化长度不足。

matchAds := make([]*ad, 0, 4096)
adsBitMap.GetList(func(seq int) {
    if NewFilter(ctx, ad) {
        matchAds = append(matchAds, adlist[seq])
    }
})

// 顺便提一下,bitmap是一个uint64数组,GetList(f) 是将每一个等于1的bit索引传给 f
// GetList方法里面用了cpu的BSF指令来提高性能。



实际上最终定向后得到的广告往往在数万甚至数十万的级别,而 go 的 slice 扩容在超过1024个元素以后是1.25倍,可想而知会出现大量的内存分配和拷贝,导致性能随着广告数量的增加逐渐恶化。最近的广告数量也确实有了大幅的上升 —— 逻辑上形成了闭环。

经过优化,使用更大的初始化长度,并且使用 sync.Pool 来进一步减少内存分配,最终上线后p95和p99都下降了超过50%,效果显著。

参考:
golang 使用pprof和go-torch做性能分析 https://www.cnblogs.com/li-peng/p/9391543.html
Aug 10

记 python 超时的一个坑 不指定

felix021 @ 2019-8-10 13:34 [IT » 其他] 评论(1) , 引用(0) , 阅读(4992) | Via 本站原创
# 背景

有一个 python 脚本调用 A 服务的 x 接口获取若干 GB 的数据(大量对象),读取和解析大约需要 5 分钟。

由于 x 接口的改造,需要改成调用 B 服务的 y 接口。

A、B 服务都是基于字节跳动的 KITE 框架开发的(今日头条Go建千亿级微服务的实践),通信协议是 thrift 0.9.2 。

# 现象

改成调用 B 服务,在测试过程中发现,每次大约到 3 分钟以后就会出现报错 TTransportException(TSocket read 0 bytes);之后会重试,但第一次报错后,之后每次大约1分钟内就会再次报同样的错误,重试 3 次后放弃、进程退出。

# 排查

1. 由于测试的时间是晚高峰,初步判断可能是晚高峰服务端压力太大导致。次日平峰期测试仍然复现。

2. 搜索,发现有人遇到类似问题,是从 thrift 0.9 升级到 1.0,服务端没有进行 utf8 编码导致客户端的解析问题,他通过修改服务端代码解决。然而服务端显然不存在问题,因为其他的服务调用该接口表现稳定。此外我遇到的问题并没有升级thrift版本。

3. 还是从报错信息入手,在代码里搜索 "TSocket read 0 bytes",来自于 python2.7/site-packages/thrift/transport/TSocket.py

  def read(self, sz):
    try:
      buff = self.handle.recv(sz)
    except socket.error, e:
      if (e.args[0] == errno.ECONNRESET and
          (sys.platform == 'darwin' or sys.platform.startswith('freebsd'))):
        self.close()
        buff = ''
      elif e.args[0] == errno.EINTR:
        buff = self.handle.recv(sz)
        if len(buff) > 0:
          return buff
      else:
        raise
    if len(buff) == 0:
      raise TTransportException(type=TTransportException.END_OF_FILE, message='TSocket read 0 bytes')
    return buff


4. 通过插入调试代码,发现并没有抛出异常,说明确实只读到了 0 字节,因此可以大致判断问题发生在 server 端。

5. 查看 B 服务的 log,发现确实有“客户端超时” 的报错信息。通过查看 KITE 框架的文档,发现默认的超时时间是 3 秒,A服务在配置文件里指定了 20s 的超时时间,而 B 服务没有指定。

6. 通过修改 B 服务的超时时间,调用成功。但为什么 python 作为一个客户端,会出现长达 3s 的停顿导致超时呢,尤其是在局域网甚至本机环境,不可能是网络原因。

7. 联想到曾经踩过的一个坑(详见:https://www.felix021.com/blog/read.php?2142),猜测是python的gc导致。虽然python是引用计数,但为了避免循环引用导致的内存泄漏,还是有一个 stw 的 gc 扫描。通过关闭这个扫描,就解决了这个超过 3s 的停顿

import gc
gc.disable()


# 吐槽

python真是慢。同样一个api,golang只要17s就完成了调用、反序列化,而python需要长达5分钟。

# 吐槽 #2

大概过了半个月,python把内存用爆了,最后只好用 go 重写了。
Aug 10
1. 现象

某日线上服务报警(基于时序数据库做的),请求量大幅下滑。

观察ganglia监控图表,发现有部分机器CPU占用率断崖式下跌,从原先的1000%+下降到100%(20核40线程的CPU),通过内存监控可以确认服务本身并未重启。

登录异常机器,用 lsof -i :PORT1 也可以看到端口号仍被占用,但是却无法接受请求;同样,该服务的 pprof 监听端口 PORT2 能接受请求,但无响应请求。

2. 排查

在异常机器上通过  "netstat -antpl | grep CLOSE_WAIT | grep PORT1 | wc -l" 可以看到有大量连接等待关闭,达到连接上限,所以无法接受请求,PORT2 则正常。

挑一台机器重启后服务恢复正常。为了恢复业务,重启了大部分异常机器上的服务,保留两台持续排查。

使用 top 查看cpu占用率,如上所述,始终保持在 100% 左右,说明有一个线程在全速运行。

通过 perf top (注:也可以使用pstack,能看到更详细的调用栈),发现是某一个二分查找的函数在占用cpu。

经过对代码的分析,发现是传入的值小于有效查找范围,代码实现不完善,导致出现了死循环。

进一步排查发现某个api未做好数据有效性保护,导致出现无效数据。

3. 分析

问题的直接原因已经定位,但是不明确的是,为什么一个 goroutine 死循环会导致进程整体hang住?

cpu 占用率只有100%,说明只有一个 goroutine 死循环,根据 Go 的 GMP 模型,理论上应该可以schedule其他的 goroutine 继续接受请求。

查看该进程的线程数(cat /proc/PID/status),看到开启了80+系统线程,说明不是线程数量的问题。

尝试查看该进程的 goroutine 数,但 pprof 不可用,而负责这个 metrics 打点的 goroutine 自从异常以后也未再上报数据。

写了一个简单的样例代码,开启一个简单死循环的goroutine,并不会阻碍其他goroutine的执行。
func test1() {
        fmt.Println("test1")
        i := 0
        for {
                i++
        }
}

func main() {
        go test1()
        for i := 0; i < 100; i++ {
                time.Sleep(1 * time.Second)
                fmt.Printf("i = %d\n", i)
        }
}


有一位同学根据现象搜到了这篇文章: 如何定位 golang 进程 hang 死的 bug

根据这篇文章的分析,在有死循环goroutine的情况下,其他goroutine主动调用 runtime.GC() 会出现 hang 住的情况。

验证代码如下,确实符合预期,和前述事故的表现一致。

func test1() {
        fmt.Println("test1")
        i := 0
        for {
                i++
        }
}

func main() {
        go test1()
        for i := 0; i < 100; i++ {
                time.Sleep(1 * time.Second)
                fmt.Printf("i = %d\n", i)
                if i == 3 {
                        runtime.GC()
                }
        }
}


综合以上分析可知,当 golang 中出现一个死循环的 goroutine、该 goroutine 就会一直占用 cpu,无法被调度;而需要 STW 的 gc 又无法暂停该 goroutine,因此出现了一个调度上的死锁。

另外,根据那篇文章的说法,在 for 循环中没有函数调用的话,编译器不会插入调度代码,所以无法完成抢占式调用。《深入解析Go - 抢占式调度》中也有具体的说明 https://tiancaiamao.gitbooks.io/go-internals/content/zh/05.5.html

实际测试发现,如果是调用自己写的另外一个简单函数,仍然会出现死锁,而调用注入 fmt.Println 之类的函数,则不会出现死锁,说明Go并不是在函数调用的时候插入调度检测代码(这也不符合直觉,每次函数调用都有额外性能开销,不太划算),而是在某些库函数中增加了调度检测。

完。

Aug 2
- 堆和栈有什么区别?
- 什么分配在堆上,什么分配在栈上?
- 为什么有了堆还需要栈/有了栈还需要堆?
- 效率差别在哪儿?如何优化?
- 有哪些常见的内存分配算法?
- 内存分配算法的主要挑战是什么?如何解决?

继续引申还有gc的一系列问题
这一篇写得还蛮好的:https://blog.csdn.net/jiahehao/article/details/1842234 ,但是注意不要被最后一段话洗脑。
分页: 5/103 第一页 上页 1 2 3 4 5 6 7 8 9 10 下页 最后页 [ 显示模式: 摘要 | 列表 ]