算法 -- IT技术博客大学习 -- 共学习共进步！

Memcached的内存管理在网上也可以搜集到不少不错的文章，新浪的这篇《Memcached深度分析》讲得不错，读别人的文章还是不如自己直接去读源码分析源码来得直接，这里写一下我阅读Memcached源码时对于Memcached内存管理机制的理解。 Memcached的代码结构很简单，从main()函数入口进去之后便是几个模块的初始化函数，和内存管理相关的主要有两个函数，一个是assoc_init()，这个是用来初始化哈希表的，关于这个哈希表的作用留在外面讨论，另一个是slabs_init()，该函数用来初始化slab，下面先来讨论一下slab机制。

• Redis的事件循环与定时器模型

简单翻阅了下Redis的源码，读一款server软件的源码我一般是从进程/线程模型开始的，Redis让我有些诧异，它采用了单进程单线程的模型，一般的server软件都会采用多进程或者多线程再或者多线程多进程混合的模型来设计，从而充分利用多核处理器的并行计算能力来提高软件的性能，Redis这种模型我只能推断程序的可并行化程度不高，顺序计算反而能省去多线程同步和维护线程池/进程池的开销，我对于数据库server端的设计没有什么经验也没有太多的理解，如有谬误欢迎大家指正。当然，这里要写的不是关于Redis的进程模型，而是Redis的事件模型和定时器模型。

• 一个状态模式的小改进

设计模式中的状态模式这是标准的状态模式.其中Context管理所有状态,而每个状态都是自己的类,而状态的流转逻辑由状态自己执行. 然后完整的状态模式实现太过”重”,而且状态流转的描述在代码上也不会是一目了然.所以我对状态模式进行了简化和优化.使其很”轻”,易于使用和实现,而且对于状态流转在代码上也能一目了然.所有的流转逻辑都能在一屏上显示出来.

• Linux 核心编程 – fsync, write

write ssize_t write(int fd, const void *buf, size_t count); 将数据写到文件中. 注意, 如果文件是保存在硬盘中, write() 函数调用返回之后, 并不表示数据已经写入到硬盘中, 这时如果掉电, 数据可能会丢失. fsync int fsync(int fd); 程序调用本函数, 通知内核把数据写到硬盘(file)中. 比如, 你开发一个数据库软件, 就需要这样的函数, 否则掉电或者系统崩溃时便会丢失数据. 如果你的程序不调用 fsync(), Linux 内核也会自动在”合适”的时候将你的数据真正写入到硬盘(类似调用 fsync), 最长的延时默认是 30 秒. 阻塞阻塞是 IO 的精华所在, 不管是文件 IO 还是网络 IO, 只有真正了理解了 IO 阻塞, 才能做出所谓在高并发高性能软件(服务器)

• 一个状态模式的小改进

设计模式中的状态模式这是标准的状态模式.其中Context管理所有状态,而每个状态都是自己的类,而状态的流转逻辑由状态自己执行. 然后完整的状态模式实现太过”重”,而且状态流转的描述在代码上也不会是一目了然.所以我对状态模式进行了简化和优化.使其很”轻”,易于使用和实现,而且对于状态流转在代码上也能一目了然.所有的流转逻辑都能在一屏上显示出来.

• 关于hashcode 里面使用31 系数的问题

首先我们来了解一下hashcode，什么是hashcode？有什么作用？ hashcode其实就是散列码，使用hashcode使用高效率的哈希算法来定位查找对象！我们在使用容器来存储数据的时候会计算一串散列码，然后将数据放入容器。如：String s =“java”,那么计算机会先计算散列码，然后放入相应的数组中，数组的索引就是从散列吗计算来的，然后再装入数组里的容器里，如List.这就相当于把你要存的数据分成了几个大的部分，然后每个部分存了很多值，你查询的时候先查大的部分，再在大的部分里面查小的，这样就比先行查询要快很多！一个对象的HashCode就是一个简单的Hash算法的实现,虽然它和那些真正的复杂的！Hash算法相比还不能叫真正的算法,但如何实现它,不仅仅是程序员的编程水平问题, 而是关系到你的对象在存取时性能的非常重要的问题.有可能,不同HashCode可能会使你

• 浅析Linux Kernel 哈希路由表实现(二)

在向外发送数据包的时候，首先需要查询路由表来确定路由包的路由，主要由ip_route_output_key()函数来完成，该函数又调用了ip_route_output_flow()，而这个函数最终又调用了__ip_route_output_key()这个函数来进行路由的查询，下面主要来看一下这个函数。

• 浅析Linux Kernel 哈希路由表实现(一)

1. 路由表目前Linux内核中支持两种路由表，一种是Hash路由表，另一种是Trie路由表，Trie算法查找效率很高，但它也因极其消毫内存资源而闻名，因此一般用在大型机上，否则在路由项过多时很可能造成内存的耗尽。在一般的机器上最好还是使用Hash路由表，之前有争论说Linux使用Hash路由表相比于二叉树效率太低，不适合商用，其实只要设计良好的哈希算法，尽量减少哈希碰撞，Hash路由表的查找效率也是很高的，在最好的情况下算法复杂算可以达到O(1)，当然，最差也不过是O(n)，我们有理由相信Linux中存在各种优秀的哈希算法，这些都是值得我们学习的。

• 浅析Linux Kernel中的那些链表

链表是Linux内核中最重要的数据结构，但Linux内核中的链表与传统的数据结构书中看到的链表结构略有不同。这里简单写一下我对于Linux内核中链表的理解，不足之处欢迎路过的大牛给出批评意见。 1.传统形式的链表数据结构书中的链表一般是下面这种形式： struct list { struct list *pre; struct list *next; void *data; }; 每一个链表结构中都包括两个同类型的指针，分别指向链表的上一个节点和下一个节点。这样当该节点处于一个循环链表中时，链表的首节点一般不用于保存数据，但首节点也需要是一个struct list类型，当结构庞大时首节点也必须分配同样大小的空间，这样就造成了内存的浪费。

• 浅析linux kernel network之socket创建

去年受@colyli 指点，决定花些时间读一些linux kernel network部分的代码，准备把阅读代码的过程记录下来，也希望能有大牛前来指点，下面就先写一下创建socket对象的过程。

• Apache基础数据结构(tables)代码浅析

提到Apache社区脑子里立马会呈现出一系列的Java项目集合,尽管@gnawux师兄教导我不要纠结于语言,但对于Java的抵制还是很难一下子就消失的，所幸Apache社区最重量级的项目Apache开源HTTP服务器httpd的源代码是完全使用C语言开发的，尽管近年来涌现出种种轻量级高性能Web服务器，Apache仍以它的功能广泛和真正的高性能而处于无可取代的位置。 Apache也经常受人诟病，矛头直指它的低效，我没有太多这方面的经验，因此没有过多的发言权，看到一些大牛们对这个问题的评论是觉得Apache低效是因为对Apache缺少了解。我个人也觉得这样一款多年风行Web服务器领域的软件肯定有它存在的理由，我们认为它不好可能是我们对它的了解不够。在网上看到过关于Apache源码是否值得阅读的讨论，很多人认为Apache源码组织结构不好，不太适合阅读，更多人推荐nginx等源码，其实我

• 给你的代码《约法四章》：基本功能、错误处理、智能纠错、日志收集

作为21世纪的码农，如果只是想混混工资的话，这篇文章可能不太适合你，但如果想在技术上有所提升，本文也许能帮你照亮前进的道路。程序员不能只是天天埋头写代码，还得关心代码的质量，其实写代码很容易，稍微用心点学都能写，但是要产出好的代码却不是那么容易事，所谓好的代码不是说你完成了某某功能就牛B，在完成了基本功能的同时还有很细节要注意，在各种关于代码质量的书中都的提及到了这样的概念：代码格式、命名规则、功能注释等，虽然这些东西看上去并不能主宰软件的“生与死”，但是谁又能保证一个软件从出生到结束都由一个人维护呢？关于代码规范这个话题我不打算列入本文的内容，原因有二，其一是很多书中都的提及到，我就不必重申；其二是很多程序员其实也很注重这个问题，只是注释多少的问题。那么就标题中的四点来给我们的代码约法四章，让我们这些码农的代码更健壮。

• 无限递归导致 Segmentation fault

某服务器上一个 cron job 是 shell 脚本调用 Java 程序，最近老是报 Segmentation fault, 每次看见此信息 /bin/sh: line 1: 4285 Segmentation fault java ... 总觉得无处下手，bash 的问题？Java 版本不对？信息量太少了。其实遇到这种事情不能谎，表面上没有信息一定要挖出信息来。今天仔细一看，这个脚本把标准输出重定向到一个日志文件去了，于是去看日志。这个程序的主体是对一个信息列表做循环，恰好在每个循环的关键部分开始前、结束后都会写一条日志。其目的是为了计时，不过正是这两条日志让我很快找到了错误缘由，因为发现日志文件的末尾只有一个开始前的，说面在这个循环的处理过程里面发生了 Segmentation fault. 找出程序的源代码，发现循环里面调用的方法有一个是递归的，情况就开始明朗了，猜测就是递归

• 漫话中文自动分词和语义识别（下）：句法结构和语义结构

这篇文章是漫话中文分词算法的续篇。在这里，我们将紧接着上一篇文章的内容继续探讨下去：如果计算机可以对一句话进行自动分词，它还能进一步整理句子的结构，甚至理解句子的意思吗？这两篇文章的关系十分紧密，因此，我把前一篇文章改名为了《漫话中文自动分词和语义识别（上）》，这篇文章自然就是它的下篇。我已经在很多不同的地方做过与这个话题有关的演讲了，在这里我想把它们写下来，和更多的人一同分享。什么叫做句法结构呢？让我们来看一些例子。“白天鹅在水中游”，这句话是有歧义的，它可能指的是“白天有一只鹅在水中游”，也可能指的是“有一只白天鹅在水中游”。不同的分词方案，产生了不同的意义。有没有什么句子，它的分词方案是唯一的，但也会产生不同的意思呢？有。比如“门没有锁”，它可能是指的“门没有被锁上”，也有可能是指的“门

• 推荐算法Slope One初探

Slope One 算法是由 Daniel Lemire 教授在 2005 年提出的一个 Item-Based 推荐算法。 Slope One 算法试图同时满足这样的的 5 个目标：易于实现和维护：普通工程师可以轻松解释所有的聚合数据，并且算法易于实现和测试。运行时可更新的：新增一个评分项，应该对预测结果即时产生影响。高效率的查询响应：快速的执行查询，可能需要付出更多的空间占用作为代价。对初次访问者要求少：对于一个评分项目很少的用户，也应该可以获得有效的推荐。合理的准确性：与最准确的方法相比，此方法应该是有竞争力的，准确性方面的微小增长不能以简单性和扩展性的大量牺牲为代价。

• 深入浅出Flashcache（五）

前几天因为测试新版的Flashcache，为了便于监控性能指标，用Perl写了个秒级的监控程序Flashstat，一开始是通过定期获取dmsetup status的信息做解析，后来在flashcache-dev邮件列表中讨论时，Flashcache的...

• 深入浅出Flashcache（四）

我们可以用内存来模拟一个性能很好的Flash设备，当然这有一个缺点，就是主机重启后就啥都没了，不过用于实验测试这应该不是什么大问题。用内存来模拟块设备有两种方法，ramdisk或者tmpfs+loop device。由于ramdisk要调整大小需要修改grub并重启，这里我们用tmpfs来实现。

• 深入浅出Flashcache（三）

前文简单介绍了block device和device mapper。有了这两个基础，再来看flashcache的代码，就容易理解多了。Flashcache是一个内核模块，要更清晰的理解代码，还需要了解一下内核模块编写的一些基础知...

• 深入浅出Flashcache（二）

前文简单的介绍了block device，别急，虽然这个系列的主要目的是介绍Flashcache，这一篇还是不会切入正题，因为我们还需要先了解下什么是device mapper。假如一台主机插入了多块硬盘，单块硬盘...

• 深入浅出Flashcache（一）

Cache is king. 在计算机系统中，cache的魔爪无处不在。CPU中有L1,L2,甚至L3 cache;Linux有pagecache，MySQL有buffer cache/query cache;IO系统中Raid卡/磁盘也有cache;在大型互联网系统中，数据库前面一般也都有一层...