• IntelliJ IDEA将terminal设置为git bash

    平时在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的调整。

    [阅读更多...]
  • gorm 查询总是将表名转为复数的问题

    这几天在用GoLang写个东西,期间用到了gorm框架。 在用gorm查询时遇到了一个奇怪的问题:就是这个框架会自动将model的名称转为复数形式。 先来看下具体的报错信息。这里是一个用户model: 查询语句在这里: 执行查询的时候收到了如下的错误信息: 错误信息显示查询的时候没有查预期中user表,反而是查了一个复数形式的users表。 跟踪了下gorm框架的代码,发现这里是获取表名的关键点: 关键在NamingStrategy的ns.SingularTable属性上。查了下资料后知道可以配置中设置相关的属性: 具体是在创建数据库连接时做这个配置。完整的数据库连接配置在这里: 倒数第4行代码是起点。(这是第一种方式) 后来又在gorm的文档中发现了其他两种方式: 为User model 创建一个TableName()函数,大致如下: 这是第二种方式。 在查询时临时指定表名 这是第三种方式。但是可以看出,这个方案并不好,谁有耐心在每次查询时都指定表名啊。 在gorm框架的schema.go的ParseWithSpecialTableName()方法(第123行)可以看到下面的代码: 在这段代码里可以看到设置表名的几种方式和对应的优先级。这里除我们前面提到的三种设置表名的方式外,还提示了第四种方式:通过嵌入式命名规则。可以猜测下第四种方式的使用场景:比如在需要分表的场景下这种方式还是非常便捷的。不过现在对我来说前面三种方式已经完全够用了,第四种具体如何使用我就懒得探索了… 就这样了!END!!!

    [阅读更多...]
  • 企业直投广告RTA引擎

    概述 RTA 即Realtime API的简称,是一种实时的广告程序接口,用于满足广告主实时个性化的投放需求。RTA 将流量选择权交给广告主,通常在定向环节中将用户身份的识别的请求发送给广告主,进行用户的筛选。 最近几年国内越来越重视用户隐私,许多之前用的很顺手的操作(比如上传人群包)在现在就得斟酌下了。RTA是解决这类问题的一个好方案。RTA可以在不上传人群包的情况下完成人群定向,同时可以结合产品数据进行实时调整,非常灵活。 RTA能帮广告主做到如下事情: 流量筛选 投放控制 出价干预 其中第三点需要媒体的支持。 RTA业务流程 每次⼴告请求参与竞价时, 平台携带用户信息请求⼴告主服务器, 广告主判断此次请求是否参竞,平台根据广告主返回结果进行定向流量竞投。 流程图如下: 根据上面的流程图可以看出RTA主要是在媒体的DSP或SSP接收到流量后,执行竞价逻辑前发挥作用。 RTA引擎处理流程 先来看下整体的处理流程图: 我们使用RTA对拉新和拉活的流量都有做筛选。 对于拉新只能利用请求中的信息做基础定向或者使用曝光/点击的数据进行曝光/点击频控。不过如果有采买第三方的数据,就还可以多做些事情。 对于拉活,可以基于历史数据和实时的曝光/点击/UV数据做如下事情: 基于请求中的IP/经纬度/年龄段等信息做基础定向筛选 投放频控:曝光频控,点击频控,UV频控(天/月/效果) 人群包定向 根据用户质量控制出价 再来简单说下流程图中的几个关键节点: 检查是否是有效流量:因为我们的后续判断主要是根据设备ID来做的,所以不包含有效设备ID的流量就会被视为无效流量,当然还有一些测试流量也会被标记为无效流量 提取RTA_ID:RTA_ID标识一行RTA配置,每个RTA请求中都会包含一到多个不同的RTA_ID(比如头条),如果请求中没有RTA_ID(比如百度),则取对应媒体在广告主端配置的全部RTA配置 标记实验分桶:对设备ID做Hash运算后执行求余运算进行分组,分组信息会记录在请求及响应日志中,为后续的数据计算和分析提供依据 检查配置:根据RTA_ID检查是否有做相关配置。配置数据存放在MySQL中,RTA引擎会启动一个协程每3分钟从MySQL查询全量配置保存到内存 基础定向检查:基于请求中的IP/经纬度/年龄段等信息做基础定向筛选,这一点在媒体那边也能完成,且更精准,故在这里仅做了规划,没有实现,在流程图中用深色做了标记 频控检查:根据设备ID来判断当前用户是否被做了频控。需要被频控的设备ID通过RTA引擎外部的实时任务或定时任务计算得到,频控的数据早期存放在redis缓存中,后期通过kafka将需要做频控数据发送到RTA引擎内存中 历史设备检查:通过检查是否是历史设备来决定是做拉新投放还是拉活投放。我们有维护历史设备库,仅需要根据设备ID判断该设备是否在历史设备库中就可以判断该设备是否是历史设备。历史设备库中的有效设备总量约为3.5亿,直接通过MySQL查询对MySQL数据库将是一场灾难,而把这些数据直接放在RTA引擎内存中或redis内存中也会有存储压力或查询压力,故我们在RTA引擎内部维护了一个CuckooFilter(CuckooFilter)来存储全量历史设备数据,这些历史设备数据在内存中占用的空间约为2G 人群定向检查:拉活投放不是只判断了是历史设备了就可以投放了,还有更细粒度的需求,比如针对七日人群或城市人群或指定年龄段人群进行投放,这些数据的规模一般也就是百万级,可以直接存放在Redis中 用户质量评估:头条是支持用户质量分和出价系数的,这两个信息反映了用户对 广告主的价值,通过这两者广告主可以在一定程度上干预出价。算法同学会结合已有数据计算出每个历史用户的的质量分和出价系数,并将之保存到redis中。使用时只需要根据设备ID查询获取即可。 以上就是RTA流程中的关键节点了。其它部分参考前面的流程图就行。 RTA引擎和其他服务的关系大致如下图: 遇到的问题 接下来介绍下RTA运行中遇到的各种问题及解决方案。 1. 请求规模问题 媒体一般要求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之后再来的请求就会被丢弃掉。 2. 媒体数据质量 在投放完成后还需要回收相关数据作为算法迭代的素材。这就需要将RTA收到的请求数据和后续的曝光点击数据连接起来,依据在RTA请求处理中做的实验分组进行效果对比和评估。 最开始我们做的连接是流量级别的连接,但是因为种种缘故,曝光和请求数据的连接率始终都不够好。期间也有和媒体做过多轮沟通,但是最终曝光连接率也只能提升到70%左右。 最后我们放弃了流量级别的连接,采用了宏观的分组方案,即分别在请求/曝光/点击几层按相同的逻辑进行分组计算,然后按整体比例进行统计和分析。经过实验,结果和预期还是比较匹配的。 3. 头条设备ID加密带来的问题 这个问题是由近期头条的一次升级带来的(升级的背景在这里)。 因为头条在发送的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实现不同媒体要求的各种请求格式。因为回传的数据格式较之监测复杂太多,肯定是要为相当一部分媒体编写独立逻辑的。但是也需要为回传格式相对简单的媒体提供一个统一的解决方案。为此,我们实现了一个转化回传处理引擎,通过一行配置规则就能组合出大部分的回传数据,如下是一行配置示例: 就这样通过配置规则与独立逻辑的组合最终实现了个性化与灵活性的统一。 回传这块儿遇到的第二个问题是在拉活回传的时候经常会出现用户日志早于点击请求到达的现象,因为我们有根据设备ID对用户日志做布隆过滤,这样就会导致相当一部分用户漏传。解决方案也相对简单:使用Kafka Consumer的pause()和resume()方法做下延迟消费就可以了——毕竟媒体对转化回传的实时性要求不强。 综述 以上就是直投的监测归因回传三个核心模块,对应的数据流图如下: 在广告直投的业务中除了之外还有素材加工,商品库生成,报表等内容,下图是我们直投各个业务模块的一个示意: 大体上就是这样。 其他 这篇东西在去年的这个时候就已经起好标题,并写了大概四分之一的内容——再之后就搁置起来了… 时间匆匆过去,估计很多人应该都已记不得马老师,更遑论“接化发”三字诀,幸好我还记得这个拖延了好久的计划,恰好最近也忽然多了许多时间,就趁写交接文档的时候一并完成了

    [阅读更多...]
  • Druid Json查询interval时间问题

    前天在使用Druid完成一个新项目时遇到了查询时间错误的问题。就是日志一直在往Druid里灌,但是查近一个小时的数据怎么也查不到。经检查,日志消费情况,时间戳的填充也都是没有问题的。后来尝试将查询起始时间往前推了1天,总算查到了数据(查询时间巨长)。而且根据查询结果中的一些时间字段来看,还是有最近一个小时的记录的。这说明我的查询json是OK的,问题出在时间上。 尝试调整了几次interval时间后,确定了要把查询起止时间往前推8个小时才能查到预期的结果。8 这个数字引起了我的注意——我们通常采用的北京时间就是东八区时区时间。是不是向Druid写入日志时,把时间戳给处理成0时区时间了。赶紧和Druid管理员沟通,确定了如我猜测:如果写入的时间是时间戳格式就会被处理成0时区UTC时间。 再说下解决方案。大体有仨: 调整Druid时区配置 我将日志中的时间戳(13位长整型毫秒值)改为格式化后的时间(如:2019-03-01 12:12:12)。 接受现状,查询时把时间往前推8小时 接受现状是不可能的,因为不符合个人美学。 其中第一个方案,我记得Druid官方文档是有说明的,这个应该可以改。(查了下官网,具体在JVM调优这一节)。但是不能指望运维改,毕竟在线服务都跑了好久了,贸然改了默认时区线上服务是要受影响的。 因此只剩第二个选项了。和运维沟通后,确认了虽然我之前写的是时间戳,但现在直接改成格式化后的时间也是OK的,只是会损失一些数据。最终定下了就采用这种方式。(今天试了下,不能直接改,之前写入的数据被丢弃了,运维重置了元数据才搞定) 其实还可以从其他方向考虑下,大概有两种: 第一种:使用Druid SQL来查询,查询时间仍然采用长整型时间戳,下面是一个范例: 另外使用Druid SQL查询时也可以在context中通过sqlTimeZone设置查询时区(知道有,但没试过)。 但是我不喜欢使用Druid SQL(有一点点性能的考虑)。PASS! 第二种:使用period Granularities,在查询时指定查询使用的时区。这个在官网有一个例子:Period Granularities。但是嫌繁琐,而且结果未必尽如人意,仍然PASS! 另外,这次我还开发了一些Druid JSON查询的工具类,如果有需要可以从GitHub拉取:zhyea / druid-explore 。代码中仅包括我现在用到的功能,后续用到了其他功能(如Filter)也会继续补充。 扯点儿闲白:这篇文我从早上就开始酝酿,但是先后出现了博客服务器问题,游戏晋级,零食,水果等种种阻碍,终于才能开始着手写,然后在半个多小时的时间内一气完成——但是完成时天色已全黑。再次感叹之前多次的感叹:小事开头难,大事坚持难。 END!!

    [阅读更多...]
  • springboot入门15 – profile设置

    配置方式 命令行方式 命令行方式是一种外部配置的方式,在执行java -jar命令时可以通过 –spring.profiles.active=test的方式进行激活指定的profiles列表。 使用方式如下所示: 系统变量方式 需要添加一个名为SPRING_PROFILES_ACTIVE的环境变量。 linux环境下可以编辑环境变量配置文件/etc/profile,添加下面的一行: windows如何配置就不多说了——不知道就自行百度。 这种方式在docker之类的环境下很有用,一次编译,环境自由切换 Java系统属性方式 Java系统属性方式也是一种外部配置的方式,在执行java -jar命令时可以通过-Dspring.profiles.active=test的方式选择指定的profiles。 使用方式如下所示: 注意:-D 方式设置Java系统属性要在-jar前定义。 配置文件方式 配置文件方式是最常用的方式。我们只需要在application.yml配置文件添加配置即可,使用方式如下所示: 优先级 优先级大致如下: 经过测试命令行方式的优先级最高,而内部配置文件方式则是最低的。 激活多个profile 如果需要激活多个profile可以使用逗号隔开,如: END!!

    [阅读更多...]
  • GoLang设计模式整合版

    过去的一段时间里整理了下GoLang设计模式相关的一些内容。主要是是翻译的《All Design Patterns in Go》这个系列。因为文中有一些图片,且翻译的质量也有些不是很好,所以暂时放在博客园上,在这里仅是列个目录出来。考虑着做一些修整后再将完善一些的版本放到这里。 其实我本来不太喜欢拿设计模式说事儿的(主要是面试的一些不好经历),也有过轻模式重原则需求为中心的观点。直到去年(2022年)开始使用GoLang做一些生产上的项目,面对一门新的且极具个性的语言,一时不知道该如何着手组织代码,就顺手在搜索引擎上敲出了“Go语言 设计模式”这样的搜索条目。当意识到在做什么的时候不禁开始苦笑——属于是自己打自己脸了。 从这里开始,我觉得有必要修正下对设计模式的看法了:设计模式是一项入门阶段的基本功——毕竟是经过许多年的实践提炼出来的东西,可靠性上还是有些保证的。但是拘泥于设计模式肯定也是不可取的,在入门阶段过去后就得有点儿自己的想法了。这个过程有点儿类似倚天中张无忌学太极剑,也好像令狐冲学独孤九剑,最开始还有类似“破刀式”“破枪式”这样的固定招法,但只到领悟了“无招胜有招”才算是登堂入室。 啊啊,废话太多了。目录在下面,先凑合看一下: 01. GoLang 设计模式 – 建造者模式 02. GoLang 设计模式 – 工厂模式 03. GoLang 设计模式 – 抽象工厂模式 04. GoLang 设计模式 – 单例模式 05. GoLang 设计模式 – 原型模式 06. GoLang 设计模式 – 对象池模式 07. GoLang 设计模式 – 责任链模式 08. GoLang 设计模式 – 命令模式 09. GoLang 设计模式 – 迭代器模式 10. GoLang 设计模式 – 中介者模式 11. GoLang 设计模式 – 备忘录模式 12. GoLang 设计模式 – 空对象模式 13. GoLang 设计模式 – 观察者模式 14. GoLang 设计模式 – 状态模式 15. GoLang 设计模式 – 策略模式 16. GoLang 设计模式 – 模板方法模式 17. GoLang 设计模式 – 访客模式 18. GoLang 设计模式 – 适配器模式 19. GoLang 设计模式 – 桥接模式 20. GoLang 设计模式 – 组合模式 21. GoLang 设计模式 – 装饰模式 22. GoLang 设计模式 – 门面模式 23.

    [阅读更多...]
  • ExtJs7 生产和测试环境选择不同的配置

    最近开始使用ExtJs7开发点儿小东西,其中有些配置在生产环境和测试环境是不一样的。本来想将就下,在生产和测试的时候分别改动下,但是改了几次后实在受不了了,想找个地儿统一管理下。 查了资料,在sencha论坛找到了这个帖子:Different API URL for development and Production。题主有和我相同的疑问,也得到了解答。但是美中不足的是,他们的方案只适用于extjs6.x版本。好在有方向了——可以从 app.json 文件着手,然后利用Ext.mainifest取值。 仔细看了一遍 app.json 文件,发现在这里可以发挥一下: 这里的注释提示可以在相应的区域分别作 生产/测试/开发 环境的配置。 我在development区域添加了host配置: 然后在Application.js中尝试读取host配置: 在浏览器中刷新页面,看到了预期中的输出。Over! End!

    [阅读更多...]
  • 基于redis实现分布式bloomfilter

    如果想要判断一个元素是不是在一个集合里,一般想到的是将所有元素保存起来,然后通过比较确定。链表,树等等数据结构都是这种思路. 但是随着集合中元素的增加,我们需要的存储空间越来越大,检索速度也越来越慢(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类: BloomFilterHelper类的构造器需要传入两个参数:expectedInsertions 和 fpp。 expectedInsertions : 预期写入的字符串总数 fpp :误判率 误判率当然是越低越好,但是也意味着要为存储的数据准备更多的空间,但redis的Bitmap天然是有上限的,因此需要根据实际情况做最优设计。 另外,这里使用了commons-codec这个包来计算字符串的hash值。采用的是Murmur hash64计算。 然后是向redis的Bitmap中写入相应信息: 最后是要验证字符串对应的offset是否在Bitmap中。下面是从Bitmap中取值的代码: 以及相应的校验代码: 大体上就是这些内容了。 完整代码在GitHub:zhyea / springboot-redis。 End!

    [阅读更多...]
  • Windows下git bash添加alias

    windows下的git bash算是最简单直接的linux命令行工具了。我平时也喜欢将之用为Jetbrains家各种IDE的terminal。 但是使用git bash时,有些习惯的linux命令,如ll,是没有的,只能使用ls -l。因此需要想办法添加alias。 步骤大致如下: 打开git安装目录下的etc目录(如:D:\Program Files\Git\etc) 编辑这个目录下的bash.bashrc文件 添加如下命令: 大致就是这样。

    [阅读更多...]