19 纯粹的码农

尚未进行身份认证

我要认证

暂无相关简介

等级
TA的排名 1w+

CAP理论

CAP理论在中国有着广泛的知名度,

2014-06-14 16:02:34

FLP Impossibility

FLP Impossibility(FLP不可能性)是份额

2014-06-04 13:28:41

求多个有序数组的中位数

题目:求解多个有序数组的中位数题目的意思是如果多个有序数组能在一起排序,则取位置为中间的数字,如果有奇数个数字则中位数只有一个;若为偶数个则有两个,一般取第一个,也称下中位。但不能把数组合在一起做插入或快速排序,因为数据可能是海量的。该题目可能有很多种实现方法,而我们给出一种仅依赖中位数性质的算法。如果存在一个已经排好序的大数组(有序数列),则会发现几个性质:对

2012-09-15 10:57:47

Zookeeper的一致性协议:Zab

Zookeeper使用了一种称为Zab(Zookeeper Atomic Broadcast)的协议作为其一致性复制的核心,据其作者说这是一种新发算法,其特点是充分考虑了Yahoo的具体情况:高吞吐量、低延迟、健壮、简单,但不过分要求其扩展性。下面将展示一些该协议的核心内容:另,本文仅讨论Zookeeper使用的一致性协议而非讨论其源码实现Zookeeper的实现是有Client、Serv

2012-03-01 15:39:28

Fast Paxos

自从Lamport在1998年发表Paxos算法后,对Paxos的各种改进工作就从未停止,其中动作最大的莫过于2005年发表的Fast Paxos。无论何种改进,其重点依然是在消息延迟与性能、吞吐量之间作出各种权衡。为了容易地从概念上区分二者,称前者Classic Paxos,改进后的后者为Fast Paxos。1. Fast Paxos概览Lamport在40多页的论文中不仅提出了Fas

2012-02-28 11:31:33

一致性算法中的节点下限

在众多的分布式一致性算法中,经常需要通过节点的数量满足某种规则来保证算法的正确性,比如Paxos算法,依赖一个”多数派“ 节点的工作的正确性。这类算法的共同目标是容许尽量多的节点失败但又不影响算法的正确性”。  这类问题本质上都抽象为数学上集合之间的逻辑关系,下面我们便从集合的性质入手讨论,为此先引入两个问题:  假设N为一非空结合,n为集合的元素数,M1,M2,...,Mm为N的m个子集

2012-02-26 23:53:31

层次锁

层次锁,更多地是在数据库设计中被提到,但也有少数分布式锁系统也实现这个概念。下面内容主要还是从数据库设计的角度来理解层次锁的概念。1. 事务锁粗略说来,当执行SQL语句时数据库都会开启事务,在SQL执行完毕commit时,会把所有受影响数据写到磁盘文件并结束事务。在事务执行期间,为了保证事务的ACID,SQL所影响到的表、行等数据都会被不同程度的进行锁定,我们笼统称为“事务锁”。从使用者的

2012-01-23 17:55:53

离散对数加密算法

与前章所述RSA公钥加密算法类似,离散对数加密算法也属于公钥加密算法,RSA依赖大数因数分解的困难性,而离散对数则依赖有限域上的离散指数的难计算性保障其安全。目前三大公钥加密算法(RSA、离散对数、椭圆曲线)都依赖数论与群论的知识,在介绍具体的算法前有必要再简介下所关联的数学知识。1.欧拉公式与φ(m)特性在RSA公钥加密算法中已经提到欧拉公式、费马小定理,可以说是三大加密算法的基础,

2011-12-28 14:22:30

幂取模算法

在众多的加密算法中都需要进行幂的取模运算,比如在RSA算法中需要计算ne mod N,我们称之为幂模算法,其中:N=p*q(p,q为大素数)n为加密数据,ne为公钥,d为私钥,满足关系ed≡1 (mod (p-1)*(q-1))其中n,e都是非常大的数,这样计算ne mod N就需要一些新方法,其计算方式也关系到RSA的效率问题。对一般的幂模运算:ab mod m,存在下面三种算法

2011-12-22 01:29:11

RSA公钥加密算法

本系列将会介绍RSA、离散对数、椭圆曲线三大公钥加密算法,RSA算法将会作为该系列的第一篇。1. 算法产生背景公钥加密或说非对称加密其作用已经不言而喻,在实际中已经得到大量应用,比如HTTPS证书,其中便包含了网站的公钥信息。非对称加密与对称加密最大的区别是,加密与解密使用不同的密钥,通过公钥加密的内容只有通过私钥才能解密,反之亦然。因此,发布者完全可以把公钥公布于众,使发送者便于查询。与

2011-12-20 17:58:41

Mysql中的MVCC

Mysql到底是怎么实现MVCC的?这个问题无数人都在问,但google中并无答案,本文尝试从Mysql源码中寻找答案。  在Mysql中MVCC是在Innodb存储引擎中得到支持的,Innodb为每行记录都实现了三个隐藏字段:6字节的事务ID(DB_TRX_ID

2011-09-04 00:25:01

深入JVM锁机制2-Lock

JVM Lock, ReentrantLock,CLH,CAS,自旋锁,偏向锁

2011-07-28 18:15:39

深入JVM锁机制1-synchronized

JVM锁,synchronized,Lock,自选锁,偏向锁,Cache一致性,Cache一致性流量,SMP

2011-07-28 16:24:41

φ累积失败检测算法

  在分布式系统中经常使用心跳(Heartbeat)来检测Server的健康状况,但从理论上来说,心跳无法真正检测对方是否crash,主要困难在于无法真正区别对方是宕机还是“慢”。传统的检测方法是设定一个超时时间T,只要在T之内没有接收到对方的心跳包便认为对方宕机,方法简单粗暴,但使用广泛。 1. 传统错误检测存在的缺陷    如上所述,在传统方式下,目标主机会每间隔t秒发起心跳,而接

2011-06-13 17:59:00

基于Lease的一致性

Lease,一致性,Proxy

2011-03-31 15:55:00

Gossip算法

Gossip,Anti-Entropy,Rumor mongering,最终一致性,cassandra

2011-03-24 23:38:00

Keyspace中的paxos

1. KeyspaceKeyspace是一款基于Paxos的开源Key-Value的数据库,底层存储基于BerkelyDB,Keyspace的核心功能是在BerkelyDB之上添加了一致层,保证每个节点的数据完全一致。Keyspace基于Master-Slave模式,所有的写均有Master承担,并通过paxos一致传播到slave,读可以根据基本路由到master或slave。因此,当mas

2011-03-21 17:11:00

PaxosLease

世上有很多选举算法,但最完美的莫过于Paxos,但把paxos用于master选举与用于value的选举有用众多不同之处,主要一点是二者执行频率不同。value选举需要频繁、高密度地执行paxos算法,每instance选举一个value。因此,原生的paxos算法无法满足高性能的要求;另一个问题是,paxos理论上存在活锁,lamprot推荐大家通过选举Leader避免这个问题。所有的实现都

2011-03-21 17:04:00

Viewstamps算法

viewstamp算法,paxos算法,分布式事务,leader选举

2011-03-03 13:53:00

Paxos算法3-实现探讨

前两篇Paxos算法的讨论,让我们对paxos算法的理论形成过程有了大概的了解,但距离其成为一个可执行的算法程序还有很长的路要走,原因是很多的细节和错误未被考虑。Google Chubby的作者说,paxos算法实现起来远没有看起来简单,原因是paxos的容错仅限于server crash这一种情况,但在实际工程实现时要考虑磁盘损坏、文件损坏、Leader身份丢失等诸多的错误。 1. Pa

2011-02-04 09:00:00

查看更多

勋章 我的勋章
    暂无奖章