首页
精选文章一致性查看全文在分布式环境下，因为多副本，网络分区，硬件故障，物理距离等问题导致的数据乱序问题，延迟问题，不可达问题是不可避免的，一致性问题就是在诸多不确定因素下，保证程序的正确性。影响正确性主要有以下的原因： 并发 在单线程单核场景下，程序的执行顺序和程序表达的逻辑顺序是一致的，不会出现数据不一致的情况，但是在多线程场景下，多个线程共享存储器，线程读取的数据可以是其他线程写入的值，此时从当前线程的视角来看，数据的正确性因为共享存储的原因，需要更多的进行协调。 延迟 延迟不仅仅发生在分布式系统下，即使是单机的数据读写也不是一个瞬时的过程，从距离CPU 30厘米的内存条中读取数据至少需要几个纳秒，而不同的数据机房甚至远隔几千公里。物理距离导致了不同服务器之间的数据会因为不同的延迟而数据不一致。 而在分布式系统中，因为延迟问题被放大，甚至会产生不可达的情况，所以我们没办法完全避免歧义的产生。只能增加一些特定的约束。这些约束就是一致性的理论基础，分为线性一致性和顺序一致性。 线性一致性 虽然每个操作都是有耗时的，线性一致性的约束是指每个涉及到数据的操作都是原子的，这里的原子并非是指这些操作是物理上不可中断的，可以横跨多个系统组件甚至多台机器，但是其外部表现和一个原子操作是等效的。 我们可以利用线性一致性的原子性约束来安全地修改状态。我们定义一个类似CAS（compare-and-set）的操作，当且仅当寄存器持有某个值的时候，我们可以往它写入新值。 CAS操作可以作为互斥量，信号量，通道，计数器，列表，集合，映射，树等等的实现基础，使得这些共享数据结构变得可用。线性一致性保证了变更的安全交错。 此外，线性一致性的时间界限保证了操作完成后…布隆过滤器查看全文布隆过滤器是Bloom提出了过滤机制，主要用于判断数据是否存在，如果数据存在返回true，否则返回false，但是当返回true的时候布隆过滤器不保证数据一定准确，也就是可能一定的假存在的可能性，但返回false的时候数据一定是不存在的。布隆过滤器一般通过Bitmap和一组Hash函数构成，当值被写入持久化存储的同时写入布隆过滤器，写入逻辑如下： 将Hash函数组中的每个Hash函数对Key进行Hash操作。 Hash操作之后进行位置运算，例如对bitmap数组的长度取模。 将Hash结果对应的位置写入1 在查询的时候，也会运用这一组Hash函数分别对请求值进行Hash和位置运算，最后判断这一组的结果值是否全为1，如果不是全1，则数据一定不存在，反之如果为0，则判定数据存在，但是因为Hash冲突的原因，所以全为1也有一定的误差存在，尤其是bitmap的空间不足的时候。 和其他表示集合类的数据结构，例如平衡二叉搜索树、Trie 树、哈希表，数组或者链表，布隆过滤器的空间复杂度最低，因为布隆过滤器不存储数据本身，而仅仅存储数据的一组哈希值，而且位数组的存储结构也更加紧凑，避免了指针开销。 布隆过滤器的仅仅需要计算一组Hash值，时间复杂度也接近O（1）。三阶段提交查看全文三阶段提交是分布式事务的一种实现方案，是两阶段提交的优化。两阶段存在阻塞问题和一致性问题。 阻塞 两阶段提交中协调者发起的准备指令和提交指令必须收到所有参与者的返回才能决定后续的状态，否则将持续处于阻塞状态，此时占用的资源会被一直锁定，长期占据的资源会对性能有较大的影响。 协调者在执行事务的过程中如果发生故障，则所有的参与者都会陷入阻塞等待后续指令。 不一致 协调者发送提交指令，部分参与者成功提交了事务，部分参与者未能接受提交指令，此时多个参与者的状态就出现了不一致的情况。 如果部分参与者在接收到提交指令之后发生宕机，而此时协调者也发生了宕机，后续选举出来的协调者的继任者无法确定所有参与者的状态，此时会出现故障。 三阶段针对两阶段存在的两个问题，阻塞和不一致问题给出了解决方案，其中，阻塞问题通过引入超时机制解决，不一致问题通过引入新的阶段预提交环节解决。 三阶段提交将分布式事务分成三个环节，准备阶段，预提交阶段，提交阶段。 准备阶段 和两阶段提交类似，准备阶段的主要功能也是完成资源锁定以及数据写入等操作，准备阶段通过将锁等资源获取前置，减少后续提交阶段失败的可能性。 三阶段事务的准备阶段，协调者会对所有的参与者发起准备的指令。 参与者接收到准备指令之后，进行事务操作，本环节的事务操作一般包括资源锁定，记录回滚日志（Undolog），执行成功会给协调者发送成功的返回，否则返回失败。 协调者收到所有参与者的返回都是成功时，而阶段提交会进入提交阶段。 协调者如果收到部分参与者的返回是失败的时候，则将成功的参与者进行回滚。 预提交阶段 三阶段提交的预提交阶段会完成事务中剩余的操作。 如果在预提交阶段进行回滚… |
热门分类开源Golang消息队列JavaJavascriptLinuxMysqlNLPPHP事务内存管理分布式理论分类存储常用存储开源软件操作系统画图网络编程数据库算法虚拟化前端存储理论常用算法微服务数据结构算法应用计算机原理中间件共识算法分布式分治动态规划容器并发排序架构组件绘图工具网络协议编程语言理论算法思想树缓存架构C++字符串算法工程思想搜索
算法题库精选内容 |
