月归档：2016年08月

场景一

有这样一个场景：系
统中有大约100w的用户，每个用户平
均有3个邮箱账号，每隔5分钟，每个邮箱账需要收取100封邮件，最多3亿份邮件需要下载到服务器中(不含附件和正文)。用20台机器划分计算的压力，从
多个不同的网路出口进行访问外网，计算的压力得到缓解，那么每台机器的计算压力也不会很大了。

        通过我们的讨论和以往的经验判断在这场景中可以实现并行计算，但我们还期望能对并行计算的节点进行动态的添加/删除，做到在线更新并行计算的数目并且不会影响计算单元中的其他计算节点，但是有4个问题需要解决，否则会出现一些严重的问题：

1. 20台机器同时工作时，有一台机器down掉了，其他机器怎么进行接管计算任务，否则有些用户的业务不会被处理，造成用户服务终断。
2. 随着用户数量增加，添加机器是可以解决计算的瓶颈，但需要重启所有计算节点，如果需要，那么将会造成整个系统的不可用。
3. 用户数量增加或者减少，计算节点中的机器会出现有的机器资源使用率繁忙，有的却空闲，因为计算节点不知道彼此的运行负载状态。
4. 怎么去通知每个节点彼此的负载状态，怎么保证通知每个计算节点方式的可靠性和实时性。

        先不说那么多专业名词，白话来说我们需要的是...

继续阅读 →

ZooKeeper的基本原理

ZooKeeper是以Fast Paxos算法为基础的，通过选举产生一个leader，只有leader才能提交propose，具体算法可见Fast Paxos 。

2）ZooKeeper的基本运转流程

ZooKeeper主要存在以下两个流程：

• 选举Leader
• 同步数据

选举Leader过程中算法有很多，但要达到的选举标准是一致的：

• Leader要具有最高的zxid 
• 集群中大多数的机器得到响应并follow选出的Leader

下图为ZooKeeper数据流动图，比较直观地描述了ZooKeeper是如何同步数据的：

继续阅读 →

一：快速排序算法

快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下，排序 n 个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比较，但这种状况并不常见。事实上，快速排序通常明显比其他Ο(n log n) 算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来。

快速排序使用分治法（Divide and conquer）策略来把一个串行（list）分为两个子串行（sub-lists）。

算法步骤：

1 从数列中挑出一个元素，称为 “基准”（pivot），

2 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。

3 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

递归的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好了。虽然一直递归下去，但是这个算法总会退出，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去

参考：

快速排序

https://zh.wikipedia.org...

继续阅读 →