murmur hash,一个更快的hash算法

在打算搭建memcache集群的时候,使用了crc3算法来对key进行hash,然而发现该算法性能比较低,于是寻找一个高性能,低碰撞的hash算,很高兴有前人已经为我们发明了这种算法——murmur。

MurmurHash算法:高运算性能,低碰撞率,由Austin Appleby创建于2008年,现已应用到Hadoop、libstdc++、nginx、libmemcached等开源系统。2011年 Appleby被Google雇佣,随后Google推出其变种的CityHash算法。

MurmurHash算法,自称超级快的hash算法,是FNV的4-5倍。官方数据如下:

OneAtATime – 354.163715 mb/sec
FNV – 443.668038 mb/sec
SuperFastHash – 985.335173 mb/sec
lookup3 – 988.080652 mb/sec
MurmurHash 1.0 – 1363.293480 mb/sec
MurmurHash 2.0 – 2056.885653 mb/sec

    //-----------------------------------------------------------------------------  
    // MurmurHash2, 64-bit versions, by Austin Appleby  
      
    // The same caveats as 32-bit MurmurHash2 apply here - beware of alignment   
    // and endian-ness issues if used across multiple platforms.  
      
    typedef unsigned long int uint64_t;  
      
    // 64-bit hash for 64-bit platforms  
    uint64_t MurmurHash64A ( const void * key, int len, unsigned int seed )  
    {  
            const uint64_t m = 0xc6a4a7935bd1e995;  
            const int r = 47;  
      
            uint64_t h = seed ^ (len * m);  
      
            const uint64_t * data = (const uint64_t *)key;  
            const uint64_t * end = data + (len/8);  
      
            while(data != end)  
            {  
                    uint64_t k = *data++;  
      
                    k *= m;   
                    k ^= k >> r;   
                    k *= m;   
      
                    h ^= k;  
                    h *= m;   
            }  
      
            const unsigned char * data2 = (const unsigned char*)data;  
      
            switch(len & 7)  
            {  
            case 7: h ^= uint64_t(data2[6]) << 48;  
            case 6: h ^= uint64_t(data2[5]) << 40;  
            case 5: h ^= uint64_t(data2[4]) << 32;  
            case 4: h ^= uint64_t(data2[3]) << 24;  
            case 3: h ^= uint64_t(data2[2]) << 16;  
            case 2: h ^= uint64_t(data2[1]) << 8;  
            case 1: h ^= uint64_t(data2[0]);  
                    h *= m;  
            };  
       
            h ^= h >> r;  
            h *= m;  
            h ^= h >> r;  
      
            return h;  
    }   
      
      
    // 64-bit hash for 32-bit platforms  
    uint64_t MurmurHash64B ( const void * key, int len, unsigned int seed )  
    {  
            const unsigned int m = 0x5bd1e995;  
            const int r = 24;  
      
            unsigned int h1 = seed ^ len;  
            unsigned int h2 = 0;  
      
            const unsigned int * data = (const unsigned int *)key;  
      
            while(len >= 8)  
            {  
                    unsigned int k1 = *data++;  
                    k1 *= m; k1 ^= k1 >> r; k1 *= m;  
                    h1 *= m; h1 ^= k1;  
                    len -= 4;  
      
                    unsigned int k2 = *data++;  
                    k2 *= m; k2 ^= k2 >> r; k2 *= m;  
                    h2 *= m; h2 ^= k2;  
                    len -= 4;  
            }  
      
            if(len >= 4)  
            {  
                    unsigned int k1 = *data++;  
                    k1 *= m; k1 ^= k1 >> r; k1 *= m;  
                    h1 *= m; h1 ^= k1;  
                    len -= 4;  
            }  
      
            switch(len)  
            {  
            case 3: h2 ^= ((unsigned char*)data)[2] << 16;  
            case 2: h2 ^= ((unsigned char*)data)[1] << 8;  
            case 1: h2 ^= ((unsigned char*)data)[0];  
                            h2 *= m;  
            };  
      
            h1 ^= h2 >> 18; h1 *= m;  
            h2 ^= h1 >> 22; h2 *= m;  
            h1 ^= h2 >> 17; h1 *= m;  
            h2 ^= h1 >> 19; h2 *= m;  
      
            uint64_t h = h1;  
      
            h = (h << 32) | h2;  
      
            return h;  
    }

php多进程编程:第一次fork

工作原因,要用到php多进程,于是粗略的了解一下,完成之后把过程记录下来,整理成教程,希望对学习php多进程编程的程序员有所帮助。

前言

使用php cli的时候,我们在终端会这样

php hello.php

运行一个hello.php程序,这样linux会为我们创建一个进程。不考虑 nohup ,在一个终端,我们以cli方式运行的php程序也只能有这一个进程。一个进程处理的任务必定是有限的,在系统资源空闲那么多的情况下,为什么不使用多进程来提高效率呢?

不过php多进程需要安装pcntl和posix扩展(windows不支持)

(更多…)

记录一下使用中PDO出现的一个问题:Cannot execute queries while other unbuffered queries are active. Consider using PDOStatement::fetchAll().

在使用PDO的时候,一条sql语句打死都不执行,dump一下errorInfo试试,出现这样的错误信息

问题描述

array(3) {
[0]=>
string(5) "HY000"
[1]=>
int(2014)
[2]=>
string(269) "Cannot execute queries while other unbuffered queries are active.  Consider using PDOStatement::fetchAll().  Alternatively, if your code is only ever going to run against mysql, you may enable query buffering by setting the PDO::MYSQL_ATTR_USE_BUFFERED_QUERY attribute."
}

居然告诉我还有语句没有执行完成?当前的查询未能执行,逗我么!考虑使用fetchAll,或者开启缓冲查询,行,你说得对….

问题出现的使用场景

服务器

服务器为linux,安装了一个什么面板套件之类的,不是自家机器,也懒得去折腾,在本地的windows环境并没有该问题。 (更多…)

redis的RDB文件存储结构分析

原文标题:15天玩转redis —— 第十一篇 让你彻底了解RDB存储结构

这里我们来继续分析一下RDB文件存储结构,首先大家都知道RDB文件是在redis的“快照”的模式下才会产生,那么如果我们理解了RDB文件的结构,是不是让我们对“快照”模式能做到一个心中有数呢?

一:RDB结构剖析

首先呢,我们要对RDB文件有一个概念性的认识,比如下面画的图一样:

214741-20151225090825265-774838214

 

从图中,我们大概看到了RDB文件的一个简要的存储模式,但为了更好的方便对照,我准备save一个empty database,对比一下看看效果:

(更多…)

c语言中的define用法

作为代码中,第一个看到的,极有可能就是define这个东西,称为宏!(define是可以出现在任何地方的,但是我们一般把这个写到最开始)然而,很多时候,初学者有时候可能看不懂她,因此,我的c语言学习的第一篇就写这个啦。

define基本用法,简单定义

最浅显的,define能用一个有含义的字符来替代一些数字,比如

#define PI 3.141592654

这样,假如以后要计算圆的周长或者面积,就可以用PI这个字符而不用写3.141592654啦。

比如

#define PI 3.141592654
#include "stdio.h"
int main(){
    int r = 3;
    float s;
    s = PI*r*r;
    printf("%f",s);
}

(更多…)

CGI与FastCGI是什么

当我们在谈到cgi的时候,我们在讨论什么

最早的Web服务器简单地响应浏览器发来的HTTP请求,并将存储在服务器上的HTML文件返回给浏览器,也就是静态html。事物总是不 断发展,网站也越来越复杂,所以出现动态技术。但是服务器并不能直接运行 php,asp这样的文件,自己不能做,外包给别人吧,但是要与第三做个约定,我给你什么,然后你给我什么,就是握把请求参数发送给你,然后我接收你的处 理结果给客户端。那这个约定就是 common gateway interface,简称cgi。这个协议可以用vb,c,php,python 来实现。cgi只是接口协议,根本不是什么语言。下面图可以看到流程

222132422994681 (更多…)

varnish安装:varnish如何安装

ubuntu中varnish的安装

varnish在Ubuntu package 仓库版本可能比较低,,我们一般建议使用varnish-cache.org提供的包。请注意,我们只为Ubuntu的LTS版本( Long Term Support,长时间支持版本,一般三年)提供安装包,其他中间版本并不提供。但这些版本也许会在较新的ubuntu版本中工作。varnish支持的架构是amd64。

使用root执行下面的代码安装varnish提供的最新版本

 apt-get install apt-transport-https
 curl https://repo.varnish-cache.org/GPG-key.txt | apt-key add -
 echo "deb https://repo.varnish-cache.org/ubuntu/ trusty varnish-4.1" >> /etc/apt/sources.list.d/varnish-cache.list
 apt-get update
 apt-get install varnish

(更多…)

varnish的基本工作原理

Varnish是一个HTPP反向代理缓存,它接受来自客户端的请求并试图从缓存中取出相应的数据来应答,如果缓存中并没有相应的数据,它将会把请求指向后端机器,获取并且储存响应的数据,之后再交付给用户。

当varnish有缓存的时候响应通常只需要几微秒的时间,比直接访问后端机器通常要快两个数量级,所以要做的就是尽可能的将页面缓存到varnish中。 (更多…)

XMLHttpRequest文档

XMLHttpRequest 是一个 JavaScript 对象,它最初由微软设计,随后被 Mozilla,Apple, 和 Google采纳. 如今,该对象已经被 W3C组织标准化. 通过它,你可以很容易的取回一个URL上的资源数据. 尽管名字里有XML, 但XMLHttpRequest 可以取回所有类型的数据资源,并不局限于XML. 而且除了HTTP ,它还支持fileftp 协议.

创建一个 XMLHttpRequest 实例, 可以使用如下语句:

var req = new XMLHttpRequest();

方法概述

void abort();
DOMString getAllResponseHeaders();
DOMString? getResponseHeader(DOMString header);
void open(DOMString method, DOMString url, optional boolean async, optional DOMString? user, optional DOMString? password);
void overrideMimeType(DOMString mime);
void send();
void send(ArrayBuffer data);
void send(Blob data);
void send(Document data);
void send(DOMString? data);
void send(FormData data);
void setRequestHeader(DOMString header, DOMString value);
非标准方法
[noscript] void init(in nsIPrincipal principal, in nsIScriptContext scriptContext, in nsPIDOMWindow ownerWindow);
[noscript] void openRequest(in AUTF8String method, in AUTF8String url, in boolean async, in AString user, in AString password);
void sendAsBinary(in DOMString body);

(更多…)

ajax的核心,好好认识一下XMLHttpRequest

相信包括在我的绝大多数人都用jQuery的$.get(),$.post(),$.ajax()方法用的很爽了,关于其原生的请求却很少去发掘,很多时候(比如用html5开发app的时候),我并不再需要jQuery,弄明白XMLHttpRequest用原生的就能很好的处理ajax了。

首先,由于我的js是通过jQuery入门的,所以才会有这篇文章。

从new一个对象开始

var xmlhttp = new XMLHttpRequest();

之后的请求,读取,出错等等各种处理都在xmlhttp这个对象里面啦

(更多…)