从数据结构比较HBase的3种memstore实现方案-低调大师

从数据结构比较HBase的3种memstore实现方案

2020-03-31 853

HBase在写入时会将数据暂存在memstore中，满足一定条件后再刷到磁盘；

其实现主要有以下要求：

既要快速读取，还要快速写入
需要有序，以方便scan
尽可能内存友好，减少gc

目前存在以下3种实现方案：

DefaultMemstore
CompactingMemstore
CCSMapMemStore

其核心的差异在于所采用的数据结构不同；

对于一个有序数据集合，通常用数组或链表的结构进行存放，二者具有如下特点：

链表：定位需要遍历，时间复杂度为O(N)，但新增不需要挪动现有元素；
数组：通过二分查找定位，时间复杂度为O(logN)，但新增麻烦，需要挪动现有元素；
对比前述要求可知，链表和数组都无法同时满足1和2；

常见的做法是给链表增加额外的索引结构，形成跳表，以空间换时间；

基于链表的跳表：给链表增加索引节点后，可通过二分查找定位，时间复杂度为O(logN)，并且新增时不需要挪动现有元素，但缺点是增加了很多节点，具体实现时意味着多了很多对象；
这个结构可满足要求中的1和2，但不满足3，Jdk中自带的ConcurrentSkipListMap就是一种实现，简称CSLM；

还有一种思路，就是把跳表的所有节点进行合并，存放到数组结构中；

基于数组的跳表：通过记录元素节点长度和其它节点位置，来体现跳表结构，即不要求数据按物理顺序存放，也可通过二分查找，还不需要太多对象；
这个结构可以很好的满足前述3点要求，那有没有什么缺点？由于节点位置都需要自己计算，对比链表跳表中的直接赋值，实现上要略微复杂一些；

阿里提供了一个这样的实现叫CompactedConcurrentSkipListMap，简称CCSM，下面是issue中的附图：

前述3种memstore所采用的数据结构如下图所示：

DefaultMemstore的实现中，active是可变的数据集，接受当前的写入操作，而snapshot是flusher线程基于之前的active生成，为不可变的数据集，这两部分都采用了Jdk自带的CSLM；

实际上由于snapshot部分不可变，不存在新增元素时需要移动现有元素的问题，所以用数组即可，可以减少跳表结构的额外节点开销，这就是CompactingMemstore的主要优化思路；

具体实现时active会比较小，大约2M左右，因此额外节点的数量就会比较少，写满后会flush成同样小的segment，然后compact等操作不停的将其转成数组结构，并合并为少量大的segment；

CCSMapMemStore则是将整个跳表实现替换掉，无论是active还是snapshot，从最大程度上减少了对象的创建，也避免了CompactingMemstore中compact带来的开销；

阿里提供的性能测试结果如下：

参考资料：
https://issues.apache.org/jira/browse/HBASE-14918
https://issues.apache.org/jira/browse/HBASE-20312
https://mp.weixin.qq.com/s/LPhfQmx0lhRayA_KQWD0-g

微信关注我们

原文链接：https://yq.aliyun.com/articles/752758

转载内容版权归作者及来源网站所有！

低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。

阿里云ECS云服务器与轻量服务器的区别及如何选择

阿里云ECS服务器提供云服务器、轻量应用服务器两种不同类型，新手初次接触云计算时，面对不同机型并不知道如何选择，容易犯选择困难症。简单的说它们的区别主要在配置和应用场景不同，本文主要讲区别及选择。 ECS云服务器、轻量应用服务器性能介绍 1、ECS云服务器 ECS云服务器不用买硬件了，所有前期准备工作都由阿里云商家完成了，甚至包括后期维护、安全防御都由阿里云来操作。让用户能便捷、高效率、更专注于自己的业务。阿里云ECS服务器的应用场景比轻量服务器要大很多，比如Web应用，高并发应用或网站，高I/O数据库，访问量较大的应用或网站，大数据及实时在线分析，机器学习和深度学习等AI应用，企业官网或企业级业务等。更多参阅官方文档 2、轻量应用服务器轻量应用服务器面向新手提供一站式服务，把一键部署应用、一键域名解析、一键网站发布、安全、运维、应用管理等服务，通通集成在一个页面里面，极大的方便了用户使用，优化了搭建网站的体验，降低了新手的入门门槛。轻量服务器可搭建小型网站、个人博客、学习环境、小型电商网站、开发环境、论坛、管理工具、代码存储、代码测试等。更多参阅官方文档 ECS云服务器、轻量应用...

2020-04-01

666

背景知识 Linux层面 linux对于文件的读取，提供了不同的函数，引用资料如下：当对同一文件句柄（在Windows下）或是文件描述符（在Linux下）进行随机读写操作时，会存在文件指针的定位与读/写俩个步骤，但由于这不是一个原子操作，就可能产生如下问题：进程A对某文件先定位到 f1 处，然后被中断，然后进程B对同一文件定位到 f2 处，然后被中断，进程A再次执行，从文件的当前指针处开始读或是写，于是这便产生了不是期望的结果了。（这里要注意，对同一文件的俩次打开，得到的将是俩个不同的句柄或是描述符，所以不用担心这种情况会出问题）解决办法：在Linux下，pread函数就好像是专门为上面的问题服务的，它本身就是原子性的操作，定位文件指针与读操作一气呵成，而且读操作并不改变文件指针。总体来说，常用的有seek()+read() 和 pread()这2种方式，优劣如下： seek()+read()非线程安全，但由于利用了文件描述符所保存的文件指针，不需要每次读取时都去定位，因此读取效率较高，应用层面多线程访问时则需要做同步； pread()是原子操作，线程安全，但由于每次都需要定位...

2020-04-01

996

资源下载

更多资源

优质分享App

近一个月的开发和优化，本站点的第一个app全新上线。该app采用极致压缩，本体才4.36MB。系统里面做了大量数据访问、缓存优化。方便用户在手机上查看文章。后续会推出HarmonyOS的适配版本。

Mario

马里奥是站在游戏界顶峰的超人气多面角色。马里奥靠吃蘑菇成长，特征是大鼻子、头戴帽子、身穿背带裤，还留着胡子。与他的双胞胎兄弟路易基一起，长年担任任天堂的招牌角色。

Spring

Spring框架（Spring Framework）是由Rod Johnson于2002年提出的开源Java企业级应用框架，旨在通过使用JavaBean替代传统EJB实现方式降低企业级编程开发的复杂性。该框架基于简单性、可测试性和松耦合性设计理念，提供核心容器、应用上下文、数据访问集成等模块，支持整合Hibernate、Struts等第三方框架，其适用范围不仅限于服务器端开发，绝大多数Java应用均可从中受益。

Sublime Text

Sublime Text具有漂亮的用户界面和强大的功能，例如代码缩略图，Python的插件，代码段等。还可自定义键绑定，菜单和工具栏。Sublime Text 的主要功能包括：拼写检查，书签，完整的 Python API ， Goto 功能，即时项目切换，多选择，多窗口等等。Sublime Text 是一个跨平台的编辑器，同时支持Windows、Linux、Mac OS X等操作系统。