CAP定理(原则)以及BASE理论

CAP定理(原则)以及BASE理论 CAP定理(原则)概念   CAP原则又称CAP定理,指的是在一个分布式系统中, Consistency(一致性)、 Availability(可用性)、Partition tolerance(分区容错性),三者不可得兼。1. 数据一致性(consistency)   一致性(C):在分布式系统中的所有数据备份,在同一时刻是否同样的值。(等同于所有节点访问同一份最新的数据副本)   在分布式系统中,如果能够做到针对一个数据项的更新操作执行成功后,所有的用户都可以读到其最新的值,那么这样的系统就被认为具有强一致性(严格的一致性)。 2. 服务可用性(avail...

半小时学会LevelDB原理及应用

LevelDB LevelDB之概览   LevelDB是Google传奇工程师Jeff Dean和Sanjay Ghemawat开源的KV存储引擎。   了解原理之前首先要用起来,下面动手实现个例子:安装调试(mac上直接命令行下brew install leveldb即可安装,编译时候记得加上-lleveldb)   example:

设计思路   LevelDB的数据是存储在磁盘上的,采用LSM-Tree的结构实现。LSM-Tree将磁盘的随机写转化为顺序写,从而大大提高了写速度。   为了做到这一点LSM-Tree的思路...

密码学hash函数-SHA256-512

Hash函数又称哈希函数、散列函数、杂凑函数。它是一种单向密码体制,即从一个从明文到密文的不可逆映射,只有加密过程,没有解密过程。 Hash函数H将可变长度的数据块M作为输入,产生固定长度的Hash值h=H(M)。 在安全应用中使用的Hash函数称为密码学Hash函数。(单向性)、(抗碰撞性) 弱抗碰撞性:给定一个消息M,要找到另一个消息M',使得H(M)=H(M')很难。 强抗碰撞性:要找到两个随机明文M和M',使得H(M)=H(M')很难。 Hash函数特点: 1. 易压缩 2. 易计算 3. 单向性 4. 抗碰撞性 5. 高灵敏性 密码学Hash函数的应用范围 消息认证 消息认证是用来验...

Paxos发展、算法原理

Paxos 发展史   Leslie Lamport所提出的Paxos算法是现代分布式系统中的一项重要的基础性技术,得到广泛的应用。 Paxos的整个发展过程大概可以分为三个阶段:   第一阶段:萌芽期,大致是1988-1996年。Liskov等人在PODC上发表了Viewstamped Replication: A New Primary Copy Method to Support Highly-Available Distributed Systems ,提出了一个在副本出现宕机情况下仍能正常工作的主从备份算法,该算法与Paxos在本质上是一致的(The ABCD’s of Paxos)...

priority_queue优先队列/C++

priority_queue优先队列/C++ 概述   priority_queue是一个拥有权值观念的queue,只允许在底端加入元素,并从顶端取出元素。   priority_queue带有权值观念,权值最高者,排在最前面。   缺省情况下priority_queue系利用一个max-heap完成,后者是一个以vector表现的complete binary tree。 定义   由于priority_queue完全以底部容器为根据,再加上heap处理规则,所以其实现非常简单。缺省情况下是以vector为底部容器。   priority_queue的所有元素,进出都有一定的规则,只有que...

几种垃圾回收GC概述

垃圾回收机制 引用计数回收器(Reference Counting Collector)   原理是在每个对象内部维护一个整数值,叫做这个对象的引用计数,当对象被引用时引用计数加一,当对象不被引用时引用计数减一。当引用计数为 0 时,自动销毁对象。 目前引用计数法主要用在 c++ 标准库的 std::shared_ptr 、微软的 COM 、Objective-C 和 PHP 中。   计数器表示资源(内存中的对象)的使用次数,当计数器变成零的时候就可以将该资源销毁。在向已有的系统添加垃圾回收器时,开发人员通常会选择计数回收器,因为这种方式最容易与已有的资源管理器和代码集成在一起。   不过引...

椭圆曲线ECC基本概念-紫魔戒

title: 椭圆曲线ECC基本概念 - 紫魔戒 categories: - cryptography tags: - 椭圆曲线 - ECC - 密码学 date: 2017-06-26 10:57:00 椭圆曲线的曲线方程是以下形式的三次方程: y2+axy+by=x3+cx2+dx+e a,b,c,d,e是满足某些简单条件的实数。定义中包含一个称为无穷点的元素,记为O 如果其上的3个点位于同一直线上,那么它们的和为O O为加法单位元,即对ECC上任一点P,有 设P1=(x, y)是ECC上一点,加法逆元定义为P2=-P1=(x, y) P1,P2连线延长到无穷远,得到ECC上另一点O,即P...

大数据处理-Trie树

大数据处理——Trie树 1.1、什么是Trie树   Trie树,即字典树,又称单词查找树或键树,是一种树形结构,是一种哈希树的变种。典型应用是用于统计和排序大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计。它的优点是:最大限度地减少无谓的字符串比较,查询效率比哈希表高。   Trie的核心思想是空间换时间。利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。 它有3个基本性质:   1. 根节点不包含字符,除根节点外每一个节点都只包含一个字符。   2. 从根节点到某一节点,路径上经过的字符连接起来,为该节点对应的字符串。   3. 每个节点的所有子节点包...

大数据处理-Bitmap

  MapReduce是一种编程模型,用于大规模数据集(大于1TB)的并行运算。概念"Map(映射)"和"Reduce(归约)" Bit-map空间压缩和快速排序去重 1. Bit-map的基本思想   32位机器上,对于一个整型数,比如int a=1 在内存中占32bit位,这是为了方便计算机的运算。但是对于某些应用场景而言,这属于一种巨大的浪费,因为我们可以用对应的32bit位对应存储十进制的0-31个数,而这就是Bit-map的基本思想。Bit-map算法利用这种思想处理大量数据的排序、查询以及去重。   Bitmap在用户群做交集和并集运算的时候也有极大的便利。 2. Bit-map应...

什么是隔离见证?简单介绍隔离见证-紫魔戒

每一个比特币交易,都可以分为两部分。第一部分是转账记录,第二部分是用来证明这个交易合法性(主要是签名)的。第一部分可称为“交易状态”,第二部分就是所谓的见证(witness)。如果你只关心每个账户的余额,那么转账记录就已经足够了。只有部分人(主要是矿工)才有必要取得交易见证。 (交易信息就是谁给谁在什么时间转了多少钱。 见证信息就是哪个节点在什么时间验证交易信息的可靠性。) 中本聪在设计比特币的时候直接把这两个信息直接放在了区块内,所以一个区块就承载不了更多的交易信息,如果隔离了“见证信息”,那么区块链只记录交易信息,那么一个区块可承载的交易更多交易。 中本聪设计比特币时,并没有把两部分资料分...