另外，服务器经常需要脚本，你需要知道shell脚本的知识。
然后，就是网络通信，服务器和客户端需要进行通信，你需要知道tcp/ip协议，网络编程，>一个任务的响应时间(response time)是指一个任务请求, 这个任务实际完成的时间跨度 在静态调度中, 任务的临界时刻(critical instant)这个概念被首先提出来 它被定义为一个特定的时刻, 如果在这个时刻有这个任务的请求, 那么这个任务就会需要最大的响应时间 由此得出定理1: 一个任务的临界时间就是比这个任务优先级高的所有任务同时发出请求的时刻定理1的价值在于它找到了一个证明一个调度算法能否调度任一任务集充分必要条件, 那就是所有任务同时请求执行的时的情况下每个任务仍能满足各自的期限, 那么这个任务集就可以被这个调度算法调度有了这个推论, 我们就可以证明RM调度的最优性了定理2: 如果一个任务集能够被静态调度, 那么RMS算法就能够调度这个任务集 从这个意义上说, RMS是最优的静态调度算法这个定理的证明方法就是有名的交换法 证明思路如下:假设一个任务集S采用其他静态优先级算法可以调度,那么总有这样两个优先级相邻的任务i和j, 有Ti>Tj,而Pi≤Pj把Ti和Tj的优先级Pi和Pj互换,明显可以看出这时S仍然可以调度, 因为在所有任务同时请求的情况下, 交换这两个任务不会影响其它任务的完成时间, 同时这两个任务都可以在各自期限内完成 按照这样的方法,其他任何静态优先级调度最终都可以转换成RM调度RMS已被证明是静态最优调度算法, 开销小, 灵活性好, 是实时调度的基础性理论。即使系统瞬时过载, 也完全可预测哪些任务丢失时限。缺点是处理机利用率较低, 最坏的情况下，当n→∞时, 不超过ln2 (≈ 70%)。另外, RMS是充分但非必要条件。而在一般情况下，对于随机的任务集大约只有88% 70%或者88%的处理器利用率对于许多实时应用来说是一个严重的限制，动态调度算法如最早截止期最先（earliest deadline first，EDF）或者最少空闲时间最先（least laxity first，LLF）已经被证明是最优的，并且能够实现100% 的处理器利用率具有资源同步约束的RMS调度当实时任务间共享资源时, 可能出现低优先级任务不可预测地阻塞高优先级任务执行的情况, 叫优先级倒置。这时RMS 算法不能保证任务集的调度, 必须使用有关协议控制优先级的倒置时间。常用的协议有优先级顶级协议和堆资源协议, 使用这些协议可使优先级的倒置时间最多为一个资源临界段的执行时间, 并且不会发生死锁。基于RMS 的非周期任务的调度实时系统中的非周期任务可采用延迟服务器算法或随机服务器算法进行调度。它们的最大特点是可在周期任务的实时调度环境下处理随机请求。两者的基本思想是将非周期任务转化成周期任务, 再利用RMS算法进行调度。前者用一个或几个专用的周期任务执行所有非周期任务, 这种周期任务叫非周期任务服务器。根据周期大小,服务器有固定优先级, 服务器的执行时间被称为预算, 它在每个服务器周期Ts 的起点补充。只要服务器有充足的预算, 就可在其周期内为非周期任务服务。该算法实现简单, 但可调度性分析较难, 有时会出现抖动, 可能发生一个非周期任务在相邻两个服务器周期中连续执行2倍预算的现象, 与RMS理论不符, 需要适当修改RMS算法。随机服务器算法与延迟服务器算法相似, 但预算不是在每个周期起点补充, 而是在预算消耗Ts时间之后再补充。该算法与RMS分析算法一致, 但实现复杂。EDF最早截止时间优先算法（EDF）也称为截止时间驱动调度算法（DDS），是一种动态调度算法。EDF指在调度时，任务的优先级更具任务的截止时间动态分配。截止时间越短，优先级越高。EDF有如下定理：定理2：如果一个任务集按EDF算法调度，当且仅当U<=1。EDF的特点(1) 任务模型: 与RMS 调度相同。(2) 优先级分配方法: 动态分配, 距要求时限所剩时间越短优先级越高。理论上，EDF和LLF算法都是单处理器下的最优调度算法。但是由于EDF和LLF在每个调度时刻都要计算任务的deadline或者空闲时间，并根据计算结果改变任务优先级，因此开销大、不易实现，其应用受到一定限制。多处理器实时调度
近年来，区块链技术（部分人更愿意称之为分布式账本技术）的走红将分布式技术的概念带入大众的视野。区块链技术之所以备受追捧，一方面是其展现了一种在计算机的辅助下，人类可以以无中心、无权威、无层级的方式来进行社会协作的美妙前景；另一方面，从物理上可论证，分布式的简单协议，比中心化的复杂协议更为高效。分布式技术似乎能够在带来公平的同时，还带来效率。
要理解分布式技术并不困难，因为分布式技术并不高深，但其设计上往往巧妙得令人拍手称赞。
本文介绍一种常见而巧妙的分布式技术，Kademlia算法。
Kademlia算法是一种分布式存储及路由的算法。什么是分布式存储？试想一下，一所1000人的学校，现在学校突然决定拆掉图书馆（不设立中心化的服务器），将图书馆里所有的书都分发到每位学生手上（所有的文件分散存储在各个节点上）。即是所有的学生，共同组成了一个分布式的图书馆。
在这种场景下，有几个关键的问题需要回答。
接下来，让我们来看看Kademlia算法如何巧妙地解决这些问题。
首先我们来看看每个同学（节点）都有哪些属性：
每个同学会维护以下内容：
根据上面那个类比，可以看看这个表格：
（Hash的概念解释，可参见 百度百科-哈希算法 ）
关于为什么不是每个同学都有全量通讯录（每个节点都维护全量路由信息）：其一，分布式系统中节点的进入和退出是相当频繁的，每次有变动时都全网广播通讯录更新，通讯量会很大；其二，一旦任意一个同学被坏人绑架了（节点被黑客攻破），则坏人马上就拥有了所有人的手机号码，这并不安全。
原来收藏在图书馆里，按索引号码得整整齐齐的书，以一种什么样的方式分发到同学们手里呢？大致的原则，包括：1）书本能够比较均衡地分布在同学们的手里，不会出现部分同学手里书特别多、而大部分同学连一本书都没有的情况；2）同学想找一本特定的书的时候，能够一种相对简单的索引方式找到这本书。
Kademlia作了下面这种安排：
假设《分布式算法》这本书的书名的hash值是 00010000 ，那么这本书就会被要求存在学号为 00010000 的同学手上。（这要求hash算法的值域与node ID的值域一致。Kademlia的Node ID是160位2进制。这里的示例对Node ID进行了简略）
但还得考虑到会有同学缺勤。万一 00010000 今天没来上学（节点没有上线或彻底退出网络），那《分布式算法》这本书岂不是谁都拿不到了？那算法要求这本书不能只存在一个同学手上，而是被要求同时存储在学号最接近 00010000 的k位同学手上，即 00010001 、 00010010 、 00010011 …等同学手上都会有这本书。
同样地，当你需要找《分布式算法》这本书时，将书名hash一下，得到 00010000 ，这个便是索书号，你就知道该找哪（几）位同学了。剩下的问题，就是找到这（几）位同学的手机号。
由于你手上只有一部分同学的通讯录，你很可能并没有 00010000 的手机号（IP地址）。那如何联系上目标同学呢？
一个可行的思路就是在你的通讯录里找到一位拥有目标同学的的同学。前面提到，每位同学手上的通讯录都是按距离分层的。算法的设计是，如果一个同学离你越近，你手上的通讯录里存有ta的手机号码的概率越大。而算法的核心的思路就可以是：当你知道目标同学Z与你之间的距离，你可以在你的通讯录上先找到一个你认为与同学Z最相近的同学B，请同学B再进一步去查找同学Z的手机号。
上文提到的距离，是学号（Node ID）之间的异或距离(XOR distance）。异或是针对yes/no或者二进制的运算
举2个例子：
01010000 与 01010010 距离（即是2个ID的异或值）为 00000010 （换算为十进制即为2）；
01000000 与 00000001 距离为 01000001 （换算为十进制即为2 6 +1，即65）；
如此类推。
那通讯录是如何按距离分层呢？下面的示例会告诉你，按异或距离分层，基本上可以理解为按位数分层。设想以下情景：
以 0000110 为基础节点，如果一个节点的ID，前面所有位数都与它相同，只有最后1位不同，这样的节点只有1个—— 0000111 ，与基础节点的异或值为 0000001 ，即距离为1；对于 0000110 而言，这样的节点归为 “k-bucket 1” ；
如果一个节点的ID，前面所有位数相同，从倒数第2位开始不同，这样的节点只有2个： 0000101 、 0000100 ，与基础节点的异或值为 0000011 和 0000010 ，即距离范围为3和2；对于 0000110 而言，这样的节点归为 “k-bucket 2” ；
……
如果一个节点的ID，前面所有位数相同，从倒数第n位开始不同，这样的节点只有2 (i-1) 个，与基础节点的距离范围为[2 (i-1) , 2 i ）；对于 0000110 而言，这样的节点归为 “k-bucket i” ；
对上面描述的另一种理解方式：如果将整个网络的节点梳理为一个按节点ID排列的二叉树，树最末端的每个叶子便是一个节点，则下图就比较直观的展现出，节点之间的距离的关系。
回到我们的类比。每个同学只维护一部分的通讯录，这个通讯录按照距离分层（可以理解为按学号与自己的学号从第几位开始不同而分层），即k-bucket1, k-bucket 2, k-bucket 3…虽然每个k-bucket中实际存在的同学人数逐渐增多，但每个同学在它自己的每个k-bucket中只记录k位同学的手机号（k个节点的地址与端口，这里的k是一个可调节的常量参数）。
由于学号（节点的ID）有160位，所以每个同学的通讯录中共分160层（节点共有160个k-bucket）。整个网络最多可以容纳2^160个同学（节点），但是每个同学（节点）最多只维护160 k 行通讯录（其他节点的地址与端口）。
我们现在来阐述一个完整的索书流程。
A同学（学号 00000110 ）想找《分布式算法》，A首先需要计算书名的哈希值，hash(《分布式算法》) = 00010000 。那么A就知道ta需要找到 00010000 号同学（命名为Z同学）或学号与Z邻近的同学。
Z的学号 00010000 与自己的异或距离为 00010110 ，距离范围在[2 4 , 2 5 )，所以这个Z同学可能在k-bucket 5中（或者说，Z同学的学号与A同学的学号从第5位开始不同，所以Z同学可能在k-bucket 5中）。
然后A同学看看自己的k-bucket 5有没有Z同学：
Kademlia的这种查询机制，有点像是将一张纸不断地对折来收缩搜索范围，保证对于任意n个学生，最多只需要查询log 2 (n)次，即可找到获得目标同学的（即在对于任意一个有[2 (n−1) , 2 n )个节点的网络，最多只需要n步搜索即可找到目标节点）。
以上便是Kademlia算法的基本原理。以下再简要介绍协议中的技术细节。
Kademlia算法中，每个节点只有4个指令
该机制保证了任意节点加入和离开都不影响整体网络。
Kademlia是分布式哈希表（Distributed Hash Table, DHT）的一种。而DHT是一类去中心化的分布式系统。在这类系统中，每个节点（node）分别维护一部分的存储内容以及其他节点的路由/地址，使得网络中任何参与者（即节点）发生变更（进入/退出）时，对整个网络造成的影响最小。DHT可以用于构建更复杂的应用，包括分布式文件系统、点对点技术文件分享系统、合作的网页高速缓存、域名系统以及实时通信等。
Kademlia算法在2002年由Petar Maymounkov 和 David Mazières 所设计，以异或距离来对哈希表进行分层是其特点。Kademlia后来被eMule、BitTorrent等P2P软件采用作为底层算法。Kademlia可以作为信息安全技术的奠基之一。
Kademlia的优点在于：
参考文献
wiki百科-分布式哈希表
wiki百科-Kademlia
Kademlia: A Peer-to-peer information system based on the XOR Metric
王子亭的Kademlia笔记
韩锋《区块链的人工智能》新星出版社《区块链新经济蓝图及导读》的译后注
零成本：只是在DNS服务器上绑定几个A记录，域名注册商一般都免费提供解析服务；
部署简单：就是在网络拓扑进行设备扩增，然后在DNS服务器上添加记录。
DNS轮询的缺点：
1、可靠性低
假设一个域名DNS轮询多台服务器，如果其中的一台服务器发生故障，那么所有的访问该服务器的请求将不会有所回应，这是任何人都不愿意看到的。即使从DNS中去掉该服务器的IP，但在Internet上，各地区电信、网通等宽带接入商将众多的DNS存放在缓存中，以节省访问时间，DNS记录全部生效需要几个小时，甚至更久。所以，尽管DNS轮询在一定程度上解决了负载均衡问题，但是却存在可靠性不高的缺点。
2、负载分配不均匀（有，但不会有那么大的影响）
DNS负载均衡采用的是简单的轮询算法，不能区分服务器的差异，不能反映服务器的当前运行状态，不能做到为性能较好的服务器多分配请求，甚至会出现客户请求集中在某一台服务器上的情况。
DNS服务器是按照一定的层次结构组织的，本地DNS服务器会缓存已解析的域名到IP地址的映射，这会导致使用该DNS服务器的用户在一段时间内访问的是同一台Web服务器，导致Web服务器间的负载不均匀。此外，用户本地计算机也会缓存已解析的域名到IP地址的映射。当多个用户计算机都缓存了某个域名到IP地址的映射时，而这些用户又继续访问该域名下的网页，这时也会导致不同Web服务器间的负载分配不均匀。
负载不均匀可能导致的后果有：某几台服务器负荷很低，而另几台服务器负载很高、处理缓慢；配置高的服务器分配到的请求少，而配置低的服务器分配到的请求多。多核服务器和多个epoll没什么关系，多核能力还是留给CPU计算型任务吧，至于网络IO，一个epoll实例轻松处理10K以上并发连接。只遇到过后续处理数据的瓶颈，没遇过epoll接入和收发数据的瓶颈。
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）