Month: 七月 2018

蛤?什么是 raft 协议?

Raft 协议是一个分布式的一致性协议,主要通过 Leader Election 和 Log Replication 两个步骤来实现高可用的一致性状态存储。

这篇文章并不是 Raft 协议的一个完整介绍,只是其中核心概念的一个总结概括,要完全理解所有细节还是得看论文。

# Leader 选举

1. 每个节点有三种状态:follower、candidate、leader。
2. 作为 leader 有任期(term)的概念,根据基本法必须选举上台。Term 是一个自增的数字。
3. 作为 leader 要不断发送心跳给 follower,告诉他们一律不得经商。
4. 所有节点都有一个随机的定时器(150ms~300ms),当 follower 没有收到日志后就会升级为 candidate,term + 1,给自己投一票,并且发送 Request Vote RPC 给所有节点,也就是 apply for professor 啦。
5. 节点收到 Request Vote 后,如果自己还没有投票,而且比自己在的任期大,那就说明水平比自己高到不知道哪里去了,就投票出去,否则拒绝。
6. 如果节点发现自己的票超过了一半,就吟两句诗,认为自己是 leader 了
7. 新的 leader 上台后,继续发送日志昭告天下,其他的 candidate 自动灰溜溜的变为 follower 了。

# 日志复制(Log Replication)

1. 所有的请求都发送给 leader,一律由中央负责。
2. leader 把收到的请求首先添加到自己的日志当中
3. 然后发送 Append Entries RPC 给所有的 follower,要求他们也添加这条日志
4. 当大多数的节点都添加这条日志之后,leader 上这条日志就变为了 commited
5. leader 再发送给所有的节点,告诉他们这条日志 commited
6. leader 返回给客户端,告诉他请求成功

## 分区容忍

如果网络发生了分区,也就是另立中央了,那么 raft 的日志复制机制也可以保证一致性。

比如下图中,由于中间的网络分区,出现了两个 leader,这之后如果给下面的 leader(Node B)中发送请求,因为它向一个节点中同步日志,所以只能获得两个节点的确认,因此提交失败。而如果向上面的leader 中发送请求,可以向两个节点中同步日志,也就是说一共三个节点都是同步的,那么就提交成功。不会出现两个 leader 分叉的情况。

![](https://ws4.sinaimg.cn/large/006tKfTcly1ftu1lfepqbj30zk0lmmz7.jpg)

参考资料:

1. [Raft 动画演示](http://thesecretlivesofdata.com/raft/)
2. [Raft 论文](http://www.infoq.com/cn/articles/raft-paper)

LSM 和 sstable

# 核心要点

lsm 是 bigtable、leveldb、rocksdb 等数据库采用的算法。

硬盘,尤其是机械硬盘,顺序写入性能远大于随机写入性能,所以 lsm 把大量的随机写入抓换成了顺序写入,从而极大地又花了写入能力。同时查找效率收到了损伤。

适用于顺序写入多,随机读取少的场景。

之所以要使用 Immutable Memtable,就是为了避免将 MemTable 中的内容序列化到磁盘中时会阻塞写操作。

## 操作

1. 插入

写入 WAL,然后操作 memtable。WAL 是顺序读写,而memtable 是跳表,操作都很迅速

2. 更新

和插入其实是一样的操作

3. 删除

插入一条特殊的删除日志,在 memtable 中标记删除

4. compaction(压缩)

当 memtable 达到设定的阈值的时候,会写入到 immutable memtable,然后写入到硬盘上的 sstable。当 sstable 的数量达到某个阈值的时候,就合并到下一级的 memtable。需要注意的是只有第一级的memtable可能有重复的键值,其他层都不会有重复的,所以可以多线程 compact。

5. 读取

最原始的算法:首先从memtable读,然后从sstable中往高层读取。

可以采取的优化方法:

1. 把 sstable 的一些原始信息放到 manifest 中,放在内存中,快速查找
2. 使用 bloom filter 先过滤一遍,看 key 是否在 LSM 中,然后再查找。

一图胜千言:

![](https://ws3.sinaimg.cn/large/801b780aly1ftt76pvzotj21kw13eh8u.jpg)

参考:

1. http://blog.fatedier.com/2016/06/15/learn-lsm-tree/

红黑树

红黑树的要求:

1. 节点是红色或黑色。
2. 根是黑色。
3. 所有叶子都是黑色(叶子是NIL节点)。
4. 每个红色节点必须有两个黑色的子节点。(从每个叶子到根的所有路径上不能有两个连续的红色节点。)
5. 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。

![](https://upload.wikimedia.org/wikipedia/commons/thumb/6/66/Red-black_tree_example.svg/900px-Red-black_tree_example.svg.png)

两篇不错的教程:

1. [漫画:什么是红黑树](https://juejin.im/post/5a27c6946fb9a04509096248)
2. [维基上的红黑树](https://zh.wikipedia.org/wiki/%E7%BA%A2%E9%BB%91%E6%A0%91)

MySQL 性能小技巧和在 Django 中的应用

对于 delete update insert 等语句一定要使用 limit 子句限制影响的行数,避免一次更改特别多的行,造成数据库假死

while (1) {
    //每次只做1000条
    mysql_query("DELETE FROM logs WHERE log_date <= '2009-11-01' LIMIT 1000");
    if (mysql_affected_rows() == 0) {
        // 没得可删了,退出!
        break;
    }
    // 每次都要休息一会儿
    usleep(50000);
}

2. 垂直分割

把不会用作索引的,或者是过长的字段可以考虑使用其他存储引擎,比如 rocksdb 等。

3. IPv4 地址可以存为 uint32

使用 uint32 存储 IP 地址不光可以节省空间,而且可以按区间查询。

4. 避免 select *

从数据库里读出越多的数据,那么查询就会变得越慢。并且,如果你的数据库服务器和应用服务器是两台独立的服务器的话,这还会增加网络传输的负载。

所以,你应该养成一个需要什么就取什么的好的习惯。

不要使用:

SELECT * FROM user WHERE user_id = 1

使用:

SELECT username FROM user WHERE user_id = 1

在 django 中,可以使用 only

books = Book.objects.filter(author="Jim").only('book_name')

5. 当只要一行数据时使用 LIMIT 1

当你查询表的有些时候,你已经知道结果只会有一条结果,但因为你可能需要去fetch游标,或是你也许会去检查返回的记录数。

在这种情况下,加上 LIMIT 1 可以增加性能。这样一样,MySQL数据库引擎会在找到一条数据后停止搜索,而不是继续往后查少下一条符合记录的数据。

下面的示例,只是为了找一下是否有“中国”的用户,很明显,后面的会比前面的更有效率。(请注意,第一条中是Select *,第二条是Select 1)

SELECT * FROM user WHERE country = 'China'
SELECT 1 FROM user WHERE country = 'China' LIMIT 1

在 Django 中可以使用 [:1] 来添加 limit 1

6. EXPLAIN 你的 SELECT 查询

使用 EXPLAIN 关键字可以让你知道MySQL是如何处理你的SQL语句的。这可以帮你分析你的查询语句或是表结构的性能瓶颈。

7. 尽量让查询能 fit 进内存中

参考:

  1. https://coolshell.cn/articles/1846.html

每个程序员都应该知道的延迟数字

动作 时间 换算
L1 缓存访问 0.5 ns 0.5ns
分支预测错误 5 ns 5ns
L2 缓存访问 7 ns 7ns
互斥锁/解锁 25 ns 25ns
内存访问 100 ns 100ns
使用 Zippy压缩 1KiB 3,000 ns 3 µs
通过 1 Gbps 网络发送 2KiB 20,000 ns 20 µs
SSD 随机读取 150,000 ns 150 µs
内存中连续读取 1 MB 250,000 ns 250 µs
同一个数据中心的来回 500,000 ns 0.5 ms
从 SSD 上连续读取 1 MB* 1,000,000 ns 1 ms
机械磁盘寻道 10,000,000 ns 10 ms
机械磁盘连续读取 1 MB 20,000,000 ns 20 ms
发送数据包 加州->荷兰->加州 150,000,000 ns 150 ms
  • 假设 ~1GB/sec SSD

如果把这些时长都乘以 10 亿的话:

动作 时长 相当于
L1 缓存访问 0.5 s 一次心跳 (0.5 s)
分支预测错误 5 s 打个哈欠
L2 缓存访问 7 s 打个长哈欠
互斥锁/解锁 25 s 冲一杯咖啡
内存访问 100 s 刷牙
使用 Zippy压缩 1KiB 50 min 一集电视剧(包括广告)
通过 1 Gbps 网络发送 2KiB 5.5 hr 从午餐到下午工作结束
SSD 随机读取 1.7 days 一个普通的周末
内存中连续读取 1 MB 2.9 days 一个长周末
同一个数据中心的来回 5.8 days 一个普通假期
从 SSD 上连续读取 1 MB* 11.6 days 等快递等了两周
机械磁盘寻道 16.5 weeks 大学里的一个学期
机械磁盘连续读取 1 MB 7.8 months 几乎能造个人了
上面两个加起来 1 year 整整一年
发送数据包 加州->荷兰->加州 4.8 years 快能读个博士了

可视化网页:
https://people.eecs.berkeley.edu/~rcs/research/interactive_latency.html

这些数字的作用是什么?

了解这些时间的量级有助于比较不同的解决方案。通过这些数字,你可以看出来从远程服务器的内存中读一些数据时比直接从硬盘上读取快的。在一般的程序中,这也就意味着使用磁盘存储比使用数据库服务器要慢,因为数据库通常把所有东西都放在内存里了。而且这也说明了为什么在服务全球客户的时候 CDN 至关重要。从北美到欧洲的一个 ping 就要花上 100+ ms,所以从地理上来说,内容应该是分布式部署的。

The idea is more about knowing the scale of time it takes to help compare different solution. With those number you can see that it’s faster to get data in memory from a distant server than to read the same data from disk. In common application that means using disk storage is less efficient that storing it in a database on an other server, since it usually keeps almost everything in memory. It also tells a lot about why CDN are needed if you are serving client worldwide. A ping from North America to Europe will always takes 100+ ms, so having geographically distributed content is a good idea.

对于互斥锁的开启锁定时间
mutex lock/unlock time is important for anyone writing code that depends on code that is accessing the same data structures at the same time. If you don’t know that there is a considerable cost to writing such code, now you do; and this number can quantify it.

还需要注意顺序读写和批量读写带来的提速

常见问题

随着摩尔定律的发展,这些数字会不会不太准确了?

首先摩尔定律基本上经失效了。其次,这些数字的重点是他们之间的比例,而不是具体数字。

延迟, 带宽和吞吐之间的区别和联系?

Tube

  • 延迟表示通过管道需要花费的时间
  • 带宽表示管道的宽度
  • 每秒钟流过的水的数量就是吞吐

吞吐 = 延迟 x 带宽

然而不幸的是, 吞吐这个词经常被用作两个意思. 有时候吞吐的意思是指的系统总荷载, 有时候又指
的是每秒吞吐量, 也就是带宽(当然单位不同).

参考:

  1. https://gist.github.com/hellerbarde/2843375
  2. https://softwareengineering.stackexchange.com/questions/312485/how-can-jeff-deans-latency-numbers-every-programmer-should-know-be-accurate-i
  3. https://stackoverflow.com/questions/36949735/what-is-the-difference-between-latency-bandwidth-and-throughput

MySQL 中的 wait_timeout 是做什么的?

Mysql 中默认的 wait_timeout 和 interactive_timeout 的值是八小时,也就是一个连接(交互式和非交互式的)只有在 8 小时没有活动之后才会被关闭掉。对于互联网公司来说,这个值实在太大了,一个库可能被很多脚本和服务访问,可能只是一个简短的查询就不需要数据库了,如果每个查询都占据了8小时的时间,那么 mysql 很快连接数就会满了,报出 too many connections 错误。

mysql 默认的连接数可以修改 max_connections 参数,但是一个服务器能支撑的连接数显然是由硬件决定的。

设置 wait_timeout 过短可能会造成一些问题,如果在 django 中两次查询的之间时间大于 wait_timeout,就会报 (2006, ‘MySQL server has gone away’)。django 官方给的建议是:

  1. 当你的脚本不需要使用数据库的时候,主动关闭连接,比如在 django 中使用 from django.db import connection; connection.close()
  2. 增大 wait_timeout 的值

不过django默认 CONN_MAX_AGE 是 0,也就是在查询数据库之后会立即关闭链接,理论上应该不会报这个错误。但是这样不能复用链接,会造成对数据压力很大。

CONN_MAX_AGE 应该小于数据库本身的最大连接时间wait_timeout,否则应用程序可能会获取到连接超时的数据库连接,这时会出现MySQL server has gone away的报错。

可以在 settings.py 中动态地获取并填充这个值,然后写到 CONN_MAX_AGE 中

理论上这样就不会再报错了,但是难免数据库重启或者什么时候会报错,总是使用 close_old_connections 还是很烦。

有一种思路是在检测到和数据库链接断开的时候,自动重连,但是这样会破坏 django.db.atomic,但是可以实现一种不同的backend。可以参考这两个:

  1. https://github.com/django/django/pull/2740/commits/38f58aa4d751ad83f1dc76d5b945a1036239584f

  2. https://github.com/django/django/pull/2454/commits/36b8bf870cab183b7ad63c0d8e7e8c02e314a053#diff-f8a587a973ef4c3a94d7550a5b85342c

还有一种解决思路是使用 connection pooling,我们可以使用 sqlalchemy 的 连接池作为django连接数据库的工具。参考这里:http://menendez.com/blog/mysql-connection-pooling-django-and-sqlalchemy/, 不过这种方法比较 hack。

参考

  1. https://code.djangoproject.com/ticket/21597#no2
  2. https://github.com/django/django/commit/2ee21d9f0d9eaed0494f3b9cd4b5bc9beffffae5
  3. https://stackoverflow.com/questions/1125504/django-persistent-database-connection
  4. django 优化
  5. https://docs.djangoproject.com/en/2.1/ref/databases/#persistent-connections
  6. 如何设置 max_age

动态规划(LeetCode 413. Arithmetic Slices)

# LeetCode 413. Arithmetic Slice

是一道可以用动态规划解的问题

## 题目

给定一个数组,找出其中等差数列的个数。等差数列的定义:3各元素以上,每个元素之间差相等。

比如:

“`
1, 3, 5, 7, 9
7, 7, 7, 7
3, -1, -5, -9
“`
下面的就不是:

“`
1, 1, 2, 5, 7
“`

例子:

“`
A = [1, 2, 3, 4]

return: 3, for 3 arithmetic slices in A: [1, 2, 3], [2, 3, 4] and [1, 2, 3, 4] itself.
“`

## 解法

观察发现,当我们遍历数组的时候,如果能和前一个元素构成等差数列,那么在这个位置可以构成的等差数列的个数就是上一个位置加一,所以的到递推公式:

“`
dp[i] = dp[i-1] + 1
“`

借用官方答案里的图片:

![](https://ws4.sinaimg.cn/large/006tNc79ly1ftjiweuvyaj317m0homzj.jpg)

所以我们就得到了答案:

“`
class Solution:
def numberOfArithmeticSlices(self, A):
“””
:type A: List[int]
:rtype: int
“””
dp = [0] * len(A)
for i in range(2, len(A)):
if A[i] – A[i-1] == A[i-1] – A[i-2]:
dp[i] = dp[i-1] + 1

return sum(dp)
“`

彭博到底是做什么生意的?

一句话:卖彭博终端机

为什么大家要买彭博终端机呢?界面那么老土

I think most of your questions can be answered by realizing that Bloomberg was founded in 1981, and they basically got a monopoly in financial data provision because there were no other options in 1981. That is why they have a custom monitor & keyboard: in the days before the IBM PC, everyone had a custom monitor & keyboard, because these things were not standardized. Bloomberg was a technologist & businessman before he was a politician; his business success gave him the money to run for office, his office doesn’t force people to pay for Bloomberg.

The reason they’re still a monopoly is because knowing how to navigate a Bloomberg is a critical skill for most finance professionals, and now that they have that skillset, they can be very productive moving around in it. A different (better?) UI would require they re-learn everything, which is not going to happen. And when financial professionals are making half a million a year, paying $24k/year for a terminal so that they can be productive isn’t a bad investment.
(Source: have a couple friends at Bloomberg. One is in their UI department, and keeps having his proposals for better UIs shot down for business reasons. Also married a financial professional who had to use a Bloomberg in her days as a bond trader.)

The best way to think about the Bloomberg terminal is a web browser that connects you to a private network. (Bloomberg actually is the largest known private network.) Once connected, you have access to thousands of “web apps” – which Bloomberg users call “functions”. Instead of a URL, you use a short 2 to 5 letter mnemonic code for each function, such as “MSG” for email, or “TOP” for top news. These different functions provide all sorts of various functionality – most of them are of course related to financial information. Functions like “CDSW” are for analyzing credit default swaps, “SDLC” gives you supply chain data for different companies, other functions analyze or curate Twitter, others correlate news events with historical stock data, etc. There are also many non-financial functions as well that reflect the “social network” aspect of the Bloomberg terminal, such as “POSH” which is basically a high-end Craigs list, or “DINE” which is a high-end Yelp.
All-in-all, the Bloomberg Terminal is like a private Internet for financial professionals.

核心的依赖可能是 bloomberg chat,相当于金融圈的社交网络。

“I think Facebook is the best comparison,” Ayzerov says. “If Facebook had only one fourth of your friends, you wouldn’t use it. The advantage of Bloomberg is that every financial person has it.””

Wow, great comments about Bloomberg. It makes me wonder, is there similar system for Cryptocoins traders?

Bloomberg would be very hard to dethrone. It’s key selling point is all of the data they have access to, which takes forever to setup integration with all of those providers. They continually expand data sources as well so it’s not like they are asleep at the wheel.
Finally, Bloomberg chat has strong network effects so even if you had all of the same data, many traders still wouldn’t switch to you because they can’t communicate with others still on Bloomberg.

1. It is a all-in-one news source. There are a lot of features that allow you to monitor the news from many different sources in real time.
2. It is a social network. The built-in chat and email service is _really_ basic. But, just about every one working in Finance is on it, with their contact details and resumes. As a trader, you can legally close financial transactions on the Bloomberg chat, as one would over the phone.
3. It is a data sharing platform. Banks and other market participants contribute to Bloomberg data by sending information that is normally not visible in the market. For instance FX volatilities are quoted by banks on bloomberg in real time. This information is only available in few places.
4. It is an API that allows its users to use its data for custom analytics.
5. It is an execution platform, where you can book trades, follow their values and risk when the market moves, etc.
6. It is open to 3rd parties: some banks and other data vendors have their own pages on bloomberg (which I never had access to).
7. It has many many other stuffs. There is a restaurant review system. There is a classified section. There are things to monitor the weather. It has videos, maps, it’s just huge.

redis 常见问题

主要参考这篇文章:https://mp.weixin.qq.com/s/vS8IMgBIrfGpZYNUwtXrPQ

# 1. 集合操作避免范围过大

使用 sortedset、set、list、hash等集合类的O(N)操作时要评估当前元素个数的规模以及将来的增长规模,对于短期就可能变为大集合的key,要预估O(N)操作的元素数量,避免全量操作,可以使用HSCAN、SSCAN、ZSCAN进行渐进操作。集合元素数量过大在使用过程中会影响redis的实际性能,元素个数建议尽量不要超过5000,元素数量过大可考虑拆分成多个key进行处理。

# 2. 合理使用过期时间

如果key没有设置超时时间,会导致一直占用内存。对于可以预估使用生命周期的key应当设置合理的过期时间或在最后一次操作时进行清理,避免垃圾数据残留redis。redis 不是垃圾桶。

# 3. 利用批量操作命令

假设要给一个集合导入 5000 个元素:

方案1:直接使用redis的HSET逐个设置

“`
for _ in 0..5000
HSET hash, k,v
“`
结果:失败。redis ops飙升,同时接口响应超时

方案2:改用redis的 HMSET一次将所有元素设置到hash中

“`
map = 50000个元素
HMSET hash map
“`

结果:失败。出现redis慢日志

方案3:依然使用 HMSET,只是每次设置500个,循环100次

“`
map_chunk = 500个元素
for i in 0..100
HMSET hash map_chunk[i]
“`

结果:成功

MSET/HMSET等都支持一次输入多个key,LPUSH/RPUSH/SADD等命令都支持一次输入多个value,也要注意每次操作数量不要过多,建议控制在500个以内

# 4. 合理设置值的大小

String类型尽量控制在10KB以内。虽然redis对单个key可以缓存的对象长度能够支持的很大,但是实际使用场合一定要合理拆分过大的缓存项,1k 基本是redis性能的一个拐点。当缓存项超过10k、100k、1m性能下降会特别明显。关于吞吐量与数据大小的关系可见下面官方网站提供的示意图。

在局域网环境下只要传输的包不超过一个 MTU(以太网下大约 1500 bytes),那么对于 10、100、1000 bytes不同包大小的处理吞吐能力实际结果差不多。

# 5. 禁用一些命令

keys、monitor、flushall、flushdb应当通过redis的rename机制禁掉命令,若没有禁用,开发人员要谨慎使用。其中flushall、flushdb会清空redis数据;keys命令可能会引起慢日志;monitor命令在开启的情况下会降低redis的吞吐量,根据压测结果大概会降低redis50%的吞吐量,越多客户端开启该命令,吞吐量下降会越多。

keys和monitor在一些必要的情况下还是有助于排查线上问题的,建议可在重命名后在必要情况下由redis相关负责人员在redis备机使用,monitor命令可借助redis-faina等脚本工具进行辅助分析,能更快排查线上ops飙升等问题。

# 6. 避免大量 key 同时过期

如果大量的 key 过期时间设置得过于集中,到过期的时间点,redis 可能会出现短暂的卡顿现象。一般需要在时间上加一个随机值,使得过期时间分散一些。

# 7. Redis 如何做持久化

bgsave 做镜像全量持久化,aof 做增量持久化。因为 bgsave 会耗费较长时间,不够实时,在停机的时候回导致大量丢失数据,所以需要 aof 来配合使用。在 redis 实例重启时,优先使用 aof 来回复内存状态,如果没有 aof 日志,就会使用 rdb 来恢复。

如果 aof 文件过大会导致恢复时间过长,不过 redis 会定期做 aof 重写,压缩 aof 文件日志大小。在 redis 4.0 之后还有了混合持久化的功能,将 bgsave 的全量和 aof 的增量做了融合处理,这样既保证了回复的效率有兼容了数据的安全性。

为了避免断电时后丢失数据,还可以设置 aof 日志的 sync 属性,极端情况下,可以每次写入都执行,不过会对性能有影响,一般每秒一次就可以。

# 8. 保存失败

redis 报错:Can’t save in background: fork: Cannot allocate memory。

原因是 redis 在后台保存的时候会直接 fork 一下,然后保存。由于数据库过大,就会 fork 失败,但是实际上由于 copy-on-write 机制的存在,并不会产生问题。所以可以直接更改系统的配置,允许 fork。

把 `/etc/sysctl.conf` 文件修改如下:

“`
vm.overcommit_memory=1
“`

然后重新加载:

“`
sysctl -p /etc/sysctl.conf
“`

参考资料:

1. https://stackoverflow.com/questions/11752544/redis-bgsave-failed-because-fork-cannot-allocate-memory

大规模字符串的匹配

问题:假设我们有一组比较长的文本,每一个文本都有几十k左右,还有一些敏感关键词需要删除,大概有几千,然后需要在这些文本中把关键词找出来。

# 方法1:暴力搜索

“`
import re

compiled_words = [re.compile(r’\b’ + word + r’\b’) for word in my20000words]

for sentence in sentences:
for word in compiled_words:
print(re.sub(word, “***”, sentence))

“`

# 改进1:把正则组合起来

“`
pattern = “\b(word1|word2|word3)\b”

for sentence in sentences:
print(re.sub(pattern, “***”, sentence))
“`

# 改进2:使用 Trie 优化正则

对于数组:[‘foobar’, ‘foobah’, ‘fooxar’, ‘foozap’, ‘fooza’],使用上面的方法,我们可能会写出正则:

“`
“\b(foobar|foobah|fooxar|foozap|fooza)\b”
“`

但是这并不是最优的正则,应该使用前缀树的思想来合并单词,形成下面的正则:

“`
r”\bfoo(?:ba[hr]|xar|zap?)\b”
“`

具体的方法可以看这里:https://stackoverflow.com/a/42789508/1061155

# 改进3:基于集合的搜索

“`
import re

def delete_banned_words(matchobj):
word = matchobj.group(0)
if word.lower() in banned_words:
return “”
else:
return word

word_pattern = re.compile(‘\w+’)

for sentence in sentences:
sentence = word_pattern.sub(delete_banned_words, sentence)
“`

参考:

https://stackoverflow.com/questions/42742810/speed-up-millions-of-regex-replacements-in-python-3/42789508

https://medium.freecodecamp.org/regex-was-taking-5-days-flashtext-does-it-in-15-minutes-55f04411025f