高可用

Posted on 2019-11-23

什么是`高可用`

先逛一逛百科和博客……

高可用通常是指，通过设计减少系统不能提供服务的时间。
高可用通常来描述一个系统经过专门的设计，从而减少停工时间，而保持其服务的高度可用性。
高可用指系统无中断地执行其功能的能力，代表系統的可用性程度。

定义什么的就这样吧……

核心准则

看到一篇文章的作者总结得很好（究竟啥才是互联网架构“高可用”）：

保证系统高可用，架构设计的核心准则是：冗余

想想其实也挺好理解，如果运行一个系统的资源是冗余的，那就更能应对突发的情况，如：流量激增、部分服务故障、电缆被砍等。

所以当我们看到一个产品、或系统、或服务说自己是高可用时，就可以留意它在哪些资源上做了冗余，而这些冗余能抵御的又是哪些故障。

容错机制

即使系统的资源是冗余的，也还是需要一定的手段或说机制，来保证系统的高可用运作起来

自动侦查（Auto-Detect）

就是系统要能监控资源的可用情况，那系统又是如何进行监控？定时检查？以任务执行状态判断？
自动切换（Auto-Switch）

就是系统检测到存在资源不可用时，该如何用上其冗余的资源？
自动恢复（Auto-Recovery）

就是在故障资源修复完成后，如何通知系统重新用上该资源？
其它

觉得还有许多其它的机制也可以为高可用服务：扩容、缩容、重载、降级、削锋……

工作方式

百度百科有一段介绍高可用的“工作方式”，但我想这一块应该主要是想探讨系统的各资源之间可能存在的关系：

主从（非对称）

主资源工作，冗余资源处于监控准备状态。当主资源发生故障时，冗余资源接管工作，待主资源恢复正常后，将切换并重新使用主资源，或者不切换作为冗余资源。
双机双工（互备互换）

两个资源同时支持各自的系统服务并相互监测运行情况，当其中一个资源发生故障时，另一个资源立刻接管其工作。
集群（多服务器互备）

要解析集群可能要新开一篇总结了…..

搭建集群系统，是为了单点故障:
- 消除供电的单点故障
- 消除磁盘的单点故障
- 消除 SPU（System Process Unit）单点故障
- 消除网络单点故障
- 消除软件单点故障
- ……

实施

说了这么多，那具体我们又要在哪些地方实施高可用策略？这就涉及到系统架构设计的整个流程了……

……

参考：

究竟啥才是互联网架构“高可用”

百度百科：高可用性)

元胞自动机

Posted on 2019-05-06 | Edited on 2019-11-21

我是通过生命游戏这个词，进而了解到元胞自动机的，先看生命游戏 这个听起来很”有趣”的游戏到底是怎么玩的：

生命游戏

注：本文讨论的生命游戏是指康威生命游戏（Conway’s Game of Life）

定义：

二维空间上的一个网格（正方形）代表一个元胞
元胞具有两种状态：”死亡”、”存活”
元胞周围的 8 个网格称为元胞的邻居

规则：

当前元胞为”存活”，当存活的邻居个数小于 2 时，该元胞死亡（模拟生命数量稀少）
当前元胞为”存活”，当存活的邻居个数为 2 或 3 时，该元胞保持存活
当前元胞为”存活”，当存活的邻居个数大于 3 时，该元胞死亡（模拟生命数量过多）
当前元胞为”死亡”，当存活的邻居个数等于 3 时，该元胞状态转成存活（模拟生命繁殖）

开始游戏：

在一定范围的二维空间中，创建一定量的初始元胞，然后根据游戏规则，迭代该范围中元胞的状态变化

游戏欣赏：

（域名没有备案……所以没图）

程序实现（伪代码）：

cells; // 空间中元胞二维数组（已包含初始元胞的）
newCells; // 暂存每次时间迭代产生的新元胞

// 时间迭代
Timer.interval(1000){ 
   // 空间中的元胞迭代
   for(x=0;x<width;x++){
     for(y=0;x<height;y++){
       // 计算邻居数
       neighborsCount = countNeighbors(cells,width,height,x,y); 
       // 这里有个疑问：
       // 是在迭代的同时就改变当前元胞状态，即该元胞状态改变并对后续迭代产生影响，如下：
       // cells[x][y] = updateCellStatus(cells[x][y],neighborsCount);
       // 还是将元胞的新状态用新的二维数组存起来？？？
       // 个人觉得这里应该后者比较符合，但模拟其它问题就不一定：
       newCells[x][y] = updateCellStatus(cells[x][y],neighborsCount);
     }
   }
   // 更新界面
   updateViews(newCells);
   // 交换引用，准备迭代下一个时刻
   temp = newCells;
   newCells = cells;
   cells = temp;
}

元胞自动机（cellular automata，CA）

先简单看一下百科的解析（后面几段就不复制粘贴了）：

`元胞自动机` 是一种时间、空间、状态都离散，空间相互作用和时间因果关系为局部的网格动力学模型，具有模拟复杂系统时空演化过程的能力。

还是很懵……

再结合 生命游戏 来理解：

生命游戏 可以说是简单模拟了一个种群内部生命的演化（网上也有很多文章讨论——根据初始元胞设定的不同而产生的各种”神奇”演进图案，但不是本文的重点），我们也可以称其为一种模拟生命演化的模型。其次，我们完全可以通过修改或说变化 生命游戏 的一些定义、规则、应用场景等，做出另一个东西的演化模型。如：

生命游戏 中定义的空间网格，其实重点就是平铺一个空间的想法，我们完全可以用平铺的等边三角形、菱形、等边六边型，甚至一维问题的线段、三维问题的正四、八面体等来替换
生命游戏 中网格代表元胞，我们也可以把线段、晶格等代表其它东西，如：一维的方格中每个方格代表路况，来模拟交通情况
生命游戏 中元胞有”存活”和”死亡”状态，而用一维的方格模拟交通状况时，每个”路况”方格也有”有车”和”没车”的状态，这类模型的状态通常都只考虑有限个的
生命游戏 中以统计周围邻居数来模拟种群生命的演化，而路况问题可根据前面和后面”路况”有没有车来更新当前的”路况”状态，关键是根据实际模拟的问题设定单元的状态更新规则，当然这个规则要覆盖所模拟的单元的状态

`元胞自动机` 则是这一类模型的总称，总结几个描述性的特点：

时间迭代，模拟问题的演化
空间中的单元存在有限个状态
单元的状态会受到空间内局部区域的其它单元的影响

元胞自动机的应用

了解元胞自动机的概念之后，关键还是遇到类似上述特点的问题时，能不能想到用元胞自动机来解决，或是用元胞自动机来模拟一些有趣的东西或者玩法。网上也有很多，我就不找了，我自己倒是想了 2 个觉得比较有意思：

用元胞自动机能不能解答数独问题，重点是格子的数字更新规则，我想如果遇到冲突便随机一个尽量不冲突的，再加一些标记等，这样做能不能做到一定有解
玩游戏时，经常主角队都有几个伙伴要安排站位，这样可以利用元胞自动机与五行相生相克来设计对战时阵法变化，规则就是根据角色出招的元素、对方的阵法等来更新站位的元素

噪声

Posted on 2018-11-03 | Edited on 2019-11-21

PS：本文讨论的噪声是指用于程序生成随机值的算法

学习资料：

别人的文章写得真好，所以直接做总结吧～

总结

噪声的种类

基于晶格
- 梯度噪声：Perlin 噪声、Simplex 噪声、Wavelet 噪声等
- Value 噪声
基于点
- Worley 噪声（又称：Voronoi 噪声）

Perlin 噪声

函数声明：

1
2
3

public float perlin(float x, float y)
public float perlin(float x, float y, float z)
public float perlin(float x, float y, float z, float w)

常用 2 维、3 维、4 维（可根据算法思路实现更高维）
输入为某点坐标（本文的实现用 float 类型）
输出取值范围：[0,1]
算法时间复杂度： $O(2^n)$（n 是维数）

实现

接收输入（浮点型）
计算输入点所在的晶格（整型坐标）（2 维 4 个顶点（正方形）、3 维 8 个顶点（正方体）、4 维 16 个顶点 …）
晶格顶点各自生成一个伪随机的梯度向量
- 2 维：预计算随机单位向量 G[n]、打乱 0～n-1 顺序的 P[n]，则顶点 (i,j) 的随机梯度向量为: $ g = G[(i + P[j]) \% n] $
- 3 维：选取的单位向量由 12 条单位正方体的中心点到各条边中点的向量组成：(1,1,0),(-1,1,0),(1,-1,0),(-1,-1,0), (1,0,1),(-1,0,1),(1,0,-1),(-1,0,-1), (0,1,1),(0,-1,1),(0,1,-1),(0,-1,-1)
- 4 维：选取方法与 3 维类似共 32 条单位向量
- 实际实现中，P[] 长度一般先取 256，为避免缓存溢出，再重复填充一次数组的值，最终长度为 512
计算晶体各顶点到输入点的距离向量
对晶体各顶点的梯度向量和距离向量做点积运算
对点积结果插值，求加权平均

3 维例子


// fade() = t * t * t * (t * (t * 6 - 15) + 10);

float x,y,z; // 输入坐标
float g1,g2,g3,g4,g5,g6,g7,g8; // 8 个点积结果
float x1,x2,y1,2;

x1 = lerp(g1,g2,fade(x-(int)x));// PS：实际实现可缓存 fade(x-(int)x) 的值减少计算
x2 = lerp(g3,g4,fade(x-(int)x));
y1 = lerp(x1,x2,fade(y-(int)x));

x1 = lerp(g5,g6,fade(x-(int)x));
x2 = lerp(g7,g8,fade(x-(int)x));
y2 = lerp(x1,x2,fade(y-(int)x));

float result = (lerp(y1,y2,fade(z-(int)z)) + 1)/2; // 输出结果

fade() 称为缓和曲线（ease curves）(二阶导满足连续性): $$s(t)=6t^5−15t^4+10t^3$$

Value 噪声

与 Perlin 噪声实现步骤类似，实现更简单，不同之处：

用伪随机值代替晶体顶点的伪随机梯度向量，不需要与距离向量点乘

Simplex 噪声

与 Perlin 噪声实现步骤类似，Simplex 噪声的时间复杂度更优，为 $O(n^2)$，不同之处：

Simplex 所选的晶体为单形（1 维：线段、2 维：等腰三角形、3 维：四面体、… ）
每个顶点的权重计算：$$(r^2−|\vec {dist}|^2)^4×dot(\vec {dist},\vec {grad})$$
- dist 是晶体顶点到输入点的距离向量
- grad 是晶体顶点存储的伪随机梯度向量
- $r^2$ 的取值是 0.5 或 0.6：取 0.5 时可以保证没有不连续的间断点，在连续性并不那么明显时可以取 0.6 得到更好的视觉效果
最后将各顶点权重相加再乘以一个系数（为了把结果归一到 [-1,1] 的范围）

难点：找到输入点所在的单形？？？

略具体推导

Worley 噪声

暂不研究

可平铺的（tiling）无缝的（seamless）噪声

目前公认比较好的一种方法，就是在 2n 维上计算 n 维可平铺噪声

具体做法，如：

在二维噪声中画一个圆，可得一维无缝的噪声
在四维的 xz 平面画圆得二维 x 轴的无缝噪声，在四维的 yw 平面画圆得二维 y 轴的无缝噪声

二维无缝噪声实现

//X, Y is [0..1]
public static float SeamlessNoise( float x, float y, float dx, float dy, float xyOffset ) {
    float s = x;
    float t = y;

    float nx = xyOffset + Mathf.Cos(s * 2.0f * Mathf.PI) * dx / (2.0f * Mathf.PI);
    float ny = xyOffset + Mathf.Cos(t * 2.0f * Mathf.PI) * dy / (2.0f * Mathf.PI);
    float nz = xyOffset + Mathf.Sin(s * 2.0f * Mathf.PI) * dx / (2.0f * Mathf.PI);
    float nw = xyOffset + Mathf.Sin(t * 2.0f * Mathf.PI) * dy / (2.0f * Mathf.PI);

    return Noise(nx, ny, nz, nw);
}

其中 Noise() 可以是 Perlin、Simplex、Worley 等
xyOffset 是指在四维空间某个平面上的偏移，即这个单位圆是以 xyOffset 为圆心的

分形噪声、FBM（分形布朗运动）

具体实现为：不断叠加更高频率的噪声，如：

$$noise(p)+\frac{1}{2}noise(2p)+\frac{1}{4}noise(4p)+…$$

$$|noise(p)|+\frac{1}{2}|noise(2p)|+\frac{1}{4}|noise(4p)|+…$$

$$sin(x+|noise(p)|+\frac{1}{2}|noise(2p)|+\frac{1}{4}|noise(4p)|+…)$$

三维 Perlin 分形示例代码：

public double OctavePerlin(double x, double y, double z, int octaves, double persistence) {
    double total = 0;
    double frequency = 1;
    double amplitude = 1;
    double maxValue = 0;  // Used for normalizing result to 0.0 - 1.0
    for(int i=0;i<octaves;i++) {
        total += perlin(x * frequency, y * frequency, z * frequency) * amplitude;
        
        maxValue += amplitude;
        
        amplitude *= persistence;
        frequency *= 2;
    }
    
    return total/maxValue;
}

octaves 为陪频
persistence 为持续性
amplitude 为振幅

PiaoNiao

3 posts

3 tags

什么是高可用