AntDB-M高性能设计之hash索引动态rehash

AntDB-M支持hash索引、btree索引等索引类型,hash索引以hash表的方式实现,一个简单的hash表示意图如图1所示。hash桶下的元素节点为单向或者双向链表,数据行上某一个或者某几个字段组成索引,通过hash函数对索引字段的值进行运算,映射到某个hash桶下,hash桶下的元素节点存储了数据行的行号。

        图1:hash table原理示意图

当使用 select * from table where a = value; 进行查询时,先根据value计算hash值,算出在第几个hash桶,然后遍历hash桶下的元素,根据存储的行号,取出每一行a列存储的值,与value进行比对,若完全相等,则就是要找的行。

以hash桶下的节点为双向链表举例,桶下的元素节点结构一般为

struct node{        uint8            oid;   // 数据行行号或者其它含义的value        node *    node_prev;  // 上一个节点        node *    node_next;  // 下一个节点}

sizeof(node)总共 8+8+8 =24个字节;

对于AntDB-M来讲,内存是非常宝贵的资源,在实现hash索引且保证性能的前提下,内存占用必须尽量小。对于数据库里的某张表,假设表总共有m行,表上有n个hash索引,则这张表就有n套hash结构,每套hash结构有m个桶节点,以上述双向链表为例,这张表的hash索引占用的内存为 n*(hash索引头节点占用内存 + m*24字节),24个字节有时甚至比数据表中这行数据本身还要大。

AntDB-M hash索引数据结构优化

为了减少索引数据的内存占用,AntDB-M使用数组元素来模拟链表节点,不再额外分配空间存储链表节点的值。一次性分配所有的节点,避免频繁的内存分配释放。

struct array_node{uint8   prev_oid;   // 上一个节点的位置uint8   next_oid;   // 下一个节点的位置}

sizeof(array_node)总共 8+8 =16个字节,oid为0代表上一个、下一个节点为空,即本节点的前面或者后面没有其它节点了。对于某张有n行数据的数据表,申请分配数组空间array_node[n],对于数组中的某个元素array_node[k],k有两个含义:

  • 数组中的下标,用于访问array_node[k]. prev_oid和array_node[k]. next_oid;

  • array_node[k]指向数据库此表中的第k行,可以去访问这张表第k行的内容。这样就避免存储了uint8 oid(数据行行号),节省了1/3的内存空间;如果hash桶下的节点是单向链表,则节省了2/3的内存。

下面举例说明:

假设一张数据表初始建表时预分配了m行,则对应的hash结构的bucket个数为n(n在实现时为大于m的最小素数),对应hash索引的桶节点数组预分配n个元素,即uint8 bucket_head[n], bucket_head记录每个桶的头节点指向第几行(也代表指向数组array_node的第几个元素);分配连续数组array_node[m], 对应于bucket下面双向链接的节点元素。

假设对于某个hash索引, 数据表的第3行,第29行,第36815行都映射到桶2下,则桶2的头结点指向表上的第3行数据, 也指向array_node的第3个元素。

bucket_head[2]=3;array_node [3] ->prev_oid=0;          array_node [3] -> next_oid=29;array_node [29] ->prev_oid=3;               array_node [29] ->next_oid=36815;array_node [36815] ->prev_oid=29;array_node [36815] ->next_oid=0;

这样,同样做到了前后的遍历(next_oid=0表示这是链表上的最后一个有效元素),相比前一种方式,通过数组来模拟链表,内存占用减少,并且数组的内存是一次性分配出来,内存连续,访问速度快。

随着业务的运行,数据表的规模可能不断地扩大,比如一张表刚创建时预分配1000万行,运行一段时间后扩展到5000万行,如果hash结构的bucket个数还是1000万左右,则每个bucket下面的平均有5个元素,hash冲突增大,查找效率降低。此时,我们需要对数据进行rehash,动态调整hash结构,减少hash冲突,同时又不阻塞hash table的增删改查。

AntDB-M 动态rehash原理

如图2所示,每个hash桶下面都有一把桶锁lock,当读取、插入、删除桶下元素时,需要对桶加锁。migrate_node指示当前正在迁移的bucket,具体迁移某个bucket时,也是先对bucket加桶锁,迁移完bucket下面的所有元素后释放桶锁,然后migrate_node再指向下一个bucket.

1. 每当表的数据行增加一定数量时,新建一个新的hash_table结构,此时新老两套hash_table并存;

2. 遍历老的hash_table, 从第一个桶开始,加桶锁,遍历桶下面的每一个元素,计算它在新的hash_table上的位置,迁移插入到新的hash_table结构;

3. 所有桶的元素迁移完成之后,释放老的hash_table结构,数据的增删改查完全切换到新的hash_table;

图2:AntDB-M动态rehash示意图

为何动态rehash的过程不阻塞hash table的增删改查,本文以查找和插入举例,用流程图的方式说明如下。更新(分解为查找+删除+插入)和删除的流程也是类似的,不管是查找,插入、更新、删除,都要先在老的hash结构上查找数据位于哪个bucket下面。

图3:动态rehash过程中的find

图4:动态rehash过程中的insert

性能优势

表扩容时动态扩展hash结构,不阻塞AntDB-M服务及应用,对用户透明。AntDB-M内部通过增加hash桶个数和迁移桶下元素,减少hash冲突,使得hash索引性能不因数据行的增多而降低,快速定位数据。

综上所述,hash索引巧妙设计的数据结构,以及动态rehash的并行算法使得AntDB-M的hash索引具备持续高性能的特性,以满足复杂业务应用的性能需求。

关于AntDB数据库

AntDB数据库始于2008年,是亚信科技自主研发的分布式关系型数据库品牌,AntDB-M是面向高性能内存型数据库,是AntDB的子产品之一,在运营商的核心系统上,为全国24个省份的10亿多用户提供在线服务,具备高性能、弹性扩展、高可靠等产品特性,峰值每秒可处理百万笔通信核心交易,保障系统持续稳定运行近15年,并在通信、金融、交通、能源、物联网等行业成功商用落地。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/127794.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

移动机器人选择源头厂家有什么优势

在现代工业和服务领域,移动机器人应用日益广泛,广泛应用于汽车制造、电子组装、物流仓储等领域。在选择移动机器人时,选择源头厂家具有许多优势,下面将详细介绍这些优势。 一、品质保证 源头厂家的机器人经过严格的生产流程和质…

“最强”机器学习辅助!利用自然语言让机器人更好地理解开放性世界

原创 | 文 BFT机器人 想象一下,你正在国外拜访朋友,打开他的冰箱看看有没有能够制作一顿美味早餐的食材。最初,冰箱里的许多物品对你来说都很陌生,每个物品的包装都是你不熟悉的。你开始试图理解每个物品的用途,并根据…

Avalonia播放视频(mp4)

1.Nuget添加类库Dove.Avalonia.Extensions.Media,项目路径https://github.com/michael-eddy/Avalonia.Extensions/ 2.Nuget添加VideoLAN.LibVLC.Windows PlatformLibVLC PackageMinimum OS VersionWindowsVideoLAN.LibVLC.WindowsWindows XPUWPVideoLAN.LibVLC.UW…

【Mysql】联表查询

目录 表: 思路: inner join right join left join ​编辑 表: student表 class表 思路: 1.分析查找的字段来自哪些表 2.确定使用哪种连接查询 3.确定交叉点 比如student表的name与class表的name是相等的 inner join …

python 把函数的值赋给变量

嗨喽~大家好呀,这里是魔王呐 ❤ ~! python更多源码/资料/解答/教程等 点击此处跳转文末名片免费获取 一个是模块的调用和一个自定义函数返回值赋值给变量 编写一个简单的函数模块: def run(name): list1 hello namereturn list1编写一个调用的脚…

YOLOv5 - common.py文件解读

🍨 本文为[🔗365天深度学习训练营学习记录博客 🍦 参考文章:365天深度学习训练营 🍖 原作者:[K同学啊 | 接辅导、项目定制](https://mtyjkh.blog.csdn.net/) 🚀 文章来源:[K同学的学…

el-table实现单选和隐藏全选框和回显数据

0 效果 1 单选 <el-table ref"clientTableRef" selection-change"clientChangeHandle"><el-table-column fixed type"selection" width"50" align"center" /><el-table-column label"客户名称" a…

Python进行多线程爬取数据通用模板

首先&#xff0c;我们需要导入所需的库&#xff0c;包括requests和BeautifulSoup。requests库用于发送HTTP请求&#xff0c;BeautifulSoup库用于解析HTML文档。 import requests from bs4 import BeautifulSoup然后&#xff0c;我们需要定义一个函数来发送HTTP请求并返回响应。…

C# 异步日志记录类,方便下次使用,不用重复造轮子

先定义接口类&#xff1a; using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks;namespace 异常 {internal interface ILog{Task WriteErrorLog(string message);Task WriteInfoLog(string message);Task W…

python实现FINS协议的TCP服务端(篇一)

python实现FINS协议的TCP服务端是一件稍微麻烦点的事情。它不像modbusTCP那样&#xff0c;可以使用现成的pymodbus模块去实现。但是&#xff0c;我们可以根据协议帧进行组包&#xff0c;自己去实现帧的格式&#xff0c;而这一切可以基于socket模块。本文为第一篇。 一、了解FI…

MATLAB绘图中文显示为方框

MATLAB绘图中文显示为方框 MATLAB显示英文和字母没有问题&#xff0c;但是当显示中文时会显示乱码&#xff0c;中文显示为方框&#xff0c;如下图&#xff1a; 可以在绘图命令中添加如下代码&#xff1a; set(gca,Fontname,Monospaced); 例如&#xff1a; % 滤波器系数%低通…

【EI会议征稿】第三届能源动力与控制工程国际学术会议(EPECE 2024)

第三届能源动力与控制工程国际学术会议&#xff08;EPECE 2024&#xff09; The 3rd International Conference on Energy and Power Engineering, Control Engineering (EPECE 2024) 第三届能源动力与控制工程国际学术会议&#xff08;EPECE 2024&#xff09;将于2024年2月2…

卫星遥感·格物致知丨卫星遥感的力量——自然灾害监测的太空之眼—洪涝灾害监测

遥感卫星从太空感知地球和获取地球表面的信息&#xff0c;当前有上千颗遥感卫星每天不停的对地表成像&#xff0c;其数据广泛用于地球系统科学研究、资源环境管理、国土安全和自然灾害监测等领域。卫星遥感的优势有监测范围大、不受区域地形限制、重复观测和多种类型数据(感知多…

MySQL -- 事务管理

MySQL – 事务管理 文章目录 MySQL -- 事务管理一、理解事务1.如果CURD不加控制&#xff0c;会有什么问题2.事务的概念 二、MySQL中的事务1.事务的版本支持2.事务提交方式3.事务常见操作方式3.1.事务的开始与回滚3.2.证明未commit&#xff0c;客户端崩溃&#xff0c;MySQL自动会…

Vite - 配置 - 不同的环境执行不同的配置文件

目标描述 通过不同的命令&#xff0c;执行不同的环境的配置文件中的内容&#xff1a; npm run dev : 执行开发环境的配置文件 npm run build: 执行生产环境的配置文件 环境文件准备 为了在不同的环境中使用不同的配置文件&#xff0c;我们将配置文件拆分开来。 开发环境使用开发…

【优选算法系列】【专题五位运算】第二节.371. 两整数之和and137. 只出现一次的数字 II

文章目录 前言一、两整数之和 1.1 题目描述 1.2 题目解析 1.2.1 算法原理 1.2.2 代码编写二、只出现一次的数字 II 2.1 题目描述 2.2 题目解析 2.2.1 算法原理 2.2.2 代码编写总结 前言 一、两整数之和 …

采集Prestashop独立站采集Prestashop独立站

import java.net.URL 这一行导入了Java.net包中的URL类&#xff0c;这个类在处理URL链接时非常有用。 import org.jsoup.Jsoup 这一行导入了Jsoup库&#xff0c;它是一个强大的HTML和XML文档解析库&#xff0c;我们可以使用它来解析网页内容。 import org.jsoup.nodes.Docume…

显卡服务器租用价格受哪些因素影响

显卡服务器也叫做GPU服务器&#xff0c;是一种有高性能显卡的服务器系统&#xff0c;显卡服务器能在大数据处理、科学计算等领域有很好的性能表现。今天小编就给大家讲一讲显卡服务器租用价格受哪些因素影响呢&#xff1f; 1.显卡类型和数量&#xff1a;一般说来中高端显卡的租…

pytorch搭建squeezenet网络的整套工程(升级版)

上一篇当中&#xff0c;使用pytorch搭建了一个squeezenet&#xff0c;效果还行。但是偶然间发现了一个稍微改动的版本&#xff0c;拿来测试一下发现效果会更好&#xff0c;大概网络结构还是没有变&#xff0c;还是如下的第二个版本&#xff1a; 具体看网络结构代码&#xff1a…

编译内核源码

本文将记录内核源码编译步骤&#xff0c;供有需要的人参考使用。 一、内核源码下载网址 内核源码网址&#xff1a;https://kernel.org/ 二、准备编译环境 这里需要注意区分x86架构和arm架构&#xff0c;需要不同的架构内核就准备对应的服务器即可&#xff0c;在服务器上安装…