Charlie and Dave

公司希望弄一套双授权的安全系统,老大提供了一套算法,求大家review。如果这个方案确实可行,那么我们会做完然后开源出来给大家用。

Author and License

Author: 韩拓
保留所有权利
All Rights Reserved
以下内容不以cc-by-sa3.0发布。(因为根本不是我的创作)

场景

  1. Alice希望登录到Bob上执行操作。
  2. 两者的基本控制协议为ssh。

假定

  1. 攻击者名叫Mallory。
  2. 如果Alice的私钥泄漏,管理者必须有权停止Alice到Bob的访问而不需要更换所有Bob的公钥。
  3. 除去Alice和Bob外,参与通讯过程的所有机器(即下文中的Charlie和Dave)中可能随机被攻破一台。
  4. 服务都在内网,但是如果网关和被攻破的机器是同类系统,Mallory即可具有内网监听和伪造数据报文的权限。
  5. Alice不会利用获得的Bob的权限故意执行危害性指令(但是可能被诱骗)。
  6. Alice和Bob不会被攻破。

方案

假定有两台机器,Charlie和Dave,Dave和网关不得是同类系统。根据假定4,两台机器不会同时被攻破。

  1. Alice通过SSL和Dave建立连接,上报自己的用户名,需要访问的设备和帐号,并提交一个临时生成的ssh pubkey(username, account, host, pubkey)。
  2. Dave根据预先设的IP-username-sslkey验证用户身份为Alice,并且根据ACL确认其具有访问权限。
  3. 如果通过验证,那么Dave用自己的key,通过SSL联系Bob上的某个程序,将Alice的pubkey提交到Bob的合适帐号上(account, pubkey)。
  4. Bob通过sslkey验证提交者确系Dave,将pubkey临时加入account中。
  5. Bob完成此事后,通过Dave向Alice返回成功。
  6. Alice通过SSL和Charlie联系,上报自己的(username, account, host)。
  7. Charlie根据预设的IP-username-sslkey验证用户身份为Alice,并且根据ACL确认其具有访问权限。
  8. 如果通过验证,那么Charlie用自己的key,通过SSL联系Bob上某个程序,为Alice开通到Bob的22端口的tcp盲转发。
  9. Alice利用开启的tcp通道,和自己的临时ssh private key验证登录Bob。
  10. 在Alice连接Bob上的程序后,删除alice留在Bob上的临时pubkey。

验证

假定Charlie被攻破。

  1. 方案1-5没有影响。
  2. Charlie拥有能够在任意一台机器上开启盲转发的权限。
  3. 但是Charlie并不能影响Dave去添加pubkey。

假定Dave被攻破。

  1. Dave拥有在任意一台机器上添加pubkey的权限。
  2. 但是Dave并不具有打开到任意一台机器ssh端口的权限。

无题

路过南京,突然想起前几年在狮子桥吃的鸭血粉丝汤。什么味道其实已经忘了,只是在干完了活后等火车回上海。看时间,与其在火车站无聊还不如在狮子桥吃点东西。

其实这不是我头一回吃这家。刚毕业的时候,没钱,但是又想出去玩。于是就一个人去了南京。那时南京倒是还有个朋友,可是我放假的时候人家也放假,所以还是一个人在南京到处跑。有天晚上,就是在狮子桥吃的晚饭。同样的店,同样的座位。

我已经想不起来两次看到的景观有什么细微的差别。大概来说,无非就是几个消防栓什么的。但是几年间,他们居然没有什么太大变化。

我又想起了外婆家,我长大的地方。从大体上看,好像也没什么太多的变化。但是细微处还是变了。我结婚搬了出去,外公也走了,留外婆一人独住。于是,很多东西都开始凑合了起来。原本电饭锅坏了大概是会去换一个的,现在也懒得换了。冰箱里也塞满了隔夜菜,有些甚至会隔月。

有形的东西总是会坏的,无形的东西总是会被忘记的。无论什么,消失才是大多数的宿命。和宇宙比起来,这地球只能算是沧海一粟。和时间比起来,人的生命只不过是白驹过隙。就在这小小的地球上,有多少匹白驹曾经越过溪水呢?你记住了几匹?又有几匹,曾经看到过我看的东西。狮子桥的消防栓,我的博客,火车站的长椅。他们总也有坏掉的一天,也有被人忘记得一天。记得他们的人,也有离去的一天,写下他们的文字,总有丢失的一天。直到有一天,他们的形体早已经消亡,痕迹再也不能从地球上找到。甚至记得他们痕迹的人的痕迹都已随风而逝。这时候,他们就像其他的白驹一样,成为了一个数字。

北海道之行的感想

礼貌的老奶奶

这次去日本,让我最受震动的是一位老奶奶。

大家知道我们的日语很差。我没学过,老婆只会简单的日语。所以我们在大通那里问路的时候,预期是很麻烦的。结果旁边有位老奶奶,直接给领到地方。最后走的时候,她的方向和我们相反的。虽然我日语不算太好,好歹听懂了最后一句是“请路上小心,务必保重”。

您太客气了吧。如果在中国碰到这种情况,别说我们的日语这幅德行。就算语言沟通无碍,最多也是指路,或者顺路领过去。更何况我们这种沟通情况,外加您一不顺路,二年龄又大。着实让我们觉得汗颜。

后来听同事们说,在日本问路,不管远近,只要愿意搭理你的,一律是领到地方。当然我们碰到的数量很小,所以参考意义不大。
我觉得我们纯粹是占了外国人的便宜。

唉,礼仪之帮。。。

根本不看车

原来twitter上有个笑话。从日本来中国,过马路的时候一定会被撞死。我测试了一下,原来不是笑话。

在日本过马路的时候,压根不用看车,哪怕你乱穿马路。我在街上过马路,正好碰到行人和司机都是绿灯。我示意司机先走,结果司机在那里等我。我再示意,他再等。我看看我等不起。举手谢谢,然后先走了。

这种情况占了大多数。只有少数司机,你示意他先走,他举手表示感谢,然后先走的。大多数司机根本在那里傻等着。

回国第一天,绿灯过街的时候看到一辆右转。我看了一眼,脑子里压根就没浮起来我还得让他。结果差点撞上。

这似乎和法律都没什么关系了。中国的法律是同时绿灯的,车辆让行人。行人和车辆碰撞,车辆全责。如果大部分人还是没什么顾忌。我估计要么罚到的概率太低,都有侥幸心理。要么赔偿数目过低,大部分人也不在乎。

精美而细致的商品

日本商品的一大特点就是精美而细致。便利店买个牛丼,两层装就不说了。大陆全家卖的红烧牛肉饭也是两层的。上面还粘帖了一个油料包,一个辛辣味调料包,可以自由添加或者不添加。最狠的是,里面带的筷子还有一个方便的撕开口,和一个很不错的一次性牙签。大陆全家的筷子带撕开口不错,但是却不好用,很难撕开,而且没牙签。

卖个碳酸饮料,带巨人或者海贼王宣传。去餐厅吃饭,路上一堆天体的海报。路过地铁,里面有动漫在周边更是平常到不能再平常。

简单来说这种做法就是附加值高。一个商品,本身只有100,却附加上100的附加值,还更容易卖。对于一个资源缺乏的国度来说,大批量的将资源加工成产品然后输出是不合算的。显然加工的深度越深,产生的利润越高。

中国目前根本没到这个地步,估计是因为中国的商品还没有到“难卖”的地步,或者说中国卖东西和“营销”没什么太大关系。我们总是能够找到某些办法,把产品搞出去。至于要赚钱,好像也不是靠老老实实的做产品,或者做一些营销能够搞定的。以至于我们始终宣传和重视“营销”,脑子里想的东西却和“营销”没有什么太大关系。

过度包装和垃圾分类

日本商品的一大毛病就是过度包装,而且是让人看不下去的精致包装。当然,这和“精美而细致的商品”是一脉相承的。

跑到店里,要一个挂坠,说要送人。挂坠本身带一个塑料壳,店员又给你拿一个纸袋子包好,贴个胶带封上,然后装在塑料袋里。合着一个挂坠套三层,包装比东西还重。

但是同时,日本又有着高效的垃圾分类-回收利用系统。导游介绍日本的垃圾回收率高达九成(我不知道他哪里来的数字)。按照这个来算的话,就算过度包装,人均垃圾产量依然比中国低的多。

从我看到的资料上看,至少在昭和时代早期(差不多是中日战争时期),就开始宣传资源回收了。想想也是,日本这种缺乏资源的国度要对外开战的话,节约自己的每一分资源是非常有必要的。

大雪时没有雪的街道

在札幌,我们碰到了大雪。鹅毛大雪整个落下来,一晚上能落上数十公分厚(最大降雪是130公分)。但是第二天早上七点我起床看外面,整个街道上干干净净,没有积雪,甚至连雪水融化后打湿街面都看不到。

这意味着扫雪的人至少要在早上六点就开始工作了。

当然,还是有不少街道是有雪的,尤其是还在施工的街区前面。所以这让我怀疑扫雪是有临街商铺自行负责的。否则一个城市的环卫系统很难调度这么庞大的资源,来扫除整个城市的积雪。

而且在街道上有很多箱子,里面放着一包包不知道是沙子还是盐的东西,写着可以免费使用。按照标签,是用于街区防滑的。

札幌大通公园的辐射计数器

在我的照片里有,0.033uSv/h。按照这个计算,一年的辐射量是300uSv左右。按照建议,一年最大接受1mSv的辐射。可见辐射量不算太大。

自从311海啸之后,日本人似乎对辐射量特别敏感。我专门看了两期海啸和辐射有关的节目。日本人是认认真真,自己买仪器,在不同位置不同高度测量辐射计量的。我很好奇,如果让他们来冬天的华北大地逛一圈的话。。。

北海道旅游——札幌附近地区攻略

札幌

白色恋人巧克力工坊

在宫の沢站,从大通坐东西线,340就可达。

工坊庭院非常漂亮,整点有音乐表演。一楼进去是商店,可以在那里买到全系列的产品。小火车在往里走,不过我们去的时候人挺多,很遗憾没坐上。

工坊在9:30, 11:30, 13:30, 15:30提供亲手制作巧克力饼干的课程,必须赶准时间否则就得等下一批。参观博物馆是600一人,我们报的课程是1250的,报名者参观打折到500。

课程并不复杂,戴好装备走进去,大约一刻钟到半小时的操作后,出来等烘陪结果。大约20分钟后再进去裱花,然后就可以带走了。很多小孩进去体验的,大人还可以在外面看着。

带小孩进去的需要注意安全,最好有大人陪同。

博物馆里有很多老式留音机,碰到半点(准确时间不确定)还会有表演。

建议一早冲过去,踩准点,否则容易碰到白白等着。做饼干的空余,出来在餐厅喝个茶,吃点糕点,看看风景。一般还能看到音乐表演。逛到楼下直接买点东西就走。

36片的巧克力饼干折扣价在2400日元上下,目前汇率折合人民币120上下。

蟹将军

在ささきの那里,离开狸小路非常近。从大通可以走到。

全蟹宴大概4300-4500,按现在汇率,200多点的样子。店的定位非常高档,所以绝对超值。

整个店都是要脱鞋,全地板铺塌塌米。上了一堆螃蟹,最后还有一道泡饭,是穿着和服的女服务员帮着处理的。手势超级优雅,感觉碉堡了。

狸小路

在大通南边一点,是一条非常热闹的步行街。

去的话可以先学学小钢珠(パチンコ)的玩法。其实没啥好学的,就是扔进去,完了按按钮。但是老婆楞是没看懂,没上去玩。主要是,我们完全没想到这种简单的规则还能当游戏玩。。。

狸小路5那里有个免税店,店员的中文相当不错,价格也基本是最低了(至少白色恋人巧克力是这样)。我在那里基本扫齐了所有货。

狸小路上有一家饺子の王將,两盘饺子加一个杏仁豆腐才733。换成人民币大约36,和上海基本持平。关键是,好吃到爆啊!!!顿时觉得上海的饺子店弱爆了。

居酒屋

我们总计吃了两次居酒屋。

首先,大部分居酒屋都有服务费。例如毛巾,前菜什么的。一般是一个人500上下。我们第一次不知道,进去点了1500的东西,被收了2500。老婆日语太差,还不敢问。后来就明白了,大部分这种店都是这样的。只要是居酒屋类的,都会收取一定的服务费。蟹将军不是很确定,可能也是收了服务费的。

但是,居酒屋的点菜超级困难。根据大熊酱的说法,日语二级进去也未必能全身而退。我老婆日语还不一定比我强,去了就要英文菜单了。

居酒屋基本就是吃个意思。论性价比还是饺子の王將,或者吉野家之类的比较好。可是真去日本的,基本不会选择这些。

小樽

小樽没啥好说的,总共才去了半天。

nikka的威士忌酒厂没啥好看的,倒是商店里面的商品还算不错。有很漂亮的小瓶威士忌,当纪念品很好。

情书拍摄地很坑。

商店街那里看个人喜欢。玻璃制品和八音盒都很漂亮,让人担心自己的钱包。有空的话可以多逛一下,买点海鲜吃。

滑雪

坑爹。第一天跑过去,大雪关门。第三天跑过去,还有半个小时关门。

所以,这次滑雪行程没有滑到雪。

不要玩一些太少人玩的东西啊,只有一个人玩的结果就是很可能投票失败。。。

洞爷湖

我们住的酒店叫做洞爷湖万世屋。我开始还不知道。出门一看,越后屋。我了个去。尼玛万事屋不是因为空知英秋根本住过这间吧。

不管了,扫货。整个店里面,大部分动漫都是银魂和天体的周边(偷偷说,酒店去餐厅路上还能看到天体的海报)。

登别

地狱谷有鬼灯的画报。好像还有周边,但是没空逛。

上下文切换技术

上下文切换技术

简述

在进一步之前,让我们先回顾一下各种上下文切换技术。

不过首先说明一点术语。当我们说“上下文”的时候,指的是程序在执行中的一个状态。通常我们会用调用栈来表示这个状态——栈记载了每个调用层级执行到哪里,还有执行时的环境情况等所有有关的信息。

当我们说“上下文切换”的时候,表达的是一种从一个上下文切换到另一个上下文执行的技术。而“调度”指的是决定哪个上下文可以获得接下去的CPU时间的方法。

进程

进程是一种古老而典型的上下文系统,每个进程有独立的地址空间,资源句柄,他们互相之间不发生干扰。

每个进程在内核中会有一个数据结构进行描述,我们称其为进程描述符。这些描述符包含了系统管理进程所需的信息,并且放在一个叫做任务队列的队列里面。

很显然,当新建进程时,我们需要分配新的进程描述符,并且分配新的地址空间(和父地址空间的映射保持一致,但是两者同时进入COW状态)。这些过程需要一定的开销。

进程状态

忽略去linux内核复杂的状态转移表,我们实际上可以把进程状态归结为三个最主要的状态:就绪态,运行态,睡眠态。这就是任何一本系统书上都有的三态转换图。

就绪和执行可以互相转换,基本这就是调度的过程。而当执行态程序需要等待某些条件(最典型就是IO)时,就会陷入睡眠态。而条件达成后,一般会自动进入就绪。

阻塞

当进程需要在某个文件句柄上做IO,这个fd又没有数据给他的时候,就会发生阻塞。具体来说,就是记录XX进程阻塞在了XX fd上,然后将进程标记为睡眠态,并调度出去。当fd上有数据时(例如对端发送的数据到达),就会唤醒阻塞在fd上的进程。进程会随后进入就绪队列,等待合适的时间被调度。

阻塞后的唤醒也是一个很有意思的话题。当多个上下文阻塞在一个fd上(虽然不多见,但是后面可以看到一个例子),而且fd就绪时,应该唤醒多少个上下文呢?传统上应当唤醒所有上下文,因为如果仅唤醒一个,而这个上下文又不能消费所有数据时,就会使得其他上下文处于无谓的死锁中。

但是有个著名的例子——accept,也是使用读就绪来表示收到的。如果试图用多个线程来accept会发生什么?当有新连接时,所有上下文都会就绪,但是只有第一个可以实际获得fd,其他的被调度后又立刻阻塞。这就是惊群问题thundering herd problem

现代linux内核已经解决了这个问题,方法惊人的简单——accept方法加锁。(inet_connection_sock.c:inet_csk_wait_for_connect)

线程

线程是一种轻量进程,实际上在linux内核中,两者几乎没有差别,除了一点——线程并不产生新的地址空间和资源描述符表,而是复用父进程的。

但是无论如何,线程的调度和进程一样,必须陷入内核态。

传统网络服务模型

进程模型

为每个客户分配一个进程。优点是业务隔离,在一个进程中出现的错误不至于影响整个系统,甚至其他进程。Oracle传统上就是进程模型。

缺点是进程的分配和释放有非常高的成本。因此Oracle需要连接池来保持连接减少新建和释放,同时尽量复用连接而不是随意的新建连接。

线程模型

为每客户分配一个线程。优点是更轻量,建立和释放速度更快,而且多个上下文间的通讯速度非常快。

缺点是一个线程出现问题容易将整个系统搞崩溃。

一个例子

py_http_fork_thread.py

在这个例子中,线程模式和进程模式可以轻易的互换。

如何工作的

  1. 父进程监听服务端口
  2. 在有新连接建立的时候,父进程执行fork,产生一个子进程副本
  3. 如果子进程需要的话,可以exec(例如CGI)
  4. 父进程执行(理论上应当先执行子进程,因为exec执行的快可以避免COW)到accept后,发生阻塞
  5. 上下文调度,内核调度器选择下一个上下文,如无意外,应当就是刚刚派生的子进程
  6. 子进程进程进入读取处理状态,阻塞在read调用上,所有上下文均进入睡眠态
  7. 随着SYN或者数据报文到来,CPU会唤醒对应fd上阻塞的上下文(wait_queue),切换到就绪态,并加入调度队列
  8. 上下文继续执行到下一个阻塞调用,或者因为时间片耗尽被挂起

关于更多细节,可以看这里。这篇文章里还介绍了epoll的工作细节。

评价

  • 同步模型,编写自然,每个上下文可以当作其他上下文不存在一样的操作,每次读取数据可以当作必然能读取到。
  • 进程模型自然的隔离了连接。即使程序复杂且易崩溃,也只影响一个连接而不是在整个系统。
  • 生成和释放开销很大(效率测试的进程fork和线程模式开销测试),需要考虑复用。
  • 进程模式的多客户通讯比较麻烦,尤其在共享大量数据的时候。

C10K问题

描述

当同时连接数在10K左右时,传统模型就不再适用。实际上在效率测试报告的线程切换开销一节可以看到,超过1K后性能就差的一塌糊涂了。

更细节描述,可以看这里

进程模型的问题

在C10K的时候,启动和关闭这么多进程是不可接受的开销。事实上单纯的进程fork模型在C1K时就应当抛弃了。

Apache的prefork模型,是使用预先分配(pre)的进程池。这些进程是被复用的。但即便是复用,本文所描述的很多问题仍不可避免。

线程模式的问题

从任何测试都可以表明,线程模式比进程模式更耐久一些,性能更好。但是在面对C10K还是力不从心的。问题是,线程模式的问题出在哪里呢?

内存?

有些人可能认为线程模型的失败首先在于内存。如果你这么认为,一定是因为你查阅了非常老的资料,并且没仔细思考过。

你可能看到资料说,一个线程栈会消耗8M内存(linux默认值,ulimit可以看到),512个线程栈就会消耗4G内存,而10K个线程就是80G。所以首先要考虑调整栈深度,并考虑爆栈问题。

听起来很有道理,问题是——linux的栈是通过缺页来分配内存的(How does stack allocation work in Linux?),不是所有栈地址空间都分配了内存。因此,8M是最大消耗,实际的内存消耗只会略大于实际需要的内存(内部损耗,每个在4k以内)。但是内存一旦被分配,就很难回收(除非线程结束),这是线程模式的缺陷。

这个问题提出的前提是,32位下地址空间有限。虽然10K个线程不一定会耗尽内存,但是512个线程一定会耗尽地址空间。然而这个问题对于目前已经成为主流的64位系统来说根本不存在。

内核陷入开销?

所谓内核陷入开销,就是指CPU从非特权转向特权,并且做输入检查的一些开销。这些开销在不同的系统上差异很大。

线程模型主要通过陷入切换上下文,因此陷入开销大听起来有点道理。

实际上,这也是不成立的。线程在什么时候发生陷入切换?正常情况下,应当是IO阻塞的时候。同样的IO量,难道其他模型就不需要陷入了么?只是非阻塞模型有很大可能直接返回,并不发生上下文切换而已。

效率测试报告的基础调用开销一节,证实了当代操作系统上内核陷入开销是非常惊人的小的(10个时钟周期这个量级)。

EDIT: 受内核陷入效率测试的修正影响,这部分需要改正一下。

效率测试报告的基础调用开销一节,测量了当代操作系统上内核陷入开销。在样机上,典型的内核陷入开销在50ns这个量级。这个开销不算太小,但是却不足以说明缓慢。如果把内核陷入跑满一颗CPU,这颗CPU可以执行20M次陷入。每次陷入吞吐500字节数据的话,可以满足10G吞吐。何况在大流量的情况下,必然是大颗粒IO。大粒度IO陷入次数更少,也更节约CPU。

线程模型的问题在于切换成本高

熟悉linux内核的应该知道,近代linux调度器经过几个阶段的发展。

  1. linux2.4的调度器。
  2. O(1)调度器。
  3. CFS。

实际上直到O(1),调度器的调度复杂度才和队列长度无关。在此之前,过多的线程会使得开销随着线程数增长(不保证线性)。

O(1)调度器看起来似乎是完全不随着线程的影响。但是这个调度器有显著的缺点——难于理解和维护,并且在一些情况下会导致交互式程序响应缓慢。

CFS使用红黑树管理就绪队列。每次调度,上下文状态转换,都会查询或者变更红黑树。红黑树的开销大约是O(logm),其中m大约为活跃上下文数(准确的说是同优先级上下文数),大约和活跃的客户数相当。

因此,每当线程试图读写网络,并遇到阻塞时,都会发生O(logm)级别的开销。而且每次收到报文,唤醒阻塞在fd上的上下文时,同样要付出O(logm)级别的开销。

这里参考了这篇文章,在此表示感谢。这篇文章里面清楚的介绍了各种linux调度器技术(不包括bfs)。

分析

O(logm)的开销看似并不大,但是却是一个无法接受的开销。因为IO阻塞是一个经常发生的事情。每次IO阻塞,都会发生开销。而且决定活跃线程数的是用户,这不是我们可控制的。更糟糕的是,当性能下降,响应速度下降时。同样的用户数下,活跃上下文会上升(因为响应变慢了)。这会进一步拉低性能。

问题的关键在于,http服务并不需要对每个用户完全公平,偶尔某个用户的响应时间大大的延长了是可以接受的。在这种情况下,使用红黑树去组织待处理fd列表(其实是上下文列表),并且反复计算和调度,是无谓的开销。

多路复用

简述

要突破C10K问题,必须减少系统内活跃上下文数(其实未必,例如换一个调度器,例如使用RT的SCHED_RR),因此就要求一个上下文同时处理多个链接。而要做到这点,就必须在每次系统调用读取或写入数据时立刻返回。否则上下文持续阻塞在调用上,如何能够复用?这要求fd处于非阻塞状态,或者数据就绪。

上文所说的所有IO操作,其实都特指了他的阻塞版本。所谓阻塞,就是上下文在IO调用上等待直到有合适的数据为止。这种模式给人一种“只要读取数据就必定能读到”的感觉。而非阻塞调用,就是上下文立刻返回。如果有数据,带回数据。如果没有数据,带回错误(EAGAIN)。因此,“虽然发生错误,但是不代表出错”。

但是即使有了非阻塞模式,依然绕不过就绪通知问题。如果没有合适的就绪通知技术,我们只能在多个fd中盲目的重试,直到碰巧读到一个就绪的fd为止。这个效率之差可想而知。

在就绪通知技术上,有两种大的模式——就绪事件通知和异步IO。其差别简要来说有两点。就绪通知维护一个状态,由用户读取。而异步IO由系统调用用户的回调函数。就绪通知在数据就绪时就生效,而异步IO直到数据IO完成才发生回调。

linux下的主流方案一直是就绪通知,其内核态异步IO方案甚至没有被封装到glibc里去。围绕就绪通知,linux总共提出过三种解决方案。我们绕过select和poll方案,看看epoll方案的特性。

另外提一点。有趣的是,当使用了epoll后(更准确说只有在LT模式下),fd是否为非阻塞其实已经不重要了。因为epoll保证每次去读取的时候都能读到数据,因此不会阻塞在调用上。

epoll

用户可以新建一个epoll文件句柄,并且将其他fd和这个”epoll fd”关联。此后可以通过epoll fd读取到所有就绪的文件句柄。

epoll有两大模式,ET和LT。LT模式下,每次读取就绪句柄都会读取出完整的就绪句柄。而ET模式下,只给出上次到这次调用间新就绪的句柄。换个说法,如果ET模式下某次读取出了一个句柄,这个句柄从未被读取完过——也就是从没有从就绪变为未就绪。那么这个句柄就永远不会被新的调用返回,哪怕上面其实充满了数据——因为句柄无法经历从非就绪变为就绪的过程。

类似CFS,epoll也使用了红黑树——不过是用于组织加入epoll的所有fd。epoll的就绪列表使用的是双向队列。这方便系统将某个fd加入队列中,或者从队列中解除。

要进一步了解epoll的具体实现,可以参考这篇linux下poll和epoll内核源码剖析

性能

如果使用非阻塞函数,就不存在阻塞IO导致上下文切换了,而是变为时间片耗尽被抢占(大部分情况下如此),因此读写的额外开销被消除。而epoll的常规操作,都是O(1)量级的。而epoll wait的复制动作,则和当前需要返回的fd数有关(在LT模式下几乎就等同于上面的m,而ET模式下则会大大减少)。

但是epoll存在一点细节问题。epoll fd的管理使用红黑树,因此在加入和删除时需要O(logn)复杂度(n为总连接数),而且关联操作还必须每个fd调用一次。因此在大连接量下频繁建立和关闭连接仍然有一定性能问题(超短连接)。不过关联操作调用毕竟比较少。如果确实是超短连接,tcp连接和释放开销就很难接受了,所以对总体性能影响不大。

固有缺陷

原理上说,epoll实现了一个wait_queue的回调函数,因此原理上可以监听任何能够激活wait_queue的对象。但是epoll的最大问题是无法用于普通文件,因为普通文件始终是就绪的——虽然在读取的时候不是这样。

这导致基于epoll的各种方案,一旦读到普通文件上下文仍然会阻塞。golang为了解决这个问题,在每次调用syscall的时候,会独立的启动一个线程,在独立的线程中进行调用。因此golang在IO普通文件的时候网络不会阻塞。

推测libaio解决了这个问题(TODO: test)。

事件通知机制下的几种程序设计模型

简述

使用通知机制的一大缺憾就是,用户进行IO操作后会陷入茫然——IO没有完成,所以当前上下文不能继续执行。但是由于复用线程的要求,当前线程还需要接着执行。所以,在如何进行异步编程上,又分化出数种方案。

用户态调度

首先需要知道的一点就是,异步编程大多数情况下都伴随着用户态调度问题——即使不使用上下文技术。

因为系统不会自动根据fd的阻塞状况来唤醒合适的上下文了,所以这个工作必须由其他人——一般就是某种框架——来完成。

你可以想像一个fd映射到对象的大map表,当我们从epoll中得知某个fd就绪后,需要唤醒某种对象,让他处理fd对应的数据。

当然,实际情况会更加复杂一些。原则上所有不占用CPU时间的等待都需要中断执行,陷入睡眠,并且交由某种机构管理,等待合适的机会被唤醒。例如sleep,或是文件IO,还有lock。更精确的说,所有在内核里面涉及到wait_queue的,在框架里面都需要做这种机制——也就是把内核的调度和等待搬到用户态来。

当然,其实也有反过来的方案——就是把程序扔到内核里面去。其中最著名的实例大概是微软的http服务器了。

这个所谓的“可唤醒可中断对象”,用的最多的就是协程。

协程

协程是一种编程组件,可以在不陷入内核的情况进行上下文切换。如此一来,我们就可以把协程上下文对象关联到fd,让fd就绪后协程恢复执行。

当然,由于当前地址空间和资源描述符的切换无论如何需要内核完成,因此协程所能调度的,只有在同一进程中的不同上下文而已。

如何做到

这是如何做到的呢?

我们在内核里实行上下文切换的时候,其实是将当前所有寄存器保存到内存中,然后从另一块内存中载入另一组已经被保存的寄存器。对于图灵机来说,当前状态寄存器意味着机器状态——也就是整个上下文。其余内容,包括栈上内存,堆上对象,都是直接或者间接的通过寄存器来访问的。

但是请仔细想想,寄存器更换这种事情,似乎不需要进入内核态么。事实上我们在用户态切换的时候,就是用了类似方案。

C coroutine的实现,基本大多是保存现场和恢复之类的过程。python则是保存当前thread的top frame(greenlet)。

但是非常悲剧的,纯用户态方案(setjmp/longjmp)在多数系统上执行的效率很高,但是并不是为了协程而设计的。setjmp并没有拷贝整个栈(大多数的coroutine方案也不应该这么做),而是只保存了寄存器状态。这导致新的寄存器状态和老寄存器状态共享了同一个栈,从而在执行时互相破坏。而完整的coroutine方案应当在特定时刻新建一个栈。

而比较好的方案(makecontext/swapcontext)则需要进入内核(sigprocmask),这导致整个调用的性能非常低。

关于setjmp/longjmp,你可以参考CS360 Lecture notes — Setjmp,和setjmp 的正确使用 | 云风的 BLOG

协程与线程的关系

首先我们可以明确,协程不能调度其他进程中的上下文。而后,每个协程要获得CPU,都必须在线程中执行。因此,协程所能利用的CPU数量,和用于处理协程的线程数量直接相关。

作为推论,在单个线程中执行的协程,可以视为单线程应用。这些协程,在未执行到特定位置(基本就是阻塞操作)前,是不会被抢占,也不会和其他CPU上的上下文发生同步问题的。因此,一段协程代码,中间没有可能导致阻塞的调用,执行在单个线程中。那么这段内容可以被视为同步的。

我们经常可以看到某些协程应用,一启动就是数个进程。这并不是跨进程调度协程。一般来说,这是将一大群fd分给多个进程,每个进程自己再做fd-协程对应调度。

基于就绪通知的协程框架

  1. 首先需要包装read/write,在发生read的时候检查返回。如果是EAGAIN,那么将当前协程标记为阻塞在对应fd上,然后执行调度函数。
  2. 调度函数需要执行epoll(或者从上次的返回结果缓存中取数据,减少内核陷入次数),从中读取一个就绪的fd。如果没有,上下文应当被阻塞到至少有一个fd就绪。
  3. 查找这个fd对应的协程上下文对象,并调度过去。
  4. 当某个协程被调度到时,他多半应当在调度器返回的路上——也就是read/write读不到数据的时候。因此应当再重试读取,失败的话返回1。
  5. 如果读取到数据了,直接返回。

这样,异步的数据读写动作,在我们的想像中就可以变为同步的。而我们知道同步模型会极大降低我们的编程负担。

CPS模型

其实这个模型有个更流行的名字——回调模型。之所以扯上CPS这么高大上的玩意,主要是里面涉及不少有趣的话题。

首先是回调模型的大致过程。在IO调用的时候,同时传入一个函数,作为返回函数。当IO结束时,调用传入的函数来处理下面的流程。这个模型听起来挺简单的。

然后是CPS。用一句话来描述这个模型——他把一切操作都当作了IO,无论干什么,结果要通过回调函数来返回。从这个角度来说,IO回调模型只能被视作CPS的一个特例。

例如,我们需要计算1+2*3,在cps里面就需要这么写:

mul(lambda x: add(pprint.pprint, x, 1), 2, 3)

其中mul和add在python里面如下定义:

add = lambda f, *nums: f(sum(nums))
mul = lambda f, *nums: f(reduce(lambda x,y: x*y, nums))

而且由于python没有TCO,所以这样的写法会产生非常多的frame。

但是要正确理解这个模型,你需要仔细思考一下以下几个问题:

  • 函数的调用过程为什么必须是一个栈?
  • IO过程在什么时间发生?调用发生时,还是回调时?
  • 回调函数从哪里调用?如果当时利用工具去看上下文的话,调用栈是什么样子的?

函数组件和返回值

不知道你是否思考过为什么函数调用层级(上下文栈)会被表述为一个栈——是否有什么必要性,必须将函数调用的过程定义为一个栈呢?

原因就是返回值和同步顺序。对于大部分函数,我们需要得到函数计算的返回值。而要得到返回值,调用者就必须阻塞直到被调用者返回为止。因此调用者的执行状态就必须被保存,等到被调用者返回后继续——从这点来说,调用其实是最朴素的上下文切换手段。而对于少部分无需返回的函数,我们又往往需要他的顺序外部效应——例如干掉了某个进程,开了一个灯,或者仅仅是在环境变量里面添加了一项内容。而顺序外部效应同样需要等待被调用者返回以表明这个外部效应已经发生。

那么,如果我们不需要返回值也不需要顺序的外部效应呢?例如启动一个背景程序将数据发送到对端,无需保证发送成功的情况下。或者是开始一个数据抓取行为,无需保证抓取的成功。

通常这种需求我们就凑合着用一个同步调用混过去了——反正问题也不严重。但是对于阻塞相当严重的情况而言,很多人还是会考虑到将这个行为做成异步过程。目前最流行的异步调用分解工具就是mq——不仅异步,而且分布。当然,还有一个更简单的非分布方案——开一个coroutine。

而CPS则是另一个方向——函数的返回值可以不返回调用者,而是返回给第三者。

IO过程在什么时间发生

其实这个问题的核心在于——整个回调模型是基于多路复用的还是基于异步IO的?

原则上两者都可以。你可以监听fd就绪,也可以监听IO完成。当然,即使监听IO完成,也不代表使用了内核态异步接口。很可能只是用epoll封装的而已。

回调函数的上下文环境

这个问题则需要和上面提到的“用户态调度框架”结合起来说。IO回调注册的实质是将回调函数绑定到某个fd上——就如同将coroutine绑定上去那样。只是coroutine允许你顺序的执行,而callback则会切碎函数。当然,大部分实现中,使用callback也有好处——coroutine的最小切换开销也在50ns,而call本身则只有2ns。

状态机模型

状态机模型是一个更难于理解和编程的模型,其本质是每次重入。

想像你是一个周期失忆的病人(就像“一周的朋友”那样)。那么你如何才能完成一项需要跨越周期的工作呢?例如刺绣,种植作物,或者——交一个男朋友。

当然,类比到失忆病人的例子上必须有一点限制。正常的生活技能,还有一些常识性的东西必须不能在周期失忆范围内。例如重新学习认字什么的可没人受的了。

答案就是——做笔记。每次重复失忆后,你需要阅读自己的笔记,观察上次做到哪个步骤,下一个步骤是什么。这需要将一个工作分解为很多步骤,在每个步骤内“重入”直到步骤完成,转移到下一个状态。

同理,在状态机模型解法里,每次执行都需要推演合适的状态,直到工作完成。这个模型已经很少用到了,因为相比回调函数来说,状态机模型更难理解和使用,性能差异也不大。

最后顺带一提,交一个男友的方案和其他几个略有不同,主要靠颜好高冷反差萌,一般人就不要尝试挑战了。。。当然一般人也不会一周失忆一次,毕竟生活不是韩剧也不是日本动漫。。。