• 1. 这个标题不太好起名底下这些人像不像俺们程序员的身影?
  • 2. 写在讲故事前首先,这不是讲课,这是讲故事。这个故事里没有多高大上的背景(不要往BAT或其他土豪公司上面靠啊,跟他们没关系,这纯粹是一个屌丝程序员的故事。) 其次,这个故事里,也没打算讲多么华丽丽的技术,多么高端的名词,没有太多新东西,那些东西也太虚幻,我讲不出来。我纯粹就是讲一个程序员在写程序的过程中,遇到了一些问题,然后“想办法”解决问题的过程。 最后想说,重点其实就是在阐述一个观点,思路是解决问题的关键。 最后的最后,这个故事,跟数据有关
  • 3. 先来说说故事的背景吧好像是3月19号在群聊里讨论的一个故事,聊天记录太多找不到了。这里简要说明一下背景。 就是有一个普通的程序员,给一家普通的公司做了一个电子商务网站(电子商务不电子商务的只是打个比方,不用那么在意,反正是虚构的故事,别的行业的网站也一样)。
  • 4. 故事的起头然后呢,这个网站上线后还算不错,一年下来,差不多发展了3万左右的会员用户。既然有用户,就必然有一个用户表来存储,对吧。于是就有一张这样最基本的表来存储用户。用户id用户名称注册日期1王尼玛2010-01-022黑子2010-06-023Angelababy2010-03-124鲁鲁修2010-12-125更木剑八2010-09-29
  • 5. 业务永远会发展到预想不到随着业务的发展,用户这张表上加了不少新的字段,这个表越来越“宽”了。并且这些扩充后的字段,不是每一个用户都有值的,有些用户在有些字段上是没有值的。id用户名称注册日期邮箱手机性别出生年月地域1王尼玛2010-01-02wangnima@gmail.com男1985-2-28杭州2黑子2010-06-0218682323146男1998-1-19东京3Angelababy2010-03-12angelababy@sohu.com女1989-2-28香港4鲁鲁修2010-12-12luluxiu@abc.com18508999311男1992-6-75更木剑八2010-09-2918862900012男1950-7-31
  • 6. 贯穿故事始终的需求业务的发展,会导致越来越多的字段需要加上去,有一些是用户自己填的,有一些是后台统计出来的 (购物兴趣,月消费能力,职业) 这些字段有什么用呢? 在这里我们来假设一个很重要的业务,这个将成为我们讨论的贯穿始终的一个业务。 就是这个电商平台上的商家需要看一个非常关键的数字,就是目标人群数,以便于自己的商品能够有范围的推广。 比如: 想看华北一带(北京,天津,河北,山西)的月消费能力在5000以上的,对(男装,男鞋)感兴趣的年轻(20-30)的男性。
  • 7. 这不是NoSQL么 讲到这里,有些有经验的同学已经会大喊出“NoSQL”这个词了,对的对的,这个场景的确很像“NoSQL”呼之欲出的感觉了。 不过我已经说过,不想讲太多新的技术,包括某个“NoSQL”产品的使用方式什么的,咱们还是继续基于关系型数据库来解决。我们就假设延期数据库的成本很大,我们这位程序员同学还是继续在MySQL上想办法。
  • 8. 关系型数据库的弊端不过其实讲到这里,不得不多提一下NoSQL,NoSQL的出现恰好是应对于互联网这种“业务变化大”的情况的。互联网不像传统软件,做一套软件用几年。只要做好完善的需求调研,基本就可以确定数据模型,有了数据模型,建库建表就很简单。 互联网产品是以“快”为主,昨天刚加上的线,今天又有可能要加新业务,新业务代表新字段或者新表的产生。要解决这个问题,无“固定数据模型”的NoSQL确实能起到很大作用。 但不管哪一个NoSQL产品,一是在事务一致性上表现不太好,适合于“读多写少”,或者对“读写一致性”要求不高的场景。另外,NoSQL普遍有一个问题,就是完成批量更新或者批量删除这种业务场景时,不太适合。比如像如下的SQL update table set field1=newvalue where field='条件值' 在NoSQL里基本上是要根据'条件值'把所有符合条件的数据对象查出来,然后再根据id逐条更新。 当然这种情况在互联网领域中一般很少。
  • 9. 言归正传,我们回到刚刚的问题上来随着业务越来越庞大,产品逐渐衍生出很多垂直产品。每个产品都会对这张表有要求添加新的字段。 程序员就会想,有什么样的方法能够实现一个固定的表结构,以后不管有多少业务,都不会需要再增加字段呢? 很快,他想到了一个比较好的数据模型 : 列转行存储
  • 10. 列转行存储没用太多的花招,程序员不过是加了个这样的表而已,以实现所谓的列转行的目的。用户id属性key属性value1(王尼玛)性别男1(王尼玛)出生年月1985-2-281(王尼玛)邮箱wangnima@gmail.com2(黑子)性别男2(黑子)手机wangnima@gmail.com3(Angelababy)性别女3(Angelababy)地域香港4(鲁鲁修)性别男4(鲁鲁修)手机185089993115(更木剑八)性别男用户id用户名称注册日期1王尼玛2010-01-022黑子2010-06-023Angelababy2010-03-124鲁鲁修2010-12-125更木剑八2010-09-29
  • 11. 基本的查询查询黑子的所有的信息 select * from table where user_id = 2(黑子) 查询年龄在20-30岁的人 select * from table where key='出生年月' and year(now())-year(value) between 20 and 30 查询北京的女性 select * from table where (key='性别' and value='女') and (key='地域' and value='北京')
  • 12. 是否满足需求很明显,这个表的设计,是能够满足存储和查询统计两方面的需求的。不管是按照主键查询具体的实体信息,还是按照条件查询人数,都能够满足需求。 当然,针对key和value都需要建立索引啦。不然的话,查起来还是很慢的。(话说,这个索引可够大的,建过的同学都知道。并且建了索引之后,DML的操作,也明显会变慢的。这个以后再讨论改进吧)
  • 13. 新的问题,数据增长自从用了列转行存储后,数据的模型不会变了,业务也能基本满足。但是列转行存储的问题是,数据的行数增加得很快。那么数据的行数会怎么个增加法呢。公式很好算。 最大情况下 行= 列个数 * 元数据个数 假设有3W用户,有10个要存储的列,那么这个表就是30万数据
  • 14. 数据量增长带来的问题很快,用户数增长到了30万。而要存储的数据属性也达到了30个。虽然不是每个用户都有这么多属性要存储。但明显,这个表的数据量已经快达到了千万级(30W*30=900W)。 其实DBA一般要求mysql的单独都在百万级的,不同的硬件环境这个要求不一定完全一样,但一般不会超过500万。 很明显,这个表的数据量太大了点。既然大了,那么自然就需要拆分。
  • 15. 简单的拆分既然是用户表,那么按照用户id来拆分是最好不过的。这样一个用户的所有属性,都在一个库里。这样关于一个用户的所有增删改查操作,都不需要去考虑跨库问题了。 没错,就是sharding啦(就是Scale-out啦,基于数据库的横向扩展)。分库前分库后
  • 16. 分库后的数据存储我们假设数据库就分了4个好了,好计算。至于shareding算法嘛,就简单一点吧。按客户id取模。 DB_index = userid % 10; 这样子的话。之前的那些数据就是这样来分布的用户id用户名称shareding算法所在库1王尼玛1%4=112黑子2%4=223Angelababy3%4=334鲁鲁修4%4=005更木剑八5%4=11
  • 17. 顺带提一提更好的方法普通的取模算法,在节点数不扩展的情况下,是一种很不错的方法。但是节点一旦扩展,模值就会发生很大变化。就会导致所有节点大部分数据需要迁移。 这里想顺带提一提一致性哈希的做法。 关于一致性哈希 .... 好吧,有点长,我建议大家去网上看看相关的帖子。google或者百度都会出来很多,我就不多费唇舌了。
  • 18. 一致性哈希分库后,如果加一个库,数据需要迁移的情况用户id用户名称4个库5个库1王尼玛1%4=11%5=12黑子2%4=22%5=23Angelababy3%4=33%5=34鲁鲁修4%4=04%5=45更木剑八5%4=15%5=06匿名6%4=26%5=17匿名7%4=37%5=28匿名8%4=08%5=39匿名9%4=19%5=410匿名10%4=210%5=0111匿名101%4=3111%5=1112匿名102%4=0112%6=2258匿名258%4=2258%5=3289匿名289%4=1289%5=4用户id用户名称4个库5个库1王尼玛1%100/25=01%100/20=02黑子2%100/25=02%100/20=03Angelababy3%100/25=03%100/20=04鲁鲁修4%100/25=04%100/20=05更木剑八5%100/25=05%100/20=06匿名6%100/25=06%100/20=07匿名7%100/25=07%100/20=08匿名8%100/25=08%100/20=09匿名9%100/25=09%100/20=010匿名10%100/25=010%100/20=0111匿名111%100/25=1111%100/20=1112匿名112%100/25=1112%100/20=1258匿名258%100/25=2258%100/20=2289匿名289%100/25=3289%100/20=4
  • 19. 继续回到主题上来数据库拆分成4个之后,我们的负载能力得到了相应的4倍提高。但是我们的应用似乎略显复杂了。 难道以前我们写过的每条SQL,都还需要去算一下到底查哪个库的数据么? 当然不需要了。我们只需要做一些小小的改动即可。对程序,几乎是透明的。 这里,写一些伪代码示意吧。我说过,不打算介绍任何高大上的技术,(什么TDDL之类的啊,都不打算说) 我们不用任何开源技术,仅仅自己对程序小做改动便可完成。
  • 20. 分库前的代码public class UserDAO { private JdbcHandler jh; public void insert(User user) { jt.insert(sql, user); } }
  • 21. 分库后的代码:拦截器public class UserDAO { private JdbcHandler jh; public void insert(User user){ jt.insert(sql, user); } }//这个拦截器,是要拦截在DAO之前执行的 //其实拦截哪里都行,只要有一个统一的方式能从被拦截的参数获取userId就行 public class Interceptor{ public void invoke(Integer userId,Object param){ //在threadLocal里放入sharding值 ProxyDataSource.threadLocal.set(userId); } }
  • 22. 分库后的代码:代理数据源public Proxy DataSource implements DataSource{ Map dsMap; public static ThreadLocal threadLocal; public Conection getConnection(){ try Integer userId = threadLocal.get(); Integer db_index = getDBIndex(userId); return dsMap.get(db_index).getConnection(); }finally{ threadLocal.remove(); } } public getDBIndex(Integer userId){ return userId % dsMap.size(); } }
  • 23. 分库后的代码:bean配置
  • 24. 分库总结怎么样,分库是不是很简单? 在分库之后,更可以分表。就是在统一个库里,对表也进行同样形式的拆分,因为过亿级的数据,即便分成了10个库,单表数据也是很大的。按照单表不超过100W的标准,很多时候,我们需要对表也进行同样拆分。表名类似于[user_0001,user_0002,...,user_0100]这样的扩展开来。 不管是分库还是分表,在应用层操作数据库的原理都是在SQL执行之前,通过sharding键找到真正需要执行的库源和表名。 如果是分表的话,可能需要对SQL做解析,将逻辑表名替换成真正的物理表名,不过原理都是一样的。限于篇幅,我就不继续深入讲下去了。 不而事实上,的确存在一些高大的中间件,更不需要我们在应用层来做这些事,阿里就有很多,但是再次强调,本篇不打算介绍那些中间件。纯讲思路
  • 25. 将问题更复杂一些之前讲过的列转行存储看起来好像很万能,实际上也不是万能的。有另外一些数据虽然都是用户相关数据,但是也不可能都只存到那张列转行的表里去的。类似于购物兴趣和消费统计这样的属性(一对多),可能还是需要单独一个子表去存。表结构如下。 按常理来说,这些属性不是用户自己填的,通常是某个统计团队统计出来的数据,当然也不会是实时的,通常都是离线算好的。我们只是建了一些表来存储这些离线计算的内容。 这里可能大家就会有一些讨论了,不过我们先假设情况就是这样。userid购物兴趣黑子运动产品黑子动漫周边angelababy女装angelababy珠宝首饰userid月份消费统计(元)黑子2013125423黑子2014012312angelababy201312673812angelababy201401653321
  • 26. 程序员最开始的问题哪里去了存储貌似没有问题了,而功能呢,好像都能满足。不过,我们最开始提的问题似乎没有得到解决啊。 问题是什么来着,好像是这个。 就是这个电商平台上的商家需要看一个非常关键的数字,就是目标人群数,以便于自己的商品能够有范围的推广。 比如: 统计华北一带(北京,天津,河北,山西)的平均月消费能力在5000以上的,对(男装,男鞋)感兴趣的年轻(20-30)的男性的个数
  • 27. 跨库之后的统计哦,哦,原来是统计。 这下难倒我们的程序员了。现在数据分散在4个库上(实际情况可比4个库要多得多)。 那么要怎么才能遍历4个库的内容呢。 方法1:循环查4个库,将4个库的数据加到一起,就是总数 方法2:将数据导入到诸如hbase之类的存储上。 方法3:将数据放置于某个分布式缓存上。 不错貌似每个方法都有一些弊端,具体什么弊端呢? 我觉得大家可以想一想
  • 28. 有哪些问题呢1. 如果在数据库端统计,需要数据库做多表的join,已经avg,sum或者count等操作。让数据库去这种计算,性能影响很大。 2.每一条SQL需要遍历全DB,然后merge数据,也是影响DB性能的关键。 3.全部将数据load到缓存的话,对缓存占用资源很大。并且缓存也不支持join,count等操作。 4.做离线计算的话,比如利用hadoop,实时性就得不到保证。 上述每一种方案都能解决一个方面,于是程序元开始设计综合性的方法
  • 29. 我们的目的程序员希望做这么一个东西,既要能能支持很实时,快速的统计,又要能够替代数据的多表join操作,又不占用太大的内存。 那么,大概的想法,就是,数据还是放在某个内存级的容器中,由于是内存,所以尽量要让数据占空间少,还要能支持快速的统计。这个数据结构真值得我们好好想一想。
  • 30. 存储空间计算这样存储的话。程序员算了下,统计条件加起来大概有500个左右。那么一共需要500个bit数组。而每个bit数组的长度,都是用户总数那么长。 那么假设1G的内存大概能存多少用户呢 1,000,000,000B * 8(bit) / 500= 1600万 哈哈,看起来不错啊,单机的内存可以存储1600万用户的数据。暂时针对咱们这个30万用户的量来说,看来冗余是很够的了。
  • 31. 计算机中最小的存储单元位,没错,就是位。 bit是计算中最小的存储单元。1个bit只有两个值0:1。如果设计这么一个存储的话,做统计应该是没有问题的。性别:女1110001110101010居住地:香港居住地:北京0000010110101010居住地:香港bit数组的下标,就是userid00011100性别:男这表示userid=7的用户是一个居住在北京的女性
  • 32. java中的bit程序员翻了翻api,找到一个叫BitSet的类。看样子可以用。好吧,来编个程序试试看。我们想查统计住在北京和香港的男性。 BitSet sex_man = new BitSet(); sex_man.set(1,9);//userid[1:9]都是男性 BitSet area_beijing = new BitSet(); area_beijing.set(5);//userid=5 在北京 area_beijing.set(7);//userid=5 在北京 BitSet area_xianggang = new BitSet(); area_xianggang.set(4); //userid = 7在香港 BitSet result = (BitSet) area_beijing.clone(); result.or(area_xianggang); result.and(sex_man); System.out.println(result);//看看有哪几个用户统计结果 System.out.println(result.cardinality());//看看符合条件的总人数结果是 {4,5,6} 3
  • 33. 最终的数据结构最终的数据结构应该是这样子的 内存里应该有这么一个数据结构 Map; QueryKey就是查询条件,比如性别男,性别女,年龄20等, BitSet就是用户userid组成的bit串。符合当前条件的置1,否则置0. 统计的办法就是把所有要统计的根据QueryKey从map中get出来。 然后BitSet之间做AND,OR,XOR操作。
  • 34. 看起来有点像倒排索引其实讲到这里已经差不多了。大概的思路用比较专业的术语来表示就是将“行数据”转变成“列数据”,再具体解释下就是有点类似"倒排索引"。 不过传统意义上的“倒排索引”通常是根据key来快速查找匹配的数据集合。一般用于在搜索引擎上比较常见。用关键词做索引key,根据关键词快速定位搜索结果列表。这种倒排索引通常不能跨key去做join,做统计。 而做我们用的索引则是BitSet这样支持带AND,OR,XOR等操作的,这就相当于可以多个倒排链之间做统计了。
  • 35. 还有要考虑的问题么很多呀,其实讲到这里,都还只是思路上的问题。有很多需要考虑的。我随便举几个哈。 1. 数据什么时候load到内存中(实时load,还是离线load)? 2. BitSet在做完一次and,or等操作后,里面的bit位会发生变化,那么首先应该先clone()一个bit出来操作。这个克隆的bit也是会占用内存的。在实际计算内存的时候,要把这种临时用来计算的bit的内存考虑进去。 3. 用户量太大的情况(超过千万级),单台机器的内存可能不够用了。此时还需要做分布式。 4.大量的BitSet计算也同样费CPU资源,考虑在对热点统计做缓存。
  • 36. 简单对上述几个问题给一些基本的解答吧1. 数据什么时候load到内存中(实时load,还是离线load)? 能实时load当然就实时load了,触发load的时间可以是对DB里的user表有增删改的时候,也可以是利用数据库binlog变化这种高大上的玩意儿做监听,有变化时再改变BitSet的值。 但是像月消费水平,购物习惯这种,本身就不是实时计算的结果,当然也不可能实时变化。月消费水平这种,甚至一个月刷新一次就可以了。 注意:BitSet不是线程安全的,但是还好,一般我们这种统计不需要太精确的值,所以程序是允许有一定的误差的。
  • 37. BitSet的cloneBitSet在做完一次and,or等操作后,里面的bit位会发生变化,那么首先应该先clone()一个bit出来操作。这个克隆的bit也是会占用内存的。在实际计算内存的时候,要把这种临时用来计算的bit的内存考虑进去。 BitSet的clone操作是很快的,时间成本上不用考虑,但是存储成本不可忽视。我们假设用来做这种计算的并发最大100个(就设置这么大的线程池吧,也别太大了)。那么也就是说最多会同时克隆出100个BitSet,每个BitSet的大小假设是 10000000(bit),就是1.25MB,100个BitSet就是125M内存。
  • 38. 用户量太大的情况其实在任何一个互联网领域内,发展到最后分布式是必然的。这里已经不想再过多介绍分布式了。不过可以画个草图
  • 39. 为什么还要用缓存有人说,这个设计不是已经在内存中计算的了么,为什么还需要缓存? 设计无最好,只有更好嘛? 我们可以把热点查询条件和数值缓存起来。 缓存大概是 Cache ,Integer > 这样的结构。缓存固定只放比如10000个。多的根据LRU算法移出。 至于具体的缓存技术,也不在这里讨论了,什么memcached,redis啊,不是本篇讨论的话题。
  • 40. 总结其实说了很多无用的和基础的东西哈。 但是看这一篇,一开始为了能扩展更多的字段而不需要改数据结构,而想出了“列转行”存储这样的形式。打破了以往多个属性必须要存个多个字段这样常规的思维模式。 后来为了统计方便,又采用了倒排索引里的“行转列”思想,把数据结构完全颠倒。 一份数据,就这么行转列,列转行的玩来玩去,其实都是为了满足项目需要。 最后想说的是,工具是死的,只要去学,一定能学会。 所以这里没有讲太多某个技术或者某种工具的使用。 但人是活的,写程序重在思维模式,开拓的思维,是区分程序员最重要的品质标准(没有之一),最牛逼的程序员,是懂得把什么技术用在什么地方,而不是为了用这个技术,而用这个技术。