Month: 六月 2018

后端工具和算法集

总结一下后端常用的工具和蕴含的算法

TODO: 应该把 GitHub 5000 star 以上的项目都看一下

– 前端
– 框架
– vue

– 数据库

– mysql(btree)
– postgresql
– redis
– rocksdb/leveldb
– elasticsearch
– memcached

– 消息队列

– kafka
– redis stream
– rabbitmq
– amqp 协议

– RPC 和序列化

– protobuf/grpc
– thrift
– msgpack
– envoy
– service mesh 的思想

– 负载均衡

– 四层和七层负载均衡的区别
– nginx
– LVS/IPVS
– 一致性哈希

– 部署和容器化

– docker
– cgroups
– kubernetes
– borg 论文

– CI
– jenkins

– web 框架

– django(MVC 模式)
– flask

– 日志收集

分布式系统中需要日志可能分布在不同的机器上,要想查找一条错误日志,可能需要 ssh 到不同的机器上,非常浪费时间和精力。可以把日志收集到一个统一的存储中,方便检索查看

– filebeat
– sentry

– 监控

时序数据库

– OpenTSDB
– influxdb
– prometheus

前端面板

– grafana

– 高并发厂家服务

– 计数服务
– [计数系统架构实践一次搞定](http://zhuanlan.51cto.com/art/201706/542217.htm)
– [微博计数器的设计](http://blog.cydu.net/weidesign/2012/09/09/weibo-counter-service-design-2/)
– [instagram 使用 redis 计数](https://instagram-engineering.com/storing-hundreds-of-millions-of-simple-key-value-pairs-in-redis-1091ae80f74c)
– 限流服务
– token bucket

– 搜索引擎相关

– simhash
– tf-idf

– 统一登录

– CAS,[了解CAS协议](https://blog.csdn.net/csdnxingyuntian/article/details/54970102)
– kerbos

– 操作系统

– 内存换页算法
– OPT
– FIFO
– LRU
– CLOCK

– 限流

– 锁

– 分布式锁
– 自旋锁
– 乐观锁、悲观锁

软件工程中的 “3” 的规则

我注意到了一个神奇的软件工程法则:在你正确地解决问题之前,你至少需要3个例子。

具体说来是这样的:

1. 不要试图在两个类之间共享代码,至少等到你有三个类的时候。
2. 解决问题的前两次尝试一定会失败,因为你还没完全理解这个问题。第三次才行
3. 任何想要早期就能设计好的尝试都会导致对于巧合情形的过度拟合。

# 你在说什么?请给个例子

比如说你在实现一个类,从银行抓取数据。下面是一个非常傻瓜的版本,但是应该说明了问题:

“`
class ChaseScraper:
def __init__(self, username, password):
self._username = username
self._password = password

def scrape(self):
session = requests.Session()
sessions.get(‘https://chase.com/rest/login.aspx’,
data={‘username’: self._username,
‘password’: self._password})
sessions.get(‘https://chase.com/rest/download_current_statement.aspx’)
“`

现在你想添加第二个类 CitiBankScraper 来实现相同的接口,但是改变了一些实现细节。实际上假设CitiBank只是有一个不同的 url 和表单元素名称而已。让我们来添加一个新的爬虫:

“`
class CitibankScraper:
def __init__(self, username, password):
self._username = username
self._password = password

def scrape(self):
session = requests.Session()
sessions.get(‘https://citibank.com/cgi-bin/login.pl’,
data={‘user’: self._username,
‘pass’: self._password})
sessions.get(‘https://citibank.com/cgi-bin/download-stmt.pl’)
“`

因为经过了多年DRY原则的教育,这时候我们发现这两个类的代码几乎是重复的!我们应该重构一下,把所有的重复代码都放到一个基类中。在这里,我们需要Inserve of Control 模式,让基类来控制逻辑。

“`
class BaseScraper:
def __init__(self, username, password):
self._username = username
self._password = password

def scrape(self):
session = requests.Session()
sessions.get(self._LOGIN_URL,
data={self._USERNAME_FORM_KEY: self._username,
self._PASSWORD_FORM_KEY: self._password})
sessions.get(self._STATEMENT_URL)

class ChaseScraper(BaseScraper):
_LOGIN_URL = ‘https://chase.com/rest/login.aspx’
_STATEMENT_URL = ‘https://chase.com/rest/download_current_statement.aspx’
_USERNAME_FORM_KEY = ‘username’
_PASSWORD_FORM_KEY = ‘password’

class CitibankScraper(BaseScraper):
_LOGIN_URL = ‘https://citibank.com/cgi-bin/login.pl’
_STATEMENT_URL = ‘https://citibank.com/cgi-bin/download-stmt.pl’
_USERNAME_FORM_KEY = ‘user’
_PASSWORD_FORM_KEY = ‘pass’
“`

这应该让我们删掉了不少代码。这已经是最简单的方法之一了。所以问题在哪里呢?(出去我们实现继承的方法不好之外)

问题是我们过度拟合了!过度拟合是什么意思呢?我们正在抽象出并不能很好泛化的模式!

![facepalm](https://erikbern.com/assets/facepalm.jpg)

为了验证这一点,假设我们又需要从第三个银行抓取数据。也许它需要如下几点:

– 他需要两步验证
– 密码是使用 JSON 传递的
– 登录使用了POST而不是GET
– 需要同时访问多个页面
– 要访问的url是根据当前日期动态生成的

…… 或者随便什么东西,有1000中方式让我们的代码不能工作。我希望你已经感觉到问题所在了。我们以为我们通过前两个爬虫发现了一个模式!然鹅悲剧的是,我们的爬虫根本不能泛化到第三个银行(或者更多,第n个)。也就是说,我们过拟合了。

# 过拟合到底是什么意思?

过拟合指的是我们在数据发现了一个模式,但是这个模式并不能很好地泛化。当我们在写代码的时候,我们经常对于优化代码重复非常警觉,我们会发现一些偶然出现的模式,但是如果我们查看整个程序的话,我们知道这些模式可能并不能很好地代表整个程序的模式。所以当我们实现了两个银行的爬虫之后,我们以为我们发现了一个广泛的模式,实际上并不是。

注意到,代码重复并不总是一件坏事。工程师们通常过分关注减少重复代码,但是也应该注意区分偶然的代码重复和系统性的代码重复之间的区别。

因此,让我来引入第一个 “3” 之规则。如果你只有两个类或者对象,不要过分关注代码重复。当你在三个不同的地方看到同一个模式的时候在考虑如何重构。

# “3” 之规则应用到架构上

同样的推理可以应用到系统设计上,但是会得出一个非常不同的结论。当你从头构建一个新的系统的时候,你不知道他最终会被如何使用,不要被假设所限制。在第一代和第二代产品上,我们认为需要的限制可能真的是需要的,但是当实现第三代产品的时候,我们会发现假设是完全错误的,并最终实现正确的版本。

比如说,Luigi就是解决问题的第三次尝试。前两个尝试解决了错误的问题,并且为错误的方向做了优化。比如第一个版本依赖于在 XML 中设计依赖图。但是很显然这是非常不友好的,因为你一般县要在代码里生成依赖图比较好。而且,在前两次设计中看起来很有用的一些新设计,比如任务解耦输出,最终只给一些非常少见的例子添加了支持,但是有添加了不少复杂度。

第一个版本中看起来很奇怪的问题可能在后来是很重要的问题,反过来也是。

I was reminded of this when we built an email ingestion system at Better. The first attempt failed because we built it in a poor way (basically shoehorning it into a CRUD request). The second one had a solid microservice design but failed for usability reasons (we built a product that no one really asked for). We’re halfway through the third attempt and I’m having a good feeling about it.

这个故事告诉了我们第二个 “3” 之规则——在系统设计上,直到第三次你才能够做对。

更重要的是,如果你的第一版有一些奇怪的位置问题,不要假设你需要搞定他们。走捷径。绕开奇怪的问题。估计你也不会运行这个系统很长时间——总有一天他会坏的。第二个版本大多数时候也是坏的。第三个版本值得你把它雕琢到完美。

![three cupcakes](https://erikbern.com/assets/three-cupcakes.jpg)

原文:https://erikbern.com/amp/2017/08/29/the-software-engineering-rule-of-3.html

curio asks 源码解析

asks 是 Python 的异步框架 curio 中的 一个 http 库。它基于 h11 这个库来做 http 协议的解析,然后提供了在 curio 下的 IO 操作。下面按照功能逐个介绍其中的每个部分。

杂项

auth.py

该文件中主要包含了 http auth 相关函数, 支持了 Basic Auth 的 Digest Auth。值得注意的是,digest auth 作为一种既很复杂又不安全的认证方式,已经没有人用了。如果需要使用 http auth 的话,现在推荐的方式使用 https + basic auth。

base_funcs.py

提供了一些快捷方式函数,比如 curio.get。

cookie_utils.py

该文件主要包含了 CookieTracker, 对外的方法主要有两个 get_additional_cookies 用于获取域名对应的 cookie,_store_cookies 用于添加 cookie。

parse_cookies 函数主要用于解析 set-cookie 头部,并把解析到的 cookie 附加到 response 对象上。

errors.py

asks 中抛出的异常的类

http_utils.py

处理编码和压缩的两个函数。

请求与响应

request_object.py

该文件中主要是定义了 RequestProcessor 类。RequestProcessor 用于生成一个 HTTP 请求。

make_request 方法。hconnection定义和使用的地方相距太远了。cookie的生成应该使用join。之后调用 _request_io 发送请求

_request_io 调用 首先掉用 _send, 然后调用 _catch_response

_catch_response 调用 recv_event

_recv_event 不断调用 _async_lib.recv(self.sock, 10000) 从而不断产生数据,知道读完为之

sessions.py

session 类

request 调用 grab_connection 获取一个socket,然后把这个socket交给Request对象
grab_connection 调用 checkout_connection 获得一个socket或者,调用make_connection产生一个新的socket,注意其中有一个奇怪的 await sleep(0),可能意思是把循环交回给event loop

make_connection 调用 _connect 方法,并把host和port作为属性写到socket上

session 中有两个SocketQ的类,conn_pool, checked_out_sockets 分别用来保存已连接未使用的socket和正在使用中的socket

response_objects.py

Response 表示了一个响应。如果在发起请求的时候选择了 stream=True, response.body 会是一个 StreamBody 实例,StreamBody 用于流式处理响应。

Cookie 类表示了一个 Cookie,不知道这里为什么没有用标准库的 cookie。

Connection Pool

如果使用代理的话

req_structs.py

SocketQ 是一个 socket 的连接池。使用一个 deque 作为存储,实际上相当于又模拟了一个字典 {netloc => socket}(思考:为什么不使用OrderedDict呢?)index 返回指定 hostloc 对应的 index。pull 弹出指定 index 的 socket。__contains__ 遍历看是否包含对应的socket。需要注意的是这个类不是线程安全的,不过对于 curio 来说,线程安全似乎无关紧要,毕竟只有一个线程。

CaseIncesitiveDict 是一个对大小写不敏感的词典,直接从 requests 里面拿过来的。

curio 的网络通信

首先,需要引入curio.socket 而不是使用内置的socket

TCP通信,使用 sock.bind/listen/accept 等建立服务器,使用recv和sendall发送接收消息。
UDP通信,使用recvfrom和sendto函数通信

作为客户端使用 curio.open_connection 打开到服务器的链接,其中 ssl=True打开的是HTTPS连接诶

对于其他要使用ssl的情况,应该使用curio.ssl而不是标准库的ssl

curio.network.

ssl.wrap_socket 不支持server_hostname sslcontext.wrap_socket 支持

不要把 proxy 传递给 request 对象

添加 http 代理支持

asks 把繁重的 http 解析工作都用 h11 这个库巧妙的解决了,所以 asks 本身是非常轻量的一个库。很遗憾的是,在 asks 中尚未支持代理,下面我们尝试为 asks 增加 http 代理的支持 😛

在 http 代理模式中,每个请求都需要添加上 Proxy-Authorization 的 Header。而在 https 请求中,只有 Connect 的时候需要添加上 Proxy-Authorization 的 Header。

代理的 socket 池和真正的 socket 池要分开,这样设计还简单一点。

Python 转义 html 实体字符

在网页中经常出现 <, &, &0x0026; 这些特殊字符,这是 html 实体字符转义,用于防止 XSS 攻击。Python3 标准库中包含了 html.entities 模块,可以用于转义和反转义这些字符。

html.entities.entitydefs 中包含了名称到符号的映射:比如{'amp': '&'}
html.entities.name2codepoint 中包含了名称到数字的映射:比如 {'amp': 0x0026}
html.entities.codepoint2name 中包含了数字到名称的映射:比如 {0x0026: 'amp'}

Python 操作 ssh

“`
import paramiko
ip=’server ip’
port=22
username=’username’
password=’password’
cmd=’some useful command’
ssh=paramiko.SSHClient()
ssh.set_missing_host_key_policy(paramiko.AutoAddPolicy())
ssh.connect(ip,port,username,password)
stdin,stdout,stderr=ssh.exec_command(cmd)
outlines=stdout.readlines()
resp=”.join(outlines)
print(resp)
“`

Python 中的 queue 模块

在Python中多进程或者多线程之间通信可以使用队列,标准库中实现了一个线程安全的库 queue.Queue,和进程安全的库 multiprocessing.Queue

There are 3 kind of queues: `Queue LifoQueue HeapQueue

“`
q = Queue(size)

get(block=True) return a object
get_nowait()
put(item, block=True) put a object

qsize()
empty()
full()

task_done() # indicate one item process finished raise ValueError
join() # wait until all item processed

Queue.Empty
Queue.Full
“`

How to iterate a queue?

by using `iter(q, None)`, note that you have to put a sentinel value manually

Queue vs multiprocessing.Queue

despite their similar api, their implementation is completely different

http://stackoverflow.com/questions/925100

如果在一个线程使用了异步代码,那么所有的操作都必须使用异步操作,但是并不是所有的操作都需要或者能够使用异步操作。

在异步线程和同步线程之间分享数据需要使用一个共用的queue

如果需要把异步操作分布式不熟使用,在异步的事件循环之间分享数据也需要使用一个queue

阅读《Python hitchhiker》笔记

Package

A file modu.py in the directory pack/ is imported with the statement import pack.modu. This statement will look for an __init__.py file in pack, execute all of its top-level statements. Then it will look for a file named pack/modu.py and execute all of its top-level statements. After these operations, any variable, function, or class defined in modu.py is available in the pack.modu namespace.

A commonly seen issue is to add too much code to __init__.py files. When the project complexity grows, there may be sub-packages and sub-sub-packages in a deep directory structure. In this case, importing a single item from a sub-sub-package will require executing all __init__.pyfiles met while traversing the tree.

This and other issues led to the idea that using stateless functions is a better programming paradigm.
Another way to say the same thing is to suggest using functions and procedures with as few implicit contexts and side-effects as possible. A function’s implicit context is made up of any of the global variables or items in the persistence layer that are accessed from within the function. Side-effects are the changes that a function makes to its implicit context. If a function saves or deletes data in a global variable or in the persistence layer, it is said to have a side-effect.

Pure functions

• Pure functions are deterministic: given a fixed input, the output will always be the same.
• Pure functions are much easier to change or replace if they need to be refactored or optimized.
• Pure functions are easier to test with unit-tests: There is less need for complex context setup and data cleaning afterwards.
• Pure functions are easier to manipulate, decorate, and pass around.

However, it may be a good discipline to avoid assigning to a variable more than once, and it helps in grasping the concept of mutable and immutable types.

A LICENSE file should always be present and specify the license under which the software is made available to the public.
A TODO file or a TODO section in README should list the planned development for the code.
A CHANGELOG file or section in README should compile a short overview of the changes in the code base for the latest versions.
Project Publication
Depending on the project, your documentation might include some or all of the following components:
• An introduction should show a very short overview of what can be done with the product, using one or two extremely simplified use cases. This is the thirty-second pitch for your project.
• A tutorial should show some primary use cases in more detail. The reader will follow a step-by-step procedure to set-up a working prototype.
• An API reference is typically generated from the code (see docstrings). It will list all publicly available interfaces, parameters, and return values.
• Developer documentation is intended for potential contributors. This can include code convention and general design strategy of the project.

put project/ tests/ docs/ directory in side the project

Python functools 中有用的一些函数

functools

partial(fn, *args, **kwargs)

# lru_cache

Decorator to wrap a function with a memoizing callable that saves up to the maxsize most recent calls. It can save time when an expensive or I/O bound function is periodically called with the same arguments.
Since a dictionary is used to cache results, the positional and keyword arguments to the function must be hashable.
If maxsize is set to None, the LRU feature is disabled and the cache can grow without bound. The LRU feature performs best when maxsize is a power-of-two.
If typed is set to true, function arguments of different types will be cached separately. For example, f(3) and f(3.0) will be treated as distinct calls with distinct results.
To help measure the effectiveness of the cache and tune the maxsize parameter, the wrapped function is instrumented with a cache_info() function that returns a named tuple showing hits, misses, maxsize and currsize. In a multi-threaded environment, the hits and misses are approximate.
The decorator also provides a cache_clear() function for clearing or invalidating the cache.

# singledispatch

To define a generic function, decorate it with the @singledispatch decorator. Note that the dispatch happens on the type of the first argument, create your function accordingly

“`
@singledispatch
def fun()
pass

@fun.register(int)
def fun_int()
pass
“`

to get the dispatched func. use fun.dispatch(type)

短视频与机器学习

机器学习需要 Ground Truth
modality是什么意思…

# 浅度学习

## 短视频如何火

为什么: 大多数的短视频1天之后都销声匿迹了
数据集: 10个vine用户的follower广度优先, 获得十万种子用户

大V发布的(social), 声音很好(audio), 美感很好(visual), #hashtag选的好(text)

从以上四个方面抽取特征.

social 的影响最大

## 预测地理标签

1.2%才有地理标签, 预测是会议室/篮球场/公园等, 最重要的是visual feature

# 深度学习

## 声音相关

freesound 是一个免费的声音库. 从一个标签开始, 抽不同的标签的声音. 查找不同的声音

深度学习加迁移学习

alexnet-7是啥

## sequential and sparse

字典学习是啥?

什么事共空间?

# 未来

用户的兴趣是动态的, 但是推荐却是固定的.

无法搜索没有文字的视频 比如: 可以截一帧然后到google上搜索

用户的平台对应关系, 利用quora等, 用户自己关注了

ontology

Ø 短视频的评论也是文本信息啊
Ø Q: 短视频和长视频的分析区别
Ø A: follow等, 地理属性, 质量低