img_0980.jpg
    这节有点难。。。
    img_0981.jpg
    这一章 主要讲的是
    (1)时钟同步
    (2)相互排斥
    (3)节点的全局定位
    (4)超级节点
    花了很大时间在(1)(2)两节
    img_0982.jpgimg_0983.jpg
    之前在在分布式系统简介里提到(DS-CH1-introduction)
    decentralized algorithm的4条原则里:
    1,没有一个节点知道整个系统的信息
    2,节点决策仅仅依靠局部信息
    3,一台机器故障不会影响系统
    4,没有全局时钟的概念

    那如果时钟同步很重要(这是很明显的)
    那在分布式系统中,我们应该怎么做?
    img_0984.jpgimg_0985.jpgimg_0986.jpgimg_0987.jpgimg_0988.jpgimg_0989.jpgimg_0990.jpgimg_0991.jpgimg_0992.jpgimg_0993.jpgimg_0994.jpgimg_0995.jpgimg_0996.jpgimg_0997.jpgimg_0998.jpg
    分布式系统时钟同步问题:
    (1)Chritian算法
    (2)Berkeley算法
    img_0999.jpg
    这个就是典型一个集中式服务器,把时间当成一个信息,想知道时间,就去time server上去请求一下,
    优点:简单,好部署,集中式服务器的特点都有
    但是有缺点:信息传输过程中是有延迟的!!!发过来的时间不是当前时间啊!!

    img_1001.jpgimg_1002.jpgimg_1003.jpgimg_1004.jpgimg_1005.jpgimg_1006.jpgimg_1007.jpgimg_1008.jpg
    Berkeley算法是没有time server的
    看上面步骤
    (a)
    (b)
    (c)
    img_1009.jpg
    在分布式系统中进行物理时钟同步的代价很高,
    因为每一个节点,都有自己的物理时钟,分布式系统里的节点数太大了,去同步成一个时钟,不太可能
    所以那既然这样
    对每次的操作前,对操作的参与节点,标上逻辑前后顺序关系,这样做,是不是就是很简单了呢!!!
    img_1010.jpg
    使用happen-before来表示这种逻辑关系
    如果e1发生在e2之前,就叫e1 happen before e2 记做《分布式与云计算》第6期-DS-CH6-Synchronization - 图31

    也正如前面所说的操作参与了,才能标记逻辑顺序
    如果两个节点没有信息交互,此时就没有顺序而言,标记顺序也没有用,所有这也是物理时钟同步代价高的原因,没必要进行大量无意义的时钟同步
    img_1011.jpg
    如果两个事件没有先后顺序,就称a与b并发 a||b
    img_1012.jpg
    上面简单的描述了一下 happen-before关系

    img_1013.jpg
    进一步优化
    增加一个timestamp 如果《分布式与云计算》第6期-DS-CH6-Synchronization - 图35 ,则C(e1)所以,每个进程都会维护自己的逻辑时钟
    进程本身的事件好维护,每发生一个事件,逻辑时钟+1
    产生进程间通信也好维护,就直接把让接收消息的进程进行逻辑时钟调max+1,细节如下

    img_1014.jpg

    img_1015.jpgimg_1016.jpg
    对排序按时间的严格性分为
    全序更新:全部事件都要排序
    因果序更新:有因果关系才排序
    FIFO:有先后顺序的才排序
    这里在逻辑时钟(lamport时钟)就有疑问了,对于数据库和备选数据库来说,update1和update2两个操作是并发的,不好来规定逻辑时钟,但是这两操作必须要有先后顺序,不然不能保证两个数据库的数据一致,
    解决方案如下:
    img_1017.jpg
    这里介绍使用逻辑时钟实现全序多播的方案:

    img_1018.jpgimg_1019.jpgimg_1020.jpg
    Vector Clock 记录进程所发生的的事件数
    看下面的演示

    img_1021.jpgimg_1022.jpg

    img_1023.jpgimg_1024.jpgimg_1025.jpgimg_1026.jpgimg_1027.jpgimg_1028.jpgimg_1029.jpgimg_1030.jpg
    怎么根据消息的矢量戳和本身的矢量戳来决定是否延迟
    (1)先看第一行,第一行应该是小于1,表示,前面你发的我都收到了
    (2)再看剩下的,表示0号进程收到的其他消息,我这个进程也都接收到
    img_1031.jpgimg_1032.jpgimg_1033.jpg
    回顾一下,操作系统的临界区问题
    img_1034.jpgimg_1035.jpg

    评价分布式系统的时候增加两个指标
    MC:每个CS条目进程交换的信息数
    SD:经过多少个消息才进入临界区

    img_1036.jpg
    本节Mutual exclusion主要讲在分布式系统中,怎么协调多节点对资源的访问
    分为
    (1)集中式
    (2)分散式
    (3)分布式
    img_1037.jpg
    集中式互斥访问,把集中式的服务器当成老城管了;

    优点:容易部署,简单
    缺点:容易阻塞,节点崩溃
    img_1038.jpg
    分散式互斥访问算法:
    增加协调器,进行多数表决

    img_1039.jpgimg_1040.jpgimg_1041.jpgimg_1042.jpg
    看下面的分布式互斥访问算法方式:
    (1)0号,2号都想要访问资源,所以0号,2号都要把访问资源时间发出去,1号不想访问资源,就不用发送时间戳
    (2)1号接收别人请求资源的消息且自己不需要访问资源,就都回了个OK,
    (3)2号因为访问资源的时间戳比0号小,所以就给0号发送OK,说0号节点,你先访问
    (4)0号节点在都收到其他节点的OK后,就去访问资源,并且也记下了2号也是访问资源的,所以在访问完资源后,就对2号发送OK,叫2号节点去访问资源
    img_1043.jpgimg_1044.jpgimg_1045.jpg
    a token ring算法,就是把资源在节点环上循环,不想访问丢给下一家,想访问就去访问
    比较适合大家都想访问的那种资源,比较公平且高效
    img_1046.jpgimg_1047.jpgimg_1048.jpgimg_1049.jpgimg_1050.jpgimg_1051.jpgimg_1052.jpgimg_1053.jpgimg_1054.jpgimg_1055.jpgimg_1056.jpgimg_1057.jpgimg_1058.jpgimg_1059.jpgimg_1060.jpgimg_1061.jpg
    分布式系统死锁检测内容

    IMG_1758(20200624-194914).JPGIMG_1759(20200624-194914).JPG
    分布式系统死锁检测是重点!!
    IMG_1760(20200624-194914).JPGIMG_1761(20200624-194914).JPGIMG_1762(20200624-194914).JPGIMG_1763(20200624-194914).JPGIMG_1764(20200624-194914).JPGIMG_1765(20200624-194914).JPGIMG_1766(20200624-194914).JPGIMG_1767(20200624-194915).JPGIMG_1768(20200624-194915).JPGIMG_1769(20200624-194915).JPGIMG_1770(20200624-194915).JPGIMG_1771(20200624-194915).JPGIMG_1772(20200624-194915).JPGIMG_1773(20200624-194915).JPG