短链的实现

问题的起因是这个: 这是我的刷题日志。当时是 2017.3.4 号,做了这道题之后,一直想写下是否有更好的解题思路。但是一直没(lan)有(lan)时(lan)间(lan)。 正巧今天在复习数据结构的时候看到了 LZW 压缩器。这就可以拉出来好好扯一下了。 其实现在流行的,或者网上的标准操作套路都是使用 hash 的方式,将其对应到几个短的链接上,但是因为毕竟这个属于 hash 映射,在长度变短的情况下,始终会有冲突的危险。所以也就带来了 rehash(cpu 开销和内存开销) 和 hash 表最坏情况(退化为链表结构,查找效率退化成 O(n))的风险。 比如常见的,使用 md5 摘要一把,然后将结果存到一个 hash 表中,这个 hash 表是个抽象的概念,他可以使具象化的数据库,Key-Value Store,或者仅... [阅读全文]

从一个问题开始谈秒杀业务场景

这个首先就是从一个知乎提问开始的。有一天我看到这么一个提问: 然后,排名第一的答案就是一个静态页面,一个告知用户当前访问人数过多,请稍后再试。当然,这在很多人看来都是一个笑话。不过,对于一个之前做过秒杀业务的人来说。这真的是一段非常精妙的代码,某种角度上来说,这可以解决90%的秒杀场景。不过,用户体验太差,尤其是那些看到 console 有信息就会高潮的人来说。 所以,这边就先抛砖,来讲下我对秒杀业务的理解。 对于秒杀来说,它和传统的商城系统有着本质的区别: 低廉价格 大幅推广 瞬时售空 一般是定时上架 流量时间短、瞬时并发量高 对于技术人员来说,我们其实常常会把注意力着重的放在第五点上,就是对于流量的处理。 其实,在我的观点里,初期就将全部的精力放在第五点的优化上,这并不是... [阅读全文]

第一个任务 -- 店铺爬虫

关于这个项目,首先需求比较简单.或者说单一吧.唯一要做的就是将PHP传来的任务给做完.没有多余的爬取,只需要爬取一个页面上的商品描述和商店的描述.唯一好玩的一点就是需要在一周时间内 爬取180万url左右的数据.同时还要考虑对面的防刷设置.分配给的测试资源有两台16核32G的服务器. 很显然.爬虫的关键在于VPS的分配,因为一个ip访问某个网站的频率有限制.在有限的时间,要想爬取更多的网页,就需要多个vps,要多少呢.理论上,服务器的出口带宽为1000Mb,购买的VPS带宽为2Mb, 所以,考虑充分利用带宽,则需要500个.但事实上,我们的需求并没有如此之高.在实际测试中,发现最终的瓶颈在cpu上,频繁的字符串匹配,导致了cpu的飙涨.因为考虑到之后的维护,我用了整页面的 正则进行匹配,这样,之后的修改会方便很多.所以代码里会有如下的正则表达式: 看上去很... [阅读全文]

阅读Redis源码(三) -- redis通信协议与事件驱动

在redis中,关于事件驱动框架的代码集中在ae.h/ae.c中.作者也在头部设置了介绍:a simple event-driven programming library. 这个框架其实很简单,核心就是一个消息 队列,同时只有一个线程负责对其进行处理,这里面的调度思想,还是简单的优先级队列,文件操作优先级永远高于时间操作.而且任务之间并不会进行抢占. 具体执行过程,可以参照如下干特图: time ----------------------------------------------------------------------->| |<---- 10 ms ---->|<---- 10 ms ---->|<---- 10 ms ---->|<---- 10 ms ---->| | FE 1 ... [阅读全文]

阅读Redis源码(二) -- 数据库及持久化策略

之前的一篇文章写了关于Redis的字典数据结构,但是,他并不是与我们直接交互的.因为我们在进行添加字段的时候,往往需要添加过期值,这一点我们在字典数据结构中没有能够得到体现. 所以,我们需要关注另外一个数据结构,redisDb.即Redis的数据库储存,在redis.h中,该结构体的定义如下. typedef struct redisDb { dict *dict; /* The keyspace for this DB */ dict *expires; /* Timeout of keys with a timeout set */ dict *blocking_keys; /* Keys with clients waiting for data (BLPOP) */ dict *... [阅读全文]

阅读Redis源码(一) -- 基本数据结构

调试环境搭建 下载redis源代码包,可以访问"redis"官网进行下载.这边,我使用的是2.8.13的稳定版本. 解压之后使用eclipse for c/c++导入工程,选项是依据makefile的那项. 导入之后会出现一个语法错误,但事实上,这个错误是可以乎略的.就是在热带开始redis.c的第2969行,会有如下的代码: snprintf(buf,1024*16,ascii_logo, REDIS_VERSION, redisGitSHA1(), strtol(redisGitDirty(),NULL,10) > 0, (sizeof(long) == 8) ? "64" : "32", mode, server.port, (l... [阅读全文]