植臻

植臻

谦虚、热情、简单、极致

植臻

平方根倒数快算法

| Comments


在计算机图形学领域,若要求取照明和投影的波动角度与反射效果,就常需计算平方根倒数。而浮点求平方根倒数运算带来的耗费巨大。

第一人称射击游戏 OpenArena

起源

此算法最早被认为是由约翰·卡马克所发明,但后来的调查显示,该算法在这之前就于计算机图形学的硬件与软件领域有所应用,如SGI和3dfx就曾在产品中应用此算法。而就现在所知,此算法最早由加里·塔罗利(Gary Tarolli)在SGI Indigo的开发中使用。虽说随后的相关研究也提出了一些可能的来源,但至今为止仍未能确切知晓算法中所使用的特殊常数的起源。

下列代码是《雷神之锤III竞技场》源代码中平方根倒数速算法之实例。示例去除了C预处理器的指令,但附上了原有的注释:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
float Q_rsqrt( float number )
{
    long i;
    float x2, y;
    const float threehalfs = 1.5F;

    x2 = number * 0.5F;
    y  = number;
    i  = * ( long * ) &y;                  // evil floating point bit level hacking(对浮点数的邪恶位元hack)
    i  = 0x5f3759df - ( i >> 1 );               // what the fuck?(这他妈的是怎么回事?)
    y  = * ( float * ) &i;
    y  = y * ( threehalfs - ( x2 * y * y ) );   // 1st iteration (第一次迭代)
//      y  = y * ( threehalfs - ( x2 * y * y ) ); // 2nd iteration, this can be removed(第二次迭代,可以删除)

    return y;
}

要理解这段代码,首先需了解浮点数的存储格式。一个浮点数以32个二进制位表示,而这32位由其意义分为三段:1个符号位,如若是0则为正数,反之为负数;接下来的8位表示经过[偏移处理](这是为了使之能表示-127-128)后的指数;最后23位表示的则是[有效数字]中除最高位以外的其余数字。如图:

Float w significand.svg

将上述结构表示成公式即为

其中偏移量$B=127$,$m$表示有效数字的尾数($0<m<1$),而指数$E-B$的值决定了有效数字(在Lomont和McEniry的论文中称为“尾数”(mantissa))代表的是小数还是整数。以上图为例,将描述代入有$m=1\times2^{-2}=0.250$),且$E-B=124-127=-3$,则可得其表示的浮点数为$x=(1+0.250)\cdot2^{-3}=0.15625$。

符号位                  
0 1 1 1 1 1 1 1 = 127
0 0 0 0 0 0 1 0 = 2
0 0 0 0 0 0 0 1 = 1
0 0 0 0 0 0 0 0 = 0
1 1 1 1 1 1 1 1 = −1
1 1 1 1 1 1 1 0 = −2
1 0 0 0 0 0 0 1 = −127
1 0 0 0 0 0 0 0 = −128

8位二进制整数补码示例
如上所述,一个有符号正整数在二进制补码系统中的表示中首位为0,而后面的各位则用于表示其数值。将浮点数取别名存储为整数时,该整数的数值即为$I=E\times 2^{23}+M$,其中E表示指数,M表示有效数字;若以上图为例,图中样例若作为浮点数看待有$E=124$,$M=1\cdot 2^{21}$,则易知其转化而得的整数型号数值为$I=124\times 2^{23} + 2^{21}$。由于平方根倒数函数仅能处理正数,因此浮点数的符号位(即如上的Si)必为0,而这就保证了转换所得的有符号整数也必为正数。以上转换就为后面的计算带来了可行性,之后的第一步操作(逻辑右移一位)即是使该数的长整形式被2所除。

魔术数字

对猜测平方根倒数速算法的最初构想来说,计算首次近似值所使用的常数0x5f3759df也是重要的线索。为确定程序员最初选此常数以近似求取平方根倒数的方法,Charles McEniry首先检验了在代码中选择任意常数R所求取出的首次近似值的精度。回想上一节关于整数和浮点数表示的比较:对于同样的32位二进制数字,若为浮点数表示时实际数值为$x=(1+m_x)2^{e_x}$,而若为整数表示时实际数值则为$I_x=E_xL+M_x$,其中$L=2^{n-1-b}$。以下等式引入了一些由指数和有效数字导出的新元素:

再继续看McEniry 2007里的进一步说明: $$ y=\frac{1}{\sqrt{x}} $$

对等式的两边取二进制对数($\log _{2}$,即函数$f(n)=2^{n}$的反函数,有

以如上方法,就能将浮点数x和y的相关指数消去,从而将乘方运算化为加法运算。而由于$\log_{2}{x}$ 与$\log2(x^{-1/2})$线性相关,因此在$x$与$y{0}$(即输入值与首次近似值)间就可以线性组合的方式创建方程。在此McEniry再度引入新数$\sigma$描述$\log {2}{(1+x)}$与近似值R间的误差:由于$0\leq x<1$,有$\log{2}(1+x)\approx x$,则在此可定义$\sigma $与x的关系为$\log {2}{(1+x)}\cong x+\sigma $,这一定义就能提供二进制对数的首次精度值(此处$0\leq \sigma \leq {\tfrac {1}{3}}$;当R为0x5f3759df时,有$\sigma =0.0450461875791687011756$。由此将$\log {2}{(1+x)}=x+\sigma$代入上式,有: $$ m_y+\sigma+e_y=-\frac{1}{2}m_x-\frac{1}{2}\sigma-\frac{1}{2}e_x $$

参照首段等式代入$M{x}$,$E{x}$,$B$与$L$,有:

移项整理得: $$ E_yL+M_y=\frac{3}{2}(B-\sigma)L-\frac{1}{2}(E_xL+M_x) $$

如上所述,对于以浮点规格存储的正浮点数x,若将其作为长整型表示则示值为$I{x}=E{x}L+M_{x}$,由此即可根据x的整数表示导出y(在此$y={\frac {1}{\sqrt {x}}}$,亦即x的平方根倒数的首次近似值)的整数表示值,也即: $$ I_y=E_yL+M_y=R-\frac{1}{2}(E_xL+M_x)=R-\frac{1}{2}I_x $$

最后导出的等式$I{y}=R-{\frac {1}{2}}I{x}$即与上节代码中i = 0x5f3759df - (i»1);一行相契合,由此可见,在平方根倒数速算法中,对浮点数进行一次移位操作与整数减法,就可以可靠地输出一个浮点数的对应近似值。到此为止,McEniry只证明了,在常数R的辅助下,可近似求取浮点数的平方根倒数,但仍未能确定代码中的R值的选取方法。

关于作一次移位与减法操作以使浮点数的指数被-2除的原理,Chris Lomont的论文中亦有个相对简单的解释:以$10000=10^{4}$为例,将其指数除-2可得$10000^{-1/2}=10^{-2}=1/100$;而由于浮点表示的指数有进行过偏移处理,所以指数的真实值e应为$e=E-127$,因此可知除法操作的实际结果为$-e/2+127$,这时用R(在此即为“魔术数字”0x5f3759df)减之即可使指数的最低有效数字转入有效数字域,之后重新转换为浮点数时,就能得到相当精确的平方根倒数近似值。在这里对常数R的选取亦有所讲究,若能选取一个好的R值,便可减少对指数进行除法与对有效数字域进行移位时可能产生的错误。基于这一标准,0xbe即是最合适的R值,而0xbe右移一位即可得到0x5f,这恰是魔术数字R的第一个字节。

Cocos2dx Shader 描边

| Comments

Cocos2d-x 3.x的label使用了freetype字体引擎(http://www.freetype.org/),可以很轻松的实现描边和阴影效果。所以本篇文章只针对于sprite来实现描边效果。

官方demo中描边shader没有看懂,看效果好像是有点问题,透明的部分变成了黑色。作者也没有怎么解释,直接丢了一个网址出来(http://www.idevgames.com/forums/thread-3010.html),看样子是参考了这个帖子。

后来从网上别人的博客中找到了一遍关于描边shader的文章,这篇文章用的方法跟我想的差不多,优点是很容易理解,缺点是相对于官方demo给的描边shader效率上差了点。原文地址:http://blog.csdn.net/u011281572/article/details/44999609

原文的代码考虑了label的描边,这个对于现在的cocos3.x版本来说有点多余,我就对原文的代码做了些改动,去掉了label描边的那块儿代码,有些逻辑也做了一些改变,使得更容易理解一些。

下面是我改动后的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
varying vec4 v_fragmentColor; // vertex shader传入,setColor设置的颜色
varying vec2 v_texCoord; // 纹理坐标
uniform float outlineSize; // 描边宽度,以像素为单位
uniform vec3 outlineColor; // 描边颜色
uniform vec2 textureSize; // 纹理大小(宽和高),为了计算周围各点的纹理坐标,必须传入它,因为纹理坐标范围是0~1

// 判断在这个角度上距离为outlineSize那一点是不是透明int getIsStrokeWithAngel(float angel){
int stroke = 0;
float rad = angel * 0.01745329252; // 这个浮点数是 pi / 180,角度转弧度
vec2 unit = 1.0 / textureSize.xy;//单位坐标
vec2 offset = vec2(outlineSize * cos(rad) * unit.x, outlineSize * sin(rad) * unit.y); //偏移量
float a = texture2D(CC_Texture0, v_texCoord + offset).a;
if (a >= 0.5)// 我把alpha值大于0.5都视为不透明,小于0.5都视为透明
{
stroke = 1;
}
return stroke;
}

void main(){
vec4 myC = texture2D(CC_Texture0, v_texCoord); // 正在处理的这个像素点的颜色
if (myC.a >= 0.5) // 不透明,不管,直接返回
{
gl_FragColor = v_fragmentColor * myC;
return;
}
// 这里肯定有朋友会问,一个for循环就搞定啦,怎么这么麻烦!其实我一开始也是用for的,但后来在安卓某些机型(如小米4)会直接崩溃,查找资料发现OpenGL es并不是很支持循环,while和for都不要用
int strokeCount = 0;
strokeCount += getIsStrokeWithAngel(0.0);
strokeCount += getIsStrokeWithAngel(30.0);
strokeCount += getIsStrokeWithAngel(60.0);
strokeCount += getIsStrokeWithAngel(90.0);
strokeCount += getIsStrokeWithAngel(120.0);
strokeCount += getIsStrokeWithAngel(150.0);
strokeCount += getIsStrokeWithAngel(180.0);
strokeCount += getIsStrokeWithAngel(210.0);
strokeCount += getIsStrokeWithAngel(240.0);
strokeCount += getIsStrokeWithAngel(270.0);
strokeCount += getIsStrokeWithAngel(300.0);
strokeCount += getIsStrokeWithAngel(330.0);

if (strokeCount > 0) // 四周围至少有一个点是不透明的,这个点要设成描边颜色
{
myC.rgb = outlineColor;
myC.a = 1.0;
}

gl_FragColor = v_fragmentColor * myC;
}

大致的逻辑是:

先判断当前像素是否透明,如果不透明则直接返回。如果是透明像素,就判断这个点周围12个方向,每个方向距离当前像素距离是outlineSize的像素点是否透明,只要有一个是非透明像素,就把当前像素点设为描边的颜色,并设置成非透明。

效果如下:

Cocos2dx Shader 模糊

| Comments

模糊效果在游戏中经常会用到,有的为了突出前景会把背景给模糊化,有的是因为一些技能需要模糊效果。模糊是shader中较为简单的一种应用。cocos2dx 3.x给的demo中,就有sprite的模糊的效果。

先说下这个模糊算法的大致思路,我们在片段着色器中可以得到当前像素点的颜色值,要想让这个颜色变得模糊,就要让它与它周围的像素点的颜色稍微接近一点,那么我们就需要拿到这个像素点周围的像素点的颜色值,我们把这些个像素点的值加起来取平均值,就得到了一个区域内的平均颜色。

如果直接使用这个颜色的话,最终的效果会变得很模糊,如果我们只是想稍微模糊一点的话,就要让这个平均值更接近于当前像素点原本的颜色,为此,我们取均值的时候对每个像素点增加了一个权重的定义,当前像素点的权重最高,依次向周围减弱,使得最后得到的均值的颜色更接近于当前像素点原始的颜色。

看代码: <div class=’bogus-wrapper’>

<div class=”highlight”><table><tr><td class=”gutter”><pre class=”line-numbers”>1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 </pre></td><td class=’code’><pre>#ifdef GL_ES precision mediump float; #endif varying vec4 v_fragmentColor; varying vec2 v_texCoord; uniform vec2 resolution;//模糊对象的实际分辨率 uniform float blurRadius;//半径 uniform float sampleNum;//间隔的段数 vec4 blur(vec2); void main(void){ vec4 col = blur(v_texCoord); //* v_fragmentColor.rgb; gl_FragColor = vec4(col) * v_fragmentColor; } vec4 blur(vec2 p){ if (blurRadius > 0.0 && sampleNum > 1.0) { vec4 col = vec4(0); vec2 unit = 1.0 / resolution.xy;//单位坐标 float r = blurRadius; float sampleStep = r / sampleNum; float count = 0.0; //遍历一个矩形,当前的坐标为中心点,遍历矩形中每个像素点的颜色 for(float x = -r; x < r; x += sampleStep) { for(float y = -r; y < r; y += sampleStep) { float weight = (r - abs(x)) * (r - abs(y));//权重,p点的权重最高,向四周依次减少 col += texture2D(CC_Texture0, p + vec2(x * unit.x, y * unit.y)) * weight; count += weight; } } //得到实际模糊颜色的值 return col / count; } return texture2D(CC_Texture0, p); }</pre></td></tr></table></div>
</div>

精度限定符和varying变量等的一些基础的知识在前面的博客中遇到的已经说过。

uniform变量是顶点着色器和片段着色器共享使用的变量,uniform的值不能被改变。

uniform变量是由宿主程序设置的,代码如下:

1
2
3
4
5
6
7
8
9
 void EffectBlur::setTarget(EffectSprite *sprite)
{
Size size = sprite->getTexture()->getContentSizeInPixels();
_glprogramstate->setUniformVec2("resolution", size);
#if (CC_TARGET_PLATFORM != CC_PLATFORM_WINRT)
_glprogramstate->setUniformFloat("blurRadius", _blurRadius);
_glprogramstate->setUniformFloat("sampleNum", _blurSampleNum);
#endif
}

这里宿主程序设置了resolution,blurRadius和sampleNum三个uniform变量。渲染的时候,顶点着色器和片段着色器都可以用到这三个变量的值。

resolution是当前渲染node的实际分辨率。

blurRadius是像素点模糊处理的参考矩形的半径

sampleNum选择像素点的间隔的数量,相邻像素点的间距等于blurRadius / sampleNum

blur函数就是计算该像素点的最终颜色,参数p是当前像素点的坐标,我们以p点为中点以2r为边长得到一个矩形,这个矩形中每隔sampleStep长度的像素点是当前像素点的颜色参考像素。每个像素点会乘以一个weight权重,这个weight越靠近p点值越高,目的是为了让最终的值更接近于p点的像素颜色,然后各个像素点乘以权重后的颜色加起来,得到col,把各个权重也加起来得到count。最终的颜色值就是col/count。

效果图如下:

模糊前后:

Cocos2dx Shader 变灰

| Comments

### 灰度shader

最近在学习shader,就把cocos2d-x 3.x版本中的很简单也很常用的灰度shader拿出来学习一下。 <div class=’bogus-wrapper’>

<div class=”highlight”><table><tr><td class=”gutter”><pre class=”line-numbers”>1 2 3 4 5 6 7 8 9 10 11 12 </pre></td><td class=’code’><pre>#ifdef GL_ES precision mediump float; // ES版本的精度限定符,精度变低后可以提高效率#endif varying vec4 v_fragmentColor; varying vec2 v_texCoord; void main(void) vec4 c = texture2D(CC_Texture0, v_texCoord); gl_FragColor.xyz = vec3(0.2126*c.r + 0.7152*c.g + 0.0722*c.b); gl_FragColor.w = c.w; }</pre></td></tr></table></div>
</div> ### 代码分析

precision mediump float是open es特有的精度限定符,原本的浮点数精度是double,opengl es为了提高渲染效率,限定精度为float类型。

v_fragmentColor是从顶点着色器设置的颜色经过光栅化阶段的线性插值后传给片段着色器的颜色。

v_texCoord同样是经过线性插值而来的纹理坐标。

CC_Texture0是一个采样器,在load shader的时候,引擎会预先把这些uniform变量给加载进来。

下面这部分代码就是引擎预先加载进来的uniform变量: <div class=’bogus-wrapper’>

<div class=”highlight”><table><tr><td class=”gutter”><pre class=”line-numbers”>1 2 3 4 5 6 7 8 9 10 11 12 13 14 </pre></td><td class=’code’><pre>static const char * COCOS2D_SHADER_UNIFORMS = "uniform mat4 CC_PMatrix;\n" "uniform mat4 CC_MVMatrix;\n" "uniform mat4 CC_MVPMatrix;\n" "uniform mat3 CC_NormalMatrix;\n" "uniform vec4 CC_Time;\n" "uniform vec4 CC_SinTime;\n" "uniform vec4 CC_CosTime;\n" "uniform vec4 CC_Random01;\n" "uniform sampler2D CC_Texture0;\n" "uniform sampler2D CC_Texture1;\n" "uniform sampler2D CC_Texture2;\n" "uniform sampler2D CC_Texture3;\n" "//CC INCLUDES END\n\n"; </pre></td></tr></table></div>
</div>

这些变量在shader里面如果没有用到的话,会被引擎给优化掉。

texture2D()是shader的内建方法,作用是从CC_Texture0采样器中进行纹理采样,得到当前片段的颜色值。

gl_FragColor是shader的内建变量,表示当前片段的颜色,代码中是把从采样器中拿到的颜色值进行一个变灰处理后,最后得到的颜色值再赋值给gl_FragColor。gl_FragColor就是最终的颜色。

这个shader很简单,就是改变了一下rgb的值。0.2126,0.7152,0.0722这几个系数据说是根据人眼对rgb这三种基本颜色识别的强弱算出来的。

使用示例

在cocos2dx 3.x版本中sprite变灰的代码例子: <div class=’bogus-wrapper’>

<div class=”highlight”><table><tr><td class=”gutter”><pre class=”line-numbers”>1 2 </pre></td><td class=’code’><pre>auto sprite = Sprite::create("HelloWorld.png"); sprite->setGLProgramState(GLProgramState::getOrCreateWithGLProgramName(GLProgram::SHADER_NAME_POSITION_GRAYSCALE));</pre></td></tr></table></div>
</div> 效果如下图所示:

渲染流水线(render Flow)

| Comments

概念

渲染流水线的工作任务是由一个三维场景出发、生成(或者说渲染)一张二维图像。 –冯乐乐《unity3d shader 入门精要》

这是一个比较标准的说法,因为不一定是渲染到显示器上,也有可能把渲染结果保存到一个Texture中,就是我们常说的RenderTarget。

阶段

渲染流水线可以分为三个阶段:应用阶段、几何阶段、光栅化阶段

  • 应用阶段(CPU处理)

    这一阶段开发者需要准备好场景数据,如摄相机位置、视锥体、模型和光源等,接着,还需要做粗粒度的剔除工作(把看不见的物体剔除) 最后,需要设置好每个模型的渲染状态(使用的材质、使用的纹理、使用的Shader等) 这一阶段最重要的输出是渲染所需的几何信息,即渲染图元(rendering primitives),渲染图元可以是点、线、三角面等。

  • 几何阶段(GPU处理)

    几何阶段主要用于处理所有和我们绘制的几何相关的事情。几何阶段负责和每个渲染图元打交道,进行逐顶点、逐多边形的操作。这个阶段可以进一步分成更小的流水线阶段。 几何阶段的一个重要任务就是把顶点坐标变换到屏幕空间中,再交给光栅器进行处理。 总结:输入的渲染图元->屏幕空间的二维顶点坐标、每个顶点对应深度、着色等信息

**注意,这里是裁剪(clipping),CPU里面有做剔除(culling) **

  • 光栅化阶段(GPU处理)

    将会使用上一个阶段传递的数据来产生屏幕上的像素,并渲染出最终的图像。主要任务是决定每个渲染图元中的哪些像素应该被绘制在屏幕上。

总结

### 1.OpenGL和DirectX

开发者直接访问GPU是一件非常麻烦的事情,可能需要与各种寄存器、显存打交道,而图像编程接口在这些硬件的基础上实现了一层抽象。

而OpenGL和DirectX就是这些图像应用编程接口,他们之间江湖恩怨,可以去看这篇文章。这些接口架起了上层应用程序与底层GPU的沟通桥梁。上层应用程序向这些接口渲染命令,而这些接口会依次向显示驱动发送渲染命令,而显卡驱动会把这些命令翻译成GPU能听懂的语言来让他们进行工作。
### 2.HLSL、GLSL和CG

这三个指的都是着色器的编程语言。

HLSL:High Level Shading Language,DirectX的着色器语言,由微软控制着色器的编译,就算使用了不同的硬件,其编译结果也是一样的,其使用的平台比较局限,几乎都是微软自己的产品,如Windows、Xbox 360等

GLSL:OpenGL Shading Language,OpenGL的着色器语言,优点在于其跨平台性,可以在Windows、Mac、Linux甚至移动平台使用,这种跨平台性是由于OpenGL没有提供着色器编译器,而是由显卡驱动来完成着色器的编译工作的。即只要显示驱动支持对GLSL的编译它就可以运行。

CG:C for Graphics,NVIDIA的着色器语言,实现了真正意义上的跨平台,它会根据平台不同,编译成相应的中间语言。

3.Draw Call

Draw Call本身的意义很简单,就是CPU调用图像编程接口。

1.CPU和GPU是如何实现并行工作的?

主要的解决方案是命令缓冲区,命令缓冲区包含了一个命令队列,由CPU向其中添加命令,而由GPU从中读取命令,添加和读取的过程是独立的。这样使得CPU和GPU可以相互独立工作。当CPU需要渲染对象时,则向命令缓冲区中添加命令,而当GPU完成上一次渲染任务后,它就可以从命令队列中取出一个命令并执行它。

2.为什么Draw Call多了会影响帧率?

在每次调用Draw Call之间,CPU需要向GPU发送很多内容,包括数据、状态和命令。CPU需要完成很多工作,例如检查渲染状态等。而一旦CPU完成了这些准备工作,GPU就可以开始本次的渲染。GPU渲染的速度是比较CPU提交指令的速度要快很多的。所以性能的瓶颈会出现在CPU身上,如果Draw Call的数量太多,CPU就会把大量的时间花费在提交Draw Call上,造成CPU过载。

3.如何减少Draw Call?

主要的解决方案是批处理(Batch),把众多小的合并Draw Call合并成一个Draw Call,当然不是所有情况都能合并的。我们可以对网格进行合并,但是合并的过程是比较消耗时间的,因此批处理技术更适合于静态的网格。

合并需要注意的点:

避免使用大量很小的网格,当不可避免的要使用这些这么小的网格时,考虑是否可以合并他们。

避免使用过多的材质,因为相同的材质会方便我们进行合并

4.什么是固定函数的流水线?

简称固定管线,通常是指在旧GPU上实现的渲染流水线。开发者没有对流水线完全控制权,只有一些配置操作,配置操作只有开和关

全球同服游戏的数据库层怎么设计

| Comments


我们要做一个牛逼的产品!

老大最近说公司要做一款百万级DAU的产品,考虑服务器端承对数据库的读写压力,需要一个数据库的优化方案。有一同事说准备用mnesia分布式,然后问我们会不会有性能问题,仔细思考了一下,感觉这位同学并没有找准解决方向。

数据库集群解决什么问题

并行数据库系统的目标是充分发挥并行计算机的优势,利用系统中的各个处理机结点并行完成数据库任务,提高数据库系统的整体性能。

分布式数据库解决什么问题

分布式数据库系统主要目的在于实现场地自治和数据的全局透明共享,而不要求利用网络中的各个结点来提高系统处理性能。


mnesia的分布式是提供了一个分布式数据库的解决方案,然而他并不适用于解决百万级用户量数据库读写的性能问题。所以说,那位同学没有找到解决问题的方向。

简单了解一下mnesia的分布式

  • 适用范围:
    较低负载情况下,需要全局透明的数据,比如全局排行榜之类的数据。
  • 优势:
    erlang原生支持,使用方便,开发速度较快,问题容易排查。
  • 问题:
    mnesia分布式是一个全联通网络,节点间通信成本与节点关系是:
    n(n-1)/2,一旦数据量大,节点多,IO通信压力巨大。

实例:

-module(db_sync).

-export([create_schema/0, create_table/0, i/0]).
-export([add_account/3, del_account/1,
        read_account/1]).

-record(account, {id = 0, name = "", phone =
        13800000000}).

create_schema() ->
net_kernel:connect('two@MacAir'),
io:format("Self:~w, Connect
        Nodes:~w",[node(),
        nodes()]),
mnesia:create_schema([node()|nodes()]).

create_table() ->
    mnesia:create_table(account,
            [{disc_copies, [node()|nodes()]},
            {attributes,
            record_info(fields,
                account)}]
            ).

i() ->
mnesia:system_info().

add_account(ID, Name, Phone) ->
mnesia:transaction(fun() ->
        mnesia:write(#account{id
            = ID, name
            = Name,
            phone =
            Phone})
        end).

del_account(ID) ->
    mnesia:transaction(fun() ->
            mnesia:delete({account,
                ID})
            end).

read_account(ID) ->
    mnesia:transaction(fun()
            ->
            mnesia:read({account,
                ID})
            end). xterm1中  
erl -pa ebin -sname two -mnesia dir "two" xterm2中
erl -pa
ebin -sname one -mnesia dir "one"
db_sync:create_schema(). xterm1,xterm2中分别:
mnesia:start(). 任意节点创建表:
db_sync:create_table(). one节点插入数据:
db_sync:add_account(2, "zhizhen", 18588748984). two节点查找数据:
db_sync:read_account(2). 这就是mnesia的分布式全联通节点,它已经在底层把数据同步了。在应用层面,就比较简单了。所以说,它解决的,是一个数据节点共享的问题。mnesia分布式甚至对节点间底层通信带宽要求很高,分布式节点最好处于同一机房内。

那么百万级DAU的数据库怎么设计呢?

答案是水平分片(sharding) + 垂直分片,我们今天重点讲水平分片。

  • 适用范围: 百万级甚至千万级大数据情况通用解决方案 表的查询方式单一简单,最好是有唯一主键查询 不做联表事务查询
  • 问题: 如果有事务的话,涉及到分布式事务,是非常复杂的

简单的水平切分,hash

我们一般将大表的唯一键值作为hash的key,比如我们如果准备拆分一张3千万数据的表,做完hash之后,分插入3个分片(sharding)中。 simple_hash(Item) -> case Item rem 3 of 0 -> %insert data into user_table (ip:127.0.0.1) 1 -> %insert data into user_table (ip:127.0.0.2) 2 -> %insert data into user_table (ip:127.0.0.3) end.

这时候,随着业务的增长,如果数据涨到5千万了,慢慢地发现3个sharding已经不能满足我们的需求了,这个时候,如果打算再增加两个sharding,我们需要怎么做呢?
这个时候我们需要根据新的hash规则把数据重新导入到5个sharding中,几乎5千万行数据都要移动一遍。假设mysql美秒钟的插入速度快达2000/s,即使这样的速度,也要让服务暂停8个小时左右。这个时候DBA肯定会跟你急的,因为他需要通宵导数据。
那有没有一种更好的办法,降低增加分片的成本呢?

一致性hash

借用David Wheeler一句名言:
>All problems in computer science can be solved by another level of indirection.

是的,任何计算机相关的问题,都可以通过增加一层来解决。一致性hash就是实现了这个虚拟层。erlang一个一致性hash的开源实现:hash_ring
有了hash_ring 之后,增加2个sharding就比较简单了,下面部分是伪代码:

-module(hash).
-compile(export_all).

-define(PRINT(I, P), io:format(I, P)).

start() ->
    Nodes = hash_ring:list_to_nodes([
            '127.0.0.1', 
            '127.0.0.2',
            '127.0.0.3'
        ]),
    Ring0 = hash_ring:make(Nodes),
    erlang:put(ring, Ring0).

get_nodes() ->
    Ring = erlang:get(ring),
    hash_ring:get_nodes(Ring).

add_node(Name) ->
    Ring0 = erlang:get(ring),
    Ring1 = hash_ring:add_node(hash_ring_node:make(Name), Ring0),
    erlang:put(ring, Ring1),
    %%新添加node时,对数据进行移动
    Fun = fun(I) ->
            OldServer = hash_ring:collect_nodes(I, 1, Ring0),
            NewServer = hash_ring:collect_nodes(I, 1, Ring1),
            if OldServer =/= NewServer ->
                    %todo delete data from old server
                    %todo insert data into new server
                    todo;
                true ->
                    todo
            end
    end,
    lists:foreach(Fun, lists:seq(1, 5000)).

insert(Item) ->
    Ring0 = erlang:get(ring),
    [Node] = hash_ring:collect_nodes(Item, 1, Ring0),
    ?PRINT("insert ~p into node ~p ~n", [Item, Node]).

simple_hash(Item) ->
    case Item rem 3 of
        0 -> 
            %insert data into user_table (user table 0 ip:127.0.0.1)
            todo;
        1 -> 
            %insert data into user_table (user table 1 ip:127.0.0.2)
            todo;
        2 ->
            %insert data into user_table (user table 2 ip:127.0.0.3)
            todo
    end.

这样的话,增加2个sharding之后,只需要移动2千万条数据到新的sharding上即可。

参考文章

以此为起点

| Comments


There are some birds that you can’t lock,their every feather on their body is sparkling with freedom –《The Shawshank Redemption》


来自《创游记》。

我与街机

| Comments


The farther backward you can look, the farther forward you will see.
——Winston Churchill


不知道该从哪写起,真的忘了从哪开始,但是记得清楚,自那之后,一切都变了
某一天,拿着零花钱去买冰棒,要是当初,把钱买了冰棒。。。。。。

Erlang-mysql-driver

| Comments

历史

erlang-mysql-driver 是Yariv Sadan 从Yxa这个数据库引擎的ejabberd这个分支里fork出来的一个项目,他(Yariv Sadan)把它做成了一个独立项目,并给他起了一个高大上的名字。之后便挂在Google Code 上。

在Yariv Sadan去Facebook工作之前,他给加上了高级的prepared statements 和transactions 机制。并且修复了Yxa 版本之前落后的连接池问题。