如何实现超高并发的无锁缓存?

一、需求缘起

【业务场景】

有一类写多读少的业务场景:大部分请求是对数据进行修改,少部分请求对数据进行读取。

例子1:滴滴打车,某个司机地理位置信息的变化(可能每几秒钟有一个修改),以及司机地理位置的读取(用户打车的时候查看某个司机的地理位置)。

void SetDriverInfo(long driver_id, DriverInfoi); // 大量请求调用修改司机信息,可能主要是GPS位置的修改

DriverInfo GetDriverInfo(long driver_id); // 少量请求查询司机信息

例子2:统计计数的变化,某个url的访问次数,用户某个行为的反作弊计数(计数值在不停的变)以及读取(只有少数时刻会读取这类数据)。

void AddCountByType(long type); // 大量增加某个类型的计数,修改比较频繁

long GetCountByType(long type); // 少量返回某个类型的计数

【底层实现】

具体到底层的实现,往往是一个Map(本质是一个定长key,定长value的缓存结构)来存储司机的信息,或者某个类型的计数。

Map<driver_id, DriverInfo>

Map<type, count>

【临界资源】

这个Map存储了所有信息,当并发读写访问时,它作为临界资源,在读写之前,一般要进行加锁操作,以司机信息存储为例:

void SetDriverInfo(long driver_id, DriverInfoinfo){
 WriteLock (m_lock);
         Map<driver_id>= info;
 UnWriteLock(m_lock);
}
DriverInfo GetDriverInfo(long driver_id){
         DriverInfo t;
 ReadLock(m_lock);
         t= Map<driver_id>;
 UnReadLock(m_lock);
         return t;
}

【并发锁瓶颈】

假设滴滴有100w司机同时在线,每个司机没5秒更新一次经纬度状态,那么每秒就有20w次写并发操作。假设滴滴日订单1000w个,平均每秒大概也有300个下单,对应到查询并发量,可能是1000级别的并发读操作。

上述实现方案没有任何问题,但在并发量很大的时候(每秒20w写,1k读),锁m_lock会成为潜在瓶颈,在这类高并发环境下写多读少的业务仓井,如何来进行优化,是本文将要讨论的问题。

二、水平切分+锁粒度优化

上文中之所以锁冲突严重,是因为所有司机都公用一把锁,锁的粒度太粗(可以认为是一个数据库的“库级别锁”),是否可能进行水平拆分(类似于数据库里的分库),把一个库锁变成多个库锁,来提高并发,降低锁冲突呢?显然是可以的,把1个Map水平切分成多个Map即可:

void SetDriverInfo(long driver_id, DriverInfoinfo){

i= driver_id % N; // 水平拆分成N份,N个Map,N个锁

WriteLock (m_lock [i]); //锁第i把锁

Map[i]<driver_id>= info; // 操作第i个Map

UnWriteLock (m_lock[i]); // 解锁第i把锁

}

每个Map的并发量(变成了1/N)和数据量都降低(变成了1/N)了,所以理论上,锁冲突会成平方指数降低。

分库之后,仍然是库锁,有没有办法变成数据库层面所谓的“行级锁”呢,难道要把x条记录变成x个Map吗,这显然是不现实的。

三、MAP变Array+最细锁粒度优化

假设driver_id是递增生成的,并且缓存的内存比较大,是可以把Map优化成Array,而不是拆分成N个Map,是有可能把锁的粒度细化到最细的(每个记录一个锁)。

void SetDriverInfo(long driver_id, DriverInfoinfo){

index= driver_id;

WriteLock (m_lock [index]); //超级大内存,一条记录一个锁,锁行锁

Array[index]= info; //driver_id就是Array下标

UnWriteLock (m_lock[index]); // 解锁行锁

}

和上一个方案相比,这个方案使得锁冲突降到了最低,但锁资源大增,在数据量非常大的情况下,一般不这么搞。数据量比较小的时候,可以一个元素一个锁的(典型的是连接池,每个连接有一个锁表示连接是否可用)。

上文中提到的另一个例子,用户操作类型计数,操作类型是有限的,即使一个type一个锁,锁的冲突也可能是很高的,还没有方法进一步提高并发呢?

四、把锁去掉,变成无锁缓存

【无锁的结果】

void AddCountByType(long type /*, int count*/){
         //不加锁
         Array[type]++; // 计数++
         //Array[type] += count; // 计数增加count
}

如果这个缓存不加锁,当然可以达到最高的并发,但是多线程对缓存中同一块定长数据进行操作时,有可能出现不一致的数据块,这个方案为了提高性能,牺牲了一致性。在读取计数时,获取到了错误的数据,是不能接受的(作为缓存,允许cache miss,却不允许读脏数据)。

【脏数据是如何产生的】

这个并发写的脏数据是如何产生的呢,详见下图:

1)线程1对缓存进行操作,对key想要写入value1

2)线程2对缓存进行操作,对key想要写入value2

3)如果不加锁,线程1和线程2对同一个定长区域进行一个并发的写操作,可能每个线程写成功一半,导致出现脏数据产生,最终的结果即不是value1也不是value2,而是一个乱七八糟的不符合预期的值value-unexpected。

【数据完整性问题】

并发写入的数据分别是value1和value2,读出的数据是value-unexpected,数据的篡改,这本质上是一个数据完整性的问题。通常如何保证数据的完整性呢?

例子1:运维如何保证,从中控机分发到上线机上的二进制没有被篡改?

回答:md5

例子2:即时通讯系统中,如何保证接受方收到的消息,就是发送方发送的消息?

回答:发送方除了发送消息本身,还要发送消息的签名,接收方收到消息后要校验签名,以确保消息是完整的,未被篡改。

当当当当 => “签名”是一种常见的保证数据完整性的常见方案。

【加上签名之后的流程】

加上签名之后,不但缓存要写入定长value本身,还要写入定长签名(例如16bitCRC校验):

1)线程1对缓存进行操作,对key想要写入value1,写入签名v1-sign

2)线程2对缓存进行操作,对key想要写入value2,写入签名v2-sign

3)如果不加锁,线程1和线程2对同一个定长区域进行一个并发的写操作,可能每个线程写成功一半,导致出现脏数据产生,最终的结果即不是value1也不是value2,而是一个乱七八糟的不符合预期的值value-unexpected,但签名,一定是v1-sign或者v2-sign中的任意一个

4)数据读取的时候,不但要取出value,还要像消息接收方收到消息一样,校验一下签名,如果发现签名不一致,缓存则返回NULL,即cache miss

当然,对应到司机地理位置,与URL访问计数的case,除了内存缓存之前,肯定需要timer对缓存中的数据定期落盘,写入数据库,如果cache miss,可以从数据库中读取数据。

五、总结

在【超高并发】,【写多读少】,【定长value】的【业务缓存】场景下:

1)可以通过水平拆分来降低锁冲突

2)可以通过Map转Array的方式来最小化锁冲突,一条记录一个锁

3)可以把锁去掉,最大化并发,但带来的数据完整性的破坏

4)可以通过签名的方式保证数据的完整性,实现无锁缓存

原文发布于微信公众号 - 架构师之路(road5858)

原文发表时间:2016-07-29

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏木东居士的专栏

从0写一个爬虫,爬取500w好友关系数据

70260
来自专栏为数不多的Android技巧

Android性能优化之虚拟机调优

介绍完 深入学习Android:虚拟机&运行时 之后,很多小伙伴问我,你描述的这些知识结构看起来艰深晦涩高大上,实际工作中能有多大用途呢?今天我就简单举个例子。

20210
来自专栏java一日一条

常用的 Python 爬虫技巧总结

用python也差不多一年多了,python应用最多的场景还是web快速开发、爬虫、自动化运维:写过简单网站、写过自动发帖脚本、写过收发邮件脚本、写过简单验证码...

12750
来自专栏屈定‘s Blog

工作--用户登录注册相关设计

最近做一个网站,网站需要用户登录注册,自然也就需要一套高扩展性的用户模块设计,该篇文章记录笔者遇到问题的解决方案,希望对你有帮助。

57750
来自专栏linux驱动个人学习

tty各种设备的情况

通常使用tty来简称各种类型的终端设备。 (1)串口端口终端(/dev/ttySn)   串行端口终端(Serial Port Terminal)是使用计算机串...

405100
来自专栏FreeBuf

对自助提卡系统的一次代码审计

并非有意愿要审计该站,前面的走的黑盒没有过于精彩部分就不在贴上了,对于此系统站你们懂的,多说无益,这套程序是开源的,像这种自助提卡系统相信大家已经不在陌生了,很...

20230
来自专栏枕边书

代码迁移之旅(二)- 渐进式迁移方案

说在前面 这是代码迁移的第二篇文章,也是最后一篇了,由于个人原因,原来的迁移我无法继续参与了,但完整的方案我已经准备好了,在测试环境也已经可以正常进行了。 上篇...

25890
来自专栏拂晓风起

kcfinder4j:java版的ckfinder、kcfinder (ajax在线文件管理,ckfinder jsp/java版, jquery 在线文件管理)

18130
来自专栏ChaMd5安全团队

blackhat议题深入 | phar反序列化

在Blackhat2018,来自Secarma的安全研究员Sam Thomas讲述了一种攻击PHP应用的新方式,利用这种方法可以在不使用unserialize(...

30230
来自专栏CDA数据分析师

总结:常用的 Python 爬虫技巧

用python也差不多一年多了,python应用最多的场景还是web快速开发、爬虫、自动化运维:写过简单网站、写过自动发帖脚本、写过收发邮件脚本、写过简单验证码...

22550

扫码关注云+社区

领取腾讯云代金券