Computer

CAP 定理的含义

分布式系统(distributed system)正变得越来越重要,大型网站几乎都是分布式的。 分布式系统的最大难点,就是各个节点的状态如何同步。CAP 定理是这方面的基本定理,也是理解分布式系统的起点。 本文介绍该定理。它其实很好懂,而且是显而易见的。下面的内容主要参考了 Michael Whittaker 的文章。 一、分布式系统的三个指标 1998年,加州大学的计算机科学家 Eric Brewer 提出,分布式系统有三个指标。 Consistency Availability Partition tolerance 它们的第一个字母分别是 C、A、P。 Eric Brewer 说,这三个指标不可能同时做到。这个结论就叫做 CAP 定理。 二、Partition tolerance 先看 Partition tolerance,中文叫做”分区容错”。 大多数分布式系统都分布在多个子网络。每个子网络就叫做一个区(partition)。分区容错的意思是,区间通信可能失败。比如,一台服务器放在中国,另一台服务器放在美国,这就是两个区,它们之间可能无法通信。 上图中,G1 和 G2 是两台跨区的服务器。G1 向 G2 发送一条消息,G2 可能无法收到。系统设计的时候,必须考虑到这种情况。 一般来说,分区容错无法避免,因此可以认为 CAP 的 P 总是成立。CAP 定理告诉我们,剩下的 C 和 A 无法同时做到。 三、Consistency Consistency Read more…

By RSSBot, ago
Computer

根域名的知识

域名是互联网的基础设施,只要上网就会用到。 它还是一门利润丰厚的生意,所有域名每年都必须交注册费,这是很大的一笔钱。 这些钱交到了哪里?到底谁控制域名的价格?为什么有的域名注册费很贵,有的便宜?……今天,我就来谈谈这些与根域名(root domain)相关的知识。 一、ICANN 全世界域名的最高管理机构,是一个叫做 ICANN (Internet Corporation for Assigned Names and Numbers)的组织。它的总部在美国加州。 它原来是美国商务部下面的一个非盈利机构,所以有人说,美国政府控制了全世界的域名,这种说法是有根据的。2016年,美国政府宣布,ICANN 不再隶属于商务部,成为一个自我管理的独立机构。但是可想而知,美国政府依然对它有绝对影响。 ICANN 负责管理全世界域名系统的运作。它的一项主要工作,就是规定顶级域名(top level domain,简写为 TLD)。 二、TLD 所谓顶级域名(TLD),就是最高层级的域名。简单说,就是网址的最后一个部分。比如,网址www.example.com的顶级域名就是.com。 ICANN 就负责规定,哪些字符串可以当作顶级域名。截至2015年7月,顶级域名共有1058个。 它们可以分成两类。一类是一般性顶级域名(gTLD),比如.com、.net、.edu、.org、.xxx等等,共有700多个。另一类是国别顶级域名(ccTLD),代表不同的国家和地区,比如.cn(中国)、.io(英属印度洋领地)、.cc( 科科斯群岛)、.tv(图瓦卢)等,共有300多个。 三、顶级域名托管商 ICANN 自己不会去管理这些顶级域名,因为根本管不过来。想想看,顶级域名有1000多个,每个顶级域名下面都有许多批发商,如果每个都要管,就太麻烦了。 ICANN 的政策是,每个顶级域名都找一个托管商,该域名的所有事项都由托管商负责。ICANN 只与托管商联系,这样管理起来就容易多了。举例来说,.cn域名的托管商就是中国互联网络信息中心(CNNIC),它决定了.cn域名的各种政策。 目前,世界最大的顶级域名托管商是美国的 Verisign 公司。 四、Verisign Verisign 是一家商业公司,总部在美国维吉尼亚州。它托管了.com、.net 、.name、.gov这四个一般性顶级域名,以及.cc和.tv这两个国别顶级域名。另外,.edu和.jobs的后台管理工作,也外包给了它。 它对.com和.net的独家垄断是历史形成的。最早的时候, Network Solutions 公司接受美国国家科学基金会的委托,管理顶级域名。2000年,Verisign 收购了这家公司,继承了域名业务。2003年,Verisign 卖掉了域名注册业务,只保留顶级域名管理。也就是说,它只做域名批发,不做域名零售了。 2010年,Verisign 又把网站安全和加密证书业务卖给了 Symantec 公司。后者又在2017年把这项业务卖给了 Read more…

By RSSBot, ago
Computer

汇编语言入门教程

学习编程其实就是学高级语言,即那些为人类设计的计算机语言。 但是,计算机不理解高级语言,必须通过编译器转成二进制代码,才能运行。学会高级语言,并不等于理解计算机实际的运行步骤。 计算机真正能够理解的是低级语言,它专门用来控制硬件。汇编语言就是低级语言,直接描述/控制 CPU 的运行。如果你想了解 CPU 到底干了些什么,以及代码的运行步骤,就一定要学习汇编语言。 汇编语言不容易学习,就连简明扼要的介绍都很难找到。下面我尝试写一篇最好懂的汇编语言教程,解释 CPU 如何执行代码。 一、汇编语言是什么? 我们知道,CPU 只负责计算,本身不具备智能。你输入一条指令(instruction),它就运行一次,然后停下来,等待下一条指令。 这些指令都是二进制的,称为操作码(opcode),比如加法指令就是00000011。编译器的作用,就是将高级语言写好的程序,翻译成一条条操作码。 对于人类来说,二进制程序是不可读的,根本看不出来机器干了什么。为了解决可读性的问题,以及偶尔的编辑需求,就诞生了汇编语言。 汇编语言是二进制指令的文本形式,与指令是一一对应的关系。比如,加法指令00000011写成汇编语言就是 ADD。只要还原成二进制,汇编语言就可以被 CPU 直接执行,所以它是最底层的低级语言。 二、来历 最早的时候,编写程序就是手写二进制指令,然后通过各种开关输入计算机,比如要做加法了,就按一下加法开关。后来,发明了纸带打孔机,通过在纸带上打孔,将二进制指令自动输入计算机。 为了解决二进制指令的可读性问题,工程师将那些指令写成了八进制。二进制转八进制是轻而易举的,但是八进制的可读性也不行。很自然地,最后还是用文字表达,加法指令写成 ADD。内存地址也不再直接引用,而是用标签表示。 这样的话,就多出一个步骤,要把这些文字指令翻译成二进制,这个步骤就称为 assembling,完成这个步骤的程序就叫做 assembler。它处理的文本,自然就叫做 aseembly code。标准化以后,称为 assembly language,缩写为 asm,中文译为汇编语言。 每一种 CPU 的机器指令都是不一样的,因此对应的汇编语言也不一样。本文介绍的是目前最常见的 x86 汇编语言,即 Intel 公司的 CPU 使用的那一种。 三、寄存器 学习汇编语言,首先必须了解两个知识点:寄存器和内存模型。 先来看寄存器。CPU 本身只负责运算,不负责储存数据。数据一般都储存在内存之中,CPU 要用的时候就去内存读写数据。但是,CPU 的运算速度远高于内存的读写速度,为了避免被拖慢,CPU 都自带一级缓存和二级缓存。基本上,CPU 缓存可以看作是读写速度较快的内存。 但是,CPU 缓存还是不够快,另外数据在缓存里面的地址是不固定的,CPU Read more…

By RSSBot, ago
Computer

加密货币的本质

去年,比特币暴涨,其他币也像雨后春笋一样冒出来,已经有1000多种了。 很多人都在问,加密货币(cryptocurrency)的时代,真的来临了吗?将来会不会人类不再使用美元、人民币,改用加密货币?那么多品种,我应该使用哪一种币?要不要现在就去投资一些? 这些问题的答案,我也想知道,就花了很多时间查阅资料、研究协议。前两周发表的《区块链入门教程》和《比特币入门教程》,是我的学习心得。但是,那两篇教程主要介绍基本概念、探讨协议的可行性,没回答一个根本的问题:加密货币到底是什么? 下面就是我对这个问题的思考。阅读之前,如果你已经了解区块链和比特币,那很好;如果不了解,也没关系,本文不涉及技术,只讨论最基本的原理。 一、钱是什么? 我们都知道,人民币是钱,美元是钱,金银财宝是钱。我问一个问题,它们为什么能成为钱? 你可能回答,因为它们有价值,或者是价值的代表。但是,有价值的东西多了,为什么只有这些品种成为了钱? 答案很容易想到,因为人们普遍相信(认同)它们的价值,其他东西的价值难以得到普通认同,无法成为钱。比如,邮票的价值就没有普遍的认同,除了集邮爱好者,其他地方都不能当钱用。一般来说,认同的人越多,这种钱的通用性就越高。 我曾经去俄罗斯旅行,当地货币是卢布。可是,一旦离开俄国,没人相信它的购买力,所以卢布离开俄国就没用了。相反,全世界人民都相信美元的价值,所以全世界都能用。我用美元付账的时候,我发现那些俄国人都很满意。 所以,钱的本质,或者说货币的本质,就是它的可信性。它必须使人们相信,它是有价值的,然后才能成为钱,才能被收藏和支付。 二、可信性 为什么钱必须是可信的?因为对方必须相信它的价值,否则你没法支付出去。那么,接下来的问题就是,可信的东西是否就是钱? 我的回答是 Yes。一样东西能否成为钱,只取决于人们是否相信它的价值,至于它是不是真的有价值,根本不重要。 如果马云在一张纸条上写”这张纸条价值10000元”,下面签了他的名,并且附上防伪标记。你说这纸条是钱吗?我跟你保证,这就是钱,你用来支付,人们都会接受,马云等同于发行了一种新的纸币。 比特币也是如此,它是什么,其实不太重要。重要的是,它必须保证自己是可信的,这样才能让足够的人相信它的价值,然后才能成为钱。 三、比特币的可信性 比特币要解决的核心问题,就是创造一种可信的数字凭证。由于这种凭证可信,所以能够当做货币。 比特币的技术基础是加密学,因为只有加密学才能保证它的可信性。一旦加密被破解,它就没法当作货币了。这也是这一类数字凭证被称为”加密货币”的原因。 技术人员对比特币感兴趣,还有一个重要原因。任何需要可靠的数字凭证的场合,也许都可以用到这种技术。 四、比特币的特点 比特币有三个特点,就是因为做到了这三点,所以它可信,能够当作钱。 首先,它不会被(轻易)偷走。或者反过来说,它使得你无法去偷别人,你只能花你自己的钱。因为必须要有别人的私钥,才能取出他的钱。正常情况下,你拿不到别人的私钥。 其次,它无法伪造。每一个比特币都能追溯来源,而所有比特币都来源于矿工获得的奖励。矿工只有新建区块,才能获得奖励,这是很难的事情,所以无法伪造比特币。 最后,它无法大批生成。原因跟上一条一样,比特币的发行速度是稳定的,现在每10分钟新增12.5个,然后每四年减半,最终停止增长。因此不会像纸币那样,政府滥发导致通货膨胀。 五、比特币有实体吗? 由于后面要提到的原因,比特币不可能拥有实体,没法做到”从口袋里掏出一个币”这种场景,交易都必须通过互联网完成。 你可能会说,钱都有实体,怎么可能存在无形的钱呢?答案正好相反,钱就应该是无形的,那些实体的钱其实是对物质材料的浪费,由于技术不够发达,不得不做成实体。 我小时候买东西,都必须用现金,否则没法证明,自己拥有购买力。只有通过实体的钱,才能保证对方确实收到了钱。如果银行业发达,就不用现金了,可以使用银行卡。支付的时候,对方抄一下银行卡号码,查询银行”这个账户有钱吗”。银行回答有钱,OK,成交。 但是,互联网使得实体的银行卡也不需要了。如果存在一个开放的中央记账系统,任何人都可以查询,你把钱划到老板的账户,老板查询一下,发现收到了,交易自动成交,整个过程都是无形的,还需要什么银行卡呢? 这个中央记账系统已经实现了,就叫做区块链。 六、区块链的作用 区块链就是一个数据库,记载了所有的交易,用作中央记账系统。 每笔交易的核心,就是一句话,比如”张三向李四转移了1个比特币”。为了证明这句话可信,张三为它加上了数字签名。任何人都可以用张三的公钥,证明这确实是张三本人的行为。另一方面,其他人无法伪造张三的数字签名,所以不可能伪造这笔交易。 矿工们收到这句话,首先验证数字签名的可信性,然后验证张三确实拥有这些比特币(每一笔交易都有上一笔交易的编号,用来查询比特币的来源)。验证通过以后,就着手把这句话写入区块链了。一旦写入区块链,所有人就都可以查询到,因此这笔比特币就被认为,从张三转移到了李四。 区块链的作用就是把这句话永久保存下来了,让任何人都可以查看,并且任何人(包括张三本人在内)都无法再修改了。 货币是什么?其实就是这句话。这一句话就完成了一次支付。我们平时用人民币支付,其实只是用纸币表达这条信息。如果每个人都可以实时写入/读取中央记账系统(区块链),那么完全可以不携带货币。 七、双重支出 前面说过,交易不可能被伪造。但是,由于每一笔交易都是一串二进制信号,因此可能被复制。举例来说,”张三向李四转移了1个比特币”这句话,可能被其他人复制,也可能被张三自己复制,提交到区块链。 如果这句话被两次写入区块链,就意味着张三可以把同一笔钱花掉两次。但是,第二次写入的时候,查询区块链可以发现张三已经把这笔钱花掉了,从而认定这是不合法的交易,不能写入区块链。因此,复制交易是不可能的。 比较麻烦的是另一种情况,就是张三把同一笔钱付给两个人。他先向区块链提交一个交易”张三向李四转移了1个比特币”,然后又提交了另一个交易”张三向王五转移了1个比特币”。这两个交易都可能被认为是真实的交易,从而进入区块链。因此,必须有办法防止出现这种情况。 情况一:同一个矿工收到了这两个交易。那么他会察觉到,它们不可能同时成立,因此选择其中的一笔写入区块链。 情况二:矿工 A 收到了第一笔交易,矿工 B 收到了第二笔交易,他们各自都会认定这是合法的交易,分别把这两笔交易写入了两个区块,这时区块链就出现了分叉。 比特币协议规定,分叉点之后最先达到6个区块的那个分支,被认定为正式的区块链,其他分支都将被放弃。由于区块的生成速度由计算能力决定,所以到底哪一笔交易最后会被写入区块链,完全由它所在的分支能吸引多少计算能力决定。隐藏的逻辑是,如果大多数人(计算能力)选择相信某一笔交易,那么它就应该是真的。 综上所述,双重支出不可能发生。因为中央记账系统总有办法发现,你把同一笔钱花了两遍。但是,这也说明了比特币的一个代价,就是交易不能实时确认,必须等待至少一个小时。 八、参考链接 Read more…

By RSSBot, ago
Computer

比特币入门教程

比特币(bitcoin)诞生于2008年的一篇论文。 一个署名为中本聪的人,提出了革命性的构想:让我们创造一种不受政府或其他任何人控制的货币!这个想法堪称疯狂:一串数字,背后没有任何资产支持,也没有任何人负责,你把它当作钱付给对方,怎么会有人愿意接受? 但是,狂想居然变成了现实。随后的几年,在全世界无数爱好者的支持下,比特币网络运行起来了,越来越多的人和资本参与,星星之火,终成燎原。刚刚过去的2017年,比特币迎来了爆发式的增长,从年初的1000美元,最高涨到了2万美元,全世界都为之震动,上到政府,下到普通百姓都在关注。事实就是比特币已经并将继续改变世界。 新闻媒体往往只关注它的火爆表现,忽视或者无法回答一些基本的问题。 比特币的原理是什么? 为什么这个无人管理的体系可以成功运作? 比特币交易的流程是怎么回事? 它与区块链又是什么关系? 下面,我尝试回答这些问题,希望帮助大家理解比特币。抛开技术细节,还是很容易解释的。 有一点说明,本文只讨论技术问题,不涉及如何投资比特币,更不会预测价格走势。事实上,我也不知道,如果我知道怎么发财,可能就不会在这里写博客了。 一、非对称加密 首先,理解比特币,必须理解非对称加密。 你可能听说过这个词,所谓非对称加密,其实很简单,就是加密和解密需要两把钥匙:一把公钥和一把私钥。 公钥是公开的,任何人都可以获取。私钥是保密的,只有拥有者才能使用。他人使用你的公钥加密信息,然后发送给你,你用私钥解密,取出信息。反过来,你也可以用私钥加密信息,别人用你的公钥解开,从而证明这个信息确实是你发出的,且未被篡改,这叫做数字签名(更详细的介绍请看《什么是数字签名》)。 现在请设想,如果公钥加密的不是普通的信息,而是加密了一笔钱,发送给你,这会怎样? 首先,你能解开加密包,取出里面的钱,因为私钥在你手里。其次,别人偷不走这笔钱,因为他们没有你的私钥。因此,支付可以成功。 这就是比特币(以及其他数字货币)的原理:非对称加密保证了支付的可靠性。 由于支付的钱必须通过私钥取出,所以你是谁并不重要,重要的是谁拥有私钥。只有拥有了私钥,才能取出支付给你的钱。(事实上,真实的交易流程稍有不同,私钥保证的不是取出支付给你的钱,而是保证只有你能把这些属于你的钱支付出去,详见后文。) 二、比特币钱包 对于比特币来说,钱不是支付给个人的,而是支付给某一把私钥。这就是交易匿名性的根本原因,因为没有人知道,那些私钥背后的主人是谁。 所以,比特币交易的第一件事,就是你必须拥有自己的公钥和私钥。 你去网上那些比特币交易所开户,它们会让你首先生成一个比特币钱包(wallet)。这个钱包不是用来存放比特币,而是存放你的公钥和私钥。软件会帮你生成这两把钥匙,然后放在钱包里面。 根据协议,公钥的长度是512位。这个长度不太方便传播,因此协议又规定,要为公钥生成一个160位的指纹。所谓指纹,就是一个比较短的、易于传播的哈希值。160位是二进制,写成十六进制,大约是26到35个字符,比如 1BvBMSEYstWetqTFn5Au4m4GFg7xJaNVN2。这个字符串就叫做钱包的地址,它是唯一的,即每个钱包的地址肯定都是不一样的。 你向别人收钱时,只要告诉对方你的钱包地址即可,对方向这个地址付款。由于你是这个地址的拥有者,所以你会收到这笔钱。 由于你是否拥有某个钱包地址,是由私钥证明的(具体的证明方法稍后介绍),所以一定要保护好私钥。这是极其重要的,如果你的私钥被偷了,你的比特币也就等于没了,因为他人可以冒用你的身份了,把钱包里面的钱都转走。 同样的,你向他人支付比特币,千万不能写错他人的钱包地址,否则你的比特币就支付到了另一个不同的人了。 三、交易过程 下面,我把整个流程串起来,看看比特币如何完成一笔交易。 一笔交易就是一个地址的比特币,转移到另一个地址。由于比特币的交易记录全部都是公开的,哪个地址拥有多少比特币,都是可以查到的。因此,支付方是否拥有足够的比特币,完成这笔交易,这是可以轻易验证的。 问题出在怎么防止其他人,冒用你的名义申报交易。举例来说,有人申报了一笔交易:地址 A 向地址 B 支付10个比特币。我怎么知道这个申报是真的,申报人就是地址 A 的主人? 比特币协议规定,申报交易的时候,除了交易金额,转出比特币的一方还必须提供以下数据。 上一笔交易的 Hash(你从哪里得到这些比特币) 本次交易双方的地址 支付方的公钥 支付方的私钥生成的数字签名 验证这笔交易是否属实,需要三步。 第一步,找到上一笔交易,确认支付方的比特币来源。 第二步,算出支付方公钥的指纹,确认与支付方的地址一致,从而保证公钥属实。 第三步,使用公钥去解开数字签名,保证私钥属实。 经过上面三步,就可以认定这笔交易是真实的。 四、交易确认与区块链 确认交易的真实性以后,交易还不算完成。交易数据必须写入数据库,才算成立,对方才能真正收到钱。 Read more…

By RSSBot, ago
Computer

区块链入门教程

区块链(blockchain)是眼下的大热门,新闻媒体大量报道,宣称它将创造未来。 可是,简单易懂的入门文章却很少。区块链到底是什么,有何特别之处,很少有解释。 下面,我就来尝试,写一篇最好懂的区块链教程。毕竟它也不是很难的东西,核心概念非常简单,几句话就能说清楚。我希望读完本文,你不仅可以理解区块链,还会明白什么是挖矿、为什么挖矿越来越难等问题。 需要说明的是,我并非这方面的专家。虽然很早就关注,但是仔细地了解区块链,还是从今年初开始。文中的错误和不准确的地方,欢迎大家指正。 一、区块链的本质 区块链是什么?一句话,它是一种特殊的分布式数据库。 首先,区块链的主要作用是储存信息。任何需要保存的信息,都可以写入区块链,也可以从里面读取,所以它是数据库。 其次,任何人都可以架设服务器,加入区块链网络,成为一个节点。区块链的世界里面,没有中心节点,每个节点都是平等的,都保存着整个数据库。你可以向任何一个节点,写入/读取数据,因为所有节点最后都会同步,保证区块链一致。 二、区块链的最大特点 分布式数据库并非新发明,市场上早有此类产品。但是,区块链有一个革命性特点。 区块链没有管理员,它是彻底无中心的。其他的数据库都有管理员,但是区块链没有。如果有人想对区块链添加审核,也实现不了,因为它的设计目标就是防止出现居于中心地位的管理当局。 正是因为无法管理,区块链才能做到无法被控制。否则一旦大公司大集团控制了管理权,他们就会控制整个平台,其他使用者就都必须听命于他们了。 但是,没有了管理员,人人都可以往里面写入数据,怎么才能保证数据是可信的呢?被坏人改了怎么办?请接着往下读,这就是区块链奇妙的地方。 三、区块 区块链由一个个区块(block)组成。区块很像数据库的记录,每次写入数据,就是创建一个区块。 每个区块包含两个部分。 区块头(Head):记录当前区块的元信息 区块体(Body):实际数据 区块头包含了当前区块的多项元信息。 生成时间 实际数据(即区块体)的 Hash 上一个区块的 Hash … 这里,你需要理解什么叫 Hash,这是理解区块链必需的。 所谓 Hash 就是计算机可以对任意内容,计算出一个长度相同的特征值。区块链的 Hash 长度是256位,这就是说,不管原始内容是什么,最后都会计算出一个256位的二进制数字。而且可以保证,只要原始内容不同,对应的 Hash 一定是不同的。 举例来说,字符串123的 Hash 是a8fdc205a9f19cc1c7507a60c4f01b13d11d7fd0(十六进制),转成二进制就是256位,而且只有123能得到这个 Hash。 因此,就有两个重要的推论。 推论1:每个区块的 Hash 都是不一样的,可以通过 Hash 标识区块。 推论2:如果区块的内容变了,它的 Hash 一定会改变。 四、 Hash 的不可修改性 Read more…

By RSSBot, ago