Python3中的list、set和dict

发表于 2019-03-12 | 分类于 python |

你真的了解python中的列表，元组和字典吗？

先来回答一下几个问题：

python中求list长度的len方法的时间复杂度是多少？
python中list中的in操作符，时间复杂度是多少？
python中set中的in操作符，时间复杂度是多少？
python中dict中的in操作符，时间复杂度又是多少？为什么？

列表

我们先来看list相关内容，list我们很常见也很熟悉，list是python的内置类型，在cpython中是通过c语言来实现的。对于len取长度的操作，其时间复杂度是O(1)。对于大多数python中的len操作来说，其时间复杂度通常都是O(1)。其实现中是设置了一个常量用于记录数组的长度，因此取长度的操作是O(1).

对于list的in操作来说，需要遍历一次，因此其时间复杂度为O(n)。

集合

我们知道，集合的特性是无序，元素唯一不重复。集合的实现跟字典类型，可以看作是只有key没有value的字典，因此其底层也可以看作是哈希的实现，所以，对于集合的in操作，其时间复杂度为O(1)，而不是O(n)。

字典

字典就是哈希表的实现了，我们知道字典的查找其时间复杂度是O(1)。但是在python2中，dict.keys()返回的是一个列表，对列表的in操作，前边已经说过，是O(n)，因此，在python2中，key in dict.keys()的操作是要慢于key in dict的。在python3中，dict.keys()返回的是一个dict_keys对象，dict.values返回的是一个dict_values对象，dict.items返回的是一个dict_items对象，python3中的in操作并没有什么优化，仅仅是从hash表中查找而已。

使用Redis存储flask的项目

发表于 2019-03-06 | 分类于 flask |

flask中的session存在的问题

客户端session

在Web中，session是认证用户身份的凭证，它具备如下几个特点：

用户不可以任意篡改
A用户的session无法被B用户获取

也就是说，session的设计目的是为了做用户身份认证。但是，很多情况下，session被用作了别的用途，将产生一些安全问题，我们今天就来谈谈“客户端session”（client session）导致的安全问题。

在传统开发中，SESSION变量的内容默认会被保存在服务端的一个文件中，通过一个叫session_id的Cookie来区分用户。这类session是“服务端session”，用户看到的只是session的名称（一个随机字符串），其内容保存在服务端。

然而，并不是所有语言都有默认的session存储机制，也不是任何情况下我们都可以向服务器写入文件。所以，很多Web框架都会另辟蹊径，比如Django默认将session存储在数据库中，而对于flask这里并不包含数据库操作的框架，就只能将session存储在cookie中。

因为cookie实际上是存储在客户端（浏览器）中的，所以称之为“客户端session”。

flask中的session

flask仅仅对数据进行了签名。众所周知的是，签名的作用是防篡改，而无法防止被读取。而flask并没有提供加密操作，所以其session的全部内容都是可以在客户端读取的，这就可能造成一些安全问题。

session存储的内容可以通过以下脚本来破译：

#!/usr/bin/env python3
"""解密flask 客户端session问题 """
import sys
import zlib
from base64 import b64decode
from flask.sessions import session_json_serializer
from itsdangerous import base64_decode
def decryption(payload):
    payload, sig = payload.rsplit(b'.', 1)
    payload, timestamp = payload.rsplit(b'.', 1)
    decompress = False
    if payload.startswith(b'.'):
        payload = payload[1:]
        decompress = True
    try:
        payload = base64_decode(payload)
    except Exception as e:
        raise Exception('Could not base64 decode the payload because of '
                         'an exception')
    if decompress:
        try:
            payload = zlib.decompress(payload)
        except Exception as e:
            raise Exception('Could not zlib decompress the payload before '
                             'decoding the payload')
    return session_json_serializer.loads(payload)
if __name__ == '__main__':
    print(decryption(sys.argv[1].encode()))

这样就会造成一些安全性的问题。

解决方案

最好的方式当然是不要把session存在Cookie中，这里我们就把session内容放到Redis中，这样session就成为了服务端Session。

import pickle
from datetime import timedelta
from uuid import uuid4
from redis import StrictRedis
from werkzeug.datastructures import CallbackDict
from flask.sessions import SessionInterface, SessionMixin
class RedisSession(CallbackDict, SessionMixin):
    def __init__(self, initial=None, sid=None, new=False):
        def on_update(self):
            self.modified = True
        CallbackDict.__init__(self, initial, on_update)
        self.sid = sid
        self.new = new
        self.modified = False
class RedisSessionInterface(SessionInterface):
    serializer = pickle
    session_class = RedisSession
    def __init__(self, redis=None, prefix='session:'):
        if redis is None:
            redis = StrictRedis()
        self.redis = redis
        self.prefix = prefix
    def generate_sid(self):
        return str(uuid4())
    def get_redis_expiration_time(self, app, session):
        if session.permanent:
            return app.permanent_session_lifetime
        return timedelta(days=1)
    def open_session(self, app, request):
        sid = request.cookies.get(app.session_cookie_name)
        if not sid:
            sid = self.generate_sid()
            return self.session_class(sid=sid, new=True)
        val = self.redis.get(self.prefix + sid)
        if val is not None:
            data = self.serializer.loads(val)
            return self.session_class(data, sid=sid)
        return self.session_class(sid=sid, new=True)
    def save_session(self, app, session, response):
        domain = self.get_cookie_domain(app)
        if not session:
            self.redis.delete(self.prefix + session.sid)
            if session.modified:
                response.delete_cookie(app.session_cookie_name,
                                       domain=domain)
            return
        redis_exp = self.get_redis_expiration_time(app, session)
        cookie_exp = self.get_expiration_time(app, session)
        val = self.serializer.dumps(dict(session))
        self.redis.setex(self.prefix + session.sid,
                         int(redis_exp.total_seconds()), val)
        response.set_cookie(app.session_cookie_name, session.sid,
                            expires=cookie_exp, httponly=True,
                            domain=domain)

使用方法如下：

1 2	app = Flask(__name__) app.session_interface = RedisSessionInterface()

tcp协议详解

发表于 2019-03-05 | 分类于 network |

什么是TCP协议

tcp（Transmission Control Protocal,传输控制协议）是传输层最重要的协议，它是面向连接、基于字节流，保证报文可靠按序到达的协议。TCP的应用众多，应用层的HTTP、TELNET、TFP等协议都是在TCP的基础上运行的。

tcp是全双工协议，意味着客户端和服务端可以同时发送和接收数据。同时，tcp还是可靠的协议，也就是说不会丢包、不会乱序。同时，TCP还可以根据当前网络的拥塞程度，进行流量控制、拥塞控制。

tcp的实现是通过套接字（socket）来实现的，套接字就是IP地址加上16位的端口号。这样应用层进程就可以根据不同的端口号对tcp进行复用和分用。

TCP如何保证传输的可靠性？

在全双工的工作模式下，接收方的接收缓存和发送方的发送缓存都是有限的，应用程序产生数据过快会导致发送方缓存不足，发送方发送数据过快又会导致接受方接收缓存不足，由此可见，需要一种机制来协调发送方的发送速度和接收方的接收能力相匹配。

停止等待协议

停止等待的意思是，每发送一组数据，就停下来等待，等到收到对方的确认包以后，再次发送。没有差错的情况下，数据包一包一包的进行传输。有差错了，发送方超时没收到确认，则再次发送该包数据。这总机制是自动进行的，因此也叫做自动重传请求ARQ.

ARQ协议的缺点是，一包一包的传输，对网络的利用率过低。优化的协议叫做连续ARQ协议,它的意思是在发送方的发送窗口内，连续的把数据包传输出去，然后再一一进行确认，这样就提高点网络的利用率。发送窗口的大小要取接收窗口和拥塞窗口中的最小值。

TCP报文格式

TCP的报文首部的前20个字节是固定的，后面有4n（n是整数，最大15）个字节是可以增加的选项.

源端口和目的端口：各两个字节，因此端口的范围是1-65535.

序号：占4字节，范围[0-2^32-1], 序号会再达到最大值后重置为0

确认号：期望收到对方下一个报文段的第一个数据的字节的序号。

数据偏移：占4位，指出TCP报文段的数据起始处距离TCP报文段的数据起始处有多远。

保留：占6位，保留位以后使用。

下面几个位控制位：

紧急URG：表明报文中有紧急数据，需要尽快送达。例如，程序中断指令ctrl+c.

确认ACK：确认报文，ACK=1时有效，TCP建立连接后所有的报文段ACK必须为1

推送PUSH: 希望对方在收到报文后立即做出响应，而不是等缓存填满再发送。

复位RST: 表明TCP连接中断出现严重差错，必须重新连接。(GFW就是这么干的，阻断你请求某些网站的数据。)

同步SYN：在连接建立时用来同步序号。SYN=1 表示这是要给连接建议请求报文。见后面的三次握手。

终止FIN：释放连接时使用的标志位

窗口：两字节，表示的是本报文段一方的接收窗口大小。

校验和：占2字节，包括首部和数据两部分的校验。

紧急指针：占2字节，只有在URG为1时才有意义，指出本报文段中紧急数据的字节数（紧急数据结束后就是普通数据），即使窗口为0也可以发送紧急数据。

选项：长度可变，最长40字节。

可靠传输的实现

以字节为单位的窗口滑动

发送方根据接收方的窗口大小确定发送窗口大小，发送数据后，根据确认的序号，往前滑动窗口。接收方根据自己的缓存大小调整发送方的发送窗口，从而使自己来得及处理接收到的数据。对于不按序到达的数据，通常先进行缓存，等收齐数据再交付上层应用。TCP接收方可以捎带确认以减少传输开销。

超时重传的时间选择

假设一个报文段往返时间RTT，RTTS为多次往返的加权平均值，超时重传的时间要略大于RTTS。只要报文重传了，就不采用加权平均值，这样得出的值相对比较准确。

选择确认ACK

除了累积确认，还可以使用选择确认。就是说接收方接收到的数据为一串不连续的数据包，如果按照之前的确认方式，只能对序号最小的包号进行确认，后续已经接收到的数据包还有可能被重传。选择确认就是在选项中添加一个选项，指明接收到的数据包块，分别进行确认，这样发送方只发送未成功接收的数据包即可。

TCP如何进行流量控制？

TCP的流量控制一般使用滑动窗口来进行流量控制

TCP的拥塞控制？

TCP的拥塞控制有四种方法：慢开始、拥塞避免、快重传和快恢复。

慢开始

慢开始就是维持一个拥塞窗口，从1开始，没有拥塞窗口就扩大一倍，直至增加到发送窗口大小。

拥塞避免

拥塞避免的算法是，让拥塞窗口缓慢的增加，而不是加倍增长。

快重传

快重传，尽快让发送方知道报文丢失。一旦发送方收到3个重复的确认，就知道接收方没有收到某个报文。

快恢复

发送方知道了丢失了某个报文后，不是采用慢开始算法，而是采用快恢复算法，调整发送方窗口为拥塞窗口的1/2，同时执行拥塞避免算法。

TCP的三次握手是怎样的？

客户端C发起连接请求，SYN=1，seq=x，C进入SYN_SENT状态，
服务器S收到连接请求后，对报文进行确认 SYN=1,ACK=1,seq=y,ack=x=+1, 进入SYN_RECV状态，
客户端收到S的确认后，发送确认的确认，ACK=1,seq=x+1,ack=y+1, C进入ESTABLISHED状态。
服务器收到C的确认报文后，进入ESTABLISHED状态。

为什么建立TCP连接一定需要三次握手？

客户端对服务器的再确认，是为了防止无效的连接报文再次到达服务器端后，建立无效的连接。

如果客户端给服务器的再确认报文丢失了，TCP如何处理？

服务器S如果没有收到确认ACK报文的报文，则会隔3秒、6秒、12秒后再次发送ACK确认报文，如果一段时间内还没收到客户端发来的再确认报文，服务器将关闭这个连接。
当客户端发送数据报文的时候，服务器端会给出RST报文，通知客户端服务器连接已关闭。

TCP的四次分手过程是怎样的？

客户端C发起连接断开请求，FIN=1，seq=u,然后进入FIN-WAIT-1状态
服务器S收到C发来的断开请求，发送ACK确认报文，ACK=1,seq=v,ack=u+1, 然后进入CLOSE-WAIT状态
服务器S发送完剩余的数据，再次发送ACK报文，FIN=1,ACK=1,seq=w,ack=u+1,然后进入LAST-ACK状态
客户端C收到服务器发送来的ACK报文后，进入TIME-WAIT状态，并发送ACK确认报文，ACK=1,seq=u+1,ack=w+1
服务器S收到确认报文后，断开连接，进入CLOSE状态，客户端等待2个MSL后断开

travis初体验

发表于 2019-02-27 | 分类于 ci/cd |

持续集成/持续部署的概念最近几年非常流行，企业用户通常使用的是jenkins等工具，前段时间github宣布私有仓库免费，而针对github也有一款ci/cd的工具——travis, 现在就来体验一下吧。

注册travis

注册tavis，只需要在官网使用github账号注册，然后再赋予它读取git仓库的权限就可以了，授权完成后，你会在travis里看到你的github仓库的列表。

构建travis

构建travis的前提是你的仓库项目中有.travis.yml文件，.travis.yml文件的内容根据不同的语言而不同，具体可参考官网说明文档，我们这里使用的是python，所以参照python内容如下：

language: python
python:
  - "3.6"
script:
  - python test.py

python指明的是语言版本，script指定要测试的脚本文件。

提交测试

完成上面两步以后，就可以测试了，先修改一下项目文件，然后commit到github上，travis会自动检测到push的动作，并执行测试脚本：

travis可以做的不仅仅是测试，还可以自动部署等，持续测试中…

新玩具digitalocean

发表于 2019-02-26 | 分类于 shadowsocks |

虽然AWS、GCE和Azure都有免费12个月的试用期，但是无奈都被用过了，本来想着换个邮箱注册接着薅羊毛来着，结果发现已经用过的信用卡已不能再次使用，又不能因为这个再去单独申请多张信用卡，无奈只有寻找新的玩具。

翻遍了网上的推荐，比较多的建议有搬瓦工和vultr，主要是这两个相对比较便宜，基本是5刀一个月。但是我并没有选择这两个的原因是国内太多的人在用了，容易被长城发现并block掉。

这里要推荐的是digitalocean提供的服务，现在注册还可以有15美元的信用，以及100美元两个月的消费额度。

注册链接

然后再输入优惠码 LOWENDBOX 即可获得15美元优惠。

PPP帧和以太网帧

发表于 2019-02-21 | 分类于 network |

数据链路层的三个基本问题

运行在链路层的协议有多种，但是三个基本问题是共同，这三个基本问题是 封装成帧、透明传输和差错检测。

封装成帧

封装成帧的概念就是在数据链路层的传输协议中加入帧首部和帧尾部，方便链路层区分帧界限。为什么一定要封装成帧，这是因为一旦帧在传输过程中出现差错，链路层就可以通过帧首部和尾部进行判断，丢弃出错的帧。

透明传输

由于帧界定符是一些特殊的ascii码组合成的，在传输的数据中可能出现与界定符一样的数据，透明传输的意思就是要避免出现这样的数据，对于数据中的界定符采取转义的方式重合编码，接收方再根据同样的规则进行解码，从而完成正确的数据传输。

差错检测

差错检测就是检测一帧数据中是否在传输过程中出现了差错，如果出现差错就丢弃（数据链路层不做可靠性保证，由上层协议完成错误重发）。差错检测是使用的循环冗余校验CRC技术。

PPP协议

点对点协议（Point-to-Point Protocal）是目前应用最广泛的链路层协议。PPP协议的特点：

简单 PPP协议提供不可靠的数据服务，不提供纠错、不需要序号、不需要流量控制等功能。
封装成帧
透明性
支持多种网络层协议如IP、IPX等协议。
支持多种链路类型如串行、并行、同步和非同步等等。
差错检测
检测链接状态
最大传输单元
支持网络地址协商
支持数据压缩协商

PPP协议不支持多点线路，只支持全双工通信。

PPP协议帧格式

PPP协议的帧格式如下：


首部的第一个字段和尾部的第二个字段都是标志字段F（Flag），规定为0x7E
（0x代表它后面的字符是用十六进制表示的。7E即01111110）
标志字段表示一个帧的开始或结束。因此标志字段就是PPP帧的定界符。
连续两帧之间只需要用一个标志字段，如果连续出现两个标志字段，
就表示是一个空帧，应当丢弃。
首部中的地址字段A规定为0xFF（即11111111），
控制字段C规定为0x03（即00000011）。这两个字段实际上并没有携带PPP帧的信息。
PPP首部的第四个字段是2字节的协议字段。
当协议字段为0x0021时，PPP帧的信息字段就是IP数据报。
当为0xC021时，则信息字段是PPP链路控制协议LCP的数据，
而0x8021表示这是网络层的控制数据。

PPP协议带有身份认证功能，用户接入互联网用的基本都是PPP协议。

PPP协议的六个阶段：

链路不可用阶段：初始阶段
链路建立阶段： LCP协商，（协商认证方式等）
验证阶段： PAP/CHAP验证
网络层协议阶段：**NCP协商
PPP会话维持阶段：维持PPP会话，定时发送Echo Request报文，并等待Echo Reply报文
网络终止阶段：终止PPP会话，回到链路不可用阶段

以太网协议

经过多年的发展，现在局域网基本等于以太网的同义词，大多数局域网使用的协议都是以太网协议。

CSMA/CD协议

局域网发展早期，使用的是总线模式的局域网，特点是所有的计算机都在同一个总线上，只有当总线空闲时才能发送数据。这样就需要一个协议来协商多个计算机之间的发言冲突问题，这就是CSMA/CD协议：载波监听多点接入/冲突检测。

由于以太网发送数据都是使用曼彻斯特编码的信号，因此以太网协议不需要界定符的尾部，因为一旦主机不再发送信号，以太网中的高低电平转换就消失了，这个特点就可以作为帧的尾部。

根据CSMA/CD协议，可以推算出要想检测到传输过程中的碰撞，数据的最小长度为64字节。以太网的MTU为64-1500

MAC帧格式

MAC帧格式如下：

类型字段 （2个字节）：用来标志上一层使用的是什么协议，以便把收到的MAC帧的数据上交给上一层的这个协议
数据字段 （46-1500）：正式名称是MAC客户数据字段最小长度64 字节-18字节的首部和尾部 = 数据字段的最小长度 
FCS字段 （4 字节）： 当数据字段的长度小于 46 字节时，应在数据字段的后面加入整数字节的填充字段，以保证以太网的MAC帧长不小于64 字节
在帧的前面插入的 8 字节中的第一个字段共 7 个字节，是前同步码，用来迅速实现 MAC帧的比特同步。第二个字段是帧开始定界符，表示后面的信息就是MAC帧