002-Redis的pipeline、跳表

1. 项目中redis

# 建立redis连接
redis_conn = get_redis_connection(alias='verify_codes')
# 创建用户输入的手机号标志
sms_fmt = "sms_{}".format(tel).encode('utf8')
# 从数据库里面拿出手机号，名字是一样的
real_sms = redis_conn.get(sms_fmt)  # 那边的数据也是这样写入数据库的，不是只写了手机号进数据库。
# 判断是否一致
if (not real_sms) or (sms_text != real_sms.decode('utf8')):
  raise forms.ValidationError("短信验证码错误")
 

class SmsCodesView(View):
    """
    1,获取参数
    2,验证参数
    3,发送信息
    4,保存短信验证码
    5,返回给前端

    POST /sms_codes/
    -检查图片验证码是否正确
    -检查是否60秒有记录
    -生成短信验证码
    -发送短信
    """
    # 1. 获取参数，
    def post(self, request):   # 表单
        json_data = request.body  # body里面包含的是什么，body就是前台给到后台的数据，ajax发过来的数据
        if not json_data:
            return to_json_data(errno=Code.PARAMERR, errmsg=error_map[Code.PARAMERR])  # 报错罢了
        dict_data = json.loads(json_data.decode('utf8'))
        form = forms.CheckImgCodeForm(data=dict_data)

    # 2. 校验参数
        if form.is_valid():

            # 获取手机号
            mobile = form.cleaned_data.get('mobile')

            # 创建短信验证码内容
            sms_num = "%06d" % random.randint(0, 999999)
            # 1.将短信验证码保存到数据库
            # 确保settings.py文件中有配置redis CACHE
            # Redis原生指令参考 http://redisdoc.com/index.html
            # Redis python客户端 方法参考 http://redis-py.readthedocs.io/en/latest/#indices-and-tables

            con_redis = get_redis_connection(alias='verify_codes')

            # 创建一个在60秒内是否发送记录的标记
            sms_flag_fmt = "sms_flag_{}".format(mobile).encode('utf8')

            # 创建保存短信验证码的标记key
            sms_text_fmt = "sms_{}".format(mobile).encode('utf8')
            # 节省通讯次数
            pl = con_redis.pipeline()  # redis管道技术
            try:
                pl.setex(sms_flag_fmt, constants.SEND_SMS_CODE_INTERVAL, 1)  # 60秒的标志，1号模板
                pl.setex(sms_text_fmt, constants.IMAGE_CODE_REDIS_EXPIRES, sms_num)  # 把短信验证码保存进去了

            # 通知redis执行命令
                pl.execute()
            except Exception as e:
                logger.debug('redis 执行异常{}'.format(e))
                return to_json_data(errno=Code.UNKOWNERR, errmsg=error_map[Code.UNKOWNERR])

            # 2.发送短信 通知平台
            logger.info('SMS code:{}'.format(sms_num))

            expires = constants.SMS_CODE_REDIS_EXPIRES
            sms_tasks.send_sms_code.delay(mobile, sms_num, expires, constants.SMS_CODE_TEMP_ID)
            return to_json_data(errno=Code.OK, errmsg="短信验证码发送成功")

          
          
       

    def clean(self):
        """
        """
        # 继承父类的clean方法, 获取提交的表单数据
        cleaned_data = super().clean()
        passwd = cleaned_data.get('password')
        passwd_repeat = cleaned_data.get('password_repeat')
        # 密码判断
        if passwd != passwd_repeat:
            raise forms.ValidationError("两次密码不一致")

        # 拿到手机号
        tel = cleaned_data.get('mobile')
        # 拿到短信验证码
        sms_text = cleaned_data.get('sms_code')  # 字典类型通过键取值
        # 建立redis连接
        redis_conn = get_redis_connection(alias='verify_codes')
        # 创建用户输入的手机号标志
        sms_fmt = "sms_{}".format(tel).encode('utf8')
        # 从数据库里面拿出手机号，名字是一样的
        real_sms = redis_conn.get(sms_fmt)  # 那边的数据也是这样写入数据库的，不是只写了手机号进数据库。
        # 判断是否一致
        if (not real_sms) or (sms_text != real_sms.decode('utf8')):
            raise forms.ValidationError("短信验证码错误")

# 登录界面的，逻辑和注册逻辑的差不多

SETEX key seconds value

含义：

       将值 value 关联到 key ，并将 key 的生存时间设为 seconds (以秒为单位)。
       如果 key 已经存在， SETEX 命令将覆写旧值。

返回值：

       设置成功时返回 OK 。
       当 seconds 参数不合法时，返回一个错误。

原文链接：https://blog.csdn.net/iteye_7682/article/details/82680515

2. pineline相关

Redis 使用的是客户端-服务器（CS）模型和请求/响应协议的 TCP 服务器。这意味着通常情况下一个请求会遵循以下步骤：客户端向服务端发送一个查询请求，并监听 Socket 返回，通常是以阻塞模式，等待服务端响应。服务端处理命令，并将结果返回给客户端。
Redis 客户端与 Redis 服务器之间使用 TCP 协议进行连接，一个客户端可以通过一个 socket 连接发起多个请求命令。每个请求命令发出后 client 通常会阻塞并等待 redis 服务器处理，redis 处理完请求命令后会将结果通过响应报文返回给 client
，因此当执行多条命令的时候都需要等待上一条命令执行完毕才能执行。比如：

其执行过程如下图所示：

由于通信会有网络延迟，假如 client 和 server 之间的包传输时间需要0.125秒。那么上面的三个命令6个报文至少需要0.75秒才能完成。这样即使 redis 每秒能处理100个命令，**而我们的 client 也只能一秒钟发出四个命令。这显然没有充分利用 redis 的处理能力**。

而管道（pipeline）可以一次性发送多条命令并在执行完后一次性将结果返回，pipeline 通过减少客户端与 redis 的通信次数来实现降低往返延时时间，而且 Pipeline 实现的原理是队列，而队列的原理是时先进先出，这样就保证数据的顺序性。 Pipeline 的默认的同步的个数为53个，也就是说 arges 中累加到53条数据时会把数据提交。其过程如下图所示：client 可以将三个命令放到一个 tcp 报文一起发送，server 则可以将三条命令的处理结果放到一个 tcp 报文返回。

需要注意到是用 pipeline 方式打包命令发送，redis 必须在处理完所有命令前先缓存起所有命令的处理结果。打包的命令越多，缓存消耗内存也越多。所以并不是打包的命令越多越好。具体多少合适需要根据具体情况测试。

比较普通模式与 PipeLine 模式

测试环境：
Windows：Eclipse + jedis2.9.0 + jdk 1.7
Ubuntu：部署在虚拟机上的服务器 Redis 3.0.7

/*
 * 测试普通模式与 PipeLine 模式的效率： 
 * 测试方法：向 redis 中插入 10000 组数据
 */
public static void testPipeLineAndNormal(Jedis jedis)
		throws InterruptedException {
	Logger logger = Logger.getLogger("javasoft");
      
      
	long start = System.currentTimeMillis();
	for (int i = 0; i < 10000; i++) {
		jedis.set(String.valueOf(i), String.valueOf(i));
	}
	long end = System.currentTimeMillis();
      
      
	logger.info("the jedis total time is:" + (end - start));

	Pipeline pipe = jedis.pipelined(); // 先创建一个 pipeline 的链接对象
      
      
	long start_pipe = System.currentTimeMillis();
	for (int i = 0; i < 10000; i++) {
		pipe.set(String.valueOf(i), String.valueOf(i));
	}
	pipe.sync(); // 获取所有的 response
	long end_pipe = System.currentTimeMillis();
      
      
	logger.info("the pipe total time is:" + (end_pipe - start_pipe));
	BlockingQueue<String> logQueue = new LinkedBlockingQueue<String>();
	long begin = System.currentTimeMillis();
	for (int i = 0; i < 10000; i++) {
		logQueue.put("i=" + i);
	}
	long stop = System.currentTimeMillis();
	logger.info("the BlockingQueue total time is:" + (stop - begin));
}

从上述代码以及结果中可以明显的看到 PipeLine 在 “批量处理” 时的优势。

适用场景

有些系统可能对可靠性要求很高，每次操作都需要立马知道这次操作是否成功，是否数据已经写进 redis 了，那这种场景就不适合。

还有的系统，可能是批量的将数据写入 redis，允许一定比例的写入失败，那么这种场景就可以使用了，比如10000条一下进入 redis，可能失败了2条无所谓，后期有补偿机制就行了，比如短信群发这种场景，如果一下群发10000条，按照第一种模式去实现，那这个请求过来，要很久才能给客户端响应，这个延迟就太长了，如果客户端请求设置了超时时间5秒，那肯定就抛出异常了，而且本身群发短信要求实时性也没那么高，这时候用 pipeline 最好了。
原文链接：https://blog.csdn.net/u011489043/article/details/78769428

3. Redis-Zset底层数据结构：跳跃表（跳表）

1 为什么引入跳跃表

​ 我们知道红黑树是一种存在于内存中，可以保证在最坏的情况下，对红黑树进行例如search，insert，以及delete等基本的动态集合操作的时间复杂度为O(log n)。

但是显而易见，红黑树实现起来比较复杂，尤其是对红黑树进行insert和delete操作。并且在红黑树中进行范围查询时需要对红黑树进行中序遍历，这也是比较复杂的操作。那有没有一种能确保对动态集合search，insert以及delete等操作的时间复杂度在O(lg n)的前提下，实现比较简单，还能比较方便的进行范围查询的数据结构呢？答案是肯定的，就是我们今天要总结的数据结构——跳跃表（skip list）。

2 引入的过程

例子：假设我们在内存中有一个长度达到10万以上的一个已经排好序的链表结构。我们要往这个链表结构中插入一个元素。我们是怎么进行插入的呢？

来看下图所示的这个列表（为了使链表结构简单，图中只画出了8个元素：1，4，5，7，8，9，12，15）：

上图所示链表中，各元素按照升序排列，现在要在该链表中插入元素10，首先要确定元素10应该插入的位置，如下图所示。

由于是链表结构因此无法使用二分查找算法，只能和原链表中的结点逐一比较大小来确定位置。这一步的时间复杂度是O(N)。

插入的过程到时很容易，直接改变结点指针的目标，时间复杂度是O(1)。

因此总体的时间复杂度是O(N)。

这对于拥有上十万的集合来说，这种办法显然太慢了。那有什么办法可以让search，insert以及delete操作性能更高一点呢？

search，insert以及delete操作其实归根结底就是search太慢的问题。所以只要search操作变快insert和delete操作也会变快。

让我们来回想一下MySQL索引。所谓的索引就是把数据库表中的一些特定信息提取出来，缩小查询操作时的搜索范围，来提升查询性能。

那我们是不是可以借鉴数据库索引的思想，提取出链表中的部分关键结点。还以上面的例子，那么我们可以取出所有值为奇数的结点作为关键结点。

此时如果要插入一个值为10的新节点，不再需要和原结点1，4，5，7，8，9，12逐一进行比较，只需要比较关键结点1，5，7，9，15即可。

确定了新结点在关键结点中的位置（9和15之间），就可以回到原链表，迅速定位到对应的位置插入（同样是9和15之间）。

节点数目少，优化效果不是很明显，如果是十万个结点，比较次数就整整减少了一半！也就是说虽然增加了50%的额外的空间，但是性能提高了一倍。不过我们可以进一步思考。既然已经提取出了一层关键结点作为索引，那我们为何不能从索引中进一步提取，提出一层索引的索引？

有了2级索引之后，新的结点可以先和2级索引比较，确定大体范围之后在和1级索引进行比较，最后再回到原链表，找到并插入对应位置。

当结点很多的时候，比较次数就会减少到原来的四分之一！当节点足够多的时候，我们可以不止提出两层索引，还可以向更高层次提取，保证每一层是上一层结点数的一半。

提取的极限就是同一层只有两个结点的时候，因为一个结点没有比较的意义。这样的多层链表结构就是所谓的跳跃表。

3 跳跃表的基本概念

**跳跃表是将链表改造支持二分法查找的数据结构 。**如果是一个单链表的话，他查找数据的时间复杂度为O(n)，于是给单链表添加一级索引每两个节点提取一个节点到上一级，我们把诌出来的哪一级叫做索引或者索引层，如下图：

当你查找12的时候，你只需要遍历6次就可以得到结果值 ，

先去第一层索引查到，遍历到9的时候发现下一个节点是15那我们就知道此时12就在这两个节点之间，所以我们进行down进入下一层

继续遍历这个时候我们只需要遍历两个节点就可以找到了，所以我们遍历12在建立上层索引的情况下是只需要遍历7次，但是单链表便利需要7次，那我们在继续添加及层索引如下图:

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-maRF5Snv-1649509976822)(/Users/hello/Desktop/面试/image/截屏2022-03-20 14.25.41.png)]

当有64个节点的链表的时候，则会创建多少层索引，通过计算会有5层，那么每一层的索引个数有 n/2^k（n为总的索引树，k为创建的索引层数（不包括原始链表数据结构））,最高的层的索引层的长度为2，那我们计算出层级为k = log2^n- 1 ，我们时间复杂度为 那么时间复杂度为 O(logn)，现在就是在原有的得单链表上创建了多层索引而达到二分法查找，达到很高。那么现在这样岂不是浪费了很多的内存（空间换用时间）。

有一个问题需要注意：

• 当大量的新节点通过逐层比较，最终插入到原链表之后，上层的索引结点会渐渐变得不够用。这时候需要从新结点中选取一部分提到上一层。可是究竟应该提拔谁呢？

• 这可能是随机选取（也叫抛硬币，50%的可能性会被提拔，50%的可能性不会被提拔）的，也可能是根据某些规则确定性的选取，其中随机选取更加常见（因为跳跃表的元素删除和添加是不可预测的，很难用一种有效的算法来保证跳跃表的索引分布始终均匀，随机选取虽然不能保证索引绝对均匀分布，却可以大体上趋于均匀）。

下面以随机选取为例进行说明，比如给定一个长度是7的有序链表，结点值一次是1，2，3，5，6，7，8。

那么我们可以取出所有值为奇数的结点作为关键结点。假如值为9的新节点插入原链表：

4 跳跃表的更新

4.1 跳跃表插入节点

具体看上面的分析，这里就不再一一赘述。跳跃表插入节点的流程有以下几步：

• 新结点和各层索引结点逐一比较，确定原链表的插入位置，时间复杂度是O(logN)。

• 把索引插入到原链表，时间复杂度是O(1)。

• 利用抛硬币的随机方式，决定新结点是否提升到上一级索引。结果为正则提升，并且继续抛硬币，结果为负则停止，时间复杂度是O(logN)。

总体上，跳跃表插入操作的时间复杂度是O(logN)，而这种数据结构所占空间是2N。

4.2 跳跃表删除节点

跳跃表的删除操作比较简单，只要在索引层找到要删除的结点，然后顺藤摸瓜，删除每一层的相同结点即可。

这里还以一个长度是7的有序链表为例，结点值一次是1，2，3，5，6，7，8。取出所有值为奇数的结点作为关键结点。

如果某一层索引在删除后只剩下一个结点，那么整个一层就可以干掉了。例如要删除结点的值是5：

我们来总结一下跳跃表删除结点的操作步骤：

• 自上而下，查找第一次出现结点的索引，并逐层找到每一层对应的结点（因为每层索引都是由上层索引晋升的），时间复杂度是O(logN)。
• 删除每一层查找到的结点，如果该层只剩下一个结点，删除整个一层，时间复杂度是O(logN)。

总体上，跳跃表删除操作的时间复杂度是O(logN)。从上面的总结可以看出，相对于红黑树来说，由于跳跃表维持结构平衡的成本比较低，完全依靠随机。而红黑树在多次插入和删除后，需要rebalance来重新调整结构平衡。

原文链接：https://blog.csdn.net/weixin_37079656/article/details/116955419