- 综合排序
- 最热优先
- 最新优先
- 来自专栏微信公众号【Java技术江湖】
搞懂分布式技术2：分布式一致性协议与Paxos，Raft算法
该系列博文会告诉你什么是分布式系统，这对后端工程师来说是很重要的一门学问，我们会逐步了解常见的分布式技术、以及一些较为常见的分布式系统概念，同时也需要进一步了解zookeeper、分布式事务、分布式锁 本文较为粗略地讲述了一致性协议与两种一致性算法，更加系统的理论可以参考后面的分布式系统理论专题文章。 2PC 由于BASE理论需要在一致性和可用性方面做出权衡，因此涌现了很多关于一致性的算法和协议。 其中比较著名的有二阶提交协议（2 Phase Commitment Protocol），三阶提交协议（3 Phase Commitment Protocol）和Paxos算法。 本文要介绍的2PC协议，分为两个阶段提交一个事务。并通过协调者和各个参与者的配合，实现分布式一致性。 两个阶段事务提交协议，由协调者和参与者共同完成。 分布式事务处理的关键是： 需要记录事务在任何节点所做的所有动作；事务进行的所有操作要么全部提交，要么全部回滚。 2. XA规范 2.1.
86510发布于 2019-12-02 - 来自专栏卡尼慕
分布式共识算法
那么这里可以把问题定性为如何设计一套算法让所有节点当遇到分歧的时候能够达成一致。也就是基于异步通信的分布式共识问题。 同样，拜占庭将军问题也是一个类似的问题。这里的图片来自ppt。 ? 解决拜占庭将军问题 FLP不可能性定理 “在分布式异步通信的网络里，即便存在一个故障的节点，不存在可解决一致性的算法。” ，FLP不可能原理实际上告诉人们，不要浪费时间，去为异步分布式系统设计在任意场景下都能实现共识的算法。 但是！！！不存在任意情景下都适用的算法。但我们可以进行一些假设，来进行限制来简化问题。 假设2：拥有原计划（缺省值） 就是在所有人进攻之前就确定如果没有受到任何信息，即使信息被截，按照原计划进攻。 算法类型与相关研究 1、非拜占庭错误的情况：Paxos，Zab等 2、允许拜占庭错误：Extended Paxos、PBFT、工作量算法、权益证明。
64620发布于 2019-09-09 - 来自专栏ACM算法日常
浅谈分布式算法
可是等会大家就知道，分布式算法的基础是很简单的，即使对于raft这种比较好的一致性算法，可能只需要一个下午时间就能理解整个流程，相较于算法竞赛中的网络流之类的较为麻烦的算法，分布式的这些算法是比较简单的 分布式算法 分布式服务器的设计很多时候容易被程序员混淆，在我的理解上面，分布式服务器是能够横向扩展的，对于只是将功能分到不同模块的多进程做法，并不是分布式的做法。 MapReduce算法比较简单，只有2个函数，map和reduce，map函数负责处理数据，将处理的结果放在一个kv也就是map容器中（最终可能是输出到文件中），处理完成后，再由reduce函数汇总（规约 其实可以简单理解为内部节点的数据要保持一致，不能说a节点的字段x的值是1，另外一个节点b的字段x的值是2。 总结 如果没有MapReduce和raft这些算法，自己去实现分布式的计算和存储，可能不怎么现实，看起来简单的东西，可能是数学行业几十年的沉淀与研究产生的结果，而且分布式算法并没有出现百花齐放的状况，也可以说明研究一种算法就已经很困难
2.5K30发布于 2020-05-11 - 来自专栏技术总结
算法（2）
有两个算法 A 和 B ，假设两个算法的输入规模都是 n，算法 A 要做 2n+3 次操作，算法 B 要做 3n+1 次操作。觉得谁快？看下图： ? 而当 n = 2 时，两者效率相同；当 n > 2时，算法 A 就开始优于算法 B 了，随着 n 的增加， 算法 A 比算法 B 越来越好了，得出结论，算法 A 好过 算法 B 判断一个算法的效率时，函数中的常数和其他次要项常常可以忽略 2、在修改后的运行次数函数中，只保留最高阶项。 3、如果最高阶项存在且不是1，则去除与这个项相乘的常数，得到的结果就是大O阶 3、常数阶 高斯算法，时间复杂度不是O(3)，而是O(1)。 //第二种算法 int sum = 0, n = 100; /*执行1次*/ sum = (1 + n) * n/2; /*执行1次*/ printf( 也就是说，有多少个2相乘后大于n,则会退出循环。由2× = n ，得到 x = ㏒2n (2缩小)。所以这个循环的时间复杂度为O(㏒n)。
1.1K90发布于 2018-05-22 - 来自专栏凯哥Java
docker高级篇2-分布式存储之三种算法
面试题： 1~2亿条数据需要缓存，请问如何设计这个缓存案例？ 答：单机单台100%是不可能的。肯定是分布式缓存的。那么用Redis如何落地？ 一致性哈希算法分区： 一致性hash算法是什么？ 一致性hash算法在1997年麻省理工学院提出的，设计目标是为了解决： 分布式缓存数据变动和映射问题。 1：算法构建一致性哈希环； 一致性哈希算法必然有个hash函数并安装算法产生hash值，这个算法的所有可能哈希值会构成一个全量集，这个集合可以成为hash空间，范围是[0,2^32-1]，这是一个线性空间 ，但是在算法中，通过适当的逻辑控制将其首尾相连（0=2^32）,这样在逻辑上，就形成了一个环形的空间。 为什么会出现哈希槽算法？ 因为一致性哈希算法的数据倾斜问题，为了解决这个问题。 哈希槽实质上就是一个数组，数组[0,2^14-1]形成hash slot空间。 能干什么？
48820编辑于 2022-12-20 - 来自专栏悟空聊架构 | 公众号
2万字 | 写了八篇分布式算法，我“悟空”了
网上的资料能用大白话将分布式算法讲清楚的比较少。 学习分布式算法没有一条清晰的路线。 学习分布式协议和算法的路线可以是先学习四大基础理论，作为地基。然后再学习分布式协议和算法。 非拜占庭容错算法 在可信的环境，只需要具有故障容错能力，譬如 2PC、TCC、Paxos算法、Raft 算法、Gossip 协议、Ouorum NWR 算法、ZAB 协议。 在数据库操作层面，我们多使用二阶段提交协议（2PC）保证强一致性。在分布式系统中，多使用 Raft 算法来保证强一致性。 然后是 Paxos/Raft/ZAB/Quorum NWR/FBFT/POW 算法，能够容忍部分节点故障。 而 2PC、TCC 要求所有节点都正常运行，系统才能正常工作，可用性最低。 另外我将这八篇内容整理成了一份 PDF 文档，总共 2W+ 字，在公众号后台回复：【分布式】三个字即可获取。 分布式算法 PDF 1.0 文中插图 - END -
69730编辑于 2022-05-13 - 来自专栏凯哥Java
docker高级篇2-分布式存储之三种算法
面试题： 1~2亿条数据需要缓存，请问如何设计这个缓存案例？ 答：单机单台100%是不可能的。肯定是分布式缓存的。那么用Redis如何落地？ 一致性哈希算法分区： 一致性hash算法是什么？ 一致性hash算法在1997年麻省理工学院提出的，设计目标是为了解决： 分布式缓存数据变动和映射问题。 1：算法构建一致性哈希环； 一致性哈希算法必然有个hash函数并安装算法产生hash值，这个算法的所有可能哈希值会构成一个全量集，这个集合可以成为hash空间，范围是[0,2^32-1]，这是一个线性空间 ，但是在算法中，通过适当的逻辑控制将其首尾相连（0=2^32）,这样在逻辑上，就形成了一个环形的空间。 为什么会出现哈希槽算法？ 因为一致性哈希算法的数据倾斜问题，为了解决这个问题。 哈希槽实质上就是一个数组，数组[0,2^14-1]形成hash slot空间。 能干什么？
53140编辑于 2022-12-18 - 来自专栏java开发的那点事
分布式ID生成算法-雪花算法
原因:为什么需要雪花算法 为什么需要分布式全局唯一ID以及分布式ID的业务需求？集群高并发情况下如何保证分布式唯一全局Id生成？ 2：数据库压力还是很大，每次获取ID都得读写一次数据库， 非常影响性能，不符合分布式ID里面的延迟低和要高QPS的规则（在高并发下，如果都去数据库里面获取id，那是非常影响性能的） 基于Redis生成全局 可以初始化每台Redis的值分别是1,2,3,4,5，然后步长都是5。 15, 20, 25 来源 Twitter的分布式自增ID算法snowflake 概述 Twitter的snowflake解决了这种需求，最初Twitter把存储系统从MySQL迁移到Cassandra Twitter的分布式雪花算法SnowFlake ，经测试snowflake 每秒能够产生26万个自增可排序的ID Twitter的SnowFlake生成ID能够按照时间有序生成。
1.5K20发布于 2021-11-16 - 来自专栏Lixj's Blog
分布式id生成算法-snowflake算法
snowflake 算法是 twitter 开源的分布式 id 生成算法，采用 Scala 语言实现，是把一个 64 位的 long 型的 id，1 个 bit 是不用的，用其中的 41 bit 作为毫秒数
* SnowFlake的优点是，整体上按照时间自增排序，并且整个分布式系统内不会产生ID碰撞(由数据中心ID和机器ID作区分)，并且效率较高，经测试，SnowFlake每秒能够产生26万ID 41 bit可以表示的数字多达2^41 - 1，也就是可以标识2 ^ 41 - 1个毫秒值，换算成年就是表示69年的时间。 意思就是最多代表2 ^ 5个机房（32个机房），每个机房里可以代表2 ^ 5个机器（32台机器）。 Copyright: 采用 知识共享署名4.0 国际许可协议进行许可 Links: https://lixj.fun/archives/snowflake算法55420编辑于 2022-06-10 - 来自专栏焱融科技
分布式QoS算法解析
我们今天就来讨论一下分布式存储系统中的QoS算法。进入正题之前，我们先来了解背景知识，即什么是QoS，分布式QoS又是什么，有哪些常见的QoS算法。 我们似乎也无法在存储端做QoS算法，尤其是分布式并行文件系统，因为存储端各节点是分布式的，业务数据从不同client端发起，直接流向不同的存储端节点。 我们将这种场景称之为分布式QoS场景。 比如假设A请求Reservation为Ra，A请求均匀地发到3个server S1 S2 S3上，S1 S2 S3分别会满足Ra，最终结果是S1 S2 S3整体满足3*Ra，是指定Reservation 似乎需要S1 S2 S3上的mClock算法实例需要相互间建立联系，沟通彼此处理的请求情况，相互协调一下，才能使QoS的结果正确。 但显然这样的协调成本是很高的，这也不是dmClock的做法。 04 总结 我们讨论了QoS、分布式QoS、令牌桶等常见QoS算法，最后举例分析了mClock和dmClock算法。 关于dmClock，我们思考一个进一步的问题。
2.6K20发布于 2020-09-03 - 来自专栏程序员升级之路
分布式ID算法&实现
一、为什么需要分布式ID 1、跨机房部署 如果数据库是跨机房部署，分布式ID是必须的，不然后续做数据分析和统计、跨机房路由会踩大坑。 2、海量数据 如果数据量可能会超出数据库自增ID类型最大值， 分布式ID也是必然面对的。 二、分布式ID的需求有哪些 先看下功能性需求 1、全局唯一 即不管是哪个机房生成的，全局必须唯一，不能和其它机房产生的值冲突 2、单调递增 保证下一个ID一定大于上一个ID 3、具有一定的安全性 三、常用算法有 1、snowflake（雪花）算法 生成一个64bit的数字，数字被划分成多个段：时间戳、机器编码、序号。 优点： 整个ID是趋势递增的。 高吞吐量。 在分布式环境下，每台机器上的时钟可能有偏差，有时候会出现不是全局递增的情况。 2、基于数据库 一般基于数据库，充分利用MySQL自增ID的机制。
1.4K30发布于 2020-09-11 - 来自专栏云计算与大数据
分布式｜算法再认识
CAP理论是Eric Brewer教授在2000年提出 的，是描述分布式一致性的三个维度，分别是指： （1）一致性（Consistency） 每次读操作都能保证返回的是最新数据；在分布式系统中，如果能针对一个数据项的更新执行成功后 CAP指出，一个分布式系统只能满足三项中的两项而不可能满足全部三项。 Raft 特性： 强领导者（Strong Leader）：Raft 使用一种比其他算法更强的领导形式。例如，日志条目只从领导者发送向其他服务器。 这种方式仅仅是在所有算法都需要实现的心跳机制上增加了一点变化，它使得在解决冲突时更简单和快速。 从Paxos到Raft，分布式一致性算法解析 Paxos和Raft的前世今生
37820编辑于 2022-03-14 - 来自专栏面试
分布式的共识算法
共识算法（Consensus Algorithm）是分布式系统中一个关键的概念，主要用于确保多个节点在分布式环境中能够就某一状态达成一致。 本文将深入探讨共识算法的基本原理、常见类型及其在实际应用中的重要性。 一、共识算法的基本原理 共识算法的核心在于解决分布式系统中的一致性问题。 （2）投票和比较 节点收到其他节点的投票后，会根据以下规则进行比较： - **优先比较**`zxid`：`zxid`更大的节点优先，因为它表示该节点的数据更完整。 其他节点切换到Follower状态，并与Leader同步数据，确保所有节点的数据一致 假设这些服务器从id1-5，依序启动： 三、共识算法的应用场景 分布式数据库 在分布式数据库中，共识算法确保各节点的数据一致性 分布式文件系统 分布式文件系统（如 Google File System 和 HDFS）通过共识算法实现元数据的同步和一致性，确保文件系统在大规模分布式环境中的可靠性。
56010编辑于 2025-03-18 - 来自专栏AngelNI
排序算法-2
start++] =arr[p]; } } void mergesort(ll *A,ll start,ll end) { if(start<end) { ll mid = (start+end)/2; = a[i]; a[i] = a[j]; a[j] = t; } void heapify(ll *tree,ll n,ll i) { if(i>=n) return ; ll c1 = 2* i+1; ll c2 = 2*i+2; ll max = i; if(c1<n&&tree[c1]>tree[max]) { max = c1; } if(c2<n&&tree[c2]> tree[max]) { max = c2; } if(max ! = i) { swap(tree,max,i); heapify(tree,n,max); } } void heapsort(ll *a,ll n) { for(ll i =n/2-1;
30610发布于 2020-04-14 - 来自专栏修也的进阶日记
算法手记2
NC296 最小花费爬楼梯 牛客网题目链接(点击即可跳转):NC296 最小花费爬楼梯 题目详情: 本题详情如下图: 题目思路: 本题解题思路如下: 基础动态规划,1.写出动态转换方程2. vector<int>& cost) { vector<int> dp; dp.resize(cost.size()+1); for(int i=2; i<=cost.size();i++) dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]); return dp[cost.size ()]; } }; 结语 说点啥好呢...不断修补细节然后提高效率,不断学习算法并应用出肌肉记忆.
13200编辑于 2025-03-14 - 来自专栏Article
算法 Day 2
冒泡排序 平均时间复杂度 O(n2) 空间复杂度 O(1) function bubbleSort(arr) { var i = arr.length; var position =
13010编辑于 2022-06-14 - 来自专栏云深之无迹
Python 算法.2
如果 a+b+c=1000，且 a^2+b^2=c^2（a,b,c 为自然数），如何求出所有a、b、c可能的组合? + b**2 == c**2 and a+b+c == 1000: print("a, b, c: %d, %d, %d" % (a, b, c)) end_time + b**2 == c**2: print("a, b, c: %d, %d, %d" % (a, b, c)) end_time = time.time() print("elapsed (nlogn) < O(n2) < O(n3) < O(2n) < O(n!) = Timer("test2()", "from __main__ import test2") print("append ", t2.timeit(number=1000), "seconds")
57730发布于 2021-04-28 - 来自专栏java学习java
redis分布式锁（2）
index2获取了lock index2线程获取到了cpu的资源，开始执行方法 uuid=v2 set(lock,uuid)； index1执行删除，此时会把index2的lock删除 index1 因为已经在方法中了 index1已经比较完成了，这个时候，开始执行 删除的index2的锁！ { //1 声明一个uuid ,将做为一个value 放入我们的key所对应的值中 String uuid = UUID.randomUUID().toString(); //2 redisTemplate.opsForValue().setIfAbsent(locKey, uuid,3,TimeUnit.SECONDS); 总结 加锁 使用lua释放锁 重试 为了确保分布式锁可用
48440编辑于 2022-11-13 - 来自专栏数据云团
算法篇-python排序算法-2
让指定的元素归位，就是放到它应该放的位置（左边元素比它小，右边元素比他大），然后对每个元素归位，完成排序。
65330发布于 2019-07-18 - 来自专栏码农帮派
LeetCode中级算法-回溯算法（2）
子集 [题目] 给定一个不包含重复元素的数组，返回该数组所有可能的子集 [输入] [1,2,3] [返回] [[] [3] [2] [2 3] [1] [1 3] [1 2] [1 2 3]] [解法 所以我们在回溯index元素的时候，可以根据这两种状态分别进行回溯 [代码实现] package main import "fmt" func main() { input := []int {1,2,3 [ ["A","B","C","E"], ["S","F","C","S"], ["A","D","E","E"], ] [输入1] "ABCCED" [返回1] true [输入2] "ABCS" [返回2] false [解法] 这个题目的解点是第i个元素的上下左右是不是下一个元素，遍历整个字符串，当遍历到第i个字符串的时候，需要在上一个字母的坐标周围(上下左右)找到第i个字母
48720发布于 2021-01-12
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号