blacklist系统设计讨论

blacklist service
问题版本一：
设计一个全球范围内的blacklist service，就是有很多恶意ip会发来ddos攻击，你要设计一个blacklist的服务，能够ban掉之前已经诊断为malicious ip发过来的请求。这里不要求你设计怎么样判断一个ip是否是恶意ip，给了个isMalicious()的api signature。难点在于不同data center之间怎么sync数据，availability和consistency怎么取舍。哪里会有single point of failure，然后怎么设计能解决。最后folowup就是结合你的工作经验问这个服务上线之后你最想加一个什么功能，不一定是functional的，可以是logistics上的。面试官比较期待的答案是support和monitoring之类的。

问题版本二：
Problem statement
假设一天1Billion访问量，5%是malicious ip造成的，估算下QPS和storage。提供一个isMalicious(ip)的API, 如何ban掉一些 malicious ip address。好比123.123.123.123发了个malicious request 那你得block他之后所有的requests.
Solution
系统的核心就是存储一个黑名单，一旦 isMalicious 返回 true，就加进黑名单。处理 request 的时候发现在黑名单就直接 block request，否则 call isMalicious API。
这个黑名单用 noSQL DB 来满足较高的读写 QPS（读大于写），用 master-slave 或者 consistent hashing，enable cross-region replication。同时用 LRU Query Cache，对于常见的坏IP就直接在 Cache 里读就可以了。

1. Gateway 肯定是需要多个的，所以可以画多个。
2. Redis 我觉得就存 IP 就可以了，如果每隔一段时间需要重新更新 blacklist 的话就再存一下 last_check_time
3. 按照 IP partition，每个 data center 都存一份完整数据


Followup
如果那个API耗时很多，该怎么做？
如果数据库存储依赖不同大洲的data center，一个地区的data center维护的话，跨区的恶意IP如何处理？
部署一台全球服务器，一个地区的数据中心维护，则启用全球服务器处理跨区恶意ip
Additional feature suggestions?
Answer: add support and monitoring
Challenges
data partition

注意ipv4 和ipv6的存储上的区别
The size of an IPv6 address is 128 bits, compared to 32 bits in IPv4.
Ipv4为什么是32bits，我也不知道，可能是跟long int有关

ipv4
最小长度为7个字符(0.0.0.0)
最大长度为15个字符(255.255.255.255)
ipv6
最大长度为32个十六进制(1234.1234.1234.1234.1234.1234.1234.1234)

table design
在看高性能MySQL第3版（4.1.7节）时，作者建议当存储IPv4地址时，应该使用32位的无符号整数（UNSIGNED INT）来存储IP地址，而不是使用字符串。 但是没有给出具体原因。
为了搞清楚这个原因，查了一些资料，记录下来。
相对字符串存储，使用无符号整数来存储有如下的好处：
* 节省空间，不管是数据存储空间，还是索引存储空间
* 便于使用范围查询（BETWEEN...AND），且效率更高
通常，在保存IPv4地址时，一个IPv4最小需要7个字符，最大需要15个字符，所以，使用VARCHAR(15)即可。
MySQL在保存变长的字符串时，还需要额外的一个字节来保存此字符串的长度。而如果使用无符号整数来存储，只需要4个字节即可。

对于转换来说，MySQL提供了相应的函数来把字符串格式的IP转换成整数INET_ATON，以及把整数格式的IP转换成字符串的INET_NTOA。

sql vs nosql

怎样sync各个server的blacklist
1. nosql：Cassandra的多区域数据异步复制能力
2. Mysql：
从消息队列服务考虑

还有朋友建议使用消息队列服务。全球服务器作为生产者，区域服务器作为消费者，在全球服务器操作指定数据后，加入操作内容及数据到队列，消息队列服务配置好需要进行消费的区域服务器接口，实现数据生产 => 消费过程。

这个方案思路让我眼前一新，花了一天思路整理细节逻辑，得到一个绝对可落地的方案，大体如下：

（1）全球服务器根据数据操作类型（增、删、改）以及同步对象的区别（不同类型的区域服务器），对数据进行处理，然后加入Redis数据同步队列；

（2）区域服务器根据自己的数据需求，增加一个数据同步的消费接口，消费成功响应1000，消费失败响应失败数据；

（3）全球服务器增加一个消费Redis数据同步队列的服务，服务中区分同步服务器对象类型，分别调用不同服务器的同步数据消费接口，并且检测同步响应结果，可能存网络原因，如果同步失败，重新进行同步，并增加redis计数器，同一条同步数据超过3次同步失败，加入到数据同步失败日志中，并记录数据同步响应错误结果。

ps：本来有考虑单独开一个消息队列服务，但因为一条数据会同步给多个服务器的情况，就只好在全球服务器中通过代码处理数据再同步至多个服务器。

四、实际落地方案

上文中的方案3是全球数据同步至各区域不同服务器的主要落地方案，但如果所有区域数据库或缓存都通过全球服务器去主动同步，那项目逐渐增大后，性能问题和潜在的架构复杂度也成指数上涨，所以全球到区域的数据同步，要做分层处理，如下：

1. 全球配置数据通过上文方案3同步到区域主服务器（主数据库 / 主Redis）；

2. 区域再通过主数据库或主Redis做主从同步，为二级数据库和Redis同步数据。

这样下来，全球服务器数据同步只需要调用对应区域主服务器消费接口就行，至于区域内部的数据同步，就在各自区域内进行操作，和全球服务器没关系。


How to initialize a new added server.
不仅仅要同步整个cassandra的数据，也要同步缓存的数据

Availability和consistency怎么取舍
你可以把 Cache + DB 考虑成一个整体，我倾向于使用 Write-back Cache，因为性能优先于一致性。只用 Redis 有更高的丢数据的危险。
Write-through（直写模式）在数据更新时，同时写入缓存Cache和后端存储。此模式的优点是操作简单；缺点是因为数据修改需要同时写入存储，数据写入速度较慢。
Write-back（回写模式）在数据更新时只写入缓存Cache。只在数据被替换出缓存时，被修改的缓存数据才会被写到后端存储。此模式的优点是数据写入速度快，因为不需要写存储；缺点是一旦更新后的数据未被写入存储时出现系统掉电的情况，数据将无法找回。
哪里会有single point of failure
主从模式，一个主机连接多个处理节点，主节点负责分发任务，而子节点负责处理业务，当主节点发生故障时，会导致整个系统发故障，我们把这种故障叫做单点故障。分布式协调可以解决多个进程的同步控制，主要核心是实现分布式锁，zookeeper是分布式协调服务，是为了实现分布式锁

IP black list 这种都是设在防火墙层的，也就是所有request的入口，QPS都在百万级别，所有和数据库相关的设计都不适用，甚至redis和bloomfilter都不建议，因为访问量太大。楼上说的用512M的bit来代表whole ipv4 range是不错的建议。但如果有ipv6的话，可能还是需要引入bloomfilter和redis. 如果用，bloomfilter确实有误杀的可能，所以一旦判断为true则需要去cache里面query一下确认record是否确实存在。

政治正确的叫法叫blocklist了现在 🐶

简单说一下我的思路。
既然这是一个IP black list service，那么就会有white list 功能；系统还要区分用途和处于OSI/TCPIP哪一层：应用内置黑名单，CDN防火墙，VPN防火墙和网站/机房防火墙。一般IP黑名单不追求强一致性，即不追求拉黑即生效阻断连接或线上交易等或者拉黑即推送到每台前置机器，所以预设场景：允许IP被拉黑了延迟10秒推送到前置服务器，最后再讨论拉黑即生效的强一致性方案。
数据结构有四种可能的方案：
1，int，将ip字符串转换为int存储数字；
2，bit，一个int可以标识32个点位，即32个IP是黑/白名单，如果只是IPV4，或者有限区间的IPV6地址，可以尝试。
3，int/long数字区间，因为IP通常都是按区间分配给ISP的，可以采用黑/百名单区间配合int/bit提升性能节约空间。
4，IP分级，需要给IP分类分级别允许进入哪些服务，触发了什么审计则降级限制服务，登入了账户则升级。
无论怎么设计，都不可能有存储xx.xx.xx.xx的可能。

数据量预估：
找Internet Assigned Numbers Authority等机构了解IP的规划，搞清楚一定封锁的预定义IP库；
然后是机构IP库和消费IP库，这部分应该不会很大，而且是连续IP，也是黑名单的热点库，大多数都是1-7天封锁。所以可以确定的是这个库不会很大。
初步估算，仅IPV4，则地址数为4,294,967,296（2^32）个；使用int&bit，则有4294967296个位可表示黑白名单，即占用512M的空间，可以直接利用缓存了。

数据库可以用MySQL或者其他，甚至可以用Mysiam，但是分布式的技术环节比较多，需要额外的DBA人员搭建和维护主从同步，不推荐。
NoSQL支持分布式同步数据，应该首选；自行设计文件数据结构则越少的存储，越高的性能；具体设计来说，IP黑名单系统可以避免使用ID主键，采用提交系统唯一ID+UUId为主键，这样可以主从互相同步互不冲突。10秒的时间，足够应付跨区域的数据更新同步了。

整体系统层面，单点故障用负载均衡，有LVS,DNS等方案；大流量采用限流降级访问，或者考虑采购ECS等弹性计算平台，当流量达到峰值可能需要应付突发的大量访问。
数据同步有NoSQL先在机房或者区域中心之间更新数据，然后由消息队列把数据从机房或者区域中心推送到下属负责处理IP的子系统，这里假设各子系统之间并不互相连接。
消息队列解偶数据库和子系统，子系统只接入机房或者区域中心数据库防止区域挂掉整体崩溃。

追求拉黑即生效的强一致性方案损失性能，可以采取补偿措施，即允许黑名单IP的数据短暂性的进入系统，但在最终业务系统时访问到中心IP数据库再做验证。

最后，既然是做IP黑名单，请买好 DDoS防火墙。

原创？不考虑用bloom filter吗？

DylanL 发表于 2021-12-13 12:01
原创？不考虑用bloom filter吗？

收集一些问题和答案，欢迎讨论

wow这也太酷了。

我看不懂，但我大受震撼.jpg

太酷了 赞

JackXin 发表于 2021-12-13 15:02
收集一些问题和答案，欢迎讨论

BloomFilter是为了节约内存，和直接使用IP作为Key相比。 但是有个问题，BF有很小概率会把不在表中的key误判为在表中，即使是1/1000或者1/10，000，如果一个不在blacklist里的IP被block了，恐怕不能接受，即使概率很小

谢谢楼主分享

关于 Availability和consistency怎么取舍，你的回答似乎跑题了 :-)
我同意你说的，这个case，A > C。所以每个DC里的cache 的数据都需要复制。避免一个cache instance死掉了，所有访问冲向数据库。这是所谓的Availability。但是cache replication出于性能考虑，无法实现 strong consitency。后面的single failure point恐怕也是说的这个。

这个不全 缺少关键的东西. 你这个malicious IP是怎么检测的, rule是什么? 如果是根据过去一小段时间的访问量, 你的数据库DB schema是怎么设计的? Write-Back在这题具体是怎么应用?