平时在windows系统上更习惯用git bash作为终端，因为gitbash支持一些常用的linux命令。
现在也想把IDEA中的terminal也替换为git bash， 操作如下：
打开IDEA配置项：IntelliJ Idea File—>settings—>Tools—->Terminal 。
设置 Shell path 为 D:\Program Files\Git\bin\bash.exe ，点击Apply完成终端调整。重启IDEA可以完成terminal的调整。
这几天在用GoLang写个东西，期间用到了gorm框架。
在用gorm查询时遇到了一个奇怪的问题：就是这个框架会自动将model的名称转为复数形式。
先来看下具体的报错信息。这里是一个用户model：
|
1 2 3 4 5 6 7 8 9 10 11 12 |
// User 用户信息 type User struct { // Id value Id string `json:"id" gorm:"primaryKey"` // Username 用户名 Username string `json:"username"` // Password 密码 Password string `json:"password"` } |
查询语句在这里：
|
1 2 3 4 5 6 |
// GetById 根据ID查询用户信息 func (r *UserRepo) GetById(id int64) *model.User { var user model.User db.Last(&user, id) return &user } |
执行查询的时候收到了如下的错误信息：
|
1 2 |
Error 1146: Table 'zhyea.users' doesn't exist [1.083ms] [rows:0] SELECT * FROM `users` WHERE `users`.`id` = 1 ORDER BY `users`.`id` DESC LIMIT 1 |
错误信息显示查询的时候没有查预期中user表，反而是查了一个复数形式的users表。
跟踪了下gorm框架的代码，发现这里是获取表名的关键点：
|
1 2 3 4 5 6 7 |
// TableName convert string to table name func (ns NamingStrategy) TableName(str string) string { if ns.SingularTable { return ns.TablePrefix + ns.toDBName(str) } return ns.TablePrefix + inflection.Plural(ns.toDBName(str)) } |
关键在NamingStrategy的ns.SingularTable属性上。查了下资料后知道可以配置中设置相关的属性：
|
1 2 3 |
NamingStrategy: schema.NamingStrategy{ SingularTable: true, }, |
具体是在创建数据库连接时做这个配置。完整的数据库连接配置在这里：
|
1 2 3 4 5 6 7 8 9 10 11 12 |
db, err = gorm.Open(mysql.New(mysql.Config{ DSN: ds.Dsn, // DSN data source name DefaultStringSize: 256, // string 类型字段的默认长度 DisableDatetimePrecision: true, // 禁用 datetime 精度，MySQL 5.6 之前的数据库不支持 DontSupportRenameIndex: true, // 重命名索引时采用删除并新建的方式，MySQL 5.7 之前的数据库和 MariaDB 不支持重命名索引 DontSupportRenameColumn: true, // 用 `change` 重命名列，MySQL 8 之前的数据库和 MariaDB 不支持重命名列 SkipInitializeWithVersion: true, // 根据当前 MySQL 版本自动配置 }), &gorm.Config{ NamingStrategy: schema.NamingStrategy{ SingularTable: true, }, }) |
倒数第4行代码是起点。（这是第一种方式）
后来又在gorm的文档中发现了其他两种方式：
User model 创建一个TableName()函数，大致如下：|
1 2 3 4 |
// TableName 指定表名 func (User) TableName() string { return "user" } |
这是第二种方式。
|
1 2 |
var user model.User db.Table("user").Last(&user, id) |
这是第三种方式。但是可以看出，这个方案并不好，谁有耐心在每次查询时都指定表名啊。
在gorm框架的schema.go的ParseWithSpecialTableName()方法（第123行）可以看到下面的代码：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
modelValue := reflect.New(modelType) // 第一种方式 tableName := namer.TableName(modelType.Name()) if tabler, ok := modelValue.Interface().(Tabler); ok { // 第二种方式 tableName = tabler.TableName() } if en, ok := namer.(embeddedNamer); ok { // 第四种方式 tableName = en.Table } if specialTableName != "" && specialTableName != tableName { // 第三种方式 tableName = specialTableName } |
在这段代码里可以看到设置表名的几种方式和对应的优先级。这里除我们前面提到的三种设置表名的方式外，还提示了第四种方式：通过嵌入式命名规则。可以猜测下第四种方式的使用场景：比如在需要分表的场景下这种方式还是非常便捷的。不过现在对我来说前面三种方式已经完全够用了，第四种具体如何使用我就懒得探索了…
就这样了！END！！！
RTA 即Realtime API的简称，是一种实时的广告程序接口，用于满足广告主实时个性化的投放需求。RTA 将流量选择权交给广告主，通常在定向环节中将用户身份的识别的请求发送给广告主，进行用户的筛选。
最近几年国内越来越重视用户隐私，许多之前用的很顺手的操作（比如上传人群包）在现在就得斟酌下了。RTA是解决这类问题的一个好方案。RTA可以在不上传人群包的情况下完成人群定向，同时可以结合产品数据进行实时调整，非常灵活。
RTA能帮广告主做到如下事情：
其中第三点需要媒体的支持。
每次⼴告请求参与竞价时， 平台携带用户信息请求⼴告主服务器， 广告主判断此次请求是否参竞，平台根据广告主返回结果进行定向流量竞投。
流程图如下：
根据上面的流程图可以看出RTA主要是在媒体的DSP或SSP接收到流量后，执行竞价逻辑前发挥作用。
先来看下整体的处理流程图：
我们使用RTA对拉新和拉活的流量都有做筛选。
对于拉新只能利用请求中的信息做基础定向或者使用曝光/点击的数据进行曝光/点击频控。不过如果有采买第三方的数据，就还可以多做些事情。
对于拉活，可以基于历史数据和实时的曝光/点击/UV数据做如下事情：
再来简单说下流程图中的几个关键节点：
以上就是RTA流程中的关键节点了。其它部分参考前面的流程图就行。
RTA引擎和其他服务的关系大致如下图：
接下来介绍下RTA运行中遇到的各种问题及解决方案。
媒体一般要求RTA的处理时间在30ms以内。目前我们的RTA每天接收到139亿个请求，QPS峰值约为35w，这个规模的流量给我们造成了一定的压力。
RTA服务部署在腾讯云上，共60个节点（每个节点16核32G），走的腾讯云的四层负载均衡TGW（TGW基础原理）。有两个TGW VIP节点通过加权轮询的方式将流量引向RTA的节点。
不过应该是由于DNS缓存的问题，请求并不能均匀的转发到两个TGW的VIP上。抽样检查了一个小时的请求量，发现两个VIP对应的节点约有20%的差距。
此外RTA相关的一些基础服务比如Redis是部署在公司自有机房内的，导致只是跨机房请求就会有2ms的时间消耗。
再来说下是怎么应对这些流量的。
在设计RTA引擎的时候我们就确定了一个思路：尽量减少网络请求。目前系统依赖的外部组件有Redis和MySQL。因为只启动了一个协程定时从MySQL中同步配置信息，所以MySQL的压力可以忽略。
Redis中存储的是人群信息，这部分查询是不能避免的，但是据我们的经验，redis最多能承受5~6wQPS，再多了就会出现CPU使用率过高的报警。因为拉新投放不用请求redis，所以处理流程中的“历史设备检查”这个环节是非常重要的，有了这个环节，需要打到redis的流量会被压缩到3wQPS左右。最后，我们还启用了本地小时级缓存，从redis查询到的数据都会在本地缓存，这样对redis的请求会再次被压缩。
另外，我们还做了应用内限流，采用的是简单计数法，当每秒内请求总数超过5500之后再来的请求就会被丢弃掉。
在投放完成后还需要回收相关数据作为算法迭代的素材。这就需要将RTA收到的请求数据和后续的曝光点击数据连接起来，依据在RTA请求处理中做的实验分组进行效果对比和评估。
最开始我们做的连接是流量级别的连接，但是因为种种缘故，曝光和请求数据的连接率始终都不够好。期间也有和媒体做过多轮沟通，但是最终曝光连接率也只能提升到70%左右。
最后我们放弃了流量级别的连接，采用了宏观的分组方案，即分别在请求/曝光/点击几层按相同的逻辑进行分组计算，然后按整体比例进行统计和分析。经过实验，结果和预期还是比较匹配的。
这个问题是由近期头条的一次升级带来的（升级的背景在这里）。
因为头条在发送的RTA请求中不再提供原始设备ID或原始设备ID的MD5值，我们也只好用加密设备ID来和他们匹配，这样就导致全量历史设备库规模会变成之前的三倍（原值MD5值，原值加密值，原值MD5值加密值）。为了使RTA的不至于误判，就需要同时增加CuckooFilter的规模，加上备份CuckooFilter所需的内存空间，最终产生了OOM问题。
最终沟通出来的解决方案是为头条站内请求只保留近一年的历史设备数据，而其他媒体仍使用全量的历史设备库。通过这样的折中方案暂时解决了问题。
目前就这些问题。之后如果再想到会补上。
END！！！
这里主要是介绍下企业直投广告中的几个环节（广告监测、归因处理及转化回传）的业务逻辑，遇到的问题以及解决方案。
之前听过马师傅的“接化发”三字诀，觉得也可以套用到广告投放上，因此这次就按这个路子来说下。
所谓“接”，当然就是接收广告投放相关的数据了。企业在媒体平台投放广告后会要求媒体将点击广告的用户信息及广告信息上报回来。
这么做的目的大致有如下几个：
其中第一点的作用不是那么重要，因为我们不是简单采用CPM或CPC方式进行结算，多是以投放效果（CPA）结合CPM的方式来计算投放的费用。效果数据的收集也可以通过应用下载时的deeplink来做到（这点有机会再展开说）。
媒体通常会采用HTTP请求的形式上报广告数据。上报的数据前期主要为广告的曝光、点击等信息。后来随着视频广告的占比逐渐加大，上报的数据中也多了有效播放数据（通常默认播放时长超过3秒为有效播放）。在我们收到的数据里，曝光/播放/点击三种数据的比例大致为：60:20:1。其中曝光数据的作用不是很大，主要用来对RTA的效果进行评估。需要认真处理的是点击数据和有效播放数据，这两种数据会被用来做归因处理。
在广告监测这个环节我们遇到了两个问题：
对于第一个问题，我刚接手的时候看到的做法是为每个媒体分别创建了一个处理器来解析处理相关的请求。这种思路在早期是没问题的，甚至可以说是相当健壮也相对容易维护的一种方案。但是随着业务的发展，我们截止现在陆续对接了大大小小近五十个媒体。照说再写几十个处理逻辑也不是什么难事，关键一些大的媒体，比如头条百度腾讯，在这些媒体不同的子平台上也会有不同的投放需求，这样原来方案扩展性较差的问题就凸显出来了。对于前者，我们设计了灵犀平台，实现了不同媒体的在线配置对接。对于后者，我们在媒体的基础上又抽象出了监测维度，来适配同一媒体不同子平台的投放需求。
再来说第二个问题，我们接收的三种数据的总量一度达到了每天3.2亿，六个节点承接了3700QPS的访问。这个规模其实也不大，加之我们只是简单的接收数据，不需要返回什么内容，因此依托Nginx的轮询（RoundRobin）方案就可以完美承接下来。困难的是数据的存储：其中曝光数据只是用来做离线统计分析，直接通过Kafka扔到HDFS就可以了；剩下的点击和有效播放数据，因为还需要用来支撑归因和场景回放等业务，得分别存储到Redis和MySQL数据库中。好在这部分数据只需要按业务需求存储一定周期内的部分即可。但是随着后来视频广告占比增多，上报的有效播放数据骤增，redis和mysql先后出现了报警：redis空间使用率一度高达93%，mysql存储的相关数据达到了1.2T，并引发了主从同步的问题，甚至还影响了同一MySQL集群上其他团队的业务。解决redis存储问题的方案比较简单，只是精简了存储的内容并适当调整业务逻辑就将空间使用量压缩到了37%（就是这么简单）。对mysql这边尝试了几次调整后发现效果不大，最终是将数据移到了HBase，在MySQL中只存储了高度精简的数据来支持已有的业务查询，同时MySQL表还可以作为HBase表的二级索引。这样调整后的架构至少可以支撑当前业务总量的2.5倍压力，能够轻松较长的一段时间了。
“化”可以理解为消化或者化为己用。归因的主要作用就是消化投放相关的数据，为投放提供助力。
和广告圈子之外的人聊归因这块儿业务时，常会被问一个问题：“什么是归因？”。我的解释是：归因可以简单理解为“找到原因”或者说“溯源”，在广告投放上就是找到一个投放效果（比如说安装APP）具体是由哪个广告带来的。为完成归因处理我们需要两种数据：
归因处理的核心逻辑就是用应用日志中的设备ID来和存储的点击数据中的设备ID进行匹配，匹配上了就说明归因成功。因为我们主要是做拉新归因，所以在执行归因之前还会根据设备ID判断下是不是历史用户。
归因匹配的方式有两种：精准归因和模糊归因。精准归因就是使用设备ID做匹配，模糊归因则是在拿不到设备ID时候采用的折中方案，是用IP加设备的一些基础信息（比如系统版本号）做匹配。因此在常规操作时，模糊归因的时间窗口要远小于精准归因。根据我们的评估，1小时是模糊归因的最佳窗口，超过2小时就会暴露类似撞库的问题，更遑论3天了。精准归因的时间窗口通常是72小时。
归因的模型我们使用的是Last Click模型，这也被称为末次互动模型，是最为通用且最容易实现的模型。不过，我们也有尝试离线做过助攻模型（也称时间衰减模型），即一个用户在最终下载应用前浏览或点击过多个广告，虽然用户并没有通过这些广告产生下载行为，但我们也认为这些广告对用户是有影响的，并根据距离用户下载行为时间点的远近给这些广告一个权重。
在归因这块儿给我们带来过的最大困扰是用户应用日志的规模。早期的归因引擎处理的是全量原始访问日志，每小时100多G的日志给业务处理以及网络都带来了巨大的压力。在归因场景上其实不需要处理这么细粒度的数据——除了某些特殊的转化事件，通常只需要拿到用户的设备ID、事件时间等几个维度的数据就可以了。据此我们增加了用户日志的标准化加工和去重处理服务（也可以称作ETL服务），最终将归因日志的规模压缩到了原来的1/80左右。用户日志压缩带来的好处是显而易见的：首先运维频繁吐槽的网络问题没有了；其次归因转化处理的效率得到了显著地提升；最后日志占用空间小了，可以保存更长的时间，有助于问题的重现和测试。我们还利用这个日志ETL服务产出了另外一些数据，来支撑用户应用日志相关的其他业务，比如转化回传。
在这个环节我们会把前面两个环节消化的数据“发”给媒体。转化回传的作用就是将归因结果及后续的转化事件回传给媒体，帮助媒体优化广告模型，提升投放效果。
这块儿遇到的第一个问题还是如何gracefully实现不同媒体要求的各种请求格式。因为回传的数据格式较之监测复杂太多，肯定是要为相当一部分媒体编写独立逻辑的。但是也需要为回传格式相对简单的媒体提供一个统一的解决方案。为此，我们实现了一个转化回传处理引擎，通过一行配置规则就能组合出大部分的回传数据，如下是一行配置示例：
|
1 2 3 4 5 6 7 |
a_type=@retain_1day&sign=$md5($addParams($rmParams(#clk.callbackUrl,@sign),a_type=@retain_1day),#clk.openudid) 这个规则的处理说明： 1. 删除点击记录中存储的回调路径中的sign参数 2. 在回调路径中添加a_type参数，参数值为：retain_1day 3. 使用修改后的回调路径和点击中的openudid进行md5运算，作为回调签名（sign） 4. 将sign和a_type加到回调路径中 |
就这样通过配置规则与独立逻辑的组合最终实现了个性化与灵活性的统一。
回传这块儿遇到的第二个问题是在拉活回传的时候经常会出现用户日志早于点击请求到达的现象，因为我们有根据设备ID对用户日志做布隆过滤，这样就会导致相当一部分用户漏传。解决方案也相对简单：使用Kafka Consumer的pause()和resume()方法做下延迟消费就可以了——毕竟媒体对转化回传的实时性要求不强。
以上就是直投的监测归因回传三个核心模块，对应的数据流图如下：
在广告直投的业务中除了之外还有素材加工，商品库生成，报表等内容，下图是我们直投各个业务模块的一个示意：
大体上就是这样。
这篇东西在去年的这个时候就已经起好标题，并写了大概四分之一的内容——再之后就搁置起来了…
时间匆匆过去，估计很多人应该都已记不得马老师，更遑论“接化发”三字诀，幸好我还记得这个拖延了好久的计划，恰好最近也忽然多了许多时间，就趁写交接文档的时候一并完成了
前天在使用Druid完成一个新项目时遇到了查询时间错误的问题。就是日志一直在往Druid里灌，但是查近一个小时的数据怎么也查不到。经检查，日志消费情况，时间戳的填充也都是没有问题的。后来尝试将查询起始时间往前推了1天，总算查到了数据（查询时间巨长）。而且根据查询结果中的一些时间字段来看，还是有最近一个小时的记录的。这说明我的查询json是OK的，问题出在时间上。
尝试调整了几次interval时间后，确定了要把查询起止时间往前推8个小时才能查到预期的结果。8 这个数字引起了我的注意——我们通常采用的北京时间就是东八区时区时间。是不是向Druid写入日志时，把时间戳给处理成0时区时间了。赶紧和Druid管理员沟通，确定了如我猜测：如果写入的时间是时间戳格式就会被处理成0时区UTC时间。
再说下解决方案。大体有仨：
接受现状是不可能的，因为不符合个人美学。
其中第一个方案，我记得Druid官方文档是有说明的，这个应该可以改。（查了下官网，具体在JVM调优这一节）。但是不能指望运维改，毕竟在线服务都跑了好久了，贸然改了默认时区线上服务是要受影响的。
因此只剩第二个选项了。和运维沟通后，确认了虽然我之前写的是时间戳，但现在直接改成格式化后的时间也是OK的，只是会损失一些数据。最终定下了就采用这种方式。（今天试了下，不能直接改，之前写入的数据被丢弃了，运维重置了元数据才搞定）
其实还可以从其他方向考虑下，大概有两种：
第一种：使用Druid SQL来查询，查询时间仍然采用长整型时间戳,下面是一个范例：
|
1 2 3 |
select TIMESTAMP_TO_MILLIS("__time") "__time","value" from "_log" where "__time">=MILLIS_TO_TIMESTAMP(1576259650000) and "__time"<=MILLIS_TO_TIMESTAMP(1576302850000) |
另外使用Druid SQL查询时也可以在context中通过sqlTimeZone设置查询时区（知道有，但没试过）。
但是我不喜欢使用Druid SQL（有一点点性能的考虑）。PASS！
第二种：使用period Granularities，在查询时指定查询使用的时区。这个在官网有一个例子：Period Granularities。但是嫌繁琐，而且结果未必尽如人意，仍然PASS！
另外，这次我还开发了一些Druid JSON查询的工具类，如果有需要可以从GitHub拉取：zhyea / druid-explore 。代码中仅包括我现在用到的功能，后续用到了其他功能（如Filter）也会继续补充。
扯点儿闲白：这篇文我从早上就开始酝酿，但是先后出现了博客服务器问题，游戏晋级，零食，水果等种种阻碍，终于才能开始着手写，然后在半个多小时的时间内一气完成——但是完成时天色已全黑。再次感叹之前多次的感叹：小事开头难，大事坚持难。
END！！
命令行方式是一种外部配置的方式，在执行java -jar命令时可以通过 --spring.profiles.active=test的方式进行激活指定的profiles列表。
使用方式如下所示：
|
1 |
java -jar order-service-v1.0.jar --spring.profiles.active=dev |
需要添加一个名为SPRING_PROFILES_ACTIVE的环境变量。
linux环境下可以编辑环境变量配置文件/etc/profile，添加下面的一行：
|
1 2 |
# spring 环境配置 export SPRING_PROFILES_ACTIVE=dev |
windows如何配置就不多说了——不知道就自行百度。
这种方式在docker之类的环境下很有用，一次编译，环境自由切换
Java系统属性方式也是一种外部配置的方式，在执行java -jar命令时可以通过-Dspring.profiles.active=test的方式选择指定的profiles。
使用方式如下所示：
|
1 |
java -Dspring.profiles.active=dev -jar order-service-v1.0.jar |
注意：
-D方式设置Java系统属性要在-jar前定义。
配置文件方式是最常用的方式。我们只需要在application.yml配置文件添加配置即可，使用方式如下所示：
|
1 2 3 4 |
spring: profiles: # 选择的profiles active: dev |
优先级大致如下：
|
1 |
命令行方式 > Java系统属性方式 > 系统变量方式 > 配置文件方式 |
经过测试命令行方式的优先级最高，而内部配置文件方式则是最低的。
如果需要激活多个profile可以使用逗号隔开，如：
|
1 |
--spring.profiles.active=dev,test |
END！！
过去的一段时间里整理了下GoLang设计模式相关的一些内容。主要是是翻译的《All Design Patterns in Go》这个系列。因为文中有一些图片，且翻译的质量也有些不是很好，所以暂时放在博客园上，在这里仅是列个目录出来。考虑着做一些修整后再将完善一些的版本放到这里。
其实我本来不太喜欢拿设计模式说事儿的（主要是面试的一些不好经历），也有过轻模式重原则需求为中心的观点。直到去年（2022年）开始使用GoLang做一些生产上的项目，面对一门新的且极具个性的语言，一时不知道该如何着手组织代码，就顺手在搜索引擎上敲出了“Go语言 设计模式”这样的搜索条目。当意识到在做什么的时候不禁开始苦笑——属于是自己打自己脸了。
从这里开始，我觉得有必要修正下对设计模式的看法了：设计模式是一项入门阶段的基本功——毕竟是经过许多年的实践提炼出来的东西，可靠性上还是有些保证的。但是拘泥于设计模式肯定也是不可取的，在入门阶段过去后就得有点儿自己的想法了。这个过程有点儿类似倚天中张无忌学太极剑，也好像令狐冲学独孤九剑，最开始还有类似“破刀式”“破枪式”这样的固定招法，但只到领悟了“无招胜有招”才算是登堂入室。
啊啊，废话太多了。目录在下面，先凑合看一下：
先就这样吧。这个系列目前仅是个粗糙的版本，我之后会重新整理。
END！！
最近开始使用ExtJs7开发点儿小东西，其中有些配置在生产环境和测试环境是不一样的。本来想将就下，在生产和测试的时候分别改动下，但是改了几次后实在受不了了，想找个地儿统一管理下。
查了资料，在sencha论坛找到了这个帖子：Different API URL for development and Production。题主有和我相同的疑问，也得到了解答。但是美中不足的是，他们的方案只适用于extjs6.x版本。好在有方向了——可以从 app.json 文件着手，然后利用Ext.mainifest取值。
仔细看了一遍 app.json 文件，发现在这里可以发挥一下：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
/** * Settings specific to production builds. */ "production": { "output": { "appCache": { "enable": false, "path": "cache.appcache" } }, "loader": { "cache": "${build.timestamp}" }, "cache": { "enable": true }, "compressor": { "type": "yui" } }, /** * Settings specific to testing builds. */ "testing": { }, /** * Settings specific to development builds. */ "development": { "watch": { "delay": 250 } }, |
这里的注释提示可以在相应的区域分别作 生产/测试/开发 环境的配置。
我在development区域添加了host配置：
|
1 2 3 4 5 6 7 |
"development": { "watch": { "delay": 250 }, "host": "http://baidu.com" }, |
然后在Application.js中尝试读取host配置：
|
1 2 3 4 5 6 |
onBeforeLaunch: function () { alert(Ext.manifest['host']) this.callParent(); }, |
在浏览器中刷新页面，看到了预期中的输出。Over！
End！
如果想要判断一个元素是不是在一个集合里，一般想到的是将所有元素保存起来，然后通过比较确定。链表，树等等数据结构都是这种思路. 但是随着集合中元素的增加，我们需要的存储空间越来越大，检索速度也越来越慢(O(n),O(logn))。不过世界上还有一种叫作散列表（又叫哈希表，Hash table）的数据结构。它可以通过一个Hash函数将一个元素映射成一个位阵列（Bit array）中的一个点。这样一来，我们只要看看这个点是不是1就可以知道集合中有没有它了。这就是布隆过滤器的基本思想。
Hash面临的问题就是冲突。假设Hash函数是良好的，如果我们的位阵列长度为m个点，那么如果我们想将冲突率降低到例如 1%, 这个散列表就只能容纳m / 100个元素。显然这就不叫空间效率了（Space-efficient）了。解决方法也简单，就是使用多个Hash，如果检查到一个元素不在集合中，那肯定就不在。如果计算到在集合中，虽然也有一定的错误率，但是错误率还是比较低的。
以上内容来自百度百科《布隆过滤器》词条，阐述了bloomfilter的基础原理。BloomFilter常被用于需要唯一性校验的场景，如爬虫等。
java中有许多bloomfilter的实现包，最常用的还是guava中的BloomFilter。但是现在的应用多存在分布式部署的现象，本地的BloomFilter实现已经不能满足需求了，我们需要一个分布式BloomFilter实现。redis的Bitmap是实现分布式BloomFilter的一个好基础。
首先，我们需要计算一个字符串的不同Hash值的方案，这里准备了一个BloomFilterHelper类：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 |
import org.apache.commons.codec.digest.MurmurHash3; public class BloomFilterHelper { private final int bitSize; private final int numHashFunctions; public BloomFilterHelper(int expectedInsertions, double fpp) { // 计算bit数组长度 bitSize = optimalNumOfBits(expectedInsertions, fpp); // 计算hash方法执行次数 numHashFunctions = optimalNumOfHashFunctions(expectedInsertions, bitSize); } /** * 计算offset */ public int[] murmurHashOffset(String value) { int[] offset = new int[numHashFunctions]; long hash64 = hash64(value); int hash1 = (int) hash64; int hash2 = (int) (hash64 >>> 32); for (int i = 1; i <= numHashFunctions; i++) { int nextHash = hash1 + i * hash2; if (nextHash < 0) { nextHash = ~nextHash; } offset[i - 1] = nextHash % bitSize; } return offset; } /** * 计算bit数组长度 */ private int optimalNumOfBits(long n, double p) { if (p == 0) { // 设定最小期望长度 p = Double.MIN_VALUE; } return (int) (-n * Math.log(p) / (Math.log(2) * Math.log(2))); } /** * 计算hash方法执行次数 */ private int optimalNumOfHashFunctions(long n, long m) { return Math.max(1, (int) Math.round((double) m / n * Math.log(2))); } /** * 执行hash64运算 * * @param value 值 * @return hash计算结果 */ private long hash64(String value) { long[] result = MurmurHash3.hash128x64(value.getBytes()); return result[0]; } } |
BloomFilterHelper类的构造器需要传入两个参数：expectedInsertions 和 fpp。
误判率当然是越低越好，但是也意味着要为存储的数据准备更多的空间，但redis的Bitmap天然是有上限的，因此需要根据实际情况做最优设计。
另外，这里使用了commons-codec这个包来计算字符串的hash值。采用的是Murmur hash64计算。
然后是向redis的Bitmap中写入相应信息：
|
1 2 3 4 5 6 7 8 9 |
public void multiSetBit(final String key, boolean value, int... offsets) { redisTemplate.executePipelined((RedisCallback<Object>) connection -> { byte[] bytes = key.getBytes(); for (long offset : offsets) { connection.setBit(bytes, offset, value); } return null; }); } |
最后是要验证字符串对应的offset是否在Bitmap中。下面是从Bitmap中取值的代码：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
public List<Boolean> multiGetBit(String name, int... offsets) { List<Object> results = redisTemplate.executePipelined((RedisCallback<Object>) connection -> { for (long offset : offsets) { connection.getBit(name.getBytes(), offset); } return null; }); List<Boolean> list = new LinkedList<>(); results.forEach(obj -> list.add((Boolean) obj)); return list; } |
以及相应的校验代码：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
public boolean check0(String key, int[] offsets) { List<Boolean> list = redisClient.multiGetBit(key, offsets); for (Boolean b : list) { if (!b) { return false; } } return true; } public boolean checkAndSet(String value) { String key = new SimpleDateFormat("yyyyMMdd").format(new Date()); long ttl = redisClient.ttl(key, TimeUnit.MILLISECONDS); if (ttl < 0) { redisClient.expire(key, 1, TimeUnit.DAYS); } int[] offsets = bloomFilterHelper.murmurHashOffset(value); boolean r = check0(key, offsets); redisClient.multiSetBit(key, true, offsets); return r; } |
大体上就是这些内容了。
完整代码在GitHub：zhyea / springboot-redis。
End！
windows下的git bash算是最简单直接的linux命令行工具了。我平时也喜欢将之用为Jetbrains家各种IDE的terminal。
但是使用git bash时，有些习惯的linux命令，如ll，是没有的，只能使用ls -l。因此需要想办法添加alias。
步骤大致如下：
|
1 2 3 |
alias ls='ls -F --color=auto --show-control-chars' alias ll='ls -l' alias grep='grep --color' |
大致就是这样。