深入数据库理论：查询语言“Theory is when you know everything but nothing works. Practice is when everything works but no one knows why. In our lab, theory and practice are combined: nothing works and no one knows why”– 理论就是当你知道一切却没有一样东西好使，实践就是所有东西都好使却没人知道为什么。在我们的实验室中，理论和实践是相结合：没有一样东西好使，也没人知道为什么 ：）很多理论可能仅限于学术研究和考试内容 :| 这么多年的工作也训练出了自己的一套工作方法，理论再好还是得服务于实践，不然也只能束之高阁。但通过对理论的系统梳理，也了解了自己的工作方法在理论中处于怎样的位置，以后实践中遇到问题应该去哪里寻找答案。注：为了熟悉各种名词的英文说法，所以很多概念都用英文表示。1.理论基石：逻辑逻辑是数学的基石，当然也是我们写程序、程序执行的基石。没有逻辑，数据库查询的执行无从谈起。因此，要学习数据库查询的内部是运转的，就要从逻辑开始学起。重点了解量词的使用和从循环角度思考，这对于后面学习查询理论时是很有用处的！1.1 命题逻辑（Propositional Logic）命题（Proposition）就 ...继续阅读 (99)

关于算法，那些你不知道的事1.算法，不止于刷题提到算法，不管是科班出身还是半路出家的程序员可能都会说上几句，算法谁没学过谁不知道啊？对于走工业界路线而非学术路线的同学来说，算法学习的最大作用也许是找工作…… 毕竟工作后，绝大多数时候都用各种成熟的类库，少有自己实现高级数据结构和算法的时候。但刚结束一学期修的算法课，上得我还真跟没学过算法似的，让我大开眼界，虽然每次课上我都听的不是很懂，但每节都期盼着老师又能带来什么新奇的东西。一点点发现，原来竟然还有这么多很有用却从来没学习过甚至没听过的算法和数据结构啊！这些可以算作比较前沿的研究成果了，而且又不是离我们的日常工作非常遥远的纯理论，所以个人觉得这些知识非常值得学习，哪怕只是了解一下开拓思路。参考资料的话，除了下面每节提到的具体论文外，系统介绍这些高级算法和数据结构的书还真是凤毛麟角，不过还真发现了一本：Peter Brass的《Advanced Data Structures》。此外的话，就是老老实实地看原作者或分析得比较好的论文，这也是这学期练成的一项能力。当然，有的论文挺难的，我们可以节选着看，大多数时候还是看的挺享受的！2.随机化算法（Randomized Algorithms）随机化（Randomization）是这门课的重点，也是以前一直忽略了的，现在却发现非常重要的算法设计策略。在《Introduction to Alg ...继续阅读 (108)

Leetcode算法题分类解析：(一)总览1.为何/如何刷题1.1 必要性刷题刷题，从“刷”字就能看出其中的机械性和应试性，但这就是几乎所有IT公司面试中的一环。尽管面试者可能也对这种考察方式不是很满意，可在没有更好的方式之前，这个现状会一直保持下去。我们改变不了这个现状，那就适应它吧。1.2 分类攻破为什么要这么麻烦地分类呢？照着Leetcode的题目顺序做不就好了？个人觉得分类有几个动机：一是找信心：一开始不幸碰到看起来简单却没思路的题真的很崩溃，心想后面还有那么多呐，怎么刚开始就卡住了？通过分类就能知道这道题是典型的一类题还是只是一道很细节的题甚至“奇技淫巧”。二是提高效率：有时吃透一道题就可以解一大类。这真的跟以前上学时的备考很像，回忆一下更遥远的小学时的应用题大全那本神书。三是题目整理：目前在网上看到的都是Solution，没有只是题目或者与Solution分开的版本。为了方便思考和学习，就单独整理了这么一份只有题目和思路的版本。所以，建议大家都根据自己的理解进行分类，大体上应该都差不多，可以根据个人喜好微调。最好在一段时间内，集中解决同类问题来强化学习，而不是东一榔头西一棒子。1.3 特点分析通过题目的整理，可以看出Leetcode试题有几个特点，可能也适用于大部分面试题：问题背景简单：问题描述都比较简单几句话就能说清，只有少部分题目比较复杂比较难，例如基于棋盘、柱型图 ...继续阅读 (145)

十年之后重学C语言1.每个程序员都该有本翻烂的K&R1.1 多次自学，不得其法距离大学时学习C语言已有十个年头了。印象里最深的就是当时一位海归老师，在讲课时流露出对K&R的崇敬之情，以及用Hanoi塔的例子讲解递归。但当时的我还无法体会，也只是不走心的听听。那时的我还不知道K&R有多牛，递归有多重要。十年间经历了很多项目，也业余时间自学了很多东西。温习过C、自学过汇编、尝试操作系统内核。看过不少推荐的好书，看语法看得不厌其烦。却始终感觉对C语言既熟悉又陌生，熟悉其语法，陌生的是：这真的就是C语言最精华的部分吗？1.2 不期而遇，峰回路转转机就在刚刚结束的一学期高强度的研究生学习。因为之前已经对C的基础知识比较熟悉了，所以这学期并未刻意去系统学习（也确实没有时间）。就在实践中摸爬滚打了一学期，这次让我对C语言有了重新的认识。深深感受到：如果说算法实现只是用C小试牛刀，操作系统内核等底层开发才是让C爆发出强大力量的地方，也许刷题和实现算法时我们还有很多更加现代化的选择，例如C++、Java甚至Python，C语言不过是简洁明了的一种选择罢了。但在像操作系统内核、网络编程、编译器设计等研究生课程中，C简直处于霸主地位。暑假了有时间好好总结了，赶紧趁着感觉还在再深入理解一下。1.3 不是书不好，只是时候未到拿着这一本《The C Programming Langua ...继续阅读 (129)

CS研究生学习阶段必读书籍书单、书单、还是书单现在各种大牛推荐的书单已经太多太多了，大多包含如《Code Complete》、SICP、龙书等等经典之作，但后果就是十分雷同。因为特别经典的书的数量有限吧，多少年也出不了一本吧。所以，为了能有些新意，笔者决定推荐书单时针对特别群体或特别话题，让推荐的东西更多样性、有趣，也更有价值一些。本文就针对计算机科学专业的研究生群体，推荐一些教材和必读书籍。特别说明一下：有些书是上过课程已经读过的，感觉确实不错，有些则是将要上的课程给出的推荐教材，上网查了一下评价也挺高。主要参考了Amazon、Goodreads和豆瓣上的评价。图书推销员已上线……在正式开始推荐（销）之前，你必须要精读、并且常放于手边的两本书就是：《Discrete Mathematics and Its Applications》和经典的《The C Programming Language》（简称K&R）。因为整个研究生阶段，几乎各种课程都会反反复复的用到离散数学和C语言的相关知识。前者是笔者从国内带来的，真是明智的决定啊！从Theory of Database到Algorithm Analysis，从逻辑到集合论到概率论，真是无处不在啊！而后者更不用说了，从Operating System课到网络到各种Linux编程相关课程，C绝对是霸主。先来说说操作系统。提到OS ...继续阅读 (108)

留美CS学习的第一学期总结来美学习的第一学期就这么结束了！总体来说，在StonyBrook的这一学期没有辜负我的期望，有些方面甚至远超出我的预期。用受益匪浅四个字都不足以形容收获之大，夸张一点说：可能学到了许多自己可能一辈子都不会想到的东西。下面简单整理一下自己的心得和收获，有些东西也许对大家开阔思路能有些帮助。1.专业与课程特点CS专业可能是研究生专业里属得上的“累”专业了，学习压力是很大的！几乎每门课都有很多要求，作业形式也是“花样百出”，有的做Project和Lab，有的写Assignment，有的读Paper，还有的最后要来个Presentation等等。可以说这一学期下来真是培养了各种能力，用主流语言写代码、用Latex写各种推导、读各种论文、做PPT演示…… 对于编码类作业，一个有趣又比较讨喜的地方是自动判分脚本。当你做好作业后，可以跑脚本看自己做对了多少，然后再继续完善，有理有据！可能也正因为巨大的压力，同学们选课时都非常谨慎，也有不少为了保证GPA而避开一些“重课”。所以你能看到一些有意思的现象，作为极为重要的操作系统课只有二十几个人，门可罗雀，而网络课100人的大教室则爆满。有时看一些课程很感兴趣，但因为课程的高要求而只能错过，也是无奈。想轻轻松松（浅尝辄止）地学，看来还是自己去看网上公开课吧。有时对学校的高标准严要求也有些不理解，不知道在一学期不到四个月的时间里 ...继续阅读 (122)

算法学习的新阶段最近忙得一塌糊涂，所以根本没时间总结整理学习成果了。之前刚开学不太忙时写了几篇都没写完，因为发现面前开启了一道道大门，想系统整理的东西太多了。于是时隔快两个月，先发一篇以作记录，系统整理只能等到暑假开始时了，如果觉得有些水还请见谅……1.基本数据结构一开始接触到算法是在大学，具体有什么用也不清楚。但老师一般都说：算法+数据结构=程序。当时听起来觉得太重要了（确实重要，但现在知道了，程序的世界何止算法和数据结构这么简单），得好好学！学习过程很机械化，就是跟着老师的讲解和作业，用C++动手实现一个个基本的数据结构及操作。从单向链表、双向链表、各种二叉树…… 以为这就应该是算法了吧。工作以后，随着时间的流逝，当年学过的各种知识也跟着一点点遗忘了。什么双向链表的结点插入、二叉树的左旋右旋，早忘得一干二净！到最后也只是会用JDK里的List、Set、Map。大家都在天天用，感觉好像也没什么神秘的。于是我开始看起《算法导论》（Introduction to Algorithms，CLRS），都说是好书，第一遍把基础数据结构看了一半吧，真没感觉好…… 然后又看了一遍数据结构，开始对数据结构的内部构造及每种结构相关的算法有了扎实的记忆。比如哈希表是如何解决冲突的，就能联系到JDK的HashMap。看了红黑树，就能联系到TreeMap等等。于是以后选择数据结构时，更加的谨慎了！可是只 ...继续阅读 (133)

0.前言：在路上，再上路在前言《程序员修炼之路-(0)前言：在路上, 再上路》中已经对知识体系进行了梳理，主要分为问题定义、算法与数据结构、系统平台API、编程语言实现、代码设计、测试验证等等。目前集中精力编写算法与数据结构部分，这可能也是最艰难的一部分。其他部分之前零零散散有所涉及，之后再慢慢补充。1.计算机数学离散数学与具体数学。2.算法分析设计对于这一部分的内容编排，主要以《算法设计与分析基础》、《算法》以及LeetCode算法题中的问题分类为横向，以《算法设计与分析基础》中罗列的经典设计技巧为纵向，贯穿每一小节。因为传统算法书籍的结构经常是为了讲算法而讲，目录内容分类都很死板。而我想要的是解决这一类问题有哪些算法？都是用什么技巧和思路设计的？2.1 理论基础《程序员修炼之路-(1)基础(上)：算法设计》《程序员修炼之路-(1)基础(中)：性能分析》《程序员修炼之路-(1)基础(下)：正确性证明》2.2 线性表《程序员修炼之路-(2)线性表(上)：数组与链表》《程序员修炼之路-(2)线性表(下)：栈、队列》2.3 排序《程序员修炼之路-(3)排序(上)：基本排序》《程序员修炼之路-(3)排序(中)：合并和快速排序》2.4 搜索《程序员修炼之路-(4)搜索(上)：线性与二分查找》《程序员修炼之路-(4)搜索(中)：二叉查找树》《程序员修炼之路-(4)搜索(下)：哈希表》2.5 ...继续阅读 (84)

不觉间已经来美国快一个月了，感觉还像一场梦。从以前熟悉的生活圈子，每天起来朝九晚五地上班下班，回家吃饭看电视看书，到现在每天一睁眼从陌生的环境醒来，点点滴滴，要学习的很多。来了之后的第一大问题就是时差了。在飞机上凌晨三点多才睡到，早上七点又醒了。然后下午四点多下飞机，其实正是纽约的凌晨。等到了宿舍，收拾行李，然后打起精神出去找吃的。最后，坚持到纽约时间的晚上九、十点再睡。实际上就相当于快两天只睡了飞机上的那四个小时。这样过了一天、两天，当你以为时差已经倒过来时，之前欠下的睡眠时间就该来找你了。具体表现就是，每隔一天的晚上七八点都会昏死过去，一直到半夜十二点左右勉强起来洗漱一下再接着睡。还有更难的是，你的胃无法接受北京时间大半夜吃东西。困不行了、不想吃也得坚持，持续了一周零几天，终于完全适应了！以前十一点就得睡，不然头疼，现在纽约时间十一点时的感觉也完全一样了！倒时差果然不是一朝一夕的事儿。此外就是生活上的各种小问题了，从坐公交开始。这里公交车很少，而且都没有站牌，只能自己上网查。上错车又下来是经常的事儿。孤零零地站在路边，等一个小时车是司空见惯的。而且我附近的公交每次都是$1.25，美国硬币的cent、quarter、dime、nickle分不清…… 然后就是吃的了，美国超市卖的米面油是泰国香米、全麦面粉、橄榄油，香米软塌塌、全麦面粉应该做面包、橄榄油味道很奇特，全都买错了…… 一 ...继续阅读 (103)

因为做操作系统实验的原因，所以通读了一遍《Understanding git conceptually》，觉得确实不错，于是就简单地记录一下。有的地方理解的还不是很深，可能不够准确，等抽时间好好读一下《Pro Git》。作者开篇说到：仅仅记住在什么时候用什么命令是不够的，出问题只是早晚的事。只有理解了Git的工作原理，才算真正学会Git。遗憾的是大部分网上的教程都只是教你在何时使用哪个命令，然后让你去模仿。说得这么好，那就看看作者这篇教程是否把Git的工作原理讲清楚了。注意：以下1.2.1到1.2.3都是本地化操作，不要看到仓库、分支、合并等词语就以为一定是远程操作了，1.2.4才会讲到多人协同开发时的远程操作。1.Commit Object和Head使用Git的目的当然就是管理项目文件的版本变化，在Git中保存所有管理信息的数据结构叫做仓库（Repository）。可以在一个文件夹中通过命令git init创建仓库。仓库保存在项目文件目录下的一个叫做.git的文件夹中，它由两部分组成：提交对象（Commit object）：反映项目状态的一组文件、对父提交对象的引用、当前提交对象的SHA-1签名构成了提交对象。父提交对象的引用使得仓库的提交对象形成了一个有向无环图，我们可以一直遍历到第一次提交。每当我们要查询或操作仓库，都应该以如何操作commit object图的角度去思考。对 ...继续阅读 (101)

明天就要正式开课了！从大四实习离开校园，到今天重返，阔别了七年半。而立之年飘扬过海，远离故乡，远离亲朋，心中五味杂陈、百感交集……本以为会热泪盈眶、心潮澎湃、脑中浮现各种英雄人物事迹，事实却是当我经过十五个小时的飞行，清晨六点走出肯尼迪机场，在冷风中看着还未苏醒的纽约时，我的内心异常平静。如果你很想要一样东西，你立刻就得到了，你可能会激动万分。如果你非常想做一件事，经过几年的付出和等待，时间被这样拉长，结果可能就是平静。但平静不代表不重要。难以忘记炎炎夏日用功读书准备考试的热血，难以忘记拿到理想录取时的释然，难以忘记签证官拿起粉色小纸条时的奇妙感觉。事实证明，当你非常非常非常想做一件事时，上天真的会帮你，真的如此。我明白一个道理，凤凰不是天生如此，之所以凤凰涅磐，只是因为没被烧死。牛人们也并非天生如此，他们只是坚持到了最后，没被烈焰烧死。向之学习，致敬！走在繁华的曼哈顿街头，感觉自己的渺小。再听一遍《千万次的问》，发现这个词写的神了。走这一遭不是为了改变什么，只是想知道这世界上还有这样的地方、这样的活法。不是要当龟兔赛跑里最快的兔子，而是知道这世界上还有兔子这样的存在。此时此刻，心中有忧虑更有期待。三十岁前的自己已经没有遗憾，期待下一个十年更加热血更加精彩，下一站星辰大海！远方与大海不在别处，它只是你的心。 ...继续阅读 (112)

我的2015技术学习流水账2015年马上就要过去了，匆匆忙忙地又是一年。回头总结整理，发现这一年还挺充实的。在正常上班工作之余，学习到了不少新东西，不禁感到很欣慰！一个多月前就开始写，终于赶在2016年来临之前写完了这篇文章…… 关于本文，尽管叫做流水账，但是出于程序员条理性的“强迫症”，还是进行系统分类，分类方法参照Thoughtworks技术雷达的Tecniques、Languages & Frameworks、Tools、Platforms，将其中的Tecniques改为理论。1.理论从今年开始逐渐的深入学习计算机科学的理论，继续按照自己确立的学习路线一步一步走下去。1.1 重拾CSAPP算上今年这次应该已经“冲击”了两三次CSAPP了，这次的效果还算比较满意，几乎读完了厚厚的整本书，收获颇丰！从汇编语言、计算机组成原理、编译链接、系统编程，都算是系统的学习了一遍。具体学习笔记如下，其中(2)和(3)个人感觉还是整理的不错滴：《六星经典CSAPP笔记(1)计算机系统巡游》《六星经典CSAPP笔记(2)信息的操作和表示》《六星经典CSAPP笔记(3)程序的机器级表示》《六星经典CSAPP-笔记(7)加载与链接(上)》《六星经典CSAPP-笔记(10)系统I/O》《六星经典CSAPP-笔记(11)网络编程》《六星经典CSAPP-笔记(12)并发编程(上)》1.2 算法 & ...继续阅读 (97)

Java程序员的现代RPC指南1.前言1.1 RPC框架简介最早接触RPC还是初学Java时，直接用Socket API传东西好麻烦。于是发现了JDK直接支持的RMI，然后就用得不亦乐乎，各种大作业里凡是涉及到分布式通信的都用RMI，真是方便。后来用上了Spring，发现Spring提供了好多Exporter，可以无侵入地将一个POJO暴露为RPC服务。接触了这么多RPC框架后，发现当时公司内部自己实现了一套支持压缩、加密等附加功能的RPC基础框架，于是就读了一下源码，发现原来自己实现个简单的RPC挺简单啊，选好序列化框架后用反射为服务接口生成存根就行了。核心技术就是：序列化和动态反射。前一阵子又接触到了多语言支持的RPC框架。其实传统的方式也是能支持多种编程语言的，只要序列化框架为多种语言都提供了版本支持，那么序列化后使用相同的网络协议传输就能实现跨语言的RPC了，这也是最轻量级的自制RPC了，灵活但是手动工作量比较大。再就是重量级的SOAP WebService或简单方便的REST，后者一般采用JSON格式携带数据，最典型的场景就是前后台的服务调用，从JS到Java的RPC。本文要重点介绍的则是另外一套RPC框架。相比一般的RPC框架来说，它能够支持多种语言间的RPC；相比WebService，它却没有SOAP那么重量级，又比轻量级的REST高效。对于组件之间需要频繁通信、又对 ...继续阅读 (135)

分析得比较深刻的一篇好文，原文出处找不到了...就我自己的理解，谈谈我对读研和软件学院的看法，不妥之处一笑了之即可。如果你有实际开发工作经验，感觉自己的水平和实力进入了一个高原期，迫切需要从理论上提高，那么计算机学院是唯一选择。因为计算机学院才能让你在理论上更上一层楼。软件学院从教学计划上就没有把你往这方面带。当然能不能更上一层楼最终还是完全取决于你自己。需要特别说明的是，工作经验并不一定等于开发经验，我见过很多工作2-3年的人，但是没有一点开发经验。你说：“他们都有很强的开发能力,只是不太喜欢读书,也只是希望混个学历对今后在岗位上晋升有好处”，我可以向你保证，你所说的人绝对不是开发能力很强的人。因为，1）高手不可能不喜欢读书；2）高手不可能想去混一个学历；3）高手不可能认为晋升是因为学历的原因。还需要说明的是，考计算机的人未必个个都是高手，严格来说，大部分都不会编程序。也就是说，庸庸碌碌之辈仍然占绝大多数。研究生毕业的师兄只拿 2500元左右的比比皆是，所以不要寄希望于拿一张研究生文凭出去赚高薪。但是，对于有实际开发工作经验的人，要想自己在3年之中有一个真正的提高的话，计算机学院提供了广阔的平台。就我所知，每一个月拿2万以上的也有（上海育碧，图形特效算法设计）。所以，同为研究生毕业，能力的差距是极大的。所以，不要去问“研究生毕业能拿多少？”，要问“像我这种水平的人，研究生毕业能拿 ...继续阅读 (94)

GridGain的Hadoop加速器像GridGain等内存网格产品(IMDG)不仅可以作为简单的缓存，加速Hadoop中MapReduce计算也是IMDG的一个亮点。这样内存计算领域又多了一种思路和选择，而不只是Spark独霸一方的局面。关于GridGain的功能介绍请参考《开源IMDG之GridGain》。1.安装Hadoop 2.7.1很早之前写过一篇《Hadoop入门（一）：Hadoop伪分布安装》，那时用的还是0.20的版本，转眼间都已经2.7.1了，Hadoop发展真是飞快！所以本文的前半部分重点看一下最新版2.7.1如何搭建伪分布式集群。1.1 SSH无密码模式为当前用户配置无密码的SSH登录，通过ssh localhost测试是否还需要输入密码。[root@vm Software]# ssh-keygen -t rsa -P '' -f ~/.ssh/id_rsaGeneratingpublic/privatersakeypair. Your identification has been savedin/root/.ssh/id_rsa. Yourpublickeyhas been savedin/root/.ssh/id_rsa.pub. Thekeyfingerprintis:28:58:5c:c8:0a:b3:52:83:4f:c1:9a:71:65:12: ...继续阅读 (98)

BDD敏捷开发入门与实战1.BDD的来由2003年，Dan North首先提出了BDD的概念，并在随后开发出了JBehave框架。在Dan North博客上介绍BDD的文章中，说到了BDD的想法是从何而来。简略了解一下BDD的历史和背景，有助于我们更好地理解。1.1 TDD的困惑Dan在使用TDD敏捷实践时，时常会有很多同样的困惑萦绕脑海，这也是很多程序员敏捷实践都想知道的：where to startwhat to testwhat not to testhow much to test in one gowhat to call their testshow to understand why a test fails1.2 同事的小框架当Dan用上了一位同事编写的小框架agiledox时，灵感闪现！这个框架其实很简单，它基于JUnit测试框架，根据测试类名和方法名，将每个测试方法都打印为类似文档的输出。程序员们意识到这个小玩具可以帮它们做一些文档性的工作，于是就开始用商业领域语法命名他们的类和方法，让agiledox产生的输出能直接被商业客户、分析师、测试人员都看懂！// CustomerLookup// - finds customer by id// - fails for duplicate customers// - ...publicclassCustomerLoo ...继续阅读 (106)

操作系统内核Hack：(四)内核雏形在本系列的前一篇文章《操作系统内核Hack：(三)BootLoader制作》中，我们制作出了一个两阶段引导BootLoader，并进入了一个内核的空壳main函数。本文我们继续完善引导程序和内核，让内核的内容一点点充实起来。本文的代码可以参考GitHub上的MiniOS分支kernel_prototype。1.周边代码修改1.1 常量和宏提取像各个模块的内存这种常量，会经常被引导，所以就提取出一个单独的文件var.inc。同理，保护模式相关的常量和宏都提取到了pm.inc，这里主要是拷贝了Orange’s的代码和注释。;var.inc ;############################ ; Constants ; ############################SETUPLEN equ4BOOTSEG equ0x07c0INITSEG equ0x9000SETUPSEG equ0x9020SYSSEG equ0x1000NEWSYSSEG equ0x0000MEMSIZE equ0;INITSEG:MEMSIZE ; pm.inc ;############################ ; Macros ; ########################### ...继续阅读 (135)

操作系统内核Hack：(三)BootLoader制作关于本文涉及到的完整源码请参考MiniOS的v1_bootloader分支。1.制作方法现在我们已经了解了关于BootLoader的一切知识，让我们开始动手做一个BootLoader吧！但真正开始之前，我们还要做出一个选择，在之前的讨论中我们曾说过，有两种学习和制作引导程序和操作系统内核的路线：1）《Orange’s：一个操作系统的实现》书中的路线；2）Linux 0.11的路线。1.1 两种实现思路具体来说，第一种路线就是将BootLoader和Kernel都放到预先格式化成FAT的软盘上，BootLoader通过FAT和ELF的知识定位并加载Kernel，借助FreeDOS启动或调试我们的操作系统。并非对FAT和DOS心存偏见，毕竟现在的确很多汇编语言书籍仍然以DOS作为学习平台，但我个人更喜欢第二种路线。在引导过程，我们不依赖任何文件系统，在裸扇区中加载运行第二阶段BootLoader和Kernel。进入Kernel之后，我们再挂载一个根文件系统。为何要这样做而不跟着《Orange’s》作者的思路走呢？因为我们毕竟主要学习和模仿的是*nix族的操作系统，既然如此，为何不纯粹一些？直接循着当年Linus在Linux 0.11中的思路，这才算是一次酣畅淋漓的操作系统内核的Hack之旅！经过了本系列前两回对实验环境和底层编程基础知 ...继续阅读 (120)

操作系统内核Hack：(二)底层编程基础在《操作系统内核Hack：(一)实验环境搭建》中，我们看到了一个迷你操作系统引导程序。尽管只有不到二十行，然而要完全看懂还是需要不少底层软硬件知识的。本文的目的就是跟大家一起学习这一部分知识，本着够用就行的原则，不会完全铺开来，只要能让我们顺利走完未来的操作系统内核Hack之旅就可以了。1.开篇：“古怪”的80386如果大家跳过这一部分直接看本文后面的部分，或者您之前接触过操作系统内核的学习，一定会觉得80386的行为很古怪。为什么开机之后要设置一大堆东西然后跳到一个叫做什么保护模式的东西？为什么内存管理要分段还要分页这么麻烦？这种种令人费解的现象背后其实是有一段不同寻常的历史的，了解了其来龙去脉，一切就变得理所当然了！关于Intel的x86处理器整个家族史就不详谈了，否则可能要说上个几天几夜。我们主要关心具有里程碑意义的两款CPU：8086和80386。为什么只关注这两款CPU呢？首先通过一篇不错的资料简单了解一下这两款CPU的历史，再细说缘由。80x86段式寻址的原因Intel 8086是一个由Intel于1978年所设计的16位微处理器芯片，是x86架构的鼻祖。8086 CPU是Intel系列的16位微处理器，也就是说“算术逻辑运算单元（ALU）”的宽度，即数据总线是16位，可直接运算长度是16位的数据。但它却有20条地址线，可直接寻址 ...继续阅读 (147)

用Netty开发中间件：高并发性能优化最近在写一个后台中间件的原型，主要是做消息的分发和透传。因为要用Java实现，所以网络通信框架的第一选择当然就是Netty了，使用的是Netty 4版本。Netty果然效率很高，不用做太多努力就能达到一个比较高的tps。但使用过程中也碰到了一些问题，个人觉得都是比较经典而在网上又不太容易查找到相关资料的问题，所以在此总结一下。1.Context Switch过高压测时用nmon监控内核，发现Context Switch高达30w+。这明显不正常，但JVM能有什么导致Context Switch。参考之前整理过的恐龙书《Operating System Concept》的读书笔记《进程调度》和Wiki上的Context Switch介绍，进程/线程发生上下文切换的原因有：I/O等待：在多任务系统中，进程主动发起I/O请求，但I/O设备还没有准备好，所以会发生I/O阻塞，进程进入Wait状态。时间片耗尽：在多任务分时系统中，内核分配给进程的时间片已经耗尽了，进程进入Ready状态，等待内核重新分配时间片后的执行机会。硬件中断：在抢占式的多任务分时系统中，I/O设备可以在任意时刻发生中断，CPU会停下当前正在执行的进程去处理中断，因此进程进入Ready状态。根据分析，重点就放在第一个和第二个因素上。进程与线程的上下文切换之前的读书笔记里总结的是进程的 ...继续阅读 (195)

C实战：项目构建Make,Automake,CMake在本系列文章《C实战：强大的程序调试工具GDB》中我们简要学习了流行的调试工具GDB的使用方法。本文继续“C实战”的主题，对同样非常流行的构建工具Make的用法和原理一探究竟，并顺便看一下一些高级衍生产品。1.Make基础首先我们编写一个简单的C项目，以此项目在实战中学习Make的相关知识。更全面的介绍请参考官方手册。cdai@vm /syspace/2-ccpp/24-pragmatic/build-tool/make $ tree . ├── hello.c ├── hello.h ├── main.c └── Makefile0directories,4files整个程序的逻辑非常简单：main.c中包含一个main方法，调用了hello.c中的sayHello()函数，打印了一句话到控制台上。// cat main.c hello.h hello.c// ----- main.c -----#include "hello.h"intmain(void) { sayHello("Make");return1; }// ----- hello.h -----#ifndef _HELLO_H_#define _HELLO_H_voidsayHello(char*name);#endif// ----- hello.c ...继续阅读 (168)

分布式一致性协议Raft原理与实例1.Raft协议1.1 Raft简介Raft是由Stanford提出的一种更易理解的一致性算法，意在取代目前广为使用的Paxos算法。目前，在各种主流语言中都有了一些开源实现，比如本文中将使用的基于JGroups的Raft协议实现。关于Raft的原理，强烈推荐动画版Raft讲解。1.2 Raft原理在Raft中，每个结点会处于下面三种状态中的一种：follower：所有结点都以follower的状态开始。如果没收到leader消息则会变成candidate状态candidate：会向其他结点“拉选票”，如果得到大部分的票则成为leader。这个过程就叫做Leader选举(Leader Election)leader：所有对系统的修改都会先经过leader。每个修改都会写一条日志(log entry)。leader收到修改请求后的过程如下，这个过程叫做日志复制(Log Replication)：复制日志到所有follower结点(replicate entry)大部分结点响应时才提交日志通知所有follower结点日志已提交所有follower也提交日志现在整个系统处于一致的状态1.2.1 Leader Election当follower在选举超时时间(election timeout)内未收到leader的心跳消息(append entries)， ...继续阅读 (365)

Redis Cluster架构优化在《全面剖析Redis Cluster原理和应用》中，我们已经详细剖析了现阶段Redis Cluster的缺点：无中心化架构Gossip消息的开销不停机升级困难无法根据统计区分冷热数据客户端的挑战Cluster协议支持连接和路由表的维护开销MultiOp和Pipeline支持有限Redis实现问题不能自动发现不能自动Resharding无监控管理UI最终一致性和“脑裂”问题数据迁移以Key为单位，速度较慢数据迁移没有保存进度，故障时不能恢复Slave“冷备”，不能缓解读压力当然之前也说过了：“这与Redis的设计初衷有关，毕竟作者都已经说了，最核心的设计目标就是性能、水平伸缩和可用性”。但综合来看，要想在生产环境中使用Redis Cluster，我们还是有一些工作要做的。本文就从宏观层面上，列举一些架构优化的参考方案。1.P2P架构副作用1.1 Gossip通信开销Gossip消息的通信开销是P2P分布式系统带来的第一个副作用。有一篇关于Gossip通俗易懂的文章《Life in a Redis Cluster: Meet and Gossip with your neighbors》。Redis为集群操作的消息通信单独开辟一个TCP通道，交换二进制消息：PING/PONG：Cluster的心跳，每个结点每秒随机PING几个结点。结点的选择方法是： ...继续阅读 (590)

全面剖析Redis Cluster原理和应用1.Redis Cluster总览1.1 设计原则和初衷在官方文档Cluster Spec中，作者详细介绍了Redis集群为什么要设计成现在的样子。最核心的目标有三个：性能：这是Redis赖以生存的看家本领，增加集群功能后当然不能对性能产生太大影响，所以Redis采取了P2P而非Proxy方式、异步复制、客户端重定向等设计，而牺牲了部分的一致性、使用性。水平扩展：集群的最重要能力当然是扩展，文档中称可以线性扩展到1000结点。可用性：在Cluster推出之前，可用性要靠Sentinel保证。有了集群之后也自动具有了Sentinel的监控和自动Failover能力。1.2 架构变化与CAP理论Redis Cluster集群功能推出已经有一段时间了。在单机版的Redis中，每个Master之间是没有任何通信的，所以我们一般在Jedis客户端或者Codis这样的代理中做Pre-sharding。按照CAP理论来说，单机版的Redis属于保证CP(Consistency & Partition-Tolerancy)而牺牲A(Availability)，也就说Redis能够保证所有用户看到相同的数据（一致性，因为Redis不自动冗余数据）和网络通信出问题时，暂时隔离开的子系统能继续运行（分区容忍性，因为Master之间没有直接关系，不需要通 ...继续阅读 (328)

操作系统内核Hack：(一)实验环境搭建三四年前，心血来潮，入手《Orange’s：一个操作系统的实现》学习操作系统内核，还配套买了王爽的《汇编语言（第二版）》和《80X86汇编语言程序设计教程》，虽然Orang’s只看了不到三分之一，但当时还是很认真的，练习也做了不少。唯一遗憾的就是没有留下文字记录，导致现在忘得差不多一干二净了，后悔不已！如今想再捡起来，弥补当时的懒惰，虽然困难重重，但这么优秀的国产书怎么能看完就算了呢！而且当年还是在Windows下练习的，现在终于用上了原汁原味的Linux。再也不用在虚拟机鼓捣了，更应该重新品味一番！1.开发工具安装1.1 编译器：NASM和GCC操作系统内核的引导部分是要用汇编语言来写的，但后面大部分都是用C语言，所以编译器方面我们需要NASM和GCC。cdai@cdai ~ $sudoapt-get install build-essential nasm1.2 编辑器：SublimeTextSublime Text提供了NASM插件，通过Package Control直接就能安装，很方便。虽然没有什么智能提示，但是有关键字染色还是不错的！1.3 构建：Make构建工具方面，当然是用GNU Make。具体内容先不做详述，等到需要时再系统学习一下。1.4 模拟器：BochsLinux当然选择Bochs，此外还要安装bximage来生成映像文 ...继续阅读 (138)

Docker新手入门：基本用法1.Docker简介1.1 第一本Docker书工作中不断碰到Docker，今天终于算是正式开始学习了。在挑选系统学习Docker以及虚拟化技术的书籍时还碰到了不少麻烦，主要就是没有特别经典的书！Docker的《第一版Docker书》和《Docker技术入门与实战》普遍评价不高，而《Docker开发实践》和《Dockeru源码分析》又是2015年最近才出的，评价不是很多。综合看了下，最终还是选择了《Docker开发实践》，以下都主要以这本书作为学习资料。1.2 Docker是什么？《Docker开发实践》中讲了个故事：20世纪60年代以前的海运，货物都放置在一起，很容易挤压受损。同时，不同的运输方式之间的转运也很麻烦，例如从码头和火车汽车转运卸货时。不同货物和不同交通工具之间的组合是一个巨大的二维矩阵。海运界最后达成了一致，制定了国际标准集装箱来解决这个棘手的问题。所有货物都打包进集装箱互相隔离，所有交通工具都通过集装箱转运，极大地提供了运输的安全性和效率。在软件开发中我们也经常碰到同样的问题，使用了各种各样技术框架的应用程序，从前端静态网站到后端数据库，从PHP到Java，以及多种多样的部署环境，从测试服务器到线上环境，从虚拟机到公有云等等。Docker，正是这个集装箱，而Docker的logo也的确是个集装箱。1.3 Docker与容器和虚拟机很自 ...继续阅读 (141)

Jedis分片Sentinel连接池实验1.起因众所周知，Redis官方HA工具Sentinel已经问世很久了，但令人费解的是，Jedis官方却迟迟没有更新它的连接池。到目前Maven库中最新的2.7.3版本为止，都只能要么使用分片连接池，要么使用不分片的Sentinel连接池。如果既进行了Sharding，又对每组的主从实例配置Sentinel进行监控，怎么办？答案是只能自己开发了，晕！还好万能的GitHub上已经有人提供了一个简单可用的分片Sentinel连接池实现，于是就直接拿来用用。2.Sentinel配置我的Redis是这样配置的：一个主6379带一个从16379，名字叫mymaster-6379；另一个主6380带另一个从16380，名字叫mymaster-6380。Sentinel按照惯例，起三个实例26379,26380,26381。以其中一个为例，其他的Sentinel配置只是端口号不同：port26379dir /tmp sentinel monitor mymaster-6379192.168.241.22063792sentinel down-after-millisecondsmymaster-637930000sentinel parallel-syncsmymaster-63791sentinel failover-timeoutmymaster-6 ...继续阅读 (524)

Netty 4源码解析：请求处理通过之前《Netty 4源码解析：服务端启动》的分析，我们知道在最前端“扛压力”的是NioEventLoop.run()方法。我们指定创建出的NioServerSocketChannel就是注册到了NioEventLoop中的Selector上。所以我们继续顺藤摸瓜，看看服务端启动完成后，Netty是如何处理每个请求的。1.MainReactor1.1 事件轮询之前我们曾分析过到NioEventLoop.run()方法，但因为之前只关注启动流程所以“浅尝辄止”了，这次我们就以它为起点开始深入分析。NioEventLoop于Selector绑定，它是真正轮询Selector的地方。至于有哪一个或哪些Channel的事件绑定到Selector了，则是注册阶段决定的。对于MainReactor来说，只有一个NioEventLoop负责处理一个ServerSocketChannel的事件。// NioEventLoop@Overrideprotectedvoidrun() {for(;;) {booleanoldWakenUp = wakenUp.getAndSet(false);try{if(hasTasks()) { selectNow(); }else{ ...继续阅读 (353)

跟Netty 4学网络编程《Netty权威指南》在网上的评价不是很高，尤其是第一版，第二版能稍好些？入手后快速翻看了大半本，不免还是想对《Netty权威指南(第二版)》吐槽一下：前半本的代码排版太糟糕了，简直就是直接打印Word的版式似的。源码解析部分的条理性和代码排版好多了，感觉比其他部分的质量高多了。如果你是初学者可能会感觉很详细，几乎每部分都会来一套客户端和服务端的Demo，如果你不是入门者的话可能会感觉水分比较多。最后一部分高级特性，内容有些混乱，不少内容都在不同的章节里重复了好几遍。不管怎样，如果你是网络通信或后台中间件的入门者，尤其是Java程序员，那么这本书还是值得入手的。尤其是书中对I/O模型、协议解析、可靠性等方面的点拨还是会让你有很多收获的。好了吐槽就到这了，以下就是《Netty权威指南(第二版)》的重点摘录，抽掉了水分，所有干货都在这里了。1.Linux和Java的I/O演进之路Linux从select -> poll -> epoll机制。简要说epoll的优点就是：从主动轮询+线性扫描变为被动事件通知，mmap避免到用户态的拷贝，更加简单的API。Java方面呢，JDK 1.3之前只有阻塞I/O，到1.4加入了NIO。在JDK 1.5 update 10和Linux 2.6以上版本，JDK使用epoll替换了select/poll。1.7加入了 ...继续阅读 (412)

Netty 4源码解析：服务端启动1.基础知识1.1 Netty 4示例因为Netty 5还处于测试版，所以选择了目前比较稳定的Netty 4作为学习对象。而且5.0的变化也不像4.0这么大，好多网上的例子都已经过时了。io.nettynetty-all4.0.25.FinalNetty 4服务端的典型用法如下面代码示例所示，核心组件就是EventLoopGroup、ServerBootstrap、Handler等。其中像EventLoopGroup、Channel等都是可以灵活调配的。这里以比较常用的“主从Reactor”+Nio非阻塞为例，分析代码的执行流程。如果没有接触过Netty的话，建议先简单了解一下Reactor模型等知识再学习源码，不然可能会一头雾水。EventLoopGroup bossGroup =newNioEventLoopGroup(); EventLoopGroup workerGroup =newNioEventLoopGroup();try{ ServerBootstrap b =newServerBootstrap() .group(bossGroup, workerGroup) .channel(NioServerSocketChannel.class) ...继续阅读 (310)