分布式缓存和一致性哈希python

Ⅰ 如何用python一门语言通吃高性能并发，GPU计算和深度学习

第一个就是并发本身所带来的开销即新开处理线程、关闭处理线程、多个处理线程时间片轮转所带来的开销。

实际上对于一些逻辑不那么复杂的场景来说这些开销甚至比真正的处理逻辑部分代码的开销更大。所以我们决定采用基于协程的并发方式，即服务进程只有一个(单cpu)所有的请求数据都由这个服务进程内部来维护，同时服务进程自行调度不同请求的处理顺序，这样避免了传统多线程并发方式新建、销毁以及系统调度处理线程的开销。基于这样的考虑我们选择了基于Tornado框架实现api服务的开发。Tornado的实现非常简洁明了，使用python的生成器作为协程，利用IOLoop实现了调度队列。

第二个问题是数据库的性能，这里说的数据库包括MongoDB和Redis，我这里分开讲。

先讲MongoDB的问题，MongoDB主要存储不同的用户对于验证的不同设置，比如该显示什么样的图片。
一开始每次验证请求都会查询MongoDB，当时我们的MongoDB是纯内存的，同时三台机器组成一个复制集，这样的组合大概能稳定承载八九千的qps，后来随着我们验证量越来越大，这个承载能力逐渐就成为了我们的瓶颈。
为了彻底搞定这个问题，我们提出了最极端的解决方案，干脆直接把数据库中的数据完全缓存到服务进程里定期批量更新，这样查询的开销将大大降低。但是因为我们用的是Python，由于GIL的存在，在8核服务器上会fork出来8个服务进程，进程之间不像线程那么方便，所以我们基于mmap自己写了一套伙伴算法构建了一个跨进程共享缓存。自从这套缓存上线之后，Mongodb的负载几乎变成了零。
说完了MongoDB再说Redis的问题，Redis代码简洁、数据结构丰富、性能强大，唯一的问题是作为一个单进程程序，终究性能是有上限的。
虽然今年Redis发布了官方的集群版本，但是经过我们的测试，认为这套分布式方案的故障恢复时间不够优秀并且运维成本较高。在Redis官方集群方案面世之前，开源世界有不少proxy方案，比如Twtter的TwemProxy和豌豆荚的Codis。这两种方案测试完之后给我们的感觉TwemProxy运维还是比较麻烦，Codis使用起来让人非常心旷神怡，无论是修改配置还是扩容都可以在配置页面上完成，并且性能也还算不错，但无奈当时Codis还有比较严重的BUG只能放弃之。
几乎尝试过各种方案之后，我们还是下决心自己实现一套分布式方案，目的是高度贴合我们的需求并且运维成本要低、扩容要方便、故障切换要快最重要的是数据冗余一定要做好。
基于上面的考虑，我们确定基于客户端的分布式方案，通过zookeeper来同步状态保证高可用。具体来说，我们修改Redis源码，使其向zookeeper注册，客户端由zookeeper上获取Redis服务器集群信息并根据统一的一致性哈希算法来计算数据应该存储在哪台Redis上，并在哈希环的下一台Redis上写入一份冗余数据，当读取原始数据失败时可以立即尝试读取冗余数据而不会造成服务中断。

Ⅱ python面试之分布式

主要用于分散压力，所以分布式的服务都是部署在不同的服务器上的，再将服务做集群

根据“分层”的思想进行拆分。
例如，可以将一个项目根据“三层架构” 拆分

然后再分开部署 ：

根据业务进行拆分。
例如，可以根据业务逻辑，将“电商项目”拆分成 “订单项目”、“用户项目”和“秒杀项目” 。显然这三个拆分后的项目，仍然可以作为独立的项目使用。像这种拆分的方法，就成为垂直拆分

主要用于分散能力，主要是将服务的颗粒度尽量细化，且自成一脉，压力这块并不是其关注的点，所以多个微服务是可以部署在同一台服务器上的

微服务可以理解为一种 非常细粒度的垂直拆分 。例如，以上“订单项目”本来就是垂直拆分后的子项目，但实际上“订单项目”还能进一步拆分为“购物项目”、“结算项目”和“售后项目”，如图

现在看图中的“订单项目”，它完全可以作为一个分布式项目的组成元素，但就不适合作为微服务的组成元素了（因为它还能再拆，而微服务应该是不能再拆的“微小”服务，类似于“原子性”）

分布式服务需要提供给别的分布式服务去调用，单独拆出来 未必外部可用
微服务自成一脉，可以系统内部调用，也可以单独提供服务

为什么需要用分布式锁，见下图

变量A存在三个服务器内存中（这个变量A主要体现是在一个类中的一个成员变量，是一个有状态的对象），如果不加任何控制的话，变量A同时都会在分配一块内存，三个请求发过来同时对这个变量操作，显然结果是不对的！即使不是同时发过来，三个请求分别操作三个不同内存区域的数据，变量A之间不存在共享，也不具有可见性，处理的结果也是不对的。

分布式锁应该具备哪些条件：

1、在分布式系统环境下，一个方法在同一时间只能被一个机器的一个线程执行；
2、高可用的获取锁与释放锁；
3、高性能的获取锁与释放锁；
4、具备可重入特性；
5、具备锁失效机制，防止死锁；
6、具备非阻塞锁特性，即没有获取到锁将直接返回获取锁失败

Redis性能高
命令简单，实现方便

使用setnx加锁，key为锁名，value随意不重复就行（一般用uuid）
给锁添加expire时间，超过该时间redis过期（即自动释放锁）
设置获取锁的超时时间，若超过时间，则放弃获取锁

通过锁名获取锁值
比较锁值和当前uuid是否一致，一致则释放锁（通过delete命令删除redis键值对）

2PC：two phase commit protocol，二阶段提交协议，是一种强一致性设计。
同步阻塞（导致长久的资源锁定） ，只有第一阶段全部正常完成（返回失败，回字返回超时都会返回 “准备失败” ），才会进入第二阶段

因为协调者可能会在任意一个时间点（发送准备命令之前，发送准备命令之后，发送回滚事务命令之前，发送回滚事务命令之后，发送提交事务命令之前，发送提交事务命令之后）故障，导致资源阻塞。

T：try，指的是预留，即资源的预留和锁定，注意是预留
C：confirm，指的是确认操作，这一步其实就是真正的执行了
C：cancel，指的是撤销操作，可以理解为把预留阶段的动作撤销了

从思想上看和 2PC 差不多，都是先试探性的执行，如果都可以那就真正的执行，如果不行就回滚。

适用于对实时性要求没那么高的业务场景，如：短信通知

Ⅲ Python性能提升神器！lru_cache的介绍和讲解

我们经常谈论的缓存一词，更多的类似于将硬盘中的数据存放到内存中以至于提高读取速度，比如常说的redis，就经常用来做数据的缓存。 Python的缓存（lru_cache）是一种装饰在被执行的函数上，将其执行的结果缓存起来，当下次请求的时候，如果请求该函数的传参未变则直接返回缓存起来的结果而不再执行函数的一种缓存装饰器。

那它和redis的区别在哪？有什么优势？怎么使用？ 下面为你讲解

1.现在我们先不使用缓存来写一个求两数之和的函数，并调用执行它两次：

执行结果

可以看到 test 被执行了两次，现在我们加上缓存再进行执行：

执行结果

可以看到 test 函数只被执行了一次，第二次的调用直接输出了结果，使用了缓存起来的值。

2.当我们使用递归求斐波拉契数列 （斐波那契数列指的是这样一个数列：0,1,1,2,3,5,8，它从第3项开始，每一项都等于前两项之和） 的时候，缓存对性能的提升就尤其明显了：

不使用缓存求第40项的斐波拉契数列

执行时间

使用缓存求第40项的斐波拉契数列：

执行时间

两个差距是非常明显的，因为不使用缓存时，相当于要重复执行了很多的函数，而使用了 lru_cache 则把之前执行的函数结果已经缓存了起来，就不需要再次执行了。

查看lru_cache源码会发现它可以传递两个参数： maxsize 、 typed ：

代表被lru_cache装饰的方法最大可缓存的结果数量 （被装饰方法传参不同一样，则结果不一样；如果传参一样则为同一个结果） ， 如果不指定传参则默认值为128，表示最多缓存128个返回结果，当达到了128个时，有新的结果要保存时，则会删除最旧的那个结果。如果maxsize传入为None则表示可以缓存无限个结果；

默认为false，代表不区分数据类型，如果设置为True，则会区分传参类型进行缓存，官方是这样描述的:

但在python3.9.8版本下进行测试，typed为false时，按照官方的测试方法测试得到的还是会被当成不同的结果处理，这个时候typed为false还是为true都会区别缓存，这与官方文档的描述存在差异：

执行结果

但如果是多参数的情况下，则会被当成一个结果：

执行结果

这个时候设置typed为true时，则会区别缓存：

执行结果

当传参个数大于1时，才符合官方的说法，不清楚是不是官方举例有误

当传递的参数是dict、list等的可变参数时，lru_cache是不支持的，会报错：

报错结果

缓存 缓存位置 是否支持可变参数 是否支持分布式 是否支持过期时间设置 支持的数据结构 需单独安装 redis 缓存在redis管理的内存中 是 是 是 支持5种数据结构 是 lru_cache 缓存在应用进程的内存中，应用被关闭则被清空 否 否 否 字典（参数为：key，结果为：value） 否

经过上面的分析，lru_cache 功能相对于redis来说要简单许多，但使用起来更加方便，适用于小型的单体应用。如果涉及的缓存的数据种类比较多并且想更好的管理缓存、或者需要缓存数据有过期时间（类似登录验证的token）等，使用redis是优于lru_cache的。

Ⅳ 一致性hash算法是什么

一致性哈希算法是在1997年由麻省理工学院提出的一种分布式哈希（DHT）算法。其设计目标是为了解决因特网中的热点（Hot spot)问题，初衷和CARP十分类似。

一致性Hash是一种特殊的Hash算法，由于其均衡性、持久性的映射特点，被广泛的应用于负载均衡领域，如nginx和memcached都采用了一致性Hash来作为集群负载均衡的方案。

一致性哈希算法的目标是，当K个请求key发起请求时。后台增减节点，只会引起K/N的key发生重新映射。即一致性哈希算法，在后台节点稳定时，同一key的每次请求映射到的节点是一样的。而当后台节点增减时，该算法尽量将K个key映射到与之前相同的节点上。

优点

可扩展性。一致性哈希算法保证了增加或减少服务器时，数据存储的改变最少，相比传统哈希算法大大节省了数据移动的开销。

更好地适应数据的快速增长。采用一致性哈希算法分布数据，当数据不断增长时，部分虚拟节点中可能包含很多数据、造成数据在虚拟节点上分布不均衡，此时可以将包含数据多的虚拟节点分裂，这种分裂仅仅是将原有的虚拟节点一分为二、不需要对全部的数据进行重新哈希和划分。

虚拟节点分裂后，如果物理服务器的负载仍然不均衡，只需在服务器之间调整部分虚拟节点的存储分布。这样可以随数据的增长而动态的扩展物理服务器的数量，且代价远比传统哈希算法重新分布所有数据要小很多。

以上内容参考：网络-一致性哈希

Ⅳ 哈希表、哈希算法、一致性哈希表

    散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。它通过把关键码映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数（哈希函数），存放记录的数组叫做散列表。

  优点：

        哈希表可以提供快速的操作。

缺点：

        哈希表通常是基于数组的，数组创建后难于扩展。

        也没有一种简便的方法可以以任何一种顺序〔例如从小到大）遍历表中的数据项 。

    综上， 如果不需要有序遍历数据，井且可以提前预测数据量的大小。那么哈希表在速度和易用性方面是无与伦比的。

        1. 使用哈希函数将被查找的键转换为数组的索引。

        2. 处理哈希碰撞冲突。

    若关键字为 k ，则其值存放在 f(k) 的存储位置上。由此，不需比较便可直接取得所查记录。称这个对应关系 f 为散列函数，按这个思想建立的表为散列表。

    若对于关键字集合中的任一个关键字，经散列函数映象到地址集合中任何一个地址的概率是相等的，则称此类散列函数为 均匀散列函数 (Uniform Hash function)，这就是使关键字经过散列函数得到一个"随机的地址"，从而减少碰撞。

散列函数能使对一个数据序列的访问过程更加迅速有效，通过散列函数，数据元素将被更快地定位。

一个好的散列函数一般应该考虑下列因素 ：

    1.计算简单，以便提高转换速度。

    2.关键词对应的地址空间分布均匀，以尽量减少冲突。

1.   直接寻址法

    取关键字或者关键字的某个线性函数值作为哈希地址,即H(Key)=Key或者H(Key)=a*Key+b(a,b为整数),这种散列函数也叫做自身函数.如果H(Key)的哈希地址上已经有值了,那么就往下一个位置找,直到找到H(Key)的位置没有值了就把元素放进去。

2.   数字分析法

    数字分析法就是找出数字的规律，尽可能利用这些数据来构造冲突几率较低的散列地址。

3.   平方取中法

    取关键字平方后的中间几位作为散列地址。这种方法的原理是通过取平方扩大差别，平方值的中间几位和这个数的每一位都相关，则对不同的关键字得到的哈希函数值不易产生冲突，由此产生的哈希地址也较为均匀。该方法适用于关键字中的每一位都有某些数字重复出现频度很高的现象。

4.   折叠法

    折叠法是将关键字分割成位数相同的几部分,最后一部分位数可以不同,然后取这几部分的叠加和(注意:叠加和时去除进位)作为散列地址。

    数位叠加可以有移位叠加和间界叠加两种方法。移位叠加是将分割后的每一部分的最低位对齐,然后相加;间界叠加是从一端向另一端沿分割界来回折叠,然后对齐相加。

    该方法适用于关键字特别多的情况。

5.   随机数法

    选择一个随机数,作为散列地址,通常用于关键字长度不同的场合。

6.   除留余数法

    取关键字被某个不大于散列表表长m的数p除后所得的余数为散列地址.即H(Key)=Key MOD p,p<=m.不仅可以对关键字直接取模,也可在折叠、平方取中等运算之后取模。对p的选择很重要，一般取素数或m，若p选得不好，则很容易产生冲突。

    对不同的关键字可能得到同一散列地址，即 k1≠k2 ，而 f(k1)=f(k2) ，这种现象称为碰撞(英语:Collision)。具有相同函数值的关键字对该散列函数来说称做同义词。

    通过构造性能良好的散列函数，可以减少冲突，但一般不可能完全避免冲突，因此解决冲突是哈希法的另一个关键问题。 创建哈希表和查找哈希表都会遇到冲突，两种情况下解决冲突的方法应该一致。

下面以创建哈希表为例，说明解决冲突的方法。

1.开放寻址法

    这种方法也称再散列法，其基本思想是：当关键字key的哈希地址p=H(key)出现冲突时，以p为基础，产生另一个哈希地址p1，如果p1仍然冲突，再以p为基础，产生另一个哈希地址p2，…，直到找出一个不冲突的哈希地址pi ，将相应元素存入其中。这种方法有一个通用的再散列函数形式：Hi=(H(key)+di)%m   i=1，2，…，m-1,其中H（key）为哈希函数，m 为表长，di称为增量序列，i为碰撞次数。增量序列的取值方式不同，相应的再散列方式也不同。增量序列主要有以下几种：

    (1) 线性探测再散列

        di=1，2，3，…，m-1

        这种方法的特点是：冲突发生时，顺序查看表中下一单元，直到找出一个空单元或查遍全表。

    (2)二次探测再散列

        di=12，-12，22，-22，…，k2，-k2( k<=m/2 )

        这种方法的特点是：冲突发生时，在表的左右进行跳跃式探测，比较灵活。

    (3)伪随机探测再散列

        di=伪随机数序列。

    线性探测再散列的 优点 是：只要哈希表不满，就一定能找到一个不冲突的哈希地址，而二次探测再散列和伪随机探测再散列则不一定。线性探测再散列容易产生“二次聚集”，即在处理同义词的冲突时又导致非同义词的冲突。

    其实除了上面的几种方法，开放寻址法还有很多变种，不过都是对di有不同的表示方法。（如双散列探测法：di=i*h2(k)）

2.再哈希法

    这种方法是同时构造多个不同的哈希函数：Hi=RHi（key），i=1，2,3，…,n。

    当哈希地址H1=RH1（key）发生冲突时，再计算H2=RH2（key）……，直到冲突不再产生。这种方法不易产生聚集，但增加了计算时间。

 3.链地址法(拉链法)

    这种方法的基本思想是将所有哈希地址相同的元素构成一个称为同义词链的单链表，并将单链表的头指针存在哈希表（数组）中，因而查找、插入和删除主要在同义词链中进行。若选定的散列表长度为m，则可将散列表定义为一个由m个头指针组成的指针数组T[0..m-1]。凡是散列地址为i的结点，均插入到以T[i]为头指针的单链表中。T中各分量的初值均应为空指针。链地址法适用于经常进行插入和删除的情况。

     拉链法的优点

        与开放寻址法相比，拉链法有如下几个优点：

            (1)拉链法处理冲突简单，且无堆积现象，即非同义词决不会发生冲突，因此平均查找长度较短；

            (2)由于拉链法中各链表上的结点空间是动态申请的，故它更适合于造表前无法确定表长的情况；

            (3)开放寻址法为减少冲突，要求装填因子α较小，故当结点规模较大时会浪费很多空间。而拉链法中理论上可取α≥1，且结点较大时，拉链法中增加的指针域可忽略不计，因此节省空间；（散列表的装填因子定义为：α= 填入表中的元素个数 / 散列表的长度）

注：HashMap默认装填因子是0.75。

            (4)在用拉链法构造的散列表中，删除结点的操作易于实现。只要简单地删去链表上相应的结点即可。而对开放寻址法构造的散列表，删除结点不能简单地将被删结点的空间置为空，否则将截断在它之后填入散列表的同义词结点的查找路径。这是因为各种开放寻址法中，空地址单元都被理解没有查找到元素。 因此在用开放寻址法处理冲突的散列表上执行删除操作，只能在被删结点上做删除标记，而不能真正删除结点。

     拉链法的缺点

        拉链法的缺点是：指针需要额外的空间，故当结点规模较小时，开放寻址法较为节省空间，此时将节省的指针空间用来扩大散列表的规模，可使装填因子变小，这又减少了开放寻址法中的冲突，从而提高平均查找速度。

4、建立公共溢出区

    这种方法的基本思想是：将哈希表分为基本表和溢出表两部分，凡是和基本表发生冲突的元素，一律填入溢出表(在这个方法里面是把元素分开两个表来存储)。

    散列表的查找过程基本上和造表过程相同。一些关键码可通过散列函数转换的地址直接找到，另一些关键码在散列函数得到的地址上产生了冲突，需要按处理冲突的方法进行查找。在介绍的三种处理冲突的方法中，产生冲突后的查找仍然是给定值与关键码进行比较的过程。所以，对散列表查找效率的量度，依然用平均查找长度来衡量。

    查找过程中，关键码的比较次数，取决于产生冲突的多少，产生的冲突少，查找效率就高，产生的冲突多，查找效率就低。因此，影响产生冲突多少的因素，也就是影响查找效率的因素。

影响产生冲突多少有以下三个因素:

    1. 散列函数是否均匀;

    2. 处理冲突的方法;

    3. 散列表的装填因子。

     散列表的装填因子

        定义为:α= 填入表中的元素个数 / 散列表的长度

        α是散列表装满程度的标志因子。由于表长是定值，α与"填入表中的元素个数"成正比，所以，α越大，填入表中的元素较多，产生冲突的可能性就越大;α越小，填入表中的元素较少，产生冲突的可能性就越小。

        实际上，散列表的平均查找长度是装填因子α的函数，只是不同处理冲突的方法有不同的函数。

    这个HASH算法不是大学里数据结构课里那个HASH表的算法。这里的HASH算法是密码学的基础，了解了hash基本定义，就不能不提到一些着名的hash算法，MD5 和 SHA-1 可以说是目前应用最广泛的Hash算法，而它们都是以 MD4 为基础设计的。

Hash算法在信息安全方面的应用主要体现在以下的3个方面:

     ⑴  文件校验

        我们比较熟悉的校验算法有奇偶校验和CRC校验，这2种校验并没有抗 数据篡改 的能力，它们一定程度上能检测出数据传输中的信道误码，但却不能防止对数据的恶意破坏。

        MD5 Hash算法的"数字指纹"特性，使它成为目前应用最广泛的一种文件完整性 校验和 (Checksum)算法，不少Unix系统有提供计算md5 checksum的命令。

     ⑵  数字签名

        Hash 算法也是现代密码体系中的一个重要组成部分。由于非对称算法的运算速度较慢，所以在 数字签名 协议中，单向散列函数扮演了一个重要的角色。对 Hash 值，又称"数字摘要"进行数字签名，在统计上可以认为与对文件本身进行数字签名是等效的。而且这样的协议还有其他的优点。

     ⑶ 鉴权协议

        如下的鉴权协议又被称作挑战--认证模式:在传输信道是可被侦听，但不可被篡改的情况下，这是一种简单而安全的方法。

    一致性哈希表简称DHT，主要应用于分布式缓存中，可以用来解决分布式存储结构下动态增加和删除节点所带来的问题。比如，一个分布式的存储系统，要将数据存储到具体的节点上，如果采用普通的hash方法，将数据映射到具体的节点上，如key%N（key是数据的key，N是机器节点数），如果有一个机器加入或退出这个集群，则所有的数据映射都无效了，如果是持久化存储则要做数据迁移，如果是分布式缓存，则其他缓存就失效了。

判定哈希算法好坏的四个定义 ：

    1、平衡性(Balance)：平衡性是指哈希的结果能够尽可能分布到所有的缓冲中去，这样可以使得所有的缓冲空间都得到利用。

    2、单调性(Monotonicity)：单调性是指如果已经有一些内容通过哈希分派到了相应的缓冲中，又有新的缓冲加入到系统中。哈希的结果应能够保证原有已分配的内容可以被映射到原有的或者新的缓冲中去，而不会被映射到旧的缓冲集合中的其他缓冲区。

    3、分散性(Spread)：在分布式环境中，终端有可能看不到所有的缓冲，而是只能看到其中的一部分。当终端希望通过哈希过程将内容映射到缓冲上时，由于不同终端所见的缓冲范围有可能不同，从而导致哈希的结果不一致，最终的结果是相同的内容被不同的终端映射到不同的缓冲区中。这种情况显然是应该避免的，因为它导致相同内容被存储到不同缓冲中去，降低了系统存储的效率。 分散性的定义就是上述情况发生的严重程度。好的哈希算法应能够尽量避免不一致的情况发生，也就是尽量降低分散性。

    4、负载(Load)：负载问题实际上是从另一个角度看待分散性问题。既然不同的终端可能将相同的内容映射到不同的缓冲区中，那么对于一个特定的缓冲区而言，也可能被不同的用户映射为不同的内容。与分散性一样，这种情况也是应当避免的， 因此好的哈希算法应能够尽量降低缓冲的负荷。

    在分布式集群中，对机器的添加删除，或者机器故障后自动脱离集群这些操作是分布式集群管理最基本的功能。如果采用常用的hash取模算法，那么在有机器添加或者删除后，很多原有的数据就无法找到了，这样严重的违反了单调性原则。接下来主要说明一下一致性哈希算法是如何设计的。

以SpyMemcached的ketama算法来说，思路是这样的：

把数据用hash函数，映射到一个很大的空间里，如图所示。数据的存储时，先得到一个hash值，对应到这个环中的每个位置，如k1对应到了图中所示的位置，然后沿顺时针找到一个机器节点B，将k1存储到B这个节点中。

如果B节点宕机了，则B上的数据就会落到C节点上，如下图所示：

这样，只会影响C节点，对其他的节点A，D的数据不会造成影响。然而，这又会造成一个“雪崩”的情况，即C节点由于承担了B节点的数据，所以C节点的负载会变高，C节点很容易也宕机，这样依次下去，这样造成整个集群都挂了。

为此，引入了“虚拟节点”的概念：即把想象在这个环上有很多“虚拟节点”，数据的存储是沿着环的顺时针方向找一个虚拟节点，每个虚拟节点都会关联到一个真实节点，如下图所使用：

图中的A1、A2、B1、B2、C1、C2、D1、D2都是虚拟节点，机器A负载存储A1、A2的数据，机器B负载存储B1、B2的数据，机器C负载存储C1、C2的数据。由于这些虚拟节点数量很多，均匀分布，因此不会造成“雪崩”现象。