又一个程序猿(codemonkey /koʊdˈmʌŋki/),更多...

如何实现一个malloc

<摘要>: 任何一个用过或学过C的人对malloc都不会陌生。大家都知道malloc可以分配一段连续的内存空间,并且在不再使用时可以通过free释放掉。但是,许多程序员对malloc背后的事情并不熟悉,许多人甚至把malloc当做操作系统所提供的系统调用或C的关键字。实际上,malloc只是C的标准库中提供的一个普通函数,而且实现malloc的基本思想并不复杂,任何一个对C和操作系统有些许了解的程序员都可以很容易理解。这篇文章通过实现一个简单的malloc来描述malloc背后的机制。当然与现有C的标准库实现(例如glibc)相比,我们实现的malloc并不是特别高效,但是这个实现比目前真实的malloc实现要简单很多,因此易于理解。重要的是,这个实现和真实实现在基本原理上是一致的。这篇文章将首先介绍一些所需的基本知识,如操作系统对进程的内存管理以及相关的系统调用,然后逐步实现一个简单的malloc。为了简单起见,这篇文章将只考虑x86_64体系结构,操作系统为Linux。

作者 张洋 | 发布于 2014-08-19 | Tags C malloc 操作系统

生成特定分布随机数的方法

<摘要>: 生成随机数是程序设计里常见的需求。一般的编程语言都会自带一个随机数生成函数,用于生成服从均匀分布的随机数。不过有时需要生成服从其它分布的随机数,例如高斯分布或指数分布等。有些编程语言已经有比较完善的实现,例如Python的NumPy。这篇文章介绍如何通过均匀分布随机数生成函数生成符合特定概率分布的随机数,主要介绍Inverse Ttransform和Acceptance-Rejection两种基础算法以及一些相关的衍生方法。下文我们均假设已经拥有一个可以生成0到1之间均匀分布的随机数生成函数,关于如何生成均匀分布等更底层的随机数生成理论,请参考其它资料,本文不做讨论。

作者 张洋 | 发布于 2014-06-14 | Tags 概率 算法 随机数

2048-AI程序算法分析

<摘要>: 针对目前火爆的2048游戏,有人实现了一个AI程序,可以以较大概率(高于90%)赢得游戏,并且作者在stackoverflow上简要介绍了AI的算法框架和实现思路。但是这个回答主要集中在启发函数的选取上,对AI用到的核心算法并没有仔细说明。这篇文章将主要分为两个部分,第一部分介绍其中用到的基础算法,即minimax和alpha-beta剪枝;第二部分分析作者具体的实现。

作者 张洋 | 发布于 2014-04-04 | Tags 2048 Minimax 人工智能 算法

抓取网页内容生成Kindle电子书

<摘要>: 自从买了kindle后,总是想着如何最大效用发挥其效用。虽然多看上有很多书可以购买,网上也有很多免费的电子书,但是仍然有很多感兴趣的内容是以网页的形式存在的。例如O’Reilly Atlas就提供了诸多电子书,但是只提供免费的在线阅读;另外还有很多资料或文档都只有网页形式。于是就希望通过某种方法讲这些在线资料转为epub或mobi格式,以便在kindle上阅读。这篇文章介绍了如何借助calibre并编写少量代码来达到这个目的。

作者 张洋 | 发布于 2014-03-27 | Tags Kindle 电子书 经验技巧

开始使用Ubuntu作为工作环境

<摘要>: 2012年3月,我自购了一台13寸的Macbook Air,从那时开始至今近两年时间,我一直用它作为工作本。但是最近越来越觉得4G的内存和128G的SSD力不从心,苦于Air无法升级硬件,于是终于下决心拿出入职时公司给配的Dell E6410,自己买了内存和SSD,升级成了8G内存+370G混合硬盘(120G SSD做主盘,250G硬盘做从盘)。硬件升级事小,关键是系统的迁移代价比较大。我在Dell本上装的是Ubuntu 13.10,由于我平时习惯使用Dropbox等云端服务,浏览器配置也都通过Google账号漫游,所以这部分迁移几乎没有成本,主要的成本在开发环境配置和常用软件迁移。虽然都是Unix系,但是Mac OSX下很多软件Linux下并没有。花了大约一个周末,总算把我的Ubuntu配置的比较顺手了,目前也已经正式投入工作。其中的重头戏便是开发环境(主要是terminal和vim)的配置,另外就是一些常用工具。这篇文章记录了我一些主要的工作,算是给自己留一个文档,也希望能给打算从Mac迁移到Linux的同学做一个借鉴。

作者 张洋 | 发布于 2013-12-30 | Tags Ubuntu

一个故事告诉你比特币的原理及运作机制

<摘要>: 周末花时间看了一些比特币原理相关的资料,虽然不敢说把每个细节都完全搞懂了,不过整体思路和关键部分的主要原理还是比较明白。写一篇文章分享给大家。这篇文章的定位会比较科普,尽量用类比的方法将比特币的基本原理讲出来。这篇文章不会涉及算法和协议中比较细节的部分,打算后面会再写一篇程序员视角下的比特币原理,那里会从技术人员的视角对比特币系统中较为关键的数据结构、算法和协议进行一些讲解。在这篇文章中我会给出一个虚拟的村庄叫“比特村”,整个文章会以讲故事的方式,逐步告诉大家比特币提出的动机、解决了什么问题以及一些关键组件的目标和设计方案。

作者 张洋 | 发布于 2013-12-16 | Tags 比特币 Bitcoin

MySQL索引与Index Condition Pushdown

<摘要>: 大约在两年前,我写了一篇关于MySQL索引的文章。最近有同学在文章的评论中对文章的内容提出质疑,质疑主要集中在联合索引的使用方式上。在那篇文章中,我说明联合索引是将各个索引字段做字符串连接后作为key,使用时将整体做前缀匹配。而这名同学找到了如下一句话:index condition pushdown is usually useful with multi-column indexes:the first component(s) is what index access is done for, the subsequent have columns that we read and check conditions on。从而认为联合索引的使用方式与文中不符。实际上,这个页面所讲述的是在MariaDB 5.3.3(MySQL是在5.6)开始引入的一种叫做Index Condition Pushdown(以下简称ICP)的查询优化方式。由于本身不是一个层面的东西,前文中说的是Index Access,而这里是Query Optimization,所以并不构成对前文正确性的影响。在写前文时,MySQL还没有ICP,所以文中没有涉及相关内容,但考虑到新版本的MariaDB或MySQL中ICP的启用确实影响了一些查询行为的外在表现。所以决定写这篇文章详细讲述一下ICP的原理以及对索引使用方式的优化。

作者 张洋 | 发布于 2013-12-05 | Tags MySQL MariaDB 索引 IndexConditionPushdown

使用MPlayer观看Coursera课程视频的一些心得

<摘要>: 之前一直是在线看Coursera上的课程视频。最近迫于租住的房子网速太差,加之Coursera访问经常不稳定,为了使得流畅学习的过程不被破坏,开始考虑将视频下载到本地观看。因为之前一直没有在本地看视频的习惯,很少使用播放器,所以找个顺心的播放器就成了重中之重。经过一番折腾,最终选择了MPlayer。下面和大家分享一下用MPlayer看Coursera视频的心得。

作者 张洋 | 发布于 2013-10-06 | Tags MPlayer Coursera 经验技巧

五种常用基数估计算法效果实验及实践建议

<摘要>: 之前我曾写过一系列关于基数估计(cardinality estimation)算法的文章,文中介绍了一些常用基数估计算法的原理。最近对常用的基数估计算法做了一些实验,这篇文章描述了实验结果,包括这些算法的估计效果及误差状况,主要通过图表展示。通过观察实验数据和可视化图表可以加强对各种基数估计算法理论分析的直观理解。文章首先会对实验做一些说明,然后通过图表详细展示实验数据,最后会根据实验结果总结一些实践中有用的结论。同时文末会附上相关的参考文献及原始数据。

作者 张洋 | 发布于 2013-08-30 | Tags 算法 基数估计 大数据

准确测量机器学习模型的误差

<摘要>: 在机器学习模型的效果评估中,预测误差的分析是重中之重。对于现有的各种误差测量技术,如果使用不当,会得出极具误导性的结论。这些结论会误导模型设计者设计出过拟合的模型,过拟合是指训练出的模型对于训练集拟合的很好,但是对于新的样本集则预测效果极差。这篇文章描述了如何正确的测量模型误差,以避免此类问题。

作者 张洋 | 发布于 2013-08-16 | Tags 机器学习 数据挖掘 翻译 误差分析

我的博客系统折腾手记暨papery正式发布

<摘要>: 上周花了一个周末的时间,把我自己的博客生成系统彻底重构成较为通用的系统了。这件事其实一直就想做,不过一直没想好怎么在简单和通用间做好权衡。上周接连接到几名同学在微博上问我的博客是用什么系统搭建的,终于促使我下决心把这件事情做掉。目前这个系统已经定名为papery,源码在github上,并发布到了npm。

作者 张洋 | 发布于 2013-08-12 | Tags papery

使用SeaJS实现模块化JavaScript开发

<摘要>: SeaJS是一个遵循CommonJS规范的JavaScript模块加载框架,可以实现JavaScript的模块化开发及加载机制。与jQuery等JavaScript框架不同,SeaJS不会扩展封装语言特性,而只是实现JavaScript的模块化及按模块加载。SeaJS的主要目的是令JavaScript开发模块化并可以轻松愉悦进行加载,将前端工程师从繁重的JavaScript文件及对象依赖处理中解放出来,可以专注于代码本身的逻辑。SeaJS可以与jQuery这类框架完美集成。使用SeaJS可以提高JavaScript代码的可读性和清晰度,解决目前JavaScript编程中普遍存在的依赖关系混乱和代码纠缠等问题,方便代码的编写和维护。

作者 张洋 | 发布于 2013-08-02 | Tags Javascript SeaJS

PCA的数学原理

<摘要>: PCA(Principal Component Analysis)是一种常用的数据分析方法。PCA通过线性变换将原始数据变换为一组各维度线性无关的表示,可用于提取数据的主要特征分量,常用于高维数据的降维。网上关于PCA的文章有很多,但是大多数只描述了PCA的分析过程,而没有讲述其中的原理。这篇文章的目的是介绍PCA的基本数学原理,帮助读者了解PCA的工作机制是什么。当然我并不打算把文章写成纯数学文章,而是希望用直观和易懂的方式叙述PCA的数学原理,所以整个文章不会引入严格的数学推导。希望读者在看完这篇文章后能更好的明白PCA的工作原理。

作者 张洋 | 发布于 2013-06-22 | Tags 机器学习 线性代数 PCA

期望、方差、协方差及相关系数的基本运算

<摘要>: 这篇文章总结了概率统计中期望、方差、协方差和相关系数的定义、性质和基本运算规则。

作者 张洋 | 发布于 2013-06-05 | Tags 概率 统计 数学

时间序列分析基础

<摘要>: 时间序列是现实生活中经常会碰到的数据形式。例如北京市连续一年的日平均气温、某股票的股票价格、淘宝上某件商品的日销售件数等等。时间序列分析的的目的是挖掘时间序列中隐含的信息与模式,并借此对此序列数据进行评估以及对系列的后续走势进行预测。由于工作需要,我最近简单学习了时间序列分析相关的基础理论和应用方法,这篇文章可以看做是我的学习笔记。文章主要内容会首先描述时间序列分析的基本概念和相关的统计学基础理论,然后着重讲述十分经典和常用的ARIMA模型,在这之后会讲述季节ARIMA模型。由于打算以学习笔记的形式写这篇文章,所以我不会一下子写完整篇文章才发布,而是持续更新这篇文章,写的过程中也可能会对前面的内容进行修订。文章中会穿插许多实例(兼有模拟数据和数据分析),分析过程中将使用R为分析工具。

作者 张洋 | 发布于 2013-05-27 | Tags 数据挖掘 数据分析 时间序列 ARIMA R

算法分析中递推式的一般代数解法

<摘要>: 算法分析中经常遇到需要求解递推式的情况,即将递推式改写为等价的封闭形式。例如汉诺塔问题的时间复杂度递推形式为\(T(n)=2T(n-1)+1 \quad (n \geq 1)\),可以解出封闭形式为\(T(n)=2^n-1\)(设初始状态\(T(0)=0\))。因为递推式求解的重要性,许多算法书籍对其有专门介绍。Donald Knuth在Concrete Mathematics一书中多个章节都涉及递推式求解方法。算法导论也在第四章中专门论述的这个主题。在这些相关论述中,主要介绍了一些启发式方法,这些方法往往需要一些特殊的技巧和灵感才能完成。而本文将论述一种纯代数式的方法,这种方法将求解递推式转化为求解一个多项式的根和求解一组线性方程组,这样就使得整个求解过程不依赖于太多技巧,因此具有更好的易用性。本文首先会给出两个例子:如何使用纯代数方法求解斐波那契数列和汉诺塔递推式;然后会借助线性代数论述这种方法背后的数学意义,说明线性递推式与线性方程的内在联系以及这种解法的数学原理;最后将例子中的方法推广到一般情况。

作者 张洋 | 发布于 2013-03-17 | Tags 算法 数学 线性代数 递推式

为什么算法渐进复杂度中对数的底数总为2

<摘要>: 各种算法时,经常看到\(O(\log_2n)\)或\(O(n\log_2n)\)这样的渐进复杂度。不知有没有同学困惑过,为什么算法的渐进复杂度中的对数都是以2为底?为什么没有见过\(O(n\log_3n)\)这样的渐进复杂度?本文解释这个问题。

作者 张洋 | 发布于 2013-01-29 | Tags 算法 时间复杂度

解读Cardinality Estimation算法(第四部分:HyperLogLog Counting及Adaptive Counting)

<摘要>: 在前一篇文章中,我们了解了LogLog Counting。LLC算法的空间复杂度为\(O(log_2(log_2(N_{max})))\),并且具有较高的精度,因此非常适合用于大数据场景的基数估计。不过LLC也有自己的问题,就是当基数不太大时,估计值的误差会比较大。这主要是因为当基数不太大时,可能存在一些空桶,这些空桶的\(\rho_{max}\)为0。由于LLC的估计值依赖于各桶\(\rho_{max}\)的几何平均数,而几何平均数对于特殊值(这里就是指0)非常敏感,因此当存在一些空桶时,LLC的估计效果就变得较差。

作者 张洋 | 发布于 2013-01-09 | Tags 算法 基数估计 大数据 HyperLogLogCounting AdaptiveCounting

解读Cardinality Estimation算法(第三部分:LogLog Counting)

<摘要>: 上一篇文章介绍的Linear Counting算法相较于直接映射bitmap的方法能大大节省内存(大约只需后者1/10的内存),但毕竟只是一个常系数级的降低,空间复杂度仍然为\(O(N_{max})\)。而本文要介绍的LogLog Counting却只有\(O(log_2(log_2(N_{max})))\)。例如,假设基数的上限为1亿,原始bitmap方法需要12.5M内存,而LogLog Counting只需不到1K内存(640字节)就可以在标准误差不超过4%的精度下对基数进行估计,效果可谓十分惊人。

作者 张洋 | 发布于 2013-01-03 | Tags 算法 基数估计 大数据 LogLogCounting

解读Cardinality Estimation算法(第二部分:Linear Counting)

<摘要>: 在上一篇文章中,我们知道传统的精确基数计数算法在数据量大时会存在一定瓶颈,瓶颈主要来自于数据结构合并和内存使用两个方面。因此出现了很多基数估计的概率算法,这些算法虽然计算出的结果不是精确的,但误差可控,重要的是这些算法所使用的数据结构易于合并,同时比传统方法大大节省内存。

作者 张洋 | 发布于 2012-12-31 | Tags 算法 基数估计 大数据 LinearCounting

解读Cardinality Estimation算法(第一部分:基本概念)

<摘要>: 作为“解读Cardinality Estimation算法”系列文章的第一部分,本文将首先介绍基数的概念,然后通过一个电商数据分析的例子说明基数如何在具体业务场景中发挥作用以及为什么在大数据面前基数的计算是困难的,在这一部分也同时会详述传统基数计数的解决方案及遇到的难题。后面在第二部分-第四部分会分别详细介绍Linear Counting、LogLog Counting、HyperLogLog Counting及Adaptive Counting四个算法,会涉及算法的基本思路、概率分析及论文关键部分的解读。

作者 张洋 | 发布于 2012-12-30 | Tags 算法 基数估计 大数据

基数估计算法概览

<摘要>: 翻译自《Damn Cool Algorithms:Cardinality Estimation》,原文链接:http://blog.notdot.net/2012/09/Dam-Cool-Algorithms-Cardinality-Estimation

作者 张洋 | 发布于 2012-11-23 | Tags 基数估计 翻译

从抛硬币试验看概率论的基本内容及统计方法

<摘要>: 一般说到概率,就喜欢拿抛硬币做例子。大多数时候,会简单认为硬币正背面的概率各为二分之一,其实事情远没有这么简单。这篇文章会以抛硬币试验为例子并贯穿全文,引出一系列概率论和数理统计的基本内容。这篇文章会涉及的有古典概型、公理化概率、二项分布、正态分布、最大似然估计和假设检验等一系列内容。主要目的是以抛硬币试验为例说明现代数学观点下的概率是什么样子以及以概率论为基础的一些基本数理统计方法。

作者 张洋 | 发布于 2012-11-20 | Tags 概率 数理统计 数学

x86-64体系下一个奇怪问题的定位

<摘要>: 问题来源于一个朋友在百度的笔试题。上周六我一个朋友参加了百度举行的专场招聘会。当朋友参加完笔试和我聊起这道题时,我第一反应是这道题考察的是浮点数的内存表示,当然,在不同的CPU体系下,运行结果可能会有所不同,主要是受CPU位数和字节序的影响。

作者 张洋 | 发布于 2012-11-13 | Tags CPU 浮点数 汇编 x86

网站统计中的数据收集原理及实现

<摘要>: 网站数据统计分析工具是网站站长和运营人员经常使用的一种工具,比较常用的有谷歌分析、百度统计和腾讯分析等等。所有这些统计分析工具的第一步都是网站访问数据的收集。目前主流的数据收集方式基本都是基于javascript的。本文将简要分析这种数据收集的原理,并一步一步实际搭建一个实际的数据收集系统。

作者 张洋 | 发布于 2012-10-24 | Tags 网站统计 埋点 Web Openresty

聊聊如何检测素数

<摘要>: 最近看到一则颇为有趣的新闻,说北大一名大一新生,以素数为标准选手机号,受到广大网友膜拜。其实素数的检测算法是很有趣的,并且会涉及到数论、概率算法等诸多内容,一直觉得素数探测算法是了解概率算法很好的入口。本文和大家简单聊聊如何确定一个数是素数。

作者 张洋 | 发布于 2012-08-28 | Tags 素数 概率 数学

浅析PageRank算法

<摘要>: 本文首先会讨论搜索引擎的核心难题,同时讨论早期搜索引擎关于结果页面重要性评价算法的困境,借此引出PageRank产生的背景。第二部分会详细讨论PageRank的思想来源、基础框架,并结合互联网页面拓扑结构讨论PageRank处理Dead Ends及平滑化的方法。第三部分讨论Topic-Sensitive PageRank算法。最后将讨论对PageRank的Spam攻击方法:Spam Farm以及搜索引擎对Spam Farm的防御。

作者 张洋 | 发布于 2012-07-02 | Tags Google PageRank 搜索引擎 算法

发布一个查看PHP opcode的扩展模块及Web服务

<摘要>: 最近花了大约一星期的时间写了一个PHP扩展模块Opdumer,并封装成了Web服务。这个模块的主要内容是输出PHP代码对应的opcode。其实之前已经有一些用于查看opcode的扩展模块,如比较有名的vld。之所以重新实现一个这样的模块,主要是因为vld不支持PHP_FUNCTION API,也就是说vld只能用于CLI形式,而Opdumer同时拥有CLI API和PHP_FUNCTION API,另外,也想借助编写这个模块的机会学习Zend Engine中opcode的编译和执行机制。个人打算后面专门针对opcode的编译执行机制写一篇文章,而本文主要描述Opcode的使用方法及对应Web服务的使用。

作者 张洋 | 发布于 2012-05-16 | Tags PHP Opcode ZendEngine

PHP哈希表碰撞攻击原理

<摘要>: 最近哈希表碰撞攻击(Hashtable collisions as DOS attack)的话题不断被提起,各种语言纷纷中招。本文结合PHP内核源码,聊一聊这种攻击的原理及实现。

作者 张洋 | 发布于 2012-01-04 | Tags PHP 哈希碰撞 ZendEngine 数据结构

闭包漫谈(从抽象代数及函数式编程角度)

<摘要>: 如果Google一下“闭包”这个词,会发现网上关于闭包的文章已经不计其数,甚至很多人将闭包看做面试JavaScript程序员的必考题(虽然闭包和JavaScript没有什么必然联系)。既然如此,我为什么还要写一篇关于闭包的文章呢?首先,虽然网上关于闭包的文章甚多,但是很少以较为形式化的角度阐述闭包,而我认为理解闭包的关键之一就是从形式化角度理解其涵义;其次,大多数文章将闭包的概念与JavaScript语言绑定太死,这样容易局限对闭包概念的理解,而难以窥探到其本质。从JavaScript去理解闭包,个人认为这是本末倒置的,应该先理解纯粹意义上的闭包,然后再理解JavaScript中的闭包机制。基于以上情况,本文将从较为形式化的角度阐述闭包概念,当做对现有网络的资料的一个补充。

作者 张洋 | 发布于 2011-12-05 | Tags 闭包 Javascript Scheme

深入研究PHP及Zend Engine的线程安全模型

<摘要>: 在阅读PHP源码和学习PHP扩展开发的过程中,我接触到大量含有“TSRM”字眼的宏。通过查阅资料,知道这些宏与Zend的线程安全机制有关,而绝大多数资料中都建议按照既定规则使用这些宏就可以,而没有说明这些宏的具体作用。不知道怎么回事总是令人不舒服的,因此我通过阅读源码和查阅有限的资料简要了解一下相关机制,本文是我对研究内容的总结。本文首先解释了线程安全的概念及PHP中线程安全的背景,然后详细研究了PHP的线程安全机制ZTS(Zend Thread Safety)及具体的实现TSRM,研究内容包括相关数据结构、实现细节及运行机制,最后研究了Zend对于单线程和多线程环境的选择性编译问题。

作者 张洋 | 发布于 2011-11-04 | Tags PHP 线程安全 ZendEngine

如何使用PHP编写daemon process

<摘要>: 从php的架构体系来说,php分为三个层次:sapi、php core和zend engine。php core本身和web没有任何耦合,php通过sapi与其它应用程序通信,例如mod_php就是为apache编写的sapi实现,同样,fpm是一个基于fastcgi协议的sapi实现,这些sapi都是与web server配合用于处理web请求的。但是也有许多sapi与web无关,例如cli sapi可以使得在命令行环境下直接执行php,embed sapi可以将php嵌入其它语言(如Lua)那样。这里我并不打算详细讨论php的架构体系和sapi的话题,只是说明从架构体系角度目前的php早已被设计为支持各种环境,而非为web独有。除了架构体系的支持外,php丰富的扩展模块也为php在不同环境发挥作用提供了后盾,例如本文要提到的pcntl模块和posix模块配合可以实现基本的进程管理、信号处理等操作系统级别的功能,而sockets模块可以使php具有socket通信的能力。因此php完全可以用于编写类似于shell或perl常做的工具性脚本,甚至是具有server性质的daemon process。为了展示php如何编写daemon server,我用php编写了一个简单的http server,这个server以daemon process的形式运行。当然,为了把重点放在如何使用php编写daemon,我没有为这个http server实现具体业务逻辑,但它可以监听指定端口,接受http请求并返回给客户端一条固定的文本,整个过程通过socket实现,全部由php编写而成。

作者 张洋 | 发布于 2011-10-24 | Tags PHP Deamon

PHP Extension开发基础

<摘要>: PHP是当前应用非常广泛的一门语言,从国外的Facebook、Twitter到国内的淘宝、腾讯、百度再到互联网上林林总总的各种大中小型网站都能见到它的身影。PHP的成功,应该说很大程度上依赖于其开放的扩展API机制和丰富的扩展组件(PHP Extension),正是这些扩展组件使得PHP从各种数据库操作到XML、JSON、加密、文件处理、图形处理、Socket等领域无所不能。有时候开发人员可能需要开发自己的PHP扩展,当前PHP5的扩展机制是基于Zend API的,Zend API提供了丰富的接口和宏定义,加上一些实用工具,使得PHP扩展开发起来难度并不算特别大。本文将介绍关于PHP扩展组件开发的基本知识,并通过一个实例展示开发PHP扩展的基本过程。

作者 张洋 | 发布于 2011-10-21 | Tags PHP 系统扩展开发

使用memc-nginx和srcache-nginx模块构建高效透明的缓存机制

<摘要>: 为了提高性能,几乎所有互联网应用都有缓存机制,其中Memcache是使用非常广泛的一个分布式缓存系统。众所周知,LAMP是非常经典的Web架构方式,但是随着Nginx的成熟,越来越多的系统开始转型为LNMP(Linux+Nginx+MySQL+PHP with fpm),这是因为Nginx采用基于事件机制的I/O多路复用思想设计,在高并发情况下其性能远远优于默认采用prefork模式的Apache,另外,相对于Apache,Nginx更轻量,同时拥有大量优秀的扩展模块,使得在Nginx上可以实现一些美妙的功能。传统上,PHP中使用memcache的方法是使用php-memcache或php-memached扩展操作memcache,然而在Nginx上有构建更高效缓存机制的方法,本文将首先介绍这种机制,然后介绍具体的操作步骤方法,最后将对这种机制和传统的PHP操作memcache的性能进行一个benchmark。

作者 张洋 | 发布于 2011-10-18 | Tags Nginx Memcache 缓存 高性能 Openresty

MySQL索引背后的数据结构及算法原理

<摘要>: 本文以MySQL数据库为研究对象,讨论与数据库索引相关的一些话题。特别需要说明的是,MySQL支持诸多存储引擎,而各种存储引擎对索引的支持也各不相同,因此MySQL数据库支持多种索引类型,如BTree索引,哈希索引,全文索引等等。为了避免混乱,本文将只关注于BTree索引,因为这是平常使用MySQL时主要打交道的索引,至于哈希索引和全文索引本文暂不讨论。

作者 张洋 | 发布于 2011-10-18 | Tags MySQL 索引 B树 优化

一致性哈希算法及其在分布式系统中的应用

<摘要>: 本文将会从实际应用场景出发,介绍一致性哈希算法(Consistent Hashing)及其在分布式系统中的应用。首先本文会描述一个在日常开发中经常会遇到的问题场景,借此介绍一致性哈希算法以及这个算法如何解决此问题;接下来会对这个算法进行相对详细的描述,并讨论一些如虚拟节点等与此算法应用相关的话题。

作者 张洋 | 发布于 2011-10-18 | Tags 分布式 一致性哈希

Nginx模块开发入门

<摘要>: Nginx是当前最流行的HTTP Server之一,根据W3Techs的统计,目前世界排名(根据Alexa)前100万的网站中,Nginx的占有率为6.8%。与Apache相比,Nginx在高并发情况下具有巨大的性能优势。Nginx属于典型的微内核设计,其内核非常简洁和优雅,同时具有非常高的可扩展性。Nginx最初仅仅主要被用于做反向代理,后来随着HTTP核心的成熟和各种HTTP扩展模块的丰富,Nginx越来越多被用来取代Apache而单独承担HTTP Server的责任,例如目前淘宝内各个部门正越来越多使用Nginx取代Apache,据笔者了解,在腾讯和新浪等公司也存在类似情况。同时,大量的第三方扩展模块也令Nginx越来越强大。例如,由淘宝的工程师清无(王晓哲)和春来(章亦春)所开发的nginx_lua_module可以将Lua语言嵌入到Nginx配置中,从而利用Lua极大增强了Nginx本身的编程能力,甚至可以不用配合其它脚本语言(如PHP或Python等),只靠Nginx本身就可以实现复杂业务的处理。而春来所开发的ngx_openresty更是通过集成LuaJIT等组件,将Nginx本身变成了一个完全的应用开发平台。目前淘宝数据平台与产品部量子统计的产品都是基于ngx_openresty所开发。对ngxin_lua_module或ngx_openresty感兴趣的朋友可以参考我在关键词上给出的链接,后续我也可能会写一些与其有关的文章。本文将会重点关注Nginx模块开发入门及基础。目前Nginx的学习资料非常少,而扩展模块开发相关的资料几乎只有《Emiller's Guide To Nginx Module Development》一文,此文十分经典,但是由于Nginx版本的演进,其中少许内容可能有点过时。本文是笔者在研读这篇文章和Nginx源代码的基础上,对自己学习Nginx模块开发的一个总结。本文将通过一个完整的模块开发实例讲解Nginx模块开发的入门内容。

作者 张洋 | 发布于 2011-10-18 | Tags Nginx 系统扩展开发