Posts on 子恒的博客

[架构]单体和微服务

Mon, 15 Apr 2024 19:31:56 +0800

多大的服务

“宜小不宜微”，不宜过大的单体，也不宜滥用微服务，应保持在合适的大小。
（ps. 这里只讨论服务的大小。不讨论服务的手段，拆分解耦、服务发现、mesh、告警、限流、全链路建设，都是好的实践，任何服务都可以做的同样好）
什么样的服务大小属于合理的服务？核心有两点，合理划分服务边界，匹配组织结构。

团队视角：服务的规模应该尽量限制在最小团队，约3人左右的团队为宜
- ❎ 过大！跨团队修改同一服务，风险大且不利于基础建设。没有人对整体的架构和质量负责。没有人有全局视角，写代码因为不了解改动范围容易出故障。
- ❎ 过大！10人以上的团队不宜修改同一服务。很可能服务定位不清晰，10个人的信息交流会有很多gap，效率会大大降低
- ❎ 过小！团队每个人管三四个服务，说明服务数量过多，无用工作会增加，效率也会降低
业务视角：保证产品需求变更如果只在本团队内，修改的服务1-2个即可
- ❎ 过小！改一个小小的功能，牵扯4-5个服务。服务太小了，效率降低
- ❎ 过大！同时有四五个业务需求，对应数十个研发同时修改一个服务，而这些功能看起来并不密切。这说明服务包揽的功能太多了，已经膨胀的太大了

更微=更好?

我们以一个模块划分合理、大小合适的单体服务为例，看看如果拆分的更微小，对比起来会有哪些点值得关注：

关注点	合理的单体	更微服务
性能	无劣化	约数ms的劣化
复用性	可以仓库内直接引用	不可复用其他仓库代码；所以也不会复用到bug
可读性	容易找代码	需要跨的仓库多，层次深，理解困难
研发成本	编译可能较慢	写代码、编译、调试、发布、部署都需要多仓库并行，成本高
部署成本	单机器	高，需要多台机器
代码合入	公共部分容易冲突	不容易冲突

微服务教

我们看下某网站对单体的批评，一一回应下：

开发效率低：所有的开发在一个项目改代码，递交代码相互等待，代码冲突不断
- 确实，代码冲突会变多。但在单体内部模块划分合理的情况下，冲突的只会是公共模块；如果这些代码冲突了，使用微服务也会冲突。
代码维护难：代码功能耦合在一起，新人不知道何从下手
- 耦合是模块设计的问题，不是单体的问题。而且单体断层更少，更容易阅读
部署不灵活：构建时间长，任何小修改必须重新构建整个项目，这个过程往往很长
- 没发现编译时间有显著区别。部分单体仓库会编译多个产物，建议针对性编译，效果更好。
稳定性不高：一个微不足道的小问题，可以导致整个应用挂掉
- 绝对意义上，微服务存在同样的问题，而且更难定位。相对意义上，如果说单体的复用代码带来了问题风险的扩大，这属于因噎废食，不可取。
  微服务给我们带来了什么样的反思？拒绝盲目创新，提防吹牛皮但不切实际，小心滥用导致过犹不及。

再次回到起点：monorepo

有趣的是，越来越多人意识到了微服务的问题，最终又回归了单一的仓库，并发明了一新的词：monorepo。

Segment.com 提供活动收集和转发服务，每个客户都需要使用一种特殊格式的数据。因此，工程团队最初决定混合使用微服务和多代码库。这一策略效果很好——随着客户基数的增长，他们扩大了规模，没有出现问题。但是，当转发目的地的数量超过 100 个时，事情开始变得糟糕起来。维护、测试和部署超过 140 个代码库（每个代码库都有数百个日益分化的依赖关系）的管理负担太高了。最终，团队发现他们无法取得进展，三个全职工程师花费了大部分时间来维持系统的运行。
对于 Segment 来说，补救办法就是合并，将所有的服务和依赖迁移到一个单一代码库中。他们必须协调共享库并且测试所有内容，虽然花了很大的代价，但迁移非常成功，最终的结果是降低了复杂性，增加了可维护性。

每个团队的精力是有限的，当每个人管理的仓库>10个，团队管理的仓库>100个，会出现非常多的问题：

团队无法集中注意力管理。有很多的仓库大部分人并不知晓。这部分代码不再能被复用，也不再被了解
开发要打开很多IDE并发进行，容易出错。测试需要部署非常多的服务，也不能跨服务debug。发布时需要发布过多的仓库，发布容易遗漏；发布有很复杂的依赖，发布也会花费更久的时间。
无法发起整体性重构。重构一个服务和同时重构10个服务的难度不是一个级别。

[后台]设计合理的幂等方案

Tue, 09 Apr 2024 16:07:23 +0000

幂等的作用

幂等的作用：保证可重入性，防止重复操作导致脏数据出现。使用场景可能有

前端防抖
接口超时重试
消息重试
只能调一次接口，如一个用户只能领一次券

我们的upsert、redis分布式锁、version乐观锁、for update、唯一索引、状态机其实都有幂等的功能，会在请求重复的时候报错

分布式锁：一般用来防止并发操作，可以处理重复操作的问题。可以加在请求处理的最开始
乐观锁：锁住读实体~写实体期间，这期间的任何其他操作都会失败。但自己也可能失败，要处理好失败的回滚逻辑

方案	支持维度	性能	幂等期	判断幂等时机	使用场景	备注
分布式锁	任意	高	加锁期间	请求开始	操作实体
乐观锁	实体id	低	读-写db期间	写db时	修改实体db行	失败需要回滚前面的操作
insert+uk	任意	低	写db之后	写db时	创建实体	失败需要回滚前面的操作

幂等键设计

结论：一定要用有业务语义的幂等键！最好的幂等键组合是entity_id+idem_key的组合

接口维度的幂等：幂等的控制交给上游，由上游保证自己的请求是可以幂等/不被幂等的。比如上游直接传一个md5sum(req)作为幂等键进来（其他常用的包括req里的核心参数、reqid、时间戳、消息id）。我们检测这个幂等键是否存在：

幂等键已存在：直接幂等。问题：下游可能传错了，不幂等的也结果被幂等，比如批量请求、同一个请求里发起多次请求等。幂等应该自己来控制
幂等键不存在：不幂等，这个不会出错

为了避免上面问题的出现，我们可以结合数据库的实体uk做判断。
数据维度的幂等：采用数据库的带业务语义的uniq key+幂等键联合判断。假设uk就是实体的id，幂等键是业务传过来的自定义值。我们去查找幂等键

uk已存在，幂等键不存在：说明用户希望再次操作同一个数据实体，不幂等
uk不存在，幂等键存在：说明用户希望再次操作其他数据实体，不幂等
uk、幂等键都存在：直接幂等
uk、幂等建都不存在：不幂等

// 这个例子实现了一个幂等键
// 业务场景：假设我们要设计一个领奖接口，每个用户只能领一次奖品。
// seq: 如果此奖励一个user_id可以重复领取多次，需要用seq标识唯一
// 用户id、奖励id、和seq表达一次幂等
func getIdemKey(userId string, prizeId string, seq string) (uniqueId string){
   return fmt.Sprintf("%v_%v_%v", userId, prizeId, seq)
}

实现

实现方法：

令牌发放：服务端/客户端生成一个token（幂等键），给客户端用，客户端带着token前来请求，token是一次性的，用过就直接幂等
幂等表：mysql的数据表里加一列幂等键，这个表一般是操作流水表，用来记操作。每次来请求的时候从流水表查幂等键存不存在，存在则直接幂等
实体表uk：实体表加一列create_idem_key作为uk，幂等的时候直接报错uk冲突。缺点是只能做实体创建的幂等，不能做实体操作的幂等
分布式锁：redis里存幂等key，用setnx+幂等key+超时时间控制

我们举例一个轻量级的幂等应用：

[游记]摄影和眼睛

Sun, 03 Sep 2023 01:37:29 +0800

故事要从虎跳峡的一段徒步说起。走过人满为患的虎跳峡主景区之后，我们迅速远离了商业化的景区服务（不到三层楼的台阶居然修了收费的电梯，破坏了自然的景色不论，居然是封闭的，看不到半点峡谷和河流，甚是乏味）和拍游客照的熙熙攘攘的人群之后，心里略有不甘。眼见太阳已经走过了头顶，徒步的心又痒了起来，于是和朋友们驱车继续深入，前往中虎跳。
行车没有多久，一段曲折的山路就出现在了我们面前。路一看就没有完全修好，一眼就能看到夸张的U形弯，不仅狭窄到仅能一车通过，还有很多细碎的石子。我们下车观望，齐齐看向了队伍中驾驶经验丰富的唐，但路线的艰难和我们超长的9座商务车也只让唐无奈地点起了烟。于是我们讨论了几分钟，便留下了一部分体力不足的朋友原地等待，剩下人徒步上山（后来证明了这是极其明智的选择，路上搭到的便车阿姨已经在这条山路上开了19年，高超的驾驶技术和艰难的路况实在令我们汗颜）。
阿姨把我们送到了徒步的起点，茶马客栈。客栈后是三三两两的韩国人和美国人，看来远道而来的不止我们几个朋友。客栈后的玉龙雪山已经被夕阳渲染成了金色，颇为壮观。我们意识到自己来对地方了，便绕过客栈，顺着路标牌走了起来。

徒步路程并不劳累，但却颇具特色。路上有当地的农户，种植了一些蔬菜，我们不禁讨论起这里拉货和盖房子的困难，他们是如何把生活物资运上山。路上还有很多各种语言的路标牌，指向法国人和美国人开的客栈，我们朝着路标望去，却发现是一条蜿蜒的山路，还要攀爬数百米，只能望洋兴叹。再有很多面对圣山的堆叠起来的石片，我们后来才了解到这是一种古老的祈福仪式，在西南地区十分常见。我们一路走走拍拍，每绕过一座山就能看到远处的雪顶金山又近了一点，在愉悦的心情中行程迅速过半。

即使一路已经看过了各种美景，按理来说应该对大多数景色免疫，但是再次穿过一个山头后，我们还是对眼前的景象大为震惊。被劈的几乎垂直的峭壁中间，是一条极其深邃的山涧，里面传出清脆流水的声音，而我们的小路恰到好处地在山涧上方穿过。走过小桥的时候，虽然双腿发软，但是下面的深谷仿佛有一种魔力，让我的眼睛贪婪地搜刮着峡谷中的诸多细节。再补一眼陡峭的山壁，再看看山壁对面的金山当做佐料，一种壮阔的感觉油然而生。

朋友小W忍不住拿起手机，试图把这种壮阔记录下来，但是尝试过各种角度之后，不免垂头丧气，发现拍到的照片似乎表达不出眼前景色的百分之一。是啊，眼前的景色是流动的，我们心中的印象是由一段时间的感受组合而成，相机只能框选其中一部分，自然无法还原。朋友说要是眼睛里有个无限分辨率的摄像机该多好，就可以完整记录我们看到的景色，可惜现在的科技还无法达到。我思考了下，总觉得即使完全如他所说，却还差了一些什么，但又说不上来。

直到云南的行程过去大半年，一次偶然听到一位写生的画家讲起写生和摄影的区别，我才幡然醒悟。这位老师说，“绘画写生可不是去找哪个合适的角度，而是寻找我们感受最深的一个瞬间”，我终于意识到，除了一双无限分辨率和能看到各种角度的大脑记忆，无论如何都无法描述当时的美；因为美不仅仅包含了峭壁、小溪和雪山的各种角度，还包含了流水的声音，徒步过程的愉悦，曲折的上山过程，和朋友在一起欣赏的心情，甚至从嘈杂游客中回归自然的焕然一新，都是我们感受到美的原因，但这似乎是每个人都迥异的感受，是一张照片远远无法表达的信息。这就是摄影和眼睛的区别。
但如果认为静态的图片无法给人带来相同美的感受，也未免过于武断。艺术史已经告诉我们前人做了诸多尝试，比如捕捉瞬间极美感受的印象派，从各种视角去描绘事物本身特点的立体主义，以及描绘内心感情的抽象主义，甚至他们摒弃的写实流派，都是用不同方法试图还原美的成功案例。当产生强烈的美感时，记住美，了解美，思考美，无论是眼前的画面、景物的角度或组合、声音气味还是心情，都可以体现在照片中，让我们的摄影作品也会成为别人的眼睛。

[架构]常见的架构设计思想

Sun, 23 Apr 2023 14:45:11 +0800

这片文章想讲一下软件架构的基础，一些基本的原则和思想。我理解的架构是指导我们设计和实现软件的方法论；这意味着我们对复杂度、可扩展性、稳定性（分别对应迭代上手成本、迭代效率、事故损失）这三个方面有非常高的要求，尤其是复杂度，对修改代码的影响范围、成本、难易程度都有显著的影响，是架构要解决的核心问题。
另外，我们也不额外考虑性能，因为业务中的性能瓶颈距离我们讨论的问题往往还有几个数量级，往往是异步、流程优化、io等待等方面更加能有作为，采取什么样的设计方法能起到的作用微乎其微。

设计原则

关于原则，我想说一句话，原则是开发迭代中总结出来的经验，而不是开发迭代的规范。判断是不是原则适用的场景（而不是无脑用原则）往往更加有效，也更加困难。类似“没有银弹”。

KISS: Keep it simple, stupid，不要引入不必要的复杂
DRY: Don‘t repeat youself，不要重复代码
迪米特法则: The Least Knowledge Principle，使用者不知道实现细节
SOLID原则:

S 单一职责原则：对象应该仅具有一种单一功能
O 开闭原则：软件的目标应该是可扩展，不可修改
L 里氏替换原则：子类在任何代码中替换父类，行为一致
I 接口隔离原则：多个特定接口要好于一个宽泛用途的接口
D 依赖反转原则：抽象不应该依赖于具体，具体应当依赖于抽象（DDD就是这样，实际需求 ->抽象领域 -> 实现细节）

上面这些法则，几乎都在说：
代码简单可复用，架构高内聚低耦合

过程而非对象

面向对象（OOP）还是面向过程（函数式FP）？
这里的面向过程是对过程做结构化抽象，并不是平摊代码，这种明显的靶子行为不在我们讨论范围内。

我们先看看面向对象的核心特征（Java为例）：封装、继承、多态

封装：和自己数据有关的操作封装成成员方法，并控制可见性
继承：得到父类的属性和方法
多态：不同类型调用同一个成员方法会产生不同的结果

我们看看非面向对象的做法（Go为例）：

封装：和自己数据有关的操作封装成接收器，并控制可见性（非常类似）；和自己数据无关的操作，直接做成普通函数
继承：得到别人的属性和方法都用组合的方式，避免构造函数、重载、层次设计
多态：类型之间没有继承关系，不同类型实现同一个接口的方法。调用的时候按自己的类型去做出对应行为

封装：函数和数据的耦合

编程的宗派，王垠

对象作为数据访问的方式，是有一定好处的。然而“面向对象”（多了“面向”两个字），就是把这种本来良好的思想东拉西扯，牵强附会，发挥过了头。很多面向对象语言号称“所有东西都是对象”（Everything is an Object），把所有函数都放进所谓对象里面，叫做“方法”（method），把普通的函数叫做“静态方法”（static method）。实际上呢，只有极少需要抽象的时候（为访问对象数据提供间接的封装），你需要使用内嵌于对象之内，跟数据紧密结合的“方法”。其他的时候，你其实只是想表达数据之间的变换操作，这些完全可以用普通的函数表达，而且这样做更加简单和直接。
这种把所有函数放进方法的做法是本末倒置的，因为函数并不属于对象。绝大部分函数是独立于对象的，它们不能被叫做“方法”。强制把所有函数放进它们本来不属于的对象里面，把它们全都作为“方法”，导致了面向对象代码逻辑过度复杂。很简单的想法，非得绕好多道弯子才能表达清楚。很多时候这就像把自己的头塞进屁股里面。

过度封装会导致几个结局：

类的职责逐渐变得模糊，越来越大，远远超出了设计时的职责
对象的成员变量太多，且有没有赋值、赋值产生的依赖很难管理
对象的成员函数太多，类有哪些功能、哪些函数很难辨别

我们实践的时候，会有entity作为数据的封装，和一系列操作entity自身的成员方法。但如果涉及别的对象呢？我们有converter，helper等方法包作为补充

继承vs组合

不要仅仅为了代码复用而继承。当你使用组合来实现代码复用的时候，是不会产生继承关系的。过度使用继承的时候，如果修改了父类，会损坏所有的子类。这是因为子类和父类存在紧耦合。
不要仅仅为了多态而继承。如果你的类之间没有继承关系，并且你想要实现多态，那么你可以通过接口+组合的方式来实现，这样不仅可以实现代码重用，同时也可以实现运行时的灵活性。

Rust程序设计语言

子类不应总是共享其父类的所有特征，但是继承却始终如此。如此会使程序设计更为不灵活，并引入无意义的子类方法调用，或由于方法实际并不适用于子类而造成错误的可能性。

考虑到实际的工程往往都是多层次的组合和复用，继承能带来的收益非常小，但是后期的维护成本却是很难评估的。所以我建议在任何时候都不要使用继承。

我们讨论完面向对象的核心特质：封装、继承、多态，发现这些行为的滥用都需要格外地小心。这也是为什么工业界越来越多的go和rust，仅仅从这一章节讨论的结果来说，这些更年轻的语言汲取了面向对象（数据封装、成员方法）和函数式（接口、一等公民）的优点，取消了他们诸多迷惑的特性，这是在任何语言都可以借鉴的行为。

“干净”的代码，贼差的性能

[管理]对新人友好的项目管理手册

Mon, 15 Aug 2022 15:37:19 +0800

刚毕业的高材生小姜，有着浑厚的知识储备和满怀热情的心脏来到了某厂，在做了一段时间需求后，发现自己对做事靠谱的老司机倍加羡慕；为什么人家有条不紊，好评如潮？自己确手忙脚乱，频频提测delay，加班到深夜？

今天我们来帮帮小姜，看看小姜为什么技术扎实，态度积极确总是使不上劲？
（故事仅供参考，切勿对号入座）

需求详评

这周产品新提了一个需求，拉了小姜和老梁一起做，在详评会议上：

小姜：听的云里雾里，昏昏欲睡，听产品讲完后准备下来仔细看看代码哪里要改

老梁：对产品频频犀利发问：这个细节A为什么这样做，我感觉体验并不好？我们这个需求预期什么时候上线？是不是倒排？我看到这个项目需要我们合作方A做开发，定容了吗？

小姜恍然大悟的笔记（详评阶段应该做的）：

敲定需求细节，可以给出自己视角的建议
- 对产品考虑不周全的需求，结合现状进行扩充
- 对于欠缺价值的需求点，合理挑战
- 对于破坏系统设计过大的需求点，提早商量
敲定需求整体节奏和预期上线时间，为做方案做准备
对于涉及到前置依赖的需求，一定要尽早确认好工作节奏
- UE稿什么时候出
- 下游是否已经定容、什么时候完成开发，下游依赖接口什么时候给

技术评审

小姜：往文档里贴了下代码截图片段，告诉大家我要改这里，其他人听的一脸懵

老梁：给了一个完整的方案，涉及到合作方的关注点的内容写的非常详细，获得一致好评

小姜复制了一份老梁的模板：

排期概览（开发、联调、测试、上线的准确时间）
业务背景（问题、目标、收益）
技术方案
- 设计模块和改动点列举
- 架构图、流程图、状态机、时序图、ER图
- 异常情况和处理
- AB实验方案
- 老数据兼容
- 依赖下游方案
- 风险点（需求自身风险、产品影响风险、可维护性/效率风险）
存储设计
- DB/TCC/MQ/Redis/ES的schema变更
- 数据量级、key、分片、索引、选型、异常处理
接口文档
- http接口定义和使用文档
- rpc接口定义和使用文档
服务治理
- 异常兜底
- 监控报警
工作量评估
- 工作拆分和估分
- 进度计划
自测用例
- 冒烟测试用例（描述、步骤、期望结果）
- 希望测试测到的地方
发布计划
- MR
- 发布顺序

开发

评审之后大家迅速都加入了如火如荼的开发当中：

小姜：早早地做完了自己的工作，等着联调。联调前一天突然发现下游依赖的接口还没数据，一问原来是有个工作没有对齐漏掉了，心急如焚

老梁：按照之前拆分的开发计划，列出了一个详细的进度追踪表，可以看到工作分配到的人、完成时间、里程碑，还有风险；提前把问题消灭了，大家笑盈盈进入联调

功能点	开发状态	人力预估	开发者	自测完成	风险记录
功能A	未开始	5	小A	是	暂无
功能A适配	进行中	2	小B	否	下游接口延迟一天
功能B适配	已完成	2	小B	否
功能B	已完成	0.25	小B	否
功能C	已完成	1.5	小C	否
功能C2	已完成	1	小A	否
功能A2	已完成	1	小A	否
距离联调还剩 2 个工作日
当前时间进度 50.0%
当前完成进度 45.1%

小姜恍然大悟的笔记（开发阶段应该做的）：

[杂谈]我怎么选择笔记软件

Wed, 10 Aug 2022 16:57:25 +0800

折腾了这么久笔记软件，终于有了一个最终的方案，给大家分享下

用过的软件对比

软件	优点	缺点	用途
印象笔记	云/多端	丑，难用，残疾md	手机查看
OneNote	多目录/手写	同步难，没有md	读书、网课笔记
Typora	好看/导出	没有云、收费	离线编辑
马克飞象	比较好看	没有云、收费	离线编辑
Obsdian	比较好看	没有云、不能导出	离线编辑
CmdMarkdown	有云	难看	备份，网页版查看
StackEdit	简单	太卡了	没用
MarginNote	知识图谱	无win	读pdf书
备忘录	多端同步、轻量	格式难用	速记
Notion	多端同步、复杂	md不好用，手写不支持	替代onenote

诉求

支持markdown，且美观
支持Latex，脚注
支持云存储，移动端同步
支持mac/windows/ios/网页版
支持3级目录，支持搜索
支持手写插入
支持网页剪裁
支持离线编辑
可以导出pdf，html
支持代码块，代码块染色，行号
支持大纲

工作流

没有一个通用的工作流，所以我需要根据不同的场景来决定采用哪些软件。

速记

（todo list，check list）
备忘录

写博客

Obsdian -> github -> hugo

[互联网]广告业务的前世今生

Tue, 04 Jan 2022 17:23:09 +0800

笔者曾在腾讯商业化、字节广告变现承担过多年广告后台相关工作，对业界的广告套路和广告架构比较熟悉。本文旨在以尽量容易理解的方式来分享广告相关的知识，来给对广告业务了解较少的同学形成一个基本的认知：

广告是如何赚钱的？
广告系统的组成是什么样的？
广告系统有哪些值得学习的策略？

商业模型

广告在平台内部的“永动机”

用户产品：把平台拉新进来的用户留存，转化成活跃用户
商业化：在活跃用户的浏览行为中插入广告，获得收入
UG：把部分商业化的收入用来拉新、激励，使得有源源不断的新用户进来

广告做的是下面三个人群的生意

用户：需要使用平台的服务，如新闻、推文、博客、视频
广告主：需要构建自己的品牌价值、推销自己的产品等
平台：需要用自己产品的DAU变现

广告业务

广告形态

常见的广告形态
硬广

开屏广告
原生开屏广告
信息流广告
搜索广告

软广

图文视频软广

非标

锚点
彩蛋
hashtag
DOU+

交易链路

如果广告主想要在多个媒体（网站、广告网络、交易平台）投放广告，是一个非常繁琐的过程。因为每一个网站、广告网络、交易平台的媒体购买系统、操作规则不同，需要人工进行调整，费时低效；而且跨渠道媒体购买很可能重复购买同一部分人群。

DSP平台把广告主、代理人员从庞杂的重复手工操作中解放出来。广告主只要在DSP平台投放广告即可，由DSP平台帮助广告在多个媒体投放广告。

同理，如果流量主想在自己的网站流量位置上插入广告，如果自己去招商，也是个非常消耗人力的事情，寻找广告主、和广告主对接、广告主提供的素材匹配自己的广告位都需要很多时间。SSP平台可以快速满足流量主接入广告的需求，帮助流量主快速变现。

名词解释

DSP (Demand-Side Platform)： 需求方平台，可以简单理解为需要采买流量的平台（广告主自建或者第三方技术公司）
SSP (Supply-Side Platform)：供应方平台/媒体平台，管理流量和坑位。可以简单理解为流量（抖火西头）
DMP (Data Management Platform）：数据管理平台，管理人群，生成定向人群包
ADX (AD Exchange)：程序化广告****交易平台，通过技术对接的方式，支持客户（DSP）进行媒体的流量（用户）采买
ADN (Ad Network )： 广告网络，聚合了大量App内的展示广告资源，主要包含中长尾App流量，帮助广告主实现媒体精准、灵活的投放。汇集了很多媒体的余量

各种公司的布局：

行业角色

变现公式

**广告收入 = 活跃用户数 * 人均展示数 * 广告负载 *** 广告点击率 * 广告价格

[后台]服务端高性能架构之道（系统和服务篇）

Tue, 28 Sep 2021 21:13:08 +0800

如果你在服务端的工区，常常会听到同学们激烈的讨论，包括能不能扛得住xx流量？能不能P99达到x毫秒？某操作能不能立即生效？某服务CPU飙升了，某服务OOM了，某服务超时率暴涨了？
这些灵魂的质问，其实就是在保障服务端的高并发、高性能、高可用、高一致性等等，是我们服务端同学必备的扎实基本功。

克服系统瓶颈

服务端的代码都跑在各种版本的Linux之上，所以高性能的第一步要和操作系统打交道。我们的服务需要通过操作系统进行I/O、CPU、内存等等设备的使用，同时在使用各种系统调用时避免各种资源的开销过大。

零拷贝

认识零拷贝之前，我们先要对Linux系统I/O机制有一定的了解。当我们执行一个write(2)或者read(2)的时候（或者recv和send），什么时候操作系统会执行读写操作？什么时候又最终会落到磁盘上？
以一个简单的echo服务器为例，我们模拟下每天都在发生的请求和回包：

sockfd = socket(...); 					//打开socket
buffer = new buffer(...); 				//创建buffer 
while((clientfd = accept(socketfd...)){	// 接收一个请求
	read(clientfd, buffer, ...);        //从文件内容读到buffer中 
	write(clientfd, buffer, ...);       //将buffer中的内容发送到网络
}

看一下这段代码的拷贝流程（下图）：

数据包到达网卡，网卡进行DMA操作，把网卡寄存器的数据拷贝到内核缓冲区
CPU把内核缓冲区的数据拷贝到用户空间的缓冲区
用户空间处理buffer中的数据（此处不处理）
CPU把用户空间的缓冲区的数据拷贝到内核缓冲区
网卡进行DMA操作，把内核缓冲区的数据拷贝到网卡寄存器，发送出去

整个过程触发了4次拷贝（2次CPU，2次DMA），2次系统调用（对应4次上下文切换）
（注：DMA(Direct Memory Access)， I/O 设备直接访问内存的一个通道，可以完成数据拷贝，使得CPU 不再参与任何拷贝相关的事情，现在几乎所有的设备都有DMA）

使用mmap

mmap可以把用户空间的内存地址映射到内核空间，这样对用户空间的数据操作可以反映到内核空间，省去了用户空间的一次拷贝：

应用调用mmap，和内核共享缓冲区（只需一次）
数据包到达网卡，网卡进行DMA操作，把网卡寄存器的数据拷贝到内核缓冲区
CPU把接收到的内核缓冲区的数据拷贝到发送的内核缓冲区
网卡进行DMA操作，把内核缓冲区的数据拷贝到网卡寄存器，发送出去

整个过程触发了3次拷贝（1次CPU，2次DMA），2次系统调用（对应4次上下文切换）

使用sendfile/splice

Linux 内核版本 2.1 中实现了一个函数sendfile(2)：

他把read(2)和write(2)合二为一，成为一次系统调用，实现了把一个文件读取并写到另一个文件的语义
系统调用中不再切换回用户态，而是在内核空间中直接把数据拷贝过去（2.4 之后这一步支持了DMA拷贝，实现了CPU零拷贝）

我门看下使用sendfile之后的流程：

整个过程触发了3次拷贝（0次CPU，3次DMA），1次系统调用（对应2次上下文切换）

Linux 内核版本 2.6 中实现了一个函数splice(2)，类似sendfile，但是接收/发送方必须有一个文件是管道，通过管道的方式连接发送方和接收方的内核缓冲区，不再需要拷贝（0次CPU，2次DMA，1次系统调用）

transferTo（内部调用sendfile）的性能对比：

对于我们的启发

零拷贝能带来显著的性能提升，目前kafka，nginx默认都开启了零拷贝（大文件传输可以提升60%以上）
部分场景对时效性或者拷贝次数有严格的要求时（比如数据库、消息队列的实现），可以考虑用mmap或者直接I/O，配合自己实现的缓存替代操作系统的缓存方案
拷贝很可能是CPU消耗的主要原因，比如业务代码中的大结构体复制，所以我们要谨慎控制复制操作，尽量使用指针或者引用类型

无锁

多线程、多协程、多机器、多地部署是我们服务端实现高并发和强容灾的必备解决方案，这些方案都有一个共性，把数据或者过程分而治之。问题在于，几乎所有的并发场景都会涉及到数据竞争，涉及到共享数据的地方就会涉及到锁，协程有锁，线程有锁，多机部署的服务有分布式锁。
服务中的锁会带来很多问题，随着并发数量的加大，会带来更大的上下文切换、用户态切换的开销，出现CPU飙升且都在做一些无用功的现象，也会导致性能快速下降，甚至还不如单线程模型的效率高。除此以外，各种锁还会带来很高的复杂度，和并发的复杂度相叠加，非常容易出现死锁和各种并发问题。

因此，我们使用锁一定是去解决某种问题而去用的，能无锁就无锁，能轻量级就轻量级。

无锁的替代方案

单线程

最简单的方案就是单线程reactor模式，redis、nginx都用了这种方式来避免加锁带来的损耗和复杂性，适用于功能简单的场景。

如图，redis的单线程模型有这么几个部分：

[Go]Go语言的设计和坑

Tue, 02 Feb 2021 20:31:09 +0800

本文介绍了Go的语言设计和一些容易踩坑的细节：

理解Go为什么X，摆脱原语言的思维
解决写代码时比较困惑和不满的点，对容易出错的语法有个印象

Go学起来非常简单，但是这是语言设计者刻意为之，很多复杂的细节都藏在语言实现里，导致我们迅速学会Go之后不断踩坑

Why Go

2007年，Google设计Go，目的在于提高在并行编程（多核CPU越来越多）、分布式部署、大型代码库（以及维护他们的非常多的开发人员）的情况下的开发效率。设计时，在吸收C++优点的基础上，收集于很多工程师之间流传的的“不要像C++”
Go like C++：

内存消耗少
执行速度快
启动快

Go not like C++：

程序编译时间短（按照我过去的经验，一个C++大型项目即使make -j8也需要编译一个小时以上）
像动态语言一样灵活（runtime、interface、闭包、反射）
内置并发支持（C++的协程至少得等到std23才有，非常落后）
丰富的原生库（C++解析json，建立http服务器，使用redis这种都很难找到靠谱的库）
多语义（取消了指针运算、取消隐式类型转换、取消类型别名，取消重载，++和赋值作为表达式…）

Go的优点：

面向工程：简单。只有25个关键字，代码风格统一，可读性高，go mod包丰富
自动垃圾回收：语言运行时内置垃圾回收
语言级并发：非常好用的routine和channel，更高层次的并发抽象
静态语言动态特性

Go的缺点：

runtime的性能还需要提高
没有泛型
冗余的错误处理
Go mod不够完善

Go语⾔将⾛向何⽅?
我为什么放弃Go语言

Go的设计哲学

创始人Rob Pike在SPLASH上的演讲，阐述了设计Go的初衷
 许式伟，Go和Java在继承观念上的对比
 对面向对象的批评
 王垠：解密“设计模式”，对设计模式的批评

少即是多（less is more）：如果一个特性并不对解决任何问题有显著价值，那么go就不提供它；如果需要一个特性，那么只有一种方法去实现
面向接口编程：非侵入式接口，反对继承、反对虚函数和虚函数重载（多态）、删除构造和析构函数
正交+组合的语言特性：语言的特性之间相互独立，不相互影响。比如类型和方法是互相独立的，类型之间也是相互独立的，没有子类，包也没有子包。不同特性用组合的方式来松耦合
并发在语言层面支持：并发更好利用多核，有更强的表现力来模拟真实世界

在设计上，Go秉承了C的简单粗暴。

为什么没有继承？

Go没有子类型的概念，只能把类型嵌入到另一个类型中，所以没有类型系统。Go的作者认为类型系统被过度使用了，应该在这个方向上退一步。

使用伸缩性良好的组合，而不是继承
数据和方法不再绑定在一起，数据的集合用struct，方法的集合用interface，保持正交

类似子类父类的系统造成非常脆弱的代码。类型的层次必须在早期进行设计，通常会是程序设计的第一步，但是一旦写出程序后，早期的决策就很难进行改变了。所以，类型层次结构会促成早期的过度设计，因为程序员要尽力对软件可能需要的各种可能的用法进行预测，不断地为了避免挂一漏万，不断的增加类型和抽象的层次。这种做法有点颠倒了，系统各个部分之间交互的方式本应该随着系统的发展而做出相应的改变，而不应该在一开始就固定下来。

作者附了一个例子，是一些以接口为参数并且其返回结果也是一个接口的函数：

// 入参是接口的函数，而不是成员方法
func ReadAll(r io.Reader) ([]byte, error)
// 封装器 - 出入参都是接口
func LoggingReader(r io.Reader) io.Reader    //读到的内容录入日志
func LimitingReader(r io.Reader, n int64) io.Reader    //读n个字节停下来
func ErrorInjector(r io.Reader) io.Reader

这种组合+函数的模式是相当灵活的。如果用继承，我们可能会多三个io.Reader的定义；然后用多态去获得对应的功能

[Redis]Redis 应用篇

Thu, 24 Sep 2020 15:57:27 +0800

分布式锁

简单加锁

// 思想：利用setnx检测有没有set过，如果set过就表示没有抢到锁
> setnx locker true
OK
// ... do somthing ...
> del locker

处理set之后进程崩溃的死锁问题

// 思想：给锁加上过期时间，即使set之后进程挂掉，也不会死锁
> setnx locker true
OK
> expire locker 5
// ... do somthing ...
> del locker

处理非原子性问题

setnx之后，expire之前，进程挂了，也会死锁。怎么处理这种情况？

使用redis事务吗？事务里没有if else，要么全部执行，要么全部不执行。需求是setnx成功才执行expire，有依赖关系，没法用事务
使用新的原子命令，如下

> set locker true ex5 nx
OK
// ... do somthing ...
> del locker

处理超时问题

上面的方案设定了超时时间。但是如果少数操作的时间超过了超时时间怎么办？有两个问题：

[C++]C++ 11/14 笔记（四）

Tue, 18 Aug 2020 19:34:11 +0800

本部分介绍了c++11的并发编程。这些笔记是未完成的。

语法参考这里：
现代C++教程
实现参考这里：
C++11中的mutex, lock，condition variable实现分析

std::thread

C++ 11为我们带来了语言级的线程支持，包括线程的创建和等待：

//g++ -o t main.cpp -lpthread --std=c++11
#include <iostream>
#include <thread>
#include <chrono>

void foo(int sec)
{
    // sleep_for() 休眠sec秒后唤醒
    std::this_thread::sleep_for(std::chrono::seconds(sec));
}

int main()
{
    // join() 阻塞等待线程
    // joinable() 是否可以join（没设置任务函数不可以join）
    std::thread t;
    std::cout << "before starting, joinable: " << t.joinable() << '\n';
    t = std::thread(foo, 1);
    std::cout << "after starting, joinable: " << t.joinable() << '\n';
    t.join();

    // detach() 将当前线程对象所代表的执行实例与该线程对象分离，使得线程的执行可以单独进行。一旦线程执行完毕，它所分配的资源将会被释放。
    // 永远不要用detach()。失去控制的线程会有很多问题
    // get_id() 打印线程id
    std::thread t1(foo, 2);
    std::thread::id t1_id = t1.get_id();
    std::cout << "t1_id: " << t1_id << '\n';
    t1.detach();
}

std::mutex和std::lock_guard同步

有了线程就必然需要锁。我们看一个例子，用RAII 的方式管理线程和锁：

[后台]负载均衡（三）限流篇

Mon, 27 Jul 2020 17:28:37 +0800

限流

限流能力是高并发系统中，对于服务提供方的一种保护手段。通过限流功能，我们可以通过控制QPS的方式，以避免被瞬时的流量高峰冲垮，从而保障系统的高可用性。

考虑的问题

完成一个限流系统，我们可以结合场景的需要做下面的考虑

多规则匹配：是否会存在有多重规则的限流？比如有的规则限制每天1000次，有的规则限制每分钟1次？是同时生效还是优先生效某个？
资源类型：能限流什么？QPS，连接数，并发数
全局限流/单机限流：多个服务的实例共享一个全局的流量限额，比如所有机器共享1000QPS。或者单个实例的限流，比如被调限定每台机器不超过1000QPS
限流阈值：单位时间内的最大配额数。是按照每秒种一次，还是按照每分钟60次？
限流处理：客户端如何处理超出限额的请求？超额后直接拒绝，还是超额后进行排队？

抽象出一个方案
接口级别限流：每个接口分配一个appid和key，各自计算各自的配额
多维度限流：支持每秒N次、每分钟N次、每天N次等维度
匀速防刷：假设配置了每分钟60次，依然可能出现第一秒访问了60次用光了配额。匀速防刷可以匀速消耗配额，解决这个问题
多级限流：支持不同的限流规则，并有采用的优先级，采用优先级最高的方案进行限流

限流算法

固定窗口

固定窗口是在一段时间内可以限制访问次数的方法。

将时间划分为多个窗口
在每个窗口内每有一次请求就将计数器加一
如果计数器超过了限制数量,则本窗口内所有的请求都被丢弃。当时间到达下一个窗口时,计数器重置

这样有一定的限流效果，但是限制住的流量可能是有毛刺的。比如1000次/分钟，可能00:59的时候有1000流量，01:00的时候也有1000流量，这样这两秒内就有2000流量！
具体实现：用一个变量C标记访问次数，一个事件定时过期，并在过期时把变量C清零：

type FixedWindowCounter struct {
	TimeSlice  time.Duration
	NowCount   int32
	AllowCount int32
}

func (p *FixedWindowCounter) Take() bool {
	once.Do(func() {
		go func() {
			for {
				select {
				case <-time.After(p.TimeSlice):
					atomic.StoreInt32(&p.NowCount, 0)
				}
			}
		}()
	})

	nowCount := atomic.LoadInt32(&p.NowCount)
	if nowCount >= p.AllowCount {
		return false
	}
	if !atomic.CompareAndSwapInt32(&p.NowCount, nowCount, nowCount+1) {
		return false
	}
	return true
}

滑动窗口

滑动窗口把一个固定窗口划分为多个小区间，以固定的窗口大小在区间上滑动，在一定程度上缓解了固定窗口的毛刺问题（我们假设某一区间qps非常高）。当然性能损耗也比较大。

[后台]负载均衡（二）能力篇

Thu, 21 May 2020 17:18:55 +0800

名字服务

基础设计

名字服务考虑的基本设计

客户端发现：
服务提供者的实例在启动时或者位置信息发生变化时会向服务注册表注册自身，在停止时会向服务注册表注销自身，如果服务提供者的实例发生故障，在一段时间内不发送心跳之后，也会被服务注册表注销。
服务消费者的实例会向服务注册表查询服务提供者的位置信息，然后通过这些位置信息直接向服务提供者发起请求。

服务端发现：
第一步与客户端发现相同。
服务消费者不直接向服务注册表查询，也不直接向服务提供者发起请求，而是将对服务提供者的请求发往一个中央路由器或者负载均衡器，中央路由器或者负载均衡器查询服务注册表获取服务提供者的位置信息，并将请求转发给服务提供者。

这两种模式各有利弊，客户端发现模式的优势是，服务消费者向服务提供者发起请求时比服务端发现模式少了一次网络跳转，劣势是服务消费者需要内置特定的服务发现客户端和服务发现逻辑；
服务端发现模式的优势是服务消费者无需内置特定的服务发现客户端和服务发现逻辑，劣势是多了一次网络跳转，并且需要基础设施环境提供中央路由机制或者负载均衡机制。目前客户端发现模式应用的多一些，因为这种模式的对基础设施环境没有特殊的要求，和基础设施环境也没有过多的耦合性。
主调调用被调时，根据被调的名字从服务注册中心获取服务实例列表，包括节点ip、端口、权重、地理位置等；一般采取分钟级别的定时任务去拉取，本地做缓存，异步更新。

实现方式

DNS，传播速度太慢，没法发现端口。SkyDNS解决了这个问题，在k8s里大量使用
zookeeper或者etcd，如SmartStack，能保证强一致，但是要做很多开发
Eureka。Netflix的java生态里的优秀方案
Consul，提供服务配置、服务的内存和磁盘监测等

服务注册信息

IP和端口

一个服务端要接入名字服务，必须要先提供自己的IP和端口信息。
IP的获取方法：

通过遍历网卡的方式去获取，找到第一个不为本地环回地址的 IP 地址。dubbo就是这种方法
指定网卡名interfaceName，来获取IP
直接与服务注册中心建立 socket 连接，然后通过socket.getLocalAddress() 这种方式来获取本机的 IP
端口的获取方法：
一般的RPC服务或者Web服务监听的端口都在配置中写好，可以直接获取上报。

扩展设计

除了IP和端口，可能还有一些常用的服务信息需要注册上来，提供更高级的功能：
1.支持TLS：想知道某个 HTTP 服务是否开启了 TLS。
2.权重：对相同服务下的不同节点设置不同的权重，进行流量调度。
3.环境分配：将服务分成预发环境和生产环境，方便进行AB Test功能。
4.机房：不同机房的服务注册时加上机房的标签，以实现同机房优先的路由规则。

无损注册/下线

虽然服务注册一般发生在服务的启动阶段，但是细分的话，服务注册应该在服务已经完全启动成功，并准备对外提供服务之后才能进行注册。
1.有些 RPC 框架自身提供了方法来判断服务是否已经启动完成，如 Thrift ，我们可以通过 Server.isServing() 来判断。
2.有一些 RPC 框架本身没有提供服务是否启动完成的方式，这时我们可以通过检测端口是否已经处于监听状态来判断。
3.而对于 HTTP 服务，服务是否启动完毕也可以通过端口是否处于监听状态来判断。
下线也是一样的，可以注册服务下线的回调，或者监听服务下线的信号，或者做健康检查

健康检查

客户端主动心跳上报健康：

客户端每隔一定时间主动发送“心跳”的方式来向服务端表明自己的服务状态正常，心跳可以是 TCP 的形式，也可以是 HTTP 的形式。
也可以通过维持客户端和服务端的一个 socket 长连接自己实现一个客户端心跳的方式。
客户端的健康检查只能表明网络可达，不能代表服务可用。服务端的健康检查可以准确获得服务的健康状态：
服务端调用服务发布者某个 HTTP 接口来完成健康检查。
对于没有提供 HTTP 服务的 RPC 应用，服务端调用服务发布者的接口来完成健康检查。
可以通过执行某个脚本的形式来进行综合检查，覆盖多个场景。
服务端检查也有问题，一个是调用服务的方式不通用，需要额外实现，还有就是服务注册中心可能和服务的网络不互通。

节点变化通知

当服务有节点退出或新的节点加入时，订阅者如何及时收到通知？经典的push和pull的问题

[后台]负载均衡（一）算法篇

Wed, 06 May 2020 20:24:30 +0800

当单机的访问压力很大时，就需要引入集群。集群一个很重要的事情就是把请求均匀地分配在各个机器上，这就是负载均衡的雏形。
有基于MAC地址的二层负载均衡和基于IP地址的三层负载均衡。二层负载均衡会通过一个虚拟MAC地址接收请求，然后再分配到真实的MAC地址；三层负载均衡会通过一个虚拟IP地址接收请求，然后再分配到真实的IP地址；
四层通过虚拟IP+端口接收请求，然后再分配到真实的服务器（比如LVS，F5）；七层通过虚拟的URL或主机名接收请求，然后再分配到真实的服务器（Haproxy和Nginx）。
四层和七层是最常见的负载均衡模型。

**四层：**以常见的TCP为例，负载均衡设备在接收到第一个来自客户端的SYN请求时，通过负载均衡算法选择服务器，并对报文中目标IP地址进行修改（改为后端服务器IP），直接转发给该服务器。TCP的连接建立，即三次握手是客户端和服务器直接建立的，负载均衡设备只是起到一个类似路由器的转发动作。在某些部署情况下，为保证服务器回包可以正确返回给负载均衡设备，在转发报文的同时可能还会对报文原来的源地址进行修改。
**七层：**以常见的TCP为例，负载均衡设备如果要根据真正的应用层内容再选择服务器，只能先代理最终的服务器和客户端建立连接(三次握手)后，才可能接受到客户端发送的真正应用层内容的报文，然后再根据该报文中的特定字段，再加上设置的负载均衡算法，选择内部某台服务器。负载均衡设备在这种情况下，更类似于一个代理服务器。负载均衡和前端的客户端以及后端的服务器会分别建立TCP连接。所以从这个技术原理上来看，七层负载均衡明显的对负载均衡设备的要求更高，处理七层的能力也必然会低于四层模式的部署方式。
参考资料：四层和七层负载均衡的区别

nginx用的负载均衡算法

Nginx可以作为HTTP反向代理，把访问本机的HTTP请求，均分到后端集群的若干台服务器上。负载均衡的核心就是负载均衡所使用的平衡算法，适用于各种场景。
Nginx的负载均衡算法
Nginx目前提供的负载均衡模块：
ngx_http_upstream_round_robin，加权轮询，可均分请求，是默认的HTTP负载均衡算法，集成在框架中。
ngx_http_upstream_ip_hash_module，IP哈希，可保持会话。
ngx_http_upstream_least_conn_module，最少连接数，可均分连接。适用于链接数体现资源的服务，比如FTP。
ngx_http_upstream_hash_module，一致性哈希，可减少缓存数据的失效。

随机访问

在介绍nginx的模式前，先介绍下普通的负载均衡方法。假设有7个请求，我们给A、B、C三个节点分别4、2、1的权重。最朴素的负载均衡方式有下面几种：

完全轮询：访问完A去访问B，访问完B去访问C，再去访问A。缺点是没有权重，不能根据负载调节。
列表轮询：构造一个数组[A, A, A, A, B, B, C]，每次pop出去一个访问。缺点是pop出去的元素太随机，可能一次集中访问A ，而且占用内存太大，对于几万的权重范围不合适。
随机数：我们按照A、B、C的权重划分好区间，A（0、1、2、3），B（4、5），C（6），然后取一个随机数，模余7，看看最后的结果在哪个区间内，就取哪个节点。缺点是完全随机，无法避免集中访问。

加权轮询

假设有7个请求，我们给A、B、C三个节点分别4、2、1的权重。如果随机按照概率来选，那么很可能出现连续四个请求都在A上面的情况，这样只能保证结果看起来均衡，但是时间段内不均衡。Nginx采用了一种平滑的加权平均算法来选取节点（Weighted Round Robin）。
先引入三个概念，都用来描述服务器节点的权重：

$W$ : weight 我们指定的权重，就是上面例子中的4、2、1。
$W_{ew}$: effective_weight 有效权重，初始值为$W$。用来对故障节点降权。
如果通信中有错误产生，就减小effective_weight。（故障降权）
此后有新的请求过来时，再逐步增加effective_weight，最终又恢复到weight。（自动恢复）
$W_{cw}$ : current_weight 当前真实权重，每次都会选到最大的真实权重的节点去请求

真实权重$W_{cw}$计算方式：

初始化：$W_{cw}$ 起始值为0
获得实时权重：请求到来后，给每个节点的真实权重加上有效权重，即$每个节点 W_{cw} = W_{cw} + W_{ew}$
选出最大权重：选择真实权重最大的节点最为本次请求的目标
回避刚选的节点：最选择的节点的实时权重减去所有节点（包括自己）的有效权重和。即$选中节点 W_{cw} = W_{cw} - (W_{ew1} + W_{ew2} + … + W_{ewn})$

来看一个具体的例子：
假设A、B、C三个节点的权重分别为4、2、1。

请求序号	请求后的current_weight	选择的节点	选择后的current_weight
未请求	{0,0,0}	/	/
1	{4,2,1}	A	{-3,2,1}
2	{1,4,2}	B	{1,-3,2}
3	{5,-1,3}	A	{-2,-1,3}
4	{2,1,4}	C	{2,1,-3}
5	{6,3,-2}	A	{-1,3,-2}
6	{3,5,-1}	B	{3,-2,-1}
7	{7,0,0}	A	{0,0,0}
三个结论：每个节点被选中的次数是符合权重的；A没有被连续选取；七次之后权重会归零，是一个循环。

static ngx_http_upstream_rr_peer_t *ngx_http_upstream_get_peer(ngx_http_upstream_rr_peer_data_t *rrp)
{
    time_t                        now;
    uintptr_t                     m;
    ngx_int_t                     total;
    ngx_uint_t                    i, n, p;
    ngx_http_upstream_rr_peer_t  *peer, *best;

    now = ngx_time();
    best = NULL;
    total = 0;
    ...

    /* 遍历集群中的所有后端 */
    for (peer = rrp->peers->peer, i = 0;
         peer;
         peer = peer->next, i++)
    {

        n = i / (8 * sizeof(uintptr_t));
        m = (uintptr_t) 1 << i % (8 * sizeof(uintptr_t));

        /* 检查该后端服务器在位图中对应的位，为1时表示不可用 */
        if (rrp->tried[n] & m)
            continue;
       
        /* 永久不可用的标志 */
        if (peer->down) 
            continue;
        
       /* 在一段时间内，如果此后端服务器的失败次数，超过了允许的最大值，那么不允许使用此后端了 */
       if (peer->max_fails
            && peer->fails >= peer->max_fails
            && now - peer->checked <= peer->fail_timeout)
            continue;
        
        peer->current_weight += peer->effective_weight; /* 对每个后端，增加其当前权重 */
        total += peer->effective_weight; /* 累加所有后端的有效权重 */

        /* 如果之前此后端发生了失败，会减小其effective_weight来降低它的权重。          
         * 此后在选取后端的过程中，又通过增加其effective_weight来恢复它的权重。          
         */        
        if (peer->effective_weight < peer->weight) 
            peer->effective_weight++;
        
        /* 选取当前权重最大者，作为本次选定的后端 */
        if (best == NULL || peer->current_weight > best->current_weight) {
            best = peer;
            p = i;
        }
    }

    if (best == NULL) /* 没有可用的后端 */
        return NULL;
    
    rrp->current = best; /* 保存本次选定的后端 */

    n = p / (8 * sizeof(uintptr_t));
    m = (uintptr_t) 1 << p % (8 * sizeof(uintptr_t));

    /* 对于本次请求，如果之后需要再次选取后端，不能再选取这个后端了 */    
    rrp->tried[n] |= m;

    best->current_weight -= total; /* 选定后端后，需要降低其当前权重 */  
    /* 更新checked时间 */
    if (now - best->checked > best->fail_timeout)
        best->checked = now;
    
    return best;
}

ip_hash

ip_hash是基于客户端IP的哈希值来选择服务器。同一个客户端的请求，都会发往同一台后端，除非该后端不可用了。ip_hash能够达到保持会话的效果。
和随机加权哈希一样，ip哈希借鉴了权重分段的思想，先算出哈希值, 然后模余total_weight，得到初始权重W [0, total_weight)，开始遍历节点。如果哈希值小于当前节点的权重，就选择当前节点；如果哈希值大于等于当前节点的权重，就减去当前节点的权重，再去尝试下个节点。我们还是讨论A，B，C三个节点的情况，假设权重分别为2、4、1 。
权重的和是7，那么哈希值应该是0~6 （因为模了哈希值）
6的情况：6 >= 2 , 所以不选A，减去2。 6-2 >= 4，所以不选B，减去4。2-4 < 1，所以选C
5的情况：5 >= 2 , 所以不选A，减去2。 5-2 < 4，所以选B
4的情况：4 >= 2 , 所以不选A，减去2。 4-2 < 4，所以选B 。哈希值为3、2的情况也一样。
1、0的情况：1 < 2，所以选A
可以看到最后四个选B，两个选A，一个选C，还是均衡的。

[Linux]文件和零拷贝

Thu, 31 Oct 2019 17:25:36 +0800

文件

文件描述符

文件描述符：在Linux中，所有的文件都是通过文件描述符引用。fd是一个非负整数。按照惯例，标准输入的fd是0，标准输出的fd是1，标准错误的fd是2。分别作为STDIN_FILENO、STDOUT_FILENO、STDERR_FILENO定义在unistd中。
文件描述符的上限：fd的范围是 0 ~ OEPN_MAX-1 。OPEN_MAX一般是20或者64。这代表一个进程最多打开19或63个文件。

文件内核API

文件的打开：int open(const char *pathname, int flags)参数填上要打开的文件的名字（甚至可以不存在），会返回打开的fd。下面是一些常用的选项：

O_APPEND 文件将以追加模式打开，每次写操作之前，文件偏移量都会置于文件末尾。
O_CREAT 创建文件。如果文件已经存在，则会直接打开。
O_EXCL 和上面的O_CREAT联用时，表示如果文件已经存在，就会失败。可以保证多进程同时创建文件的原子操作。
O_SYNC 打开文件用于同步I/O。在数据写到磁盘之前写操作不会完成；一般的读操作已是同步的，所以这个标志对读操作没有影响。
O_NONBLOCK 如果可以，文件将在非阻塞模式下打开。任何其它操作都不会使该进程在I/O中阻塞。这种情况可能只用于FIFO。
O_DIRECT 打开文件用于直接I/O。将会绕过缓冲区操作。

文件的关闭：int close(int fd) 关闭一个文件会释放上面所有的记录锁。一个进程终止后，内核会自动关闭它打开的所有文件。
文件定位： off_t lseek(int fd, off_t offset, int whence) 参数whence指定了偏移地址（开始点SEEK_SET 当前点SEEK_CUR 结束点SEET_END），另一个参数offset是从参考点开始的偏移量（可正可负）。返回新的偏移地址。
空洞文件：如果写入一部分之后lseek到后面去写入，中间就会产生一个空洞，实际不占用磁盘大小。
文件读取：ssize_t read(int fd, void *buf, size_t nbytes) 返回读取到的字节数。下面的情况可能使得读取到的字节数少于需要的字节数： 1)再读这么多就到了文件尾 2)读网络缓冲区读完 3)读FIFO管道包含的字节少于需要的长度 4)读终端设备，一次一行
文件写入：ssize_t write(int fd, const void* buf, size_t nbytes) 返回写入的字节数。一般和nbytes相同。
文件属性编辑：int fcntl(int fd, int cmd, ... /* arg */ ) 提供了编辑fd属性标志的方法。

read buf该设置多大

在Linux ext4系统上，磁盘块长度st_blksize为4096字节。测试表明，在4096的整数倍上，读磁盘有更快的速率，可以根据需要选择4096或8192等字节的buf。
系统为了优化频繁写磁盘的情况，会使用预读取（read ahead）技术，在检测到顺序读时，会比本次读取需要的读出更多的数据，读入缓冲区。

[Linux]Linux socket API

Mon, 21 Oct 2019 17:45:09 +0800

创建和关闭

int socket(int domain, int type, int protocol) 创建一个socket。

domain 指定了通信的特性。AF_UNIX Unix域，AF_INET IPv4域。 AF_INET6 IPv6域。
type 指定了连接的类型。
SOCK_STREAM 有序、可靠、双向、面向连接的字节流 TCP
SOCK_DGRAM 不可靠、无连接、固定长度的报文 UDP
SOCK_SEQPACKET 固定长度、有序、可靠、双向、面向连接的字节流
protocol 为0时，选择指定域的默认协议。AF_INET域的SOCK_STREAM默认的协议为TCP，SOCK_DGRAM则为UDP。还有IPPROTO_ICMP、IPPROTO_IP、IPPROTO_RAW等。SOCK_STREAM提供字节流服务，所以程序分不出报文的界限。

int shutdown(int socketfd, int how) 关闭一个socket。

套接字函数是双向的。可以用这个函数关闭套接字的某个方向的IO。
how是SHUT_RD表示关闭读端，无法从套接字读取数据。SHUT_WR是关闭写端，无法向套接字写入数据。SHUT_RDWR无法读也无法写。
close()是一个fd的通用释放函数。他和shutdown有何不同？1) close要等所有的活动引用关闭后才释放套接字。这使得dup之后的套接字必须等待所有的引用释放。但是shutdown和引用fd数量无关。2)shutdown可以方便地关闭读写的任何一端。

网络地址

地址的结构体

// Linux 套接字
// 这是Linux定义的一个通用结构。所有地址都可以强转为这个结构体，比如IPV4、IPV6等，便于使用。
struct sockaddr {
        u_short sa_family;              /* address family */
        char    sa_data[14];            /* up to 14 bytes of direct address */
};

// IPv4 地址
// 1. in_port_t 是16位的网络序整数，需要htons转换到网络序再赋值
// 2. sin_addr 有几种常见的常量，INADDR_ANY表示所有网卡
sockaddr_in {
    sa_family_t sin_family;
    in_port_t sin_port;			    /* Port number.  (typedef uint16_t in_port_t)*/
    struct in_addr sin_addr;		/* Internet address.  （typedef uint32_t in_addr_t)*/
    unsigned char sin_zero[8];		/* sockaddr 里sa_data定义的14(sa_data)-2(sin_port)-4(sin_addr)=8字节*/
}

网络序

下面的函数提供了网络序端口和主机序端口（int类型）转换的方法。
uint32_t htonl(uint32_t hostint32)返回以网络序（大端序）表示的整数。
uint16_t htons(uint16_t hostint32)
uint32_t ntohl(uint32_t netint32) 返回以主机序（小端序）表示的整数。
uint16_t ntohs(uint16_t netint32)

[后台]RocketMQ的架构和设计

Wed, 04 Sep 2019 19:00:56 +0800

主要整理文献：
RocketMQ部署架构和技术架构 - Github
RocketMQ关键机制的设计原理 - Github
RocketMQ 原理简介 - 淘宝消息中间件项目组

设计理念和部署

消息队列需要解决的问题

发布/订阅 最基础的需求，可以做解耦&聚合，如果用Redis做，不够可靠
支持优先级队列、延时队列
顺序消费，rockmq严格有序
支持消息过滤，Producer和consumer共同过滤
持久化 内存缓存+文件
异常恢复
broker crash，os crash，掉电 —保证消息不丢，或者丢失少量数据（依赖刷盘方式是同步还是异步）
磁盘损坏，机器永久损坏 —通过异步复制，可保证99%的消息不丢
实时性 RocketMQ使用长轮询Pull方式，可保证消息非常实时，消息实时性不低于Push。
At least Once 和 Exactly Only Once，至少消费一次且只消费一次
broker的buffer容量问题。RocketMQ 的内存Buffer持久化在硬盘，抽象成一个无限长度的队列，不管有多少数据进来都能装得下，当然也会定时清理。
回溯消费 一般是按照时间维度，例如由于 Consumer 系统故障，恢复后需要重新消费 1 小时前的数据，那么 Broker 要提供一种机制，可以按照时间维度来回退消费进度。
RocketMQ 支持按照时间回溯消费，时间维度精确到毫秒，可以向前回溯，也可以向后回溯。
消息堆积 消息堆积在内存Buffer，一旦超过内存Buffer，可以根据一定的丢弃策略来丢弃消息，对性能影响不大，但是不能堆积太多
消息堆积到持久化存储系统中，例如DB，KV存储，文件记录形式。当消息不能在内存Cache命中时，要不可避免的访问磁盘，会产生大量读IO，读IO的吞吐量直接决定了消息堆积后的访问能力。
消息重试 消息重试有两种原因，一种是消息本身处理失败，如编码有问题等，重试永远不会成功。另一部分是处理消息依赖的下游服务暂时不可用，一段时间重试后可以成功。所以可以消极重试，逐步重试增大等待重试间隔。

RockMQ 模块

Name Server ：NameServer是一个非常简单的Topic路由注册中心，其角色类似Dubbo中的zookeeper，支持Broker的动态注册与发现。
(1) 路由管理
Broker管理：NameServer接受Broker集群的注册信息并且保存下来作为路由信息的基本数据。然后提供心跳检测机制，检查Broker是否还存活；
路由信息管理：每个NameServer将保存关于Broker集群的整个路由信息和用于客户端查询的队列信息。然后Producer和Conumser通过NameServer就可以知道整个Broker集群的路由信息，找到对应topic的路由信息，从而进行消息的投递和消费。
(2) 无状态：NameServer通常也是集群的方式部署，各实例间相互不进行信息通讯。它是一个几乎无状态的结点，他们之间互不通信。Broker是向每一台NameServer注册自己的路由信息，所以每一个NameServer实例上面都保存一份完整的路由信息。当某个NameServer因某种原因下线了，Broker仍然可以向其它NameServer同步其路由信息，Producer,Consumer仍然可以动态感知Broker的路由的信息。
(3) 随机选择：客户端连接时，会随机选择。
(4) 长连接：Broker向所有的NameServer结点建立长连接，注册Topic信息。Producer和Consumer也是长连接。
Broker：处理消息存储，转发等处理的服务器。
(0) 分Group：Broker以group分开，每个group只允许一个master，若干个slave。
(1) 读写分离：只有master才能进行写入操作，slave不允许。
(2) 主从同步：slave从master中同步数据。同步策略取决于master的配置，可以采用同步双写，异步复制两种。
(3) 默认消费：在默认情况下，消费者都从master消费，只有master挂掉或者产生消息堆积了才从slave消费。
Broker有下面几个重要的子模块：
(1) Remoting Module：整个Broker的实体，负责处理来自clients端的请求。
(2) Client Manager：负责管理客户端(Producer/Consumer)和维护Consumer的Topic订阅信息
(3) Store Service：提供方便简单的API接口处理消息存储到物理硬盘和查询功能。
(4) HA Service：高可用服务，提供Master Broker 和 Slave Broker之间的数据同步功能。
(5) Index Service：根据特定的Message key对投递到Broker的消息进行索引服务，以提供消息的快速查询。

[Linux]进程间通信

Thu, 01 Aug 2019 20:26:09 +0800

管道

管道是进程间通信的最古老方式。它通过共享文件来完成进程间的通信。它有两个局限性：

它是半双工的。数据只能从一个进程流向另一个进程。
通信的进程之间必须另一个进程是fork出来的。通常，一个进程会创建一个管道，然后执行fork，这样管道就会在两个进程之间共享。
FIFO解决了第一种局限性，Unix域套接字解决了第二种。我们先来看管道。

int pipe(int pipefd[2]);管道由pipe函数创建。

参数pipefd是一个两个元素的数组。pipefd[0]用来读，pipefd[1]用来写。
成功返回0 。失败返回-1并设置errno。
单进程的管道没有任何用处。在这个函数之后一般会fork，然后一个进程来写pipefd[1]，一个进程来读pipefd[0]。他们的另一个fd元素将会被关闭。

下面是一段实例, 父进程通过管道向子进程传递了信息，子进程接收并把他们输出：

#include "apue.h"

int main(void)
{
	int		n;
	int		fd[2];
	pid_t	pid;
	char	line[MAXLINE];

	if (pipe(fd) < 0)
		err_sys("pipe error");
	if ((pid = fork()) < 0) {
		err_sys("fork error");
	} else if (pid > 0) {		/* parent */
		close(fd[0]);
		write(fd[1], "hello world\n", 12);
	} else {					/* child */
		close(fd[1]);
		n = read(fd[0], line, MAXLINE);
		write(STDOUT_FILENO, line, n);
	}
	exit(0);
}

FILE *popen(const char *command, const char *type) 函数popen执行一个命令，然后返回这个命令的文件指针。

[Linux]高级IO

Wed, 31 Jul 2019 20:20:43 +0800

如果有多个IO需要处理

当一个描述符读，然后又写到另一个描述符时，可以用循环的方式访问阻塞io：

#include <stdio.h>
#include <unistd.h>
#define BUF_SIZE 128

int main(){
	char buf[BUF_SIZE];
	int n;
	while ( n = read(STDIN_FILENO, buf, BUF_SIZE) > 0) {
	        if (write(STDOUT_FILENO, buf, n) != n){
	                fprintf(stderr, "%s\n", "write error!");
	                break;
	        }
	}
	return 0;
}

但是如果要从两个fd读的时候，就不能用阻塞io去读了。因为进程阻塞在某个fd的时候，另一个fd即使输入了数据也无法处理。
比如一个telnet程序的输出有两个来源，用户输入回显和远端回包。如果阻塞在等待远端回包，用户输入就不会有回显了。解决这个问题就几种思路：

再fork一个进程，每个进程处理一个fd。这看起来很好，但是处理EOF却成了问题。如果子进程先读到EOF，那么子进程终止，返回SIGCHLD给父进程，然后父进程终止。如果父进程读到EOF，父进程就需要通知子进程结束，此时需要额外的信号（如SIGUSER1）.
用两个线程来处理，每个线程一个fd。同样的，处理线程之间的同步也会变的比较复杂。
用非阻塞的io来轮询。先read一个fd，如果没数据立即返回，然后等待若干时间，然后再read下一个fd，直到某个fd有数据读为止。这个方法有两个缺点，一是频繁的read调用浪费了cpu时间，但是大部分时间是没数据读的。二是每次read返回后等待的时间不好确定，太久会读取不及时，太短会使得cpu更加繁忙。
使用异步IO。当fd归属的设备准备好的时候，用信号通知处理进程。这个方法有两个缺点，一是信号在不同的系统上实现不同，移植性较差。二是进程收到的信号只有一种（SIGPOLL或者SIGIO），进程无法分辨是哪个fd。

有没有比较完善的方案？io多路复用来了。这种方案会记录一个我们需要的fd的列表，然后我们去查询，当这个列表中有fd有数据时，查询就会返回这个fd。

IO多路复用：select

int select(int nfds, fd_set *readfds, fd_set *writefds, fd_set *exceptfds, struct timeval *timeout); select 函数提供了查询fd状态的能力。我们传入希望监听的fd，内核告诉我们哪些fd已经有事件发生并返回。

参数 timeout 控制愿意等待的时间。timeval为NULL时，select会一直阻塞等待某个fd准备好。（如果接收到信号，select也会提前返回-1，并把errno设为INTR）
参数 readfds, writefds, exceptfds 是我们告诉内核希望监听的fd的指针。如果希望监听某fd的读事件，就加入到readfds中。后面两个用于监听写事件和异常事件。
返回时，readfds, writefds, exceptfds 中会留下对应事件已经就绪的fd。此时这些fd是可读的、可写的或发生异常的。
参数 nfds 是三个fd集合中的最大值加一，它制定了fd的遍历范围。也可以把它设为FD_SETSIZE，一般为1024，但是这样会导致select遍历系统中所有的fd。
返回值：a)如果没有就绪的fd，函数返回0。b)如果有就绪的fd，函数返回就绪的fd数量。c)如果收到信号，返回-1，并把errno设为INTR d)特别地，如果fd到达EOF，函数调用read，然后返回0
函数pselect采用了timespec类型的超时设置。此外，还可以设置sigmask用来屏蔽一些信号，防止自己被终止。

fd_set 是一个fd的集合。在实现上是一个大bit数组，它只支持赋值操作和下面宏定义的操作：

[Linux]谈一谈并行Counting

Fri, 26 Jul 2019 16:49:50 +0800

简单的并行计数

在一个简单的多线程计数程序中，我们假设要每个线程去把sum的值多加100m，同时进行。代码如下：

#include <pthread.h>
#include <stdio.h>

#if 0
  #define ADD_P(x) __sync_fetch_and_add((x), 1)
#else
  #define ADD_P(x) (++(*x))
#endif
#define TC 8

void *thgo(void *arg){
  long i = 1000*1000*100;
  while(i-- > 0){ADD_P((long *)arg);};
  pthread_t me = pthread_self();
  printf("thread sum: %ld tid: %lu \n",  *(long *)arg, (unsigned long)me);
}

int main (){
  long sum = 0;
  pthread_t ths[TC];
  // threads
  for (int i = 0; i < TC; ++i){
      pthread_create(&ths[i], NULL, thgo, &sum);
  }
  // main thread
  thgo(&sum);
  // join
  for (int i = 0; i < TC; ++i){
      pthread_join(ths[i], NULL);
  }
  printf("all final sum : %ld\n", sum);
  return 0;
}

如果使用一般的计数，会出现严重的数据踩踏问题，导致结果只能取得一定近似的值：

[Linux]并行编程：进程、线程和同步

Thu, 25 Jul 2019 15:45:04 +0800

如何进行并行编程？本文给了一些pthead库基本的多进程、多线程API，和详细的样例帮助理解这些API。
本教程基于AUPE 2013、 perfbook

Shell中的并行

后台执行 &

通过&符号指定实例在后台运行，然后统一等待结束。

compute_it 1 > 1.out &
compute_it 2 > 2.out &
wait
cat 1.out 2.out

管道 |

对于一个足够大的输入文件来说，grep模式匹配将与sed编辑和sort处理并行运行。

`1`	`grep "$pattern" \| sed -e "s/a/b/" \| sort`

POSIX多进程

下面给出的程序中建立了一个进程，然后修改了x的值并打印，最后父进程等待子进程结束。

fork

int fork()马上创建一个当前进程的子进程。子进程会复制(而不是共享)父进程的堆栈、数据空间、fd。

如果是父进程，fork返回子进程的pid。如果是子进程，fork返回0。一般用这个区分不同的分支。
fork返回负数表示失败。失败的原因可能有：系统有了太多的进程；系统中用户进程数超过了CHILD_MAX。此时返回负数。
fork后如果不需要父进程的存储空间会立马调用exec。
使用fork一般有两个目的。父进程希望复制自己，或者想执行另外的程序（调用exec）
为了避免拷贝成本，出现了写时拷贝技术(Copy-On-Write, COW)，子进程创建后分享父进程的数据，并把内存区域设置为只读。当需要写数据时再为这块数据创建副本。

vfork

int vfork()创建一个子进程，但分享(不复制)父进程的数据。当执行exec时父进程才退出休眠。专为了避免fork的拷贝成本设计。因为share父进程的数据有很大风险，所以man手册里明确说明vfork()之后，子进程只应该调用_exit()或者exec函数族。

exit

void exit(int)退出当前进程。不像return会析构局部变量，弹栈，回到上级函数。如果在子进程的main中调用了return，main会返回两次，导致程序出错。exit不会有这个问题。

wait

pid_t wait(int &status) 阻塞等待任意一个子进程结束
a)如果子进程都在运行则阻塞
b)如果一个子进程已经终止，内核向父进程发出了SIGCHLD信号，则获得终止状态并立即返回
c)成功了返回pid，没有子进程，立即出错返回-1
d)子进程状态status可以用四个返回bool的宏 WIFEXITED(int)、WIFEXITSIGNALED(int)、WIFSTOPPED(int)、WIFCONTINUED(int)、来判断属于正常、异常、暂停、暂停后继续的状态。此外还有对应的WEIXTSTATUS(int)返回子进程exit函数的参数、WTERMSIG(int)返回信号编号、WCOREDUMP(int）返回是否生成coredump等。

pid_t waitpid(pid_t pid, int &status, int option)等待指定的pid的子进程结束。
a)当pid=-1，和wait等效。
b)当option=WNOHANG，此函数会立即返回不会阻塞。
c)成功了返回pid，没有子进程，立即出错返回-1

#include <stdio.h>
#include <stdlib.h>
#include <errno.h>
#include <poll.h>
#include <sys/wait.h>
#include <unistd.h>

int x = 0;

// 等待所有的子进程结束
 static __inline__ void waitall(void)
 {
     int pid;
     int status;
     for (;;) {              
         pid = wait(&status);    //sys/wait.h
         if (pid == -1) {
             if (errno == ECHILD)    //errno.h 子进程不存在
                 break;      
             perror("wait");     
             exit(EXIT_FAILURE); 
         }
         poll(NULL, 0, 1);       // 等待1ms
     }                   
 }

int main(int argc, char *argv[])
{
    int pid;
    pid = fork();		// <unistd.h>
    if (pid == 0) { /* child */
        x = 1;                  
        printf("Child process set x=1\n");  
        exit(EXIT_SUCCESS);         //stdlib
    }
    if (pid < 0) { /* parent, upon error */
        perror("fork");   //stdio
        exit(EXIT_FAILURE);    //stdlib
    }
    /* parent */
    waitall(); 
    //父进程一直等待到子进程退出后才调用printf（）。
    //通过不同进程并发地访问printf（）的I/O缓冲区并不简单，最好也不要这么做
    printf("Parent process sees x=%d\n", x);    
    return EXIT_SUCCESS;
}

POSIX多线程

pthread_create

int pthread_create(pthread_t tidp, const pthread_attr_t *attr, void *(*start_rtn)(void *), void *arg)创建一个线程去执行参数start_rtn中的函数。该函数参数为arg。tidp参数则会写入线程的线程ID。

[Python]Scrapy Scan

Wed, 20 Mar 2019 23:00:25 +0800

scrapy是个很简单强大的python爬虫框架，不需要处理网络相关逻辑就可以轻松爬取。本文介绍了一些基本的内容。需要注意的是，本文档中所有的●表示非必须内容。
本教程基于官方文档：官方文档

安装scrapy

CentOS

1
2

yum install python34-devel.x86_64
pip3 install scrapy

创建项目

//创建项目hello
scrapy startproject hello
//创建一个爬虫（在项目根目录运行，不要加http://），名字为baidu，域名为www.baidu.com
scrapy genspider baidu "www.baidu.com"

● 需要注意的是，如果要无视robots.txt文件，请在下面的settings.py中设置ROBOTSTXT_OBEY = False
● 刚才建好的项目目录文件树如下：

tree hello 
hello
|-- hello
|   |-- __init__.py
|   |-- items.py            // 输出结构体定义
|   |-- middlewares.py
|   |-- pipelines.py
|   |-- __pycache__
|   |-- settings.py         // 设置，记得把 ROBOTSTXT_OBEY = False
|   |-- spiders
|       |-- __init__.py
|       |-- baidu.py        // 刚创建的爬虫
|       |-- __pycache__
|-- scrapy.cfg

Shell：测试代码

使用shell可以帮助实现爬虫的代码，查看网页的相关信息。结合浏览器中的审查元素查看会让你构造出需要选择的数据部分。

[数据结构]深入理解红黑树

Wed, 20 Mar 2019 23:00:25 +0800

平衡树

在谈红黑树之前，可以先看看红黑树的根源，234树。234树也是一种平衡树。
平衡树的原型都是二叉查找树，即左面的节点比他小，右边的节点比他大。但是在二叉查找树的过程中，很有可能变成树朝一边严重倾斜的情况。为了解决这个问题，设计了如下变种：

avl：严格控制树的平衡，左右树的高度差不大于1。所以查找性能是logn。在插入和删除操作时，最差的情况是每一级的父节点都会旋转。时间复杂度都是O(logn)。
红黑树：红黑树的左右子树最高差时，一个子树是另一个子树的一倍。最坏查找性能是2logn。在插入操作时，最差旋转2次，删除操作最差旋转三次，可以减少avl的平衡操作，但是依然是O(logn)的复杂度（在找到节点的插入位置就要花费logn时间）。
splay：插入删除复杂度也是O(logn)，可以用数组实现，不需要额外维护树的节点信息。但在最坏情况下他会退化成一条链。而且只读操作也会影响树的结构，在多线程环境访问下比较复杂。
替罪羊树：在查找树不平衡的时候，找到最高的一个节点（满足左右子树不差0.7倍的平衡点），重构整个子树

查找问题还可以用哈希表解决。哈希表是无序的，而且会耗费大块的内存。
一些常见的面试题：常见面试题-cnblog

各种树的性能

2-3-4树

2-3-4树-CSDN
234树是红黑树的等价变种。先来看看2-3树，这种树有两种节点，2节点和3节点。
2-节点：普通节点，有两个子连接
3-节点：有两个值A、B，三个连接（分别指向小于A，介于AB之间，大于B的儿子）
2-3树可以保证插入的时候所有叶子到根节点的距离是相同的。我们看看他如何插入：
(1) 如果值插入2节点，把他扩充成一个3节点。
(2) 如果插入插入3节点
A. 整个树只有一个3节点：把他扩展成4-节点，然后分解4-节点，然后将分解后的新树的父节点融入到2-节点的父节点中去。
B. 3-节点有一个2-节点的父节点，此时的操作是，3-节点扩充为4-节点，然后分解4-节点，然后将分解后的新树的父节点融入到2-节点的父节点中去。
C. 3-节点有一个3-节点的父节点，此时操作是：3-节点扩充为4-节点，然后分解4-节点，新树父节点向上融合，上面的3-节点继续扩充，融合，分解，新树继续向上融合，直到父节点为2-节点为止，如果向上到根节点都是3-节点，将根节点扩充为4-节点，然后分解为新树，至此，整个树增加一层，仍然保持平衡。
23树的流程比较复杂，而且涉及不同节点的转换，所以出现了红黑树来简化操作。我们把3节点的两个元素红色连接连起来。这时候红色连接出去的那个节点就成了红黑树的红节点，其余的都是黑节点。如果你将红黑树中所有的红色链接放平，那么它所有的叶子节点到根节点的距离都是相同的，所以是一个完美的黑色平衡。
所以，红黑树的另一种定义是满足下列条件的二叉查找树：
⑴ 红链接均为左链接。
⑵ 没有任何一个结点同时和两条红链接相连。(这样会出现4-节点)
⑶ 该树是完美黑色平衡的，即任意空链接到根结点的路径上的黑链接数量相同。

红黑树

github红黑树(有比较好的图解)
cnblog红黑树流程详解
红黑树的五条性质：
1）每个结点要么是红的，要么是黑的。
2）根结点是黑的。
3）每个叶结点（叶结点即指树尾端NIL指针或NULL结点）是黑的。
4）如果一个结点是红的，那么它的俩个儿子都是黑的。
5）对于任一结点而言，其到叶结点树尾端NIL指针的每一条路径都包含相同数目的黑结点。

如果我们插入一个节点，并把他染红，则树的1235项原则都不会被破坏。如何保证原则4呢？调整的原则是把红色问题向上修正到根节点，最后把根节点染黑，来达到平衡。
我们先把插入的节点染红，然后进行修正操作：
插入修复情况1：当前结点的父结点是红色且叔叔结点是红色。
将当前结点的父结点和叔叔结点涂黑，祖父结点涂红。在以祖父节点为新的当前结点再做一遍。
A. 为了解决本节点和父节点都是红色，把父节点染黑。
B. 但是父节点的在子树多了个黑色，所以要把叔叔也染黑来平衡。
C. 此时爷爷节点的子树也多了个黑色，所以把他染红。
D. 爷爷节点被染红了上面的节点曾爷爷有可能是红的，在做一次。
插入修复情况2：当前结点的父结点是红色,叔叔结点是黑色，当前结点是其父结点的右子
对策：当前结点的父结点做为新的当前结点，以新当前结点为支点左旋。左旋后，本节点上移，把问题向上修正。可以转化到情况3
插入修复情况3：当前结点的父结点是红色,叔叔结点是黑色，当前结点是其父结点的左子
解法：父结点变为黑色，祖父结点变为红色，在祖父结点为支点右旋
A. 为了解决本节点和父节点都为红，把父节点染黑
B. 为了解决父节点在的子树多了一个黑色，把叔叔染红并右旋解决

[深度学习]C1W1~C1W2

Tue, 14 Aug 2018 21:09:13 +0800

C1W1: 什么是deep learning

单一神经元

deeplearning是模拟大脑的一种机器学习算法。以房价预测为例：

上图把房子面积作为输入X，房价作为输出Y，通过拟合得到了一个一次函数
$$
Y=aX+b
$$
这个函数的负值均视为0，即使用了ReLU函数作为神经元的激活函数做了处理。
$$
f(x) = \max(aX+b, 0)
$$

Note: ReLU函数：f(x)=\max(0, x)，近年来使用ReLU函数代替sigmoid函数为计算速度做了巨大的提升。

看看更多特征的情况：

飞速发展

上图中可以看到传统算法和神经网络的效果的一个对比，在数据多的情况下神经网络有明显的优势。近年来以下的一些原因导致deep learning飞速发展成为主流

计算速度飞速提升，使得训练较大的神经网络成为可能
数据变多（labeled data 变多）

生命周期

一个典型的深度学习的流程，即是一个Idea-Code-Train 的循环

C1W2: 基本的神经网络

问题描述

这里从一个简单的问题开始说起：识别一个64x64的图像是否为猫：

每个像素有RGB三个值组成，64*64个像素就是12228个值。所以X可以表示为一个12228维的向量。Y则是0或1（是或不是猫咪）。

这里需要很多(X, Y)组成的labeled data数据用来学习。每个样本用如下的数学方式表示：
$$
X\in R^{n_x}, Y\in{0,1} \qquad 其中n_x为每个图片的维度(12288)
$$
训练集可以用很多样本表示：
$$
\textrm{m training examples: } \{(X^{(1)}, Y^{(1)}), (X^{(2)}, Y^{(2)}), … ,(X^{(3)}, Y^{(3)})\}
$$
其中每个X都有n_x列，所以整个样本集可以表示为
$$
X\in R^{n_x\times m},Y \in R^{1 \times m}
$$

[Linux]GDB调试技巧

Sun, 17 Dec 2017 00:56:18 +0800

命令行参数

gdb有下面几种运行方式：

// 1. 通过coredump文件，或者存在的进程id分析，不会拉起新进程
gdb [options] [executable-file [core-file or process-id]]
// 2. 带参数运行程序
gdb [options] --args executable-file [inferior-arguments ...]
// 3. redhat等含有用于调试python的工具
// gdb [options] [--python|-P] script-file [script-arguments ...]

几个值得注意的参数：

// 和上面的类似，使用参数指定的
--args             Arguments after executable-file are passed to inferior
--core=COREFILE    Analyze the core dump COREFILE.
--pid=PID          Attach to running process PID.
--exec=EXECFILE    Use EXECFILE as the executable.
// 远程调试
-b BAUDRATE        Set serial port baud rate used for remote debugging.
-l TIMEOUT         Set timeout in seconds for remote debugging.
// 运行某个文件中的gdb指令
--command=FILE, -x Execute GDB commands from FILE.
// 运行某gdb指令，如gdb a.out -ex r开启文件并立即运行
--eval-command=COMMAND, -ex   Execute a single GDB command.
--directory=DIR    Search for source files in DIR.
--se=FILE          Use FILE as symbol file and executable file.

简单的例子：coredump分析

gdb的一大用处是通过coredump文件分析程序哪里发生了错误。首先要打开coredump生成开关：

[后台]分布式基础概念

Thu, 09 Nov 2017 22:22:02 +0800

CAP

Brewer’s CAP Theorem, 2009

CAP理论是分布式系统的基石，他指出了分布式系统的以下特性：

Consistency 强一致性(返回的数据时刻一致)
Availability 高可用性(服务一直可用，响应时间正常)
Tolerance of network Partition 分区容错性(保证有机器宕机服务依然正常)

CAP理论表明，一个分布式系统不可能同时满足一致性，可用性和分区容错性这三个需求，
最多只能同时满足两个。证明可以看上面的链接。

所以架构师往往要做出牺牲某一特性的选择：

CP：金融行业的数据库，价格昂贵，符合ACID
CA：传统关系型数据库，用于小型系统或单机系统
AP：key-value数据库，现代UGC服务基本都是这种架构，用最终一致性来换取高可用和分区容错性。
电商：牺牲少量的可用性和一致性，比较平衡，符合BASE

ACID

老生常谈的数据库事务的特性：

原子性(Atomicity) 事务中有失败，立即回滚到执行前。没有失败，全部成功

一致性(Consistency) 事务执行后数据的约束没有被破坏

隔离性(Isolation） 事务之间不交叉进行

持久性(Durability） 事务完成，永久储存

BASE

可伸缩性最佳实践：来自eBay的经验

BASE理论是对CAP理论的延伸，核心思想是即使无法做到强一致性（CAP的Consistency），但应用可以采用适合的方式达到最终一致性，来保证系统的容量和可用性。

Basically Availble （基本可用）

基本可用是指系统只保证核心可用，在访问量突增时采用有损服务的策略，让部分用户使用降级的服务。
什么是基本可用的服务？以秒杀为例：
逻辑有损：秒杀时只执行重要逻辑，加载资源可以先使用预加载的或者小图等
业务有损：秒杀需要会员、抢秒杀资格
流程有损：比如秒杀时前段丢掉大部分请求，从后端少量请求中选取中奖的请求处理

Soft-state （软状态/柔性事务）

“Soft state” 可以理解为"无连接"的, 而 “Hard state” 是"面向连接"的。换句话说，软状态的数据库可能存在很多中间状态，不同节点到达最终统一的状态前会有延迟（如异步复制）。

Eventual Consistency （最终一致性）

并非时刻保持一致，所有复制节点在某段时间后保持一致。
最终一致性是弱一致性的一种特例：
Step 1. A首先write了一个值到存储系统
Step 2. 存储系统保证在A,B,C后续读取之前没有其它写操作更新同样的值
Step 3. 最终所有的读取操作都会读取到最A写入的最新值

从A写入到读取操作读取成功有一定的时间，即不一致性窗口。如果没有失败发生的话，“不一致性窗口”的大小依赖于以下的几个因素：交互延迟，系统的负载，以及备机slave的个数。最终一致性方面最出名的系统可以说是DNS系统，当更新一个域名的IP以后，根据配置策略以及缓存控制策略的不同，最终所有的客户都会看到最新的值。

在下一篇文章的中，会表明只要集群$V_r + V_w \leq N$，即此时读取和写入操作是不重叠的，就能保证最终一致性。这个时候不一致性的窗口依赖于存储系统的异步实现方式，不一致性的窗口大小就等于从更新开始到所有的节点都异步更新完成之间的时间。

[C++]sizeof那些事儿

Wed, 16 Aug 2017 23:33:20 +0800

sizeof 是什么

首先明确一点，sizeof是运算符，不是函数。运算符是一个对于编译器来说的概念，是由编译器处理的，在程序编译好之后所有的sizeof都已经被替换为实际的值。类似的还有decltype。所以像

`1`	`sizeof(++i);`

这类的语句是不会改变i的值的。在C99之后，sizeof增加了一些运行时特性，可以算出可变数组的大小，像这样：

int num;
scanf("%d", &num);	 //input 4
int arr[num];
sizeof(arr);		//output 16

sizeof 怎么用

sizeof 支持下面的语法：

1
2

sizeof(type) 	    (1) 以字节数返回type类型对象表示的大小 
sizeof expression 	(2) 以字节数返回expression的类型对象表示的大小

其中，sizeof(char)、 sizeof(signed char)以及sizeof(unsigned char)始终返回1。

sizeof不能用于函数类型、不完整类型（含void）或位域左值。在一些编译器里，sizeof(void)会返回0，但这是没有定义的。

普通的sizeof

几个上面用法的例子：

int main(void)
{
    // type argument:
    printf("sizeof(float)         = %u\n", sizeof(float));   //4
    printf("sizeof(void(*)(void)) = %u\n", sizeof(void(*)(void)));   //4
    printf("sizeof(char[10])      = %u\n", sizeof(char[10]));    //10

    // expression argument:
    printf("sizeof 'a'   = %u\n", sizeof 'a'); // 'a'的类型是int, 4
//  printf("sizeof main = %zu\n", sizeof main); // 错误：函数类型
    printf("sizeof &main = %u\n", sizeof main()); //类型为返回值int, 4
    printf("sizeof \"hello\" = %u\n", sizeof "hello"); // 类型为char[6], 6
    printf("sizeof(\"12345\" + 1)     = %u\n", sizeof("12345" + 1)); // 类型为指针, 4
}

需要注意的是，在函数传参等数组退化为指针的时候sizeof返回的当然是指针大小，切忌用它来计算数组大小。

[C++]C++ 100行实现线程池

Fri, 07 Apr 2017 23:17:54 +0800

一个100行左右的简单线程池。用到了std::mutex和std::thread等新特性。

线程池模型

首先把每个函数抽象为一个任务(Task)，任务的过程就是调用这个Task的run函数。
然后把线程池中的线程封装为一个线程类（Thread），一直等待调度器分配任务（空闲状态），如果有任务分配立即进入忙状态。等任务执行结束再次变为空闲状态。
最后是一个调度器类（TreadPool），包含任务队列（随时添加新任务），和一个包含了Thread的vector（线程池中的线程）。如果任务队列非空，调度器每次从中取出一个任务，然后轮询线程池，搜寻空闲线程并把这个任务交给线程。
模型如下图所示：

代码实现

下面的代码实现了上述模型。其中Task类通过睡眠一定的秒数模拟任务，可以看到T1先执行完毕（1秒完毕），T2和T3在之后同时完毕，说明调度非常成功。

//linux, g++ -std=c++14 -o t *.cpp -pthread
#include <queue>
#include <iostream>
#include <mutex>
#include <thread>
#include <vector>
#include <unistd.h> 

class Task{
private:
    int no;
public:
    Task(int n){
        no = n;
    }
    //可以继承这个类重写该方法执行任务
    virtual void run(){
        sleep(no); //构造时决定执行几秒，模拟线程运行
        std::cout << no << "T\n";
    }

};

class Thread{
private:
    std::thread _thread;
    bool _isfree;
    Task *_task;
    std::mutex _locker;
public:
    //构造
    Thread() : _isfree(true), _task(nullptr){
        _thread = std::thread(&Thread::run, this);
        _thread.detach(); //放到后台， join是等待线程结束
    }
    //是否空闲
    bool isfree(){
        return _isfree;
    }
    //添加任务
    void add_task(Task *task){
        if(_isfree){
            _locker.lock();
            _task = task;
            _isfree = false;
            _locker.unlock();
        }
    }
    //如果有任务则执行任务，否则自旋
    void run(){
        while(true){
            if(_task){
                _locker.lock();
                _isfree = false;
                _task->run();
                _isfree = true;
                _task = nullptr;
                _locker.unlock();
            }
        }
    }

};

class ThreadPool{
private:
    std::queue<Task *> task_queue;
    std::vector<Thread *> _pool;
    std::mutex _locker;

public:
    //构造线程并后台执行，默认数量为10
    ThreadPool(int n = 10){
        while(n--){
            Thread *t = new Thread();
            _pool.push_back(t);
        }
        std::thread main_thread(&ThreadPool::run, this);
        main_thread.detach();
    }
    //释放线程池
    ~ThreadPool(){
        for(int i = 0;i < _pool.size(); ++i){
            delete _pool[i];
        }
    }
    //添加任务
    void add_task(Task *task){
        _locker.lock();
        task_queue.push(task);
        _locker.unlock();
    }
    //轮询
    void run(){
        while(true){
            _locker.lock();
            if(task_queue.empty()){
                _locker.unlock();
                continue;
            }
            // 寻找空闲线程执行任务
            for(int i = 0; i < _pool.size(); ++i){
                if(_pool[i]->isfree()){
                    _pool[i]->add_task(task_queue.front());
                    task_queue.pop();
                    break;
                }
            }
            _locker.unlock();
        }
    }

};

int main(){
    ThreadPool tp(2);
    
    Task t1(1);
    Task t2(3);
    Task t3(2);

    tp.add_task(&t1);
    tp.add_task(&t2);
    tp.add_task(&t3);
    
    sleep(4);   //等待调度器结束，不然会崩溃
    return 0;
}

[C++]C++多线程基础

Mon, 03 Apr 2017 13:58:53 +0800

各种锁的基本概念以及在C++里的使用，还有C的一个生产消费模型。

操作系统的知识

概念

临界区：访问和操作共享数据的代码段
避免死锁：嵌套加锁时按顺序加锁, 防止发生饥饿

原子操作：atomic_t

自旋锁

自旋锁：请求该锁的线程在等待时自旋（特别耗费处理器时间），所以只能轻量级加锁（一般锁的时间小于上下文切换的开销）。
注意：对数据而不是对代码加锁。

读写自旋锁：读时(允许读，不允许写)，写时（不允许读，不允许写）。
注意：不能把读锁升级为写锁，不然会死锁。读写操作要清晰地分开。

信号量

信号量：请求锁的进程在等待时加入等待队列并睡眠。一般用于长时间加锁（唤醒、睡眠、加入队列都是很大的开销）。
通过P/V或者down()/up()操作来控制允许同时进行的线程数。信号量减一就等同与获取一个锁，锁为负数时线程就会进入等待队列。
0/1信号量（互斥信号量）：只允许同时一个线程执行。
计数信号量：允许同时多个线程执行。
读写信号量：互斥信号量的一种。

互斥体

互斥体(mutex): 可以睡眠的强制互斥锁。比信号量更加首选。

mutex和自旋锁的区别：

需求	加锁方法
低开销加锁	优先自旋锁
短期加锁	优先自旋锁
长期加锁	优先mutex
中断上下文加锁	只能自旋锁
持有锁时需要睡眠	只能mutex

C++11 的线程库

std::thread

std::thread用于创建一个执行的线程实例，所以它是一切并发编程的基础，使用时需要包含头文件，它提供了很多基本的线程操作，例如get_id()来获取所创建线程的线程 ID，例如使用join()来加入一个线程等。

std::mutex, std::unique_lock, std::lock_guard

使用std::mutex创建互斥体，std::unique_lock上锁。由于C++保证了所有栈对象在声明周期结束时会被销毁，所以这样的代码是异常安全的。无论发生异常还是正常结束，都会自动调用unlock()。

#include <iostream>
#include <thread>
#include <mutex>

std::mutex mtx;

void block_area() {
    std::unique_lock<std::mutex> lock(mtx);
    //...临界区
}
int main() {
    std::thread thd1(block_area);
    thd1.join();

    return 0;
}

C加锁示例：生产/消费模型

需求是两个进程维护一片共享内存，里面存十个产品（抽象为长度为10的一个循环队列）。生产者负责生产产品，注意队列满了就不能生产了，这时候进程陷入沉睡；消费者负责消费产品，消费完了队列的产品之后也要陷入沉睡。
Linux端代码如下：

[C++]C++ 11/14 笔记（三）

Mon, 30 Jan 2017 23:25:54 +0800

本部分介绍了c++11的容器、智能指针和正则。

std::array

代替原来的c数组，提供了size()，empty()，大小比较以及迭代器。
注意：

声明的第二个模板参数必须是编译期常量
不能隐式转换为指针，调用data()返回c数组地址

std::array<int,4> arr = {1,2,3,4};

// C 风格接口传参
// foo(arr, arr.size());           // 非法, 无法隐式转换
foo(&arr[0], arr.size());
foo(arr.data(), arr.size());

// 使用 `std::sort`
std::sort(arr.begin(), arr.end());

std::forward_list

单向实现的列表，提供了O(1)的插入，并且比双向更省空间。

无序容器

传统 C++ 中的有序容器 std::map/std::set，这些元素内部通过红黑树进行实现，插入和搜索的平均复杂度均为 O(log(size))。在插入元素时候，会根据 < 操作符比较元素大小并判断元素是否相同，并选择合适的位置插入到容器中。当对这个容器中的元素进行遍历时，输出结果会按照 < 操作符的顺序来逐个遍历。

而无序容器中的元素是不进行排序的，内部通过 Hash 表实现，插入和搜索元素的平均复杂度为 O(constant)，在不关心容器内部元素顺序时，能够获得显著的性能提升。

C++11 引入了两组无序容器：std::unordered_map, std::unordered_multimap 和std::unordered_set, std::unordered_multiset。

它们的用法和原有的std::map/std::multimap/std::set/set::multiset基本类似。

std::tuple

提供了N元组的数据结构。
该数据结构在cpp14中还不够完善。

智能指针

在传统 C++ 里我们使用 new 和 delete 去『记得』对资源进行释放。而 C++11引入了智能指针的概念，使用了引用计数的想法，让程序员不再需要关心手动释放内存。这些智能指针包括 std::shared_ptr/std::unique_ptr/std::weak_ptr，使用它们需要包含头文件 <memory>。

[C++]C++ 11/14 笔记（二）

Sun, 29 Jan 2017 23:25:54 +0800

本部分介绍了c++11的Lambda、函数容器和右值引用。

Lambda

结构：

1
2
3

[捕获列表](参数列表) -> 返回类型{
    // 函数体
}

比如定义一个加法的lambda：

auto add = [](auto x, auto y) {
    return x+y;
};
add(1.0, 2.3);

捕获列表用于传递外部的变量，分为以下几种：

[] 空捕获列表
[name1, name2, …] 捕获一系列变量
[=] 值捕获, 捕获的变量为lambda表达式被创建时的值
[&] 引用捕获, 值会发生变化

函数容器

std::function

函数的类型安全的容器。比如下面的std::function<int(int)> func2定义了一个返回值int,参数为(int)的一个函数对象。其中捕获列表是传引用的，所以返回的是调用func2时的1+value+important的值。

int important = 10;
std::function<int(int)> func2 = [&](int value) -> int {
    return 1+value+important;
};

std::bind/std::placeholder

有点像python的偏函数，它给函数一些预定的参数，以便于用更少的参数调用：

int foo(int a, int b, int c) {
    return a + b + c;
}
int main() {
    // 将参数1,2绑定到函数 foo 上，但是使用 std::placeholders::_1 来对第一个参数进行占位
    auto bindFoo = std::bind(foo, std::placeholders::_1, 1,2);
    // 这时调用 bindFoo 时，只需要提供第一个参数即可
    bindFoo(1);
}

右值引用

右值和左值

以赋值符号为界，左面的表示一个对象，右面的表示一个对象的值

[C++]C++ 11/14 笔记（一）

Fri, 20 Jan 2017 10:15:13 +0800

本部分介绍了c++11的崭新的类型推导、循环、模板和构造方法。

弃用的特性

1.　不允许以下赋值出现，应使用const char *后者auto。

`1`	`char *str = "hello world!";`

2.　C语言风格的类型转换被弃用，应该使用 static_cast、reinterpret_cast、const_cast 来进行类型转换
3.　register， auto_ptr关键字被弃用。

语言增强

新的关键字

使用nullptr而不是NULL。新的nullptr为nullptr_t类型，可以隐式转换为任何类型，同时避免了NULL == 0这种类型冲突。
constexpr函数：告诉编译器返回的值为常量表达式

类型推导

auto类型

auto型可以作为变量的声明类型，函数的返回类型
auto型作为函数参数在c++17中才可使用，但要注意重载的问题
auto不能用于数组的类型推导
迭代器的样例：

`1`	`for(auto itr = vec.cbegin(); itr != vec.cend(); ++itr);`

decltype函数

返回值为一个类型。比如我们可以把z声明为推测的类型

`1`	`decltype(x+y) z = x + y;`

for(item:array)循环

像Python一样地迭代：

std::vector<int> arr(5, 100);
// & 启用了引用, 如果没有则对 arr 中的元素只能读取不能修改
for(auto &i : arr) {
    std::cout << i << std::endl;
}

初始化列表

除了

拷贝构造
() 构造函数初始化
加入了使用列表来初始化的特性：

class Magic {
public:
    Magic(std::initializer_list<int> list) {}
};

Magic magic = {1,2,3,4,5};
std::vector<int> v = {1, 2, 3, 4};

模板的强化

关键字

外部模板extern template推迟模板的实例化
>>不再只是右移运算符，可以视作括号嵌套：

`1`	`std::vector<std::vector<int>> wow;`

using提供的类型别名

using提供了以下的别名：

[Python]Python版socket十行模板

Fri, 20 Jan 2017 10:15:13 +0800

以下的socket
都是python实现的服务端接受客户端键盘输入的信息，改为大写返回客户端的模板
都是同步、阻塞的
都会在数据长度大于1024时产生错误，请自己写协议
端口都是8080，请确保未被占用

tcp_server.py

6行控制监听的最大tcp链接数。
tcp是有链接的。9行建立链接，10行接受数据，11行发送数据，12行关闭链接。

    import socket

    server = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
    server.setsockopt(socket.SOL_SOCKET, socket.SO_REUSEADDR, 1)
    server.bind(("0.0.0.0", 8080))
    server.listen(1)

    while True:
        conn, addr = server.accept()
        data_from_client = conn.recv(1024).decode('utf8')
        conn.sendall(data_from_client.upper().encode('utf8'))
        conn.close()

tcp_client.py

5行链接，6行发送数据，7行接收数据，9行关闭链接。

    import socket

    while True:
        client = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
        client.connect(("0.0.0.0", 8080))
        client.sendall(input().encode('utf8'))
        data_from_server = client.recv(1024).decode('utf8')
        print('GET ' + data_from_server)
        client.close()

udp_server.py

8行收，10行发。
需要注意的是，发送时的地址写收数据时得到的地址。

    import socket

    SERVER_ADDR =  ("0.0.0.0", 8080)
    server = socket.socket(socket.AF_INET, socket.SOCK_DGRAM)
    server.bind(SERVER_ADDR)

    while True:
        data, client_addr = server.recvfrom(1024)
        sending = data.decode('utf8').upper()
        server.sendto(sending.encode('utf8'), client_addr)

udp_client.py

7行发，8行收。

[后台]用select写一个HTTP代理

Thu, 12 Jan 2017 11:23:44 +0800

函数说明

18.3. select — Waiting for I/O completion — Python 3.6.0 documentation

select.select(rlist, wlist, xlist[, timeout])

Unix select()系统调用的一个简单接口。前三个参数是文件描述符（int类型）的序列。

1
2
3

    rlist：等待准备读取
    wlist：等待准备写作
    xlist：等待一个异常

参数说明

在Unix上序列可以为空，但在Windows则不可以。可选的timeout参数将超时指定为浮点数（以秒为单位）。当省略timeout参数时，该函数阻塞，直到至少一个文件描述符已准备好。该值为0时表示轮询从不停止。

返回值

准备好的对象列表的三元组（前三个参数的子集）。当超时但没有文件描述符就绪时，返回三个空列表。

序列对象

序列中可用的对象类型包括Python文件对象（例如sys.stdin或由open()或os.popen()返回的对象），由socket.socket()返回的socket对象。你也可以自己定义一个类，只要它有一个合适的fileno()方法（返回一个真正的文件描述符，而不只是一个随机整数）。

注意：
Windows上的文件对象不可接受，但socket可以。在Windows上，底层的select()函数由WinSock库提供，不处理不是源自WinSock的文件描述符。

实现HTTP代理

代理由两个部分组成：客户端-代理的socket，和代理-Web服务器的socket。
因为代理像两边接受数据时调用recv方法都会发生阻塞，
所以，在这个样例中，事件循环由两个事件组成：客户端-代理链接可以继续接受数据了，和代理-Web服务器链接可以接受数据了（指都是代理端）。

    import select
    import socket
    import _thread
    
    BUFF_SIZE = 1024
    
    
    # get http head data from a connection
    def get_post(conn):
        res = b''
        while True:
            res += conn.recv(BUFF_SIZE)
            if b'\r\n\r\n' in res:
                break
        return res
    
    
    class Proxy:
        # init. in_conn: browser-proxy connection, out_conn: proxy-web_server connection
        def __init__(self, conn, timeout):
            self.in_conn = conn
            self.out_conn = None
            self.timeout = timeout
    
            self.run()
    
        # main function
        def run(self):
            action, url, http_ver, req, headers = self.__parse_header()
            # https
            if action in ["CONNECT"]:
                self.in_conn.send(b'HTTP/1.1 200 Connection established\r\nProxy-agent: God Proxy\r\n\r\n')
                self.__connect(headers)
            # http
            else:
                self.__connect(headers)
                self.out_conn.send(req)
            self.event_loop()
            # close connection
            self.in_conn.close()
            self.out_conn.close()
    
        # event loop
        def event_loop(self):
            count = 0
            inputs = [self.in_conn, self.out_conn]
            outputs = []
            while True:
                read_list, _, exception_list = select.select(inputs, outputs, inputs, self.timeout)
                count += 1
                for future_object in read_list:
                    # once could read, receive data
                    data = future_object.recv(1024)
                    if data:
                        # read in_conn's data, send to out_conn or out_conn to in_conn
                        if future_object is self.in_conn:
                            # print(count, 'out conn', data[:10], '...', data[-10:])
                            self.out_conn.sendall(data)
                        else:
                            # print(count, 'in conn', data[:10], '...', data[-10:])
                            self.in_conn.sendall(data)
                if exception_list:
                    break
                # time out
                if count > 100:
                    break
    
        # parse host from url and setting up out_conn socket
        def __connect(self, headers):
            host_list = headers['Host'].split(':')
            host = host_list[0]
            if host_list[-1].isdigit():
                port = int(host_list[1])
            else:
                port = 80
            socket_info = socket.getaddrinfo(host, port)[0]
            self.out_conn = socket.socket(socket_info[0])
            self.out_conn.connect(socket_info[4])
            print('WEB SITE: ', host, socket_info[4])
    
        # get headers from in_conn and parse
        def __parse_header(self):
            req = get_post(self.in_conn)
            str_req = req[:req.find(b'\r\n\r\n')].decode('utf8')
            headers = {}
            lines = str_req.split('\r\n')
            for line in lines[1:]:
                line = line.split(': ')
                headers[line[0]] = line[1]
            action, url, http_ver = lines[0].split()
            return action, url, http_ver, req, headers
    
    
    def main():
        server = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
        server.setsockopt(socket.SOL_SOCKET, socket.SO_REUSEADDR, 1)
    
        server_address = ('0.0.0.0', 8899)
        server.bind(server_address)
    
        server.listen(0)
        # 1 connection to 1 thread
        while True:
            conn, addr = server.accept()
            _thread.start_new_thread(Proxy, (conn, 3))
    
    if __name__ == '__main__':
        main()

[后台]在Python中使用epoll

Sat, 07 Jan 2017 16:07:35 +0800

学期初写代理的时候发现阻塞式socket并不能满足需要，多线程也不是一个很好的解决方案。这篇文章系统地介绍了epoll是什么以及如何使用。

英文好的同学可以直接看
How To Use Linux epoll with Python
本博客的大部分内容都是基于这篇文章的。

什么是epoll

（维基百科）
于Linux 2.5.44首度登场的epoll是Linux内核的可扩展I/O事件通知机制。它设计目的只在替换既有POSIX select(2)与poll(2)系统函数，让需要大量操作文件描述符的程序得以发挥更优异的性能(举例来说：旧有的系统函数所花费的时间复杂度为O(n)，epoll则耗时O(1))。epoll与FreeBSD的kqueue类似，底层都是由可配置的操作系统内核对象建构而成，并以文件描述符(file descriptor)的形式呈现于用户空间。

为什么使用epoll

首先理解同步异步的概念：
怎样理解阻塞非阻塞与同步异步的区别？- 知乎

同步与异步
同步和异步关注的是消息通信机制 (synchronous communication/ asynchronous communication)
所谓同步，就是在发出一个调用时，在没有得到结果之前，该调用就不返回。但是一旦调用返回，就得到返回值了。
换句话说，就是由调用者主动等待这个调用的结果。
而异步则是相反，调用在发出之后，这个调用就直接返回了，所以没有返回结果。换句话说，当一个异步过程调用发出后，调用者不会立刻得到结果。而是在调用发出后，被调用者通过状态、通知来通知调用者，或通过回调函数处理这个调用。
阻塞与非阻塞
阻塞和非阻塞关注的是程序在等待调用结果（消息，返回值）时的状态.
阻塞调用是指调用结果返回之前，当前线程会被挂起。调用线程只有在得到结果之后才会返回。
非阻塞调用指在不能立刻得到结果之前，该调用不会阻塞当前线程。

阻塞式socket：
阻塞式socket使用单线程进行通信。主线程创建一个新的socket线程并侦听该socket，它一次性接受所有连接，然后让这个线程与客户端进行交互。因为创建的线程都只和一个客户端通信，所以阻塞并不妨碍其他线程工作
虽然多线程的阻塞式通信编码简单，但是在多线程共享资源时非常困难，在多核下表现也很差

非阻塞的socket：
于是很多替代并发阻塞式socket的方法出现了，例如基于事件系统设计的epoll，它并不会阻塞线程，它可以使用一个线程实现，大大节约了资源.

可见epoll是一个同步的非阻塞解决方案。

一般步骤

使用python中的epoll一般有如下步骤：

创建epoll对象
告诉epoll对象监视特定socket上的特定事件
询问epoll对象哪些socket可能有自上次查询以来的指定事件
对这些socket执行一些操作
告诉epoll对象修改要监视的socket和事件的列表
重复步骤3到5直到完成
销毁epoll对象

代码实例

epoll设有水平触发和边沿触发两种模式。

在边沿触发操作模式下，socket发生读或写事件后，调用epoll.poll()只会给socket返回一次事件。调用程序必须处理与该事件相关的所有数据。当事件的数据为空时，对socket的继续操作将导致异常。
在水平触发操作模式中，对epoll.poll()的重复调用将导致注册事件的重复通知，直到与该事件相关联的所有数据都已被处理。

边沿触发往往被用于程序员不想使用系统的事件管理机制时。
下面的示例是一个水平触发的典型样例。
需要注意的是，event & select.EPOLLIN 表示事件的掩码，当掩码值为0时对应的事件发生。

    import socket, select

    EOL1 = b'\n\n'
    EOL2 = b'\n\r\n'
    response  = b'HTTP/1.0 200 OK\r\nDate: Mon, 1 Jan 1996 01:01:01 GMT\r\n'
    response += b'Content-Type: text/plain\r\nContent-Length: 13\r\n\r\n'
    response += b'Hello, world!'

    serversocket = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
    serversocket.setsockopt(socket.SOL_SOCKET, socket.SO_REUSEADDR, 1)
    serversocket.bind(('0.0.0.0', 8080))
    serversocket.listen(1)

    # 由于socket在默认情况下阻塞，因此使用非阻塞（异步）模式
    serversocket.setblocking(0) 

    # 创建一个epoll对象
    # 注册socket的读事件为偏好(读事件会在socket建立链接时发生)
    epoll = select.epoll()
    epoll.register(serversocket.fileno(), select.EPOLLIN)

    try:
       # connections字典将文件描述符（int类型）映射到它们对应的网络连接对象。
       connections = {}; requests = {}; responses = {}
       while True:
          # 查询epoll对象并获取等待时间内发生的事件列表。参数“1”表示可以等待一秒钟。
          events = epoll.poll(1)    
          for fileno, event in events:  # events 是(文件描述符，事件代码）二元组的数组
             # 建立一个新的链接
             if fileno == serversocket.fileno():    
                connection, address = serversocket.accept()
                connection.setblocking(0)   # 设置为非阻塞模式
                epoll.register(connection.fileno(), select.EPOLLIN) # 注册读事件（EPOLLIN）
                connections[connection.fileno()] = connection
                requests[connection.fileno()] = b''
                responses[connection.fileno()] = response
             # 当服务端该收数据（客户端已经发出）
             elif event & select.EPOLLIN:   
                requests[fileno] += connections[fileno].recv(1024)
                if EOL1 in requests[fileno] or EOL2 in requests[fileno]:
                   # 一旦接收到完整的请求，则取消注册读事件并注册写事件（EPOLLOUT）
                   # 将响应数据发送回客户端时可能会发生写事件
                   epoll.modify(fileno, select.EPOLLOUT)    
                   # 打印完整的请求(尽管与客户端的通信是交错的，但是该数据可以被组合并作为整个消息处理)
                   print('-'*40 + '\n' + requests[fileno].decode()[:-2]) 
             # 当服务端该发数据（客户端可以收）
             elif event & select.EPOLLOUT:  
                byteswritten = connections[fileno].send(responses[fileno]) # 一次一次发送响应数据
                responses[fileno] = responses[fileno][byteswritten:]
                if len(responses[fileno]) == 0: # 直到完整响应已传送到OS准备进行传输
                   epoll.modify(fileno, 0)  # 发送完整的响应后，禁止读写事件
                   connections[fileno].shutdown(socket.SHUT_RDWR)   # 关闭连接
             # HUP事件表示客户端socket已经断开连接(不需要注册, 默认发送)
             elif event & select.EPOLLHUP:  
                epoll.unregister(fileno)
                connections[fileno].close()
                del connections[fileno]
    finally:
       # Python将在程序结束时自动关闭socket连接,不需显式关闭
       epoll.unregister(serversocket.fileno())
       epoll.close()
       serversocket.close()

TCP选项

TCP_CORK选项可用于“填满”消息，直到它们准备好发送。这个选项适用于于使用HTTP 1.1流水线的HTTP服务器。

[编译原理]Python实现的语义分析器

Tue, 27 Dec 2016 20:18:40 +0800

语义分析是编译系统的第三部分,负责赋值检查,表达式检查以及代码生成.

基本思想

代码沿用了上一部分的文法表, 利用递归下降算法对每一个非终结符写一个函数. 但是文法多达70多条, 工作量太大, 就只实现了赋值语句, 表达式, 条件语句这几个代表性的文法规则. 其他实现起来也类似, 多写几个函数即可.

函数介绍

需要注意的几个细节:

compare_var_type用于比较类型, 比较失败则raise一个CompileError
在生成代码过程中, 有的传入了其他的变量, 是为了回填
把if回填做成了label的方式, 可以在后阶段再处理
未初始化的变量调用也留给了后阶段处理.

函数表:

成员函数	对应非终结符	备注
init()		初始化
get_register()		分配寄存器
get_label_no()		分配记号
compare_var_type(var_type_1,var_type_2)		比较类型,raise错误
build_table(x)		建立符号表
check_factor(factor)	<因式>	用于检查
check_factors(factor)	<因式递归>	用于检查
check_factor_c(fc)	<因子>	用于检查
check_term(term)	<项>	用于检查
check_exp(x)	<表达式>	用于检查
check_stm(x)	<赋值函数>	用于检查
generate_factor(factor)	<因式>	用于生成
generate_factors(factors,factor)	<因式递归>	用于生成
generate_factor_c(fc)	<因子>	用于生成
generate_term(term,factor)	<项>	用于生成
generate_exp(x)	<表达式>	用于生成
generate_stm(x)	<赋值函数>	用于生成
generate_func_blocks(x)	<函数块闭包>	用于生成
generate_func_block(x)	<函数块>	用于生成
generate_else_block(x)	<否则语句>	用于生成
generate_logical(x)	<逻辑表达式>	用于生成
generate_if(x)	<条件语句>	用于生成
generate_code(tree)	<函数定义>	用于生成
dfs(tree,func)		搜索函数
run(code)		获取生成结果

文法表

<函数定义>-><修饰词闭包><类型><变量>[(]<参数声明>[)][{]<函数块>[}]
<修饰词闭包>-><修饰词><修饰词闭包>
<修饰词闭包>->[@]
<修饰词>->[public]
<修饰词>->[private]
<修饰词>->[protected]
<类型>->[int]<取地址>
<类型>->[char]<取地址>
<类型>->[boolean]<取地址>
<类型>->[void]<取地址>
<取地址>-><星号><取地址>
<取地址>->[@]
<星号>->[*]
<变量>-><标志符><数组下标>
<标志符>->[id]
<数组下标>->[[]<因式>[]]
<数组下标>->[@]
<因式>->[(]<表达式>[)]
<因式>-><变量>
<因式>-><数字>
<数字>->[digit]
<表达式>-><因子><项>
<因子>-><因式><因式递归>
<因式递归>->[*]<因式><因式递归>
<因式递归>->[/]<因式><因式递归>
<因式递归>->[@]
<项>->[+]<因子><项>
<项>->[-]<因子><项>
<项>->[@]
<参数声明>-><声明><声明闭包>
<参数声明>->[@]
<声明>-><修饰词闭包><类型><变量><赋初值>
<赋初值>->[=]<右值>
<赋初值>->[@]
<右值>-><表达式>
<右值>->[{]<多个数据>[}]
<多个数据>-><数字><数字闭包>
<数字闭包>->[,]<数字><数字闭包>
<数字闭包>->[@]
<声明闭包>->[,]<声明><声明闭包>
<声明闭包>->[@]
<函数块>-><声明语句闭包><函数块闭包>
<声明语句闭包>-><声明语句><声明语句闭包>
<声明语句闭包>->[@]
<声明语句>-><声明>[;]
<函数块闭包>-><赋值函数><函数块闭包>
<函数块闭包>-><for循环><函数块闭包>
<函数块闭包>-><条件语句><函数块闭包>
<函数块闭包>-><函数返回><函数块闭包>
<函数块闭包>->[@]
<赋值函数>-><变量><赋值或函数调用>
<赋值或函数调用>->[=]<右值>[;]
<赋值或函数调用>->[(]<参数列表>[)][;]
<参数列表>-><参数><参数闭包>
<参数闭包>->[,]<参数><参数闭包>
<参数闭包>->[@]
<参数>-><标志符>
<参数>-><数字>
<参数>-><字符串>
<字符串>->[string]
<for循环>->[for][(]<赋值函数><逻辑表达式>[;]<后缀表达式>[)][{]<函数块>[}]
<逻辑表达式>-><表达式><逻辑运算符><表达式>
<逻辑运算符>->[<]
<逻辑运算符>->[>]
<逻辑运算符>->[==]
<逻辑运算符>->[!=]
<后缀表达式>-><变量><后缀运算符>
<后缀运算符>->[++]
<后缀运算符>->[--]
<条件语句>->[if][(]<逻辑表达式>[)][{]<函数块>[}]<否则语句>
<否则语句>->[else][{]<函数块>[}]
<否则语句>->[@]
<函数返回>->[return]<因式>[;]

代码实现

知道了思路还是很好读的, 无非是看每个非终结符对应了哪条规则, 再利用分支调用对应的分支.

[编译原理]Python实现的语法分析器

Tue, 27 Dec 2016 01:20:24 +0800

语法分析器是这套编译系统的第二部分,可以直接用上一篇中的词法分析器的结果继续做语法分析.

文法表

= =一直没时间更, 直到考试周格外闲…
借鉴了一个网络上的文法表, 覆盖了一些基础的C文法, 测试后发现该文法是LL(1)文法.
文法如下:

<函数定义>-><修饰词闭包><类型><变量>[(]<参数声明>[)][{]<函数块>[}]
<修饰词闭包>-><修饰词><修饰词闭包>
<修饰词闭包>->[@]
<修饰词>->[public]
<修饰词>->[private]
<修饰词>->[protected]
<类型>->[int]<取地址>
<类型>->[char]<取地址>
<类型>->[boolean]<取地址>
<类型>->[void]<取地址>
<取地址>-><星号><取地址>
<取地址>->[@]
<星号>->[*]
<变量>-><标志符><数组下标>
<标志符>->[id]
<数组下标>->[[]<因式>[]]
<数组下标>->[@]
<因式>->[(]<表达式>[)]
<因式>-><变量>
<因式>-><数字>
<数字>->[digit]
<表达式>-><因子><项>
<因子>-><因式><因式递归>
<因式递归>->[*]<因式><因式递归>
<因式递归>->[/]<因式><因式递归>
<因式递归>->[@]
<项>->[+]<因子><项>
<项>->[-]<因子><项>
<项>->[@]
<参数声明>-><声明><声明闭包>
<参数声明>->[@]
<声明>-><修饰词闭包><类型><变量><赋初值>
<赋初值>->[=]<右值>
<赋初值>->[@]
<右值>-><表达式>
<右值>->[{]<多个数据>[}]
<多个数据>-><数字><数字闭包>
<数字闭包>->[,]<数字><数字闭包>
<数字闭包>->[@]
<声明闭包>->[,]<声明><声明闭包>
<声明闭包>->[@]
<函数块>-><声明语句闭包><函数块闭包>
<声明语句闭包>-><声明语句><声明语句闭包>
<声明语句闭包>->[@]
<声明语句>-><声明>[;]
<函数块闭包>-><赋值函数><函数块闭包>
<函数块闭包>-><for循环><函数块闭包>
<函数块闭包>-><条件语句><函数块闭包>
<函数块闭包>-><函数返回><函数块闭包>
<函数块闭包>->[@]
<赋值函数>-><变量><赋值或函数调用>
<赋值或函数调用>->[=]<右值>[;]
<赋值或函数调用>->[(]<参数列表>[)][;]
<参数列表>-><参数><参数闭包>
<参数闭包>->[,]<参数><参数闭包>
<参数闭包>->[@]
<参数>-><标志符>
<参数>-><数字>
<参数>-><字符串>
<字符串>->[string]
<for循环>->[for][(]<赋值函数><逻辑表达式>[;]<后缀表达式>[)][{]<函数块>[}]
<逻辑表达式>-><表达式><逻辑运算符><表达式>
<逻辑运算符>->[<]
<逻辑运算符>->[>]
<逻辑运算符>->[==]
<逻辑运算符>->[!=]
<后缀表达式>-><变量><后缀运算符>
<后缀运算符>->[++]
<后缀运算符>->[--]
<条件语句>->[if][(]<逻辑表达式>[)][{]<函数块>[}]<否则语句>
<否则语句>->[else][{]<函数块>[}]
<否则语句>->[@]
<函数返回>->[return]<因式>[;]

Grammar.py

典型的LL(1)的分析过程, 构造NULLABLE集, FIRST集, FOLLOW集, 计算SELECT集,最后画出预测分析表, 生成AST.
其中simplify_tree是用来递归简化树上的节点的.
代码很好读,都是华老师课件上的步骤.

[普林斯顿算法公开课]双向队列和随机队列

Tue, 15 Nov 2016 13:38:03 +0800

思路

这次的内容是写一个双向队列和随机队列, 双向队列自不必说, 用链表即可, 注意一下表头表尾的操作以及只有一个元素时的删除操作.
随机队列实现随机的时候需要查询具体下标的元素, 是一个O(1)操作, 所以使用自增长内存池实现.

刷到满分的过程中逐步解决的一些问题:
1. 对题目要求的每一个Exception都要抛出.否则会有以下问题:

case test 失败

测试中断:
Warning: the grading output was truncated due to excessive length.

2. 删除的节点和数组需要置null释放, 比如Deque出队的节点, RandomizedQueue出队的元素, 否则会报

- loitering observed during 71 of 100 deletions

3. 注意RandomizedQueue的capacity大小调节的时机, 在size到达capacity一半时扩大, 在size到达capacity四分之一时减小.否则会有以下问题:

不缩小capacity: 会导致内存测试失败

调节时机不对: 会导致一半的时间测试失败, 或者测试中断:
Warning: the grading output was truncated due to excessive length.
size 不为正数的边界情况: 数组越界

= =这个capacity大小要求过于严格了, 导致我用自己习惯的增长方式没有AC…

Deque.java

/**
 * Created by chestnutheng on 16-11-14.
 */

import java.util.Iterator;

public class Deque<Item> implements Iterable<Item>{
    private Node first = null;
    private Node last = null;
    private int size = 0;
    private class Node
    {
        Item item;
        Node prev;
        Node next;
    }
    // construct an empty deque
    public Deque() {}
    // is the deque empty?
    public boolean isEmpty() {
        return size == 0;
    }
    // return the number of items on the deque
    public int size()   {
        return size;
    }
    // add the item to the front
    public void addFirst(Item item){
        if(item == null) {
            throw new java.lang.NullPointerException();
        }
        Node tv = new Node();
        tv.item = item;
        tv.next = first;
        if(first != null){
            first.prev = tv;
        }
        first = tv;
        size++;
        if(last == null){
            last = tv;
        }
    }
    // add the item to the end
    public void addLast(Item item) {
        if(item == null) {
            throw new java.lang.NullPointerException();
        }
        Node tv = new Node();
        tv.item = item;
        tv.next = null;
        tv.prev = last;
        if(last != null){
            last.next = tv;
        }
        last = tv;
        size++;
        if(first == null){
            first = tv;
        }
    }
    // remove and return the item from the front
    public Item removeFirst()   {
        if(isEmpty()){
            throw new java.util.NoSuchElementException();
        }
        Item item = first.item;
        first = first.next;
        if(first != null) {
            first.prev = null;
        }
        size--;
        if(size == 0){
            first = last = null;
        }
        return item;
    }
    // remove and return the item from the end
    public Item removeLast()   {
        if(isEmpty()){
            throw new java.util.NoSuchElementException();
        }
        Item item = last.item;
        last = last.prev;
        if(last != null) {
            last.next = null;
        }
        size--;
        if(size == 0){
            first = last = null;
        }
        return item;
    }
    // return an iterator over items in order from front to end
    public Iterator<Item> iterator(){
         class DequeIterator implements Iterator<Item>{
            private Node tv = first;
            public boolean hasNext() {
                return tv != null;
            }
            public void remove(){throw new java.lang.UnsupportedOperationException();}
            public Item next()
            {
                if(!hasNext()){
                    throw new java.util.NoSuchElementException();
                }
                Item item = tv.item;
                tv = tv.next;
                return item;
            }

        }
        return new DequeIterator();
    }
    // unit testing
    public static void main(String[] args) {
        Deque<String>deque = new Deque<>();
        deque.addLast("0");
        deque.removeLast();
        deque.size();
        deque.size();
        deque.isEmpty();
        deque.addFirst("5");
        deque.removeFirst();
        System.out.println(deque.size());
        deque.addLast("7");
        System.out.println(deque.removeFirst());
    }
}

RandomizedQueue.java

/**
 * Created by chestnutheng on 16-11-14.
 */
import java.util.Iterator;
import edu.princeton.cs.algs4.StdRandom;

public class RandomizedQueue<Item> implements Iterable<Item>{
    private int size = 0;
    private Item[] pool;
    // construct an empty randomized queue
    public RandomizedQueue(){
        pool = (Item[])new Object[5];
    }
    // check capacity size and resize
    private void check_capacity(){
        if(size == pool.length - 1){
            Item[] np = (Item[])new Object[size*2];
            for (int i = 0; i < size; ++i){
                np[i] = pool[i];
            }
            pool = np;
        }else if(size == pool.length/4 + 1 && size > 0){
            Item[] np = (Item[])new Object[size*2];
            for (int i = 0; i < size; ++i){
                np[i] = pool[i];
            }
            pool = np;
        }
    }
    // is the queue empty?
    public boolean isEmpty(){
        return size == 0;
    }
    // return the number of items on the queue
    public int size(){
        return size;
    }
    // add the item
    public void enqueue(Item item){
        if(item == null) {
            throw new java.lang.NullPointerException();
        }
        check_capacity();
        pool[size] = item;
        size++;
    }
    // remove and return a random item
    public Item dequeue(){
        if(isEmpty()){
            throw new java.util.NoSuchElementException();
        }
        int target = (int) (Math.random()*size);
        Item item = pool[target];
        pool[target] = pool[size - 1];
        pool[size - 1] = null;
        size--;
        check_capacity();
        return item;
    }
    // return (but do not remove) a random item
    public Item sample(){
        if(isEmpty()){
            throw new java.util.NoSuchElementException();
        }
        int target = (int) (Math.random()*size);
        return pool[target];
    }
    // return an independent iterator over items in random order
    public Iterator<Item> iterator(){
        class VectorIterator implements Iterator<Item>{
            private int helicopter = 0;
            private Item[] random_array;
            public VectorIterator(){
                random_array = (Item[])new Object[size];
                for (int i = 0; i < size; ++i){
                    random_array[i] = pool[i];
                }
                StdRandom.shuffle(random_array);
            }
            public boolean hasNext() {
                return helicopter < size;
            }
            public void remove(){throw new java.lang.UnsupportedOperationException();}
            public Item next() {
                if(!hasNext()){
                    throw new java.util.NoSuchElementException();
                }
                return random_array[helicopter++];
            }
        }
        return new VectorIterator();
    }
    //test client
    public static void main(String[] args){
        RandomizedQueue<Integer> r = new RandomizedQueue<>();
        r.enqueue(1);
        r.enqueue(2);
        r.dequeue();
        r.dequeue();
        for (int s:r
             ) {
            System.out.println(s);
        }
    }
}

[编译原理]Python实现的词法分析器

Tue, 15 Nov 2016 11:02:42 +0800

最近在上华保健老师的课, 在学习的过程中做了一套编译系统, 外加顺便应付学校的作业. 这个词法分析器是这套编译系统的第一部分.

其中RE到DFA, DFA到NFA的部分都是手工完成, 自己规定token格式(C语言格式), 得到一个NFA.
课程内容详见:
编译原理MOOC

算法都是课程中的算法, 不再详述.伪代码可以在华老师的课件中找到.

state_machine.json

第一部分是手写的DFA, 用类似树状数组的方式存储.

几个Key的含义如下:

SS: 起始状态
FS: 接受状态
I: 接受字符
T: 转换表   //如"8": {"3": 10, "5": 9}表示状态8输入I[3]可以转换到状态10, 状态8输入I[3]可以转换到状态9
S: 状态表    //下标对应的状态的含义

json文件:

state_machine.json

Driver.py

驱动文件,分析结果为三元组**(标识符, 内容, 行数)**的序列.

#!/usr/bin/env python3

import json


class Driver:
    STATE_MACHINE = None
    content_symbols = ['id', 'digit']
    line_no = 0
    NOW_POINT = -1
    PREV_POINT = -1
    STRING = ''
    uncommit = ''
    token_list = []

    def __init__(self, file_name):
        with open(file_name, 'r') as f:
            self.STATE_MACHINE = json.load(f)

    # reset
    def reset(self):
        self.STRING = ''
        self.uncommit = ''
        self.token_list.clear()
        self.NOW_POINT = -1    #当前分析的字符下标
        self.PREV_POINT = -1   #用于获得标识符对应的内容
        self.line_no = 0

    # next char of string
    def next_ch(self):
        self.NOW_POINT += 1
        if self.NOW_POINT < len(self.STRING):
            return self.STRING[self.NOW_POINT]
        else:
            return None

    # rollback
    def rollback(self):
        self.NOW_POINT -= 1

    # drive code
    def next_token(self):
        state = "0"
        stack = []
        # get a token
        while True:
            c = self.next_ch()
            if c is None:
                return False
            # accept state
            if int(state) in self.STATE_MACHINE["FS"]:
                stack.clear()
            stack.append(state)
            # state change or state error
            num = None
            for i in range(0, len(self.STATE_MACHINE["I"])):
                if c in self.STATE_MACHINE["I"][i]:
                    num = i
            if num is None:
                return False
            # not accepted
            try:
                state = str(self.STATE_MACHINE["T"][state][str(num)])
            except KeyError:
                break
        state = stack.pop(-1)
        self.rollback()
        # get idn and token
        idn = self.STATE_MACHINE['S'][int(state)]
        name = self.STRING[self.PREV_POINT + 1:self.NOW_POINT + 1]
        if idn != 'SPACE':
            self.token_list.append({'symbol': idn, 'raw_data': name, 'line_no': self.line_no})

        self.PREV_POINT = self.NOW_POINT
        return True

    # print token to uncommit
    def print_token(self):
        for v in self.token_list:
            self.uncommit += v['raw_data'] + '\t< ' + v['symbol']
            if v['symbol'] in self.content_symbols:
                self.uncommit += ' , ' + v['raw_data'] + '>' + '\n'
            else:
                self.uncommit += ' , - >' + '\n'

    # run a string
    def run(self, string):
        self.reset()
        STRING_ARRAY = string.replace('\t', '').split('\n')
        for v in STRING_ARRAY:
            self.NOW_POINT = -1
            self.PREV_POINT = -1
            self.line_no += 1
            self.STRING = v + ';'
            while True:
                if not self.next_token():
                    break
        self.print_token()


if __name__ == '__main__':
    d = Driver('state_machine.json')
    d.run('while(num!=100)\n{\nnum++;\n}\n')    #简短的示例
    print(d.uncommit)
    print(d.token_list)
    d.run('n++')
    print(d.uncommit)
    print(d.token_list)

[普林斯顿算法公开课]并查集解决渗透问题

Tue, 08 Nov 2016 13:39:00 +0800

Percolation.java

题目见渗透问题

运用题目给出的API来解决问题.
第一个文件是Percolation.java, 用来编写解决单个渗透问题相关代码.
API:

public class Percolation {
   public Percolation(int n)                // create n-by-n grid, with all sites blocked
   public void open(int row, int col)       // open site (row, col) if it is not open already
   public boolean isOpen(int row, int col)  // is site (row, col) open?
   public boolean isFull(int row, int col)  // is site (row, col) full?
   public boolean percolates()              // does the system percolate?

   public static void main(String[] args)   // test client (optional)
}

大体思想是, 建立一个查是否渗透的并查集, 只要最上面一排和最下面一排属于一个集合就认为是渗透的. 但是判断每两个节点是否联通需要额外的$n^2$的时间, 显然不合适.
我们引入两个假节点分别为top节点和down节点, 再把top节点与最上一排的节点连接, down节点与最下一排的节点连接, 这样渗透问题就等价转换为上下两个节点是否联通.
之后,每次打开一个节点时,只需搜索它的上下左右是否打开,如果打开就把该节点加入打开的节点的集合即可.
需要注意的两点:

[Python]Python性能分析工具

Tue, 09 Aug 2016 13:04:30 +0800

时间分析

time 命令

用*nix自带的系统命令

$ time python3 reg.py 

real	0m1.617s
user	0m1.504s
sys	0m0.112s

sys 系统调用时间
user 用户空间花费时间
real 实际时间
如果user + sys < real 说明时间被花费在IO上。

profile和cProfile

python自带了两个函数时间分析工具，cProfile和profile。cProfile是纯C写的，所以用起来快了很多。
查看帮助:

$ python3 -m cProfile -h
Usage: cProfile.py [-o output_file_path] [-s sort] scriptfile [arg] ...

Options:
  -h, --help            show this help message and exit
  -o OUTFILE, --outfile=OUTFILE
                        Save stats to <outfile>
  -s SORT, --sort=SORT  Sort order when printing to stdout, based on
                        pstats.Stats class

-o 输出的文件只能给pstats.Stats类使用。
-s 是对结果按照关键字排序，关键字有
calls, cumulative, file, line, module, name, nfl, pcalls, stdname, time

[机器学习]感知机

Sat, 06 Feb 2016 00:19:00 +0800

机器学习基石笔记感知机

损失函数

给定一个数据集 $T ={(x_1,y_1),(x_2,y_2),\cdots,(x_N,y_N)}$ , 其中 $x = R^n , , y={+1,-1}$

若存在超平面S $w\cdot x + b = 0$ 能将所有的正负实例点分到两侧，则称数据集是线性可分的，否则称线性不可分。
任意一点$x_0$到超平面的距离为
$$\frac{1}{||w||}|w\cdot x_0 + b|$$
对于误分类数据$(x_i,y_i)$来说，
$-y_i(w\cdot x_i + b) > 0$

有误分类点到超平面距离
$$-\frac{1}{||w||}y_i|w\cdot x_0 + b|$$

则所有误分类点到超平面距离为
$$-\frac{1}{||w||}\sum_{x_i \in m }y_i|w\cdot x_0 + b|$$

所以感知机$sign(w\cdot x + b)$学习损失函数为
$$L(w,b) = -\sum_{x_i \in m }y_i|w\cdot x_0 + b|$$

学习算法

选取初值$w_0,b_0$
在训练集中选取数据$(x_i,y_i)$
如果$y_i(w\cdot xi+ b) \leq 0$（分类错误）
$$w \leftarrow w + x_iy_i$$

[算法]最大值栈和最大值队列

Mon, 26 Oct 2015 19:26:00 +0800

最大值栈和最大值队列(Tsinghua OJ,PA2)

最大值栈

要求

以O(1)的时间查询栈中的最大值.

思路

维护一个最大值栈，在原栈中数据发生改变时最大值栈也跟着改变。
每次输入一个数据，若最大值栈为空，则比较最大值栈栈顶和当前元素，如果当前元素较大或相等，就把当前元素推入栈中，反之出栈时，如果出栈元素和当前元素相等，则把最大值栈中元素也推出栈。

实现

	template <typename T>
	class MaxStack
	{
	private:
		Stack <T> max_stack;
		Stack <T> _data;
	public:
		T max(){
			return max_stack.top();
		}
		void push(T ele){
			_data.push(ele);
			if(max_stack.empty() || ele >= max_stack.top()){
				max_stack.push(ele);
			}
		}
		T pop(){
			T tmp = _data.top();
			if(_data.pop() == max_stack.top()){
				max_stack.pop();
			}
			return tmp;
		}
	};

最大值队列

要求

用o(n)时间查询队列的最大值

[算法]逆序对计算的思考

Wed, 07 Oct 2015 20:33:00 +0800

逆序对计算的思考(Tsinghua OJ,PA1)

题目出自清华DSA的Programming Assignment作业灯塔(LightHouse)．

描述

海上有许多灯塔，为过路船只照明。

如图一所示，每个灯塔都配有一盏探照灯，照亮其东北、西南两个对顶的直角区域。探照灯的功率之大，足以覆盖任何距离。灯塔本身是如此之小，可以假定它们不会彼此遮挡。

若灯塔A、B均在对方的照亮范围内，则称它们能够照亮彼此。比如在图二的实例中，蓝、红灯塔可照亮彼此，蓝、绿灯塔则不是，红、绿灯塔也不是。
现在，对于任何一组给定的灯塔，请计算出其中有多少对灯塔能够照亮彼此。

输入

共n+1行。
第1行为1个整数n，表示灯塔的总数。
第2到n+1行每行包含2个整数x, y，分别表示各灯塔的横、纵坐标。

输出

1个整数，表示可照亮彼此的灯塔对的数量。

样例

Input:

Output:

限制

对于90%的测例：1 ≤ n ≤ 3×10^5
对于95%的测例：1 ≤ n ≤ 10^6
全部测例：1 ≤ n ≤ 4×10^6
灯塔的坐标x, y是整数，且不同灯塔的x, y坐标均互异
1 ≤ x, y ≤ 10^8
时间：2 sec
内存：256 MB

提示

注意机器中整型变量的范围，C/C++中的int类型通常被编译成32位整数，其范围为[-231, 231 - 1]，不一定足够容纳本题的输出。

[算法]DP解决钢条切割问题

Mon, 01 Jun 2015 16:05:00 +0800

DP解决钢条切割问题

（原题见算法导论·动态规划）

对长度为n的钢条进行切割，对应的切割长度和价格对应如下：

int cost[] = {0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30};

比如1对应价值1,10对应价值30。即相应的下标和值的对应。现求切割所得最大效益mx。

递归算法

    int cut_rod(int *cost,int n)
    {
        if(n == 0) return 0;
        int limit = MIN(n,10);       //分割第一条的上限
        int mx =  -1;
        for(int i = 1;i <= limit; ++i)
            mx = maxnum(mx,cost[i]+cut_rod(cost,n-i));    //取当前值于递归值的最大值
        return mx;
    }

由于对相同子问题的重复求解，T(n) = 2^n

递归标记数组算法（自顶而下）（DFS）

    int mem_cut_rod(int *cost,int n,int *mem)   //mem数组长度为n,所有元素须在其他函数中初始化为-1
    {
        int mx;
        if (mem[n] >= 0) return mem[n];     //对于求过的问题，直接返回存储的值
        if (n == 0) mx = 0;
        else mx = -1;
        int limit = MIN(n,10);
        for(int i = 1;i <= limit; ++i)
            mx = maxnum(mx,cost[i]+mem_cut_rod(cost,n-i,mem));   //后面的内容和递归型是一样的
        mem[n] = mx;    //储存计算出的新值
        return mx;  
    }

逆拓扑序DP（自底向上）


    int bottom_cut_rod(int *cost,int n)
    {
        int mem[MEM_LEN+1];                              //MEM_LEN = n，设置标记数组
        mem[0] = 0;                                       //i,j将从1开始，这里收益是0
        for(int i = 1; i <= n; ++i)                              //从第一个问题开始求解
        {
            int mx = -1;
            int limit = MIN(i,10);
            for(int j = 1;j <= limit; ++j)
                mx = maxnum(mx,cost[j] + mem[i-j]);     //求解最小的问题
            mem[i] = mx;
        }
        return mem[n];
    }

我们可以看到，2,3 的解法复杂度均为O(n^2)。

Mon, 01 Jan 0001 00:00:00 +0000

Posts on 子恒的博客

[架构]单体和微服务

多大的服务

更微=更好?

微服务教

再次回到起点：monorepo

[后台]设计合理的幂等方案

幂等的作用

幂等键设计

实现

[游记]摄影和眼睛

[架构]常见的架构设计思想

设计原则

过程而非对象

封装：函数和数据的耦合

继承vs组合

[管理]对新人友好的项目管理手册

需求详评

技术评审

开发

[杂谈]我怎么选择笔记软件

用过的软件对比

诉求

工作流

速记

写博客

[互联网]广告业务的前世今生

商业模型

广告业务

广告形态

交易链路

行业角色

变现公式

[后台]服务端高性能架构之道（系统和服务篇）

克服系统瓶颈

零拷贝

使用mmap

使用sendfile/splice

对于我们的启发

无锁

无锁的替代方案

单线程

[Go]Go语言的设计和坑

Why Go

Go的设计哲学

为什么没有继承？

[Redis]Redis 应用篇

分布式锁

简单加锁

处理set之后进程崩溃的死锁问题

处理非原子性问题

处理超时问题

[C++]C++ 11/14 笔记（四）

std::thread

std::mutex和std::lock_guard同步

[后台]负载均衡 （三）限流篇

限流

考虑的问题

限流算法

固定窗口

滑动窗口

[后台]负载均衡（二）能力篇

名字服务

基础设计

服务注册信息

IP和端口

扩展设计

无损注册/下线

健康检查

节点变化通知

[后台]负载均衡 （一）算法篇

nginx用的负载均衡算法

随机访问

加权轮询

ip_hash

[Linux]文件和零拷贝

文件

文件描述符

文件内核API

read buf该设置多大

[后台]负载均衡（三）限流篇

[后台]负载均衡（一）算法篇