分布式架构 - ID 生成器 hash 算法

在日常开发中,如果我们在设计数据库表的时候要考虑到如下内容

1、索引列和常用的字段尽量放置在一张表上
2、不常用的字段可以作为扩展字段放置在扩展表上
3、索引的优化
4、分库分表的实现
5、查询的优化

那么本章我们以用户表为例,说明一个上亿级别的用户量,如何进行拆分?如何进行查询优化?

user 表

#表结构
CREATE TABLE `users2` (
  `id` bigint(30) unsigned NOT NULL AUTO_INCREMENT,
  `member_id` char(21) CHARACTER SET utf8mb4 COLLATE utf8mb4_unicode_ci NOT NULL COMMENT '用户id',
  `username` varchar(191) CHARACTER SET utf8mb4 COLLATE utf8mb4_unicode_ci NOT NULL COMMENT '用户名',
  `password` varchar(191) CHARACTER SET utf8mb4 COLLATE utf8mb4_unicode_ci NOT NULL COMMENT '密码',
  `nickname` varchar(191) CHARACTER SET utf8mb4 COLLATE utf8mb4_unicode_ci NOT NULL COMMENT '昵称',
  `email` varchar(191) CHARACTER SET utf8mb4 COLLATE utf8mb4_unicode_ci NOT NULL,
  `id_card` timestamp NULL DEFAULT NULL COMMENT '身份证',
  `address` varchar(100) CHARACTER SET utf8mb4 COLLATE utf8mb4_unicode_ci DEFAULT NULL  COMMENT '地址',
  `versionId` int(11) NOT NULL COMMENT '版本号',
  `deleted_at` timestamp NULL DEFAULT NULL,
  `created_at` timestamp NULL DEFAULT NULL,
  `updated_at` timestamp NULL DEFAULT NULL,
  PRIMARY KEY (`id`,`member_id`) USING BTREE,
  UNIQUE KEY `users_email_unique` (`email`)
) ENGINE=InnoDB AUTO_INCREMENT=867051400 DEFAULT CHARSET=utf8mb4 COLLATE=utf8mb4_unicode_ci;

如上,我们看见一个表的结构。首先我们可以对这张表进行优化。

拆表(纵向)

不常用的字段(id_card,address,email)字段,我们完全可以单独放一张表来存储这些字段,并建立关联关系(通过user表id建立关系),在使用的时候,我们才从这张表中获取数据,姑且就叫users2_ext吧
,好处:mysql 单行数据体积减少,mysql 以row为单位,将数据load到内存buffer中,单位行越小,存储的数据越多,命中率越高。

水平拆分(横向)

水平拆分,我个人建议不仅分表同时也分库,这样可以使得,多张用户表可以位于不同的数据库上,因在不同的数据库上,后期也可以转到不同的物理机上,给单台服务器数据库减压。然后,水平拆分会带来一系列问题。

水平拆分 - 分表 - 通过Id range 区分

这种模式下,我们可以通过用户ID区间值来查询用户属于哪个分区,哪个数据库。(因拆分完后,数据新增在新的表上,老数据表仅做更新、查询、删除操作,此时的ID因没有新增将会是一个固定区间值,我们在设计新表的作为插入数据表时,要设置要auto_increment的起始值,不要和老数据表ID冲突)。

如 users1 => id (0,10000000)
users2=> id(10000000,~~)

假如我们要查询的ID为888888的用户,那么我们仅需要知道这个ID属于哪个区间,我们就去对应的数据表查询就可以了。 这种实现比较简单。

如果你是采用的第三方数据库,如阿里云的RDS 那么底层采用的是双机热备。(库1以0为开头,以2为自增键,库2以1为开头,以2为自增键,通过id%2==0 判断去库1查询还是库2查询,如果做了读写分离,那么就回去读库查询,而主从有延迟,如果一个新增的数据立刻执行了查询,那么走的是主库查询,相关算法参看官网文档)

水平拆分 - 分表 - hash 分表

hash分表我们要知道,hash在什么情况使用?是用来做什么的?业务场景如何?
业务场景:用户登录、注册 都有使用到username 这个字段,也就是说,我这张表用的最频繁的字段也是username以及id。那么hash 算法就是区解释 username 与 目标模型表之间的关系的
假设hash算法如下

//username 以a-z开头  或是A-Z开头的都映射到表users1 
hash	=>	[a-zA-Z]s	=>	user1

//username 以0-9开头的都映射到users2表
hash	=>	[0-9]				=>	users2

那么我们在进行查询的时候,我们就可以用username 用过hash算法直接找到目标数据表,并进行查询操作。

代码示例 - Hash

我以准备好示例,依赖laravel框架。需要的同学可以参考下

id采用uuid,并且不是在需要的时候才生成,而是根据一定算法,一次生成n个id存入redis队列当中,当需要数据表id时,再从redis中消费id,如果id不存在则会触发事件,该事件将会检查队列,并将id生成出来插入redis指定队列中,这里采用的redis队列为hash队列,因为hash队列采用hash算法,查询的时间复杂度为O(1)

UserIdGenerateInterface.php (模型生成器接口)

<?php


namespace AppServicesUser;

/**
 * @copyright Copyright&copy;2022,
 * Notes:用户id生成器
 * History:文件历史
 * tanyong 2022/7/11
 */
interface UserIdGenerateInterface
{
    /**
     * Notes:获得有效id
     * Author:tanyong
     * DateTime:2022/7/11
     * @param string $username 用户名
     * @return array[
     *      'model' =>  '模型',
     *      'id'    =>  '匹配id'
     * ]
     */
    public function getId(string $username);

    /**
     * Notes:生成指定模型有效id
     * Author:tanyong
     * DateTime:2022/7/11
     * @param string $model 指定模型
     * @param int $length 一次性生成长度
     * @return array $ids
     */
    public function generateIds(string $model,int $length = 1);

    /**
     * Notes:获取指定模型queue长度
     * Author:tanyong
     * DateTime:2022/7/11
     * @param string $model 指定模型
     * @return int $queueLength 队列长度
     */
    public function getModelQueueLength(string $model);

    /**
     * Notes:向指定模型的队列添加id
     * Author:tanyong
     * DateTime:2022/7/11
     * @param string $model 是否生成成功
     * @param string $id id
     * @return boolean 是否添加成功
     */
    public function addModelQueueId(string $model,string ... $ids);

    /**
     * Notes:从队列中返回一个有效id
     * Author:tanyong
     * DateTime:2022/7/12
     * @param string $queueName 队列名名称
     * @return int $id
     */
    public function popQueueId(string $queueName);

    /**
     * Notes:向队列中添加一个id
     * Author:tanyong
     * DateTime:2022/7/12
     * @param string $queueName 队列名称
     * @param int $ids 用户id
     * @return boolean 是否添加成功
     */
    public function pushQueueId(string $queueName,string ... $ids);

    /**
     * Notes:清楚缓存clearId
     * Author:tanyong
     * DateTime:2022/7/12
     * @return boolean
     */
    public function clearQueueId();

    /**
     * Notes:获得模型对应队列名称
     * Author:tanyong
     * DateTime:2022/7/11
     * @param string $model 模型名称
     * @return string 队列名称
     */
    public function getModelRelationQueueName(string $model);

    /**
     * Notes:获取关联模型 (hash 算法)
     * Author:tanyong
     * DateTime:2022/7/11
     * @param string $username 用户名
     * @return array $models 关联模型
     */
    public function hashRelationModel(string $username);

    /**
     * Notes:获得所有关联模型
     * Author:tanyong
     * DateTime:2022/7/11
     * @return mixed
     */
    public function getModels();

    /**
     * Notes:获得队列最大长度
     * Author:tanyong
     * DateTime:2022/7/12
     * @return mixed
     */
    public function getMaxQueueLength();

    /**
     * Notes:获得指定模型的库存ids
     * Author:tanyong
     * DateTime:2022/7/12
     * @param string $model
     * @return array $list
     */
    public function getQueueList(string $model);

    /**
     * Notes:获取模型
     * Author:tanyong
     * DateTime:2022/7/18
     * @param string $model 模型
     * @return array 模型信息
     */
    public function getModelInfo(string $model);
}

Id 生成器实现

<?php
/**
 * @copyright Copyright&copy;2022
 * Notes:描述该文件的用途
 * History:文件历史
 * tanyong 2022/7/11
 */

namespace AppServicesUser;

use AppComponentsUtilStringUtil;
use AppEventsRegisterUserNotGetIdEvent;
use IlluminateSupportFacadesRedis;

class UserIdGenerate implements UserIdGenerateInterface
{
    public $redis;

	//一次性生成100个id
    public $maxLength = 100;
	
	//模型组
    public $models = [];

    public function __construct()
    {
        $this->redis = Redis::connection()->client();

        $this->models = require("userGenerateConfig.php");
    }

    public function getId(string $username)
    {
        $models = $this->hashRelationModel($username);

        $randModel = $models[array_rand($models)];

        $queueName = $this->getModelRelationQueueName($randModel);

        $id = $this->popQueueId($queueName);

        if(empty($id))
        {
            //触发id生成
            $event = new RegisterUserNotGetIdEvent($this->getMaxQueueLength());
            event($event);

            return $this->getId($username);
        }

        return [
            'model' =>  $randModel,
            'id'    =>  $id
        ];
    }

    public function generateIds(string $model,int $length = 1)
    {
        $ids = [];
        for($i=1;$i<=$length;$i++)
            $ids[] = $this->create_uuid($this->getModelInfo($model)['idPrefix']);
        return $ids;
    }
	
	//uuid生成
    private function create_uuid($prefix = ""){
        return $prefix . StringUtil::randStr(6) . uniqid();
    }

    public function addModelQueueId(string $model, string ... $ids)
    {
        return $this->pushQueueId($this->getModelRelationQueueName($model), ... $ids);
    }

    public function popQueueId(string $queueName)
    {
        return $this->redis->sPop($queueName);
    }

    public function pushQueueId(string $queueName, string ... $ids)
    {
        return $this->redis->sAdd($queueName,... $ids);
    }

    public function getQueueList(string $model)
    {
        $queueName = $this->getModelRelationQueueName($model);

        return $this->redis->sMembers($queueName);
    }

    public function getModelInfo(string $model)
    {
        return $this->getModels()[$model] ?? null;
    }

    public function getModelQueueLength(string $model)
    {
        return $this->redis->sCard($this->getModelRelationQueueName($model));
    }

    public function clearQueueId()
    {

        $models = $this->getModels();

        foreach($models as $model)
        {
            $this->redis->del($this->getModelRelationQueueName($model));
        }

        return true;
    }

    public function getModelRelationQueueName(string $model)
    {
        return 'table_' . (new $model())->getTable() . "_ids";
    }

    public function hashRelationModel(string $username)
    {
        $start = substr($username,0,1);

        $targetModels = [];

        foreach($this->getModels() as $k=>$modelInfo)
        {
            if(is_string($modelInfo['regular']))
            {
                if(preg_match($modelInfo['regular'],$start))
                {
                    $targetModels[] = $k;
                }
            }else if(is_callable($modelInfo['regular']))
            {
                $result = call_user_func($modelInfo['regular'],$k,$start);

                if($result !== false)
                    $targetModels[] = $result;
            }
        }

        return $targetModels;
    }

    public function getModels()
    {
        return $this->models;
    }

    public function getMaxQueueLength()
    {
        return $this->maxLength;
    }
}

面模型配置

<?php

use AppModelsUsers;
use AppModelsUsers1;

return [
    Users::class    =>  [
        "regular"   =>   "/^[a-zA-Zs]+$/",
        "idPrefix"  =>   "a"
    ],
    Users1::class   =>  [
        "regular"   =>  "/^[0-9d]+$/",
        "idPrefix"  =>  1
    ],
    AppModelsUsers2::class    =>  [
        "regular"   =>  function($k,$value){
            if(in_array($value,['a','b','c','d','e']))
                return $k;

            return false;
        },
        'idPrefix'  =>  "b"
    ]
];

事件 及 触发器
用于当从redis队列中获取不到member_id时,将触发事件,重新生成指定(目前设置的是100个)个数的id

event

<?php

namespace AppEvents;

use IlluminateBroadcastingChannel;
use IlluminateBroadcastingInteractsWithSockets;
use IlluminateBroadcastingPresenceChannel;
use IlluminateBroadcastingPrivateChannel;
use IlluminateContractsBroadcastingShouldBroadcast;
use IlluminateFoundationEventsDispatchable;
use IlluminateQueueSerializesModels;

class RegisterUserNotGetIdEvent
{
    /**
     * Create a new event instance.
     *
     * @return void
     */
    public function __construct(
        public int $length
    )
    {}

    /**
     * Get the channels the event should broadcast on.
     *
     * @return IlluminateBroadcastingChannel|array
     */
//    public function broadcastOn()
//    {
//        return new PrivateChannel('channel-name');
//    }
}

listener

<?php

namespace AppListeners;

use AppEventsRegisterUserNotGetIdEvent;
use AppServicesUserUserIdGenerateInterface;
use IlluminateContractsQueueShouldQueue;
use IlluminateQueueInteractsWithQueue;

class RegisterUserIdListener
{
    /**
     * Create the event listener.
     *
     * @return void
     */
    public function __construct()
    {
        //
    }

    /**
     * Handle the event.
     *
     * @param  RegisterUserNotGetIdEvent  $event
     * @return void
     */
    public function handle(RegisterUserNotGetIdEvent $event)
    {
        /**
         * id 生成器
         * @var UserIdGenerateInterface $idGenerate
         */
        $idGenerate = app()->get(UserIdGenerateInterface::class);

        $models = $idGenerate->getModels();

        $limitLength = $event->length;

        foreach($models as $k=>$model)
        {
            $modelLength = $idGenerate->getModelQueueLength($k);

            if($limitLength > $modelLength)
            {
                $secLength = $limitLength - $modelLength;
                $ids = $idGenerate->generateIds($k,$secLength);
                if(!empty($ids))
                {
                    foreach($ids as $id)
                    {
                        $idGenerate->addModelQueueId($k,$id);
                    }
                }
            }
        }
    }
}

用户服务

<?php
/**
 * @copyright Copyright&copy;2022,
 * Notes:描述该文件的用途
 * History:文件历史
 * tanyong 2022/7/11
 */

namespace AppServicesUser;

use AppModelsUsers;

interface UserServiceInterface
{
    /**
     * Notes:获取用户信息
     * Author:tanyong
     * DateTime:2022/7/11
     * @param string $username 用户名
     * @return Users | null 用户信息
     */
    public function getUsernameInfo(string $username);

    /**
     * Notes:获取用户信息
     * Author:tanyong
     * DateTime:2022/7/11
     * @param int $id 用户id
     * @param string|null $targetModel 指定模型
     * @return Users | null 用户信息
     */
    public function get(int $id,string $targetModel=null);

    /**
     * Notes:用户注册
     * Author:tanyong
     * DateTime:2022/7/11
     * @param array $data
     * @return Users | null 用户信息
     */
    public function registerUser(array $data);

    /**
     * Notes:用户信息更新
     * Author:tanyong
     * DateTime:2022/7/11
     * @param string $username 用户名
     * @param array $data 要更新的数据
     * @return boolean 是否更新成功
     */
    public function update(string $username,array $data);

    /**
     * Notes:用户更新
     * Author:tanyong
     * DateTime:2022/7/11
     * @param Users $user 用户对象
     * @return boolean 是否更新成功
     */
    public function updateObj(Users $user);

    /**
     * Notes:获得模型最大id
     * Author:tanyong
     * DateTime:2022/7/12
     * @param string $model 模型
     * @return int $id
     */
    public function getUserModelMaxId(string $model);

    /**
     * Notes:根据邮箱获取用户信息
     * Author:tanyong
     * DateTime:2022/7/12
     * @param string $email 邮箱地址
     * @return Users
     */
    public function getEmailInfo(string $email);
}

用户实现
工厂设计模式:这里关于用户表CURD操作,都交由用户工厂去操作,服务本身不做具体实现。用户工厂的一些查询算法,本身会依据hash算法

<?php
/**
 * @copyright Copyright&copy;2022
 * Notes:描述该文件的用途
 * History:文件历史
 * tanyong 2022/7/11
 */

namespace AppServicesUser;

use AppExceptionsAppException;
use AppExceptionsCodes;
use AppFactorySuperFactoryInterface;
use AppFactoryUserModelFactoryInterface;
use AppModelsUsers;

class UserService implements UserServiceInterface
{
    /**
     * 用户工厂
     * @var UserModelFactoryInterface|AppFactoryModelFactoryInterface $userFactory
     */
    public UserModelFactoryInterface $userFactory;

    public function __construct(SuperFactoryInterface $superFactory)
    {
    	//从超级工厂中获取出用户工厂的实例
        $this->userFactory = $superFactory->getModelFactory('user');
    }

    public function getUsernameInfo(string $username)
    {
        return $this->userFactory->getUsernameInfo($username);
    }

    public function get(int $id,string $targetModel=null)
    {
        return $this->userFactory->get($id,$targetModel);
    }

    public function registerUser(array $data)
    {
        return $this->userFactory->registerUser($data);
    }

    public function update(string $username, array $data)
    {
        return $this->userFactory->update($username,$data);
    }

    public function updateObj(Users $user)
    {
        return $this->userFactory->updateObj($user);
    }

    public function getUserModelMaxId(string $model)
    {
        return $this->userFactory->getUserModelMaxId($model);
    }

    public function getEmailInfo(string $email)
    {
        return $this->userFactory->getEmailInfo($email);
    }
}

用户工厂

<?php


namespace AppFactory;

use AppModelsUsers;

/**
 * @copyright Copyright&copy;2022
 * Notes:用户工厂
 * History:文件历史
 * tanyong 2022/7/15
 */
interface UserModelFactoryInterface extends ModelFactoryInterface
{
    /**
     * Notes:获取用户信息
     * Author:tanyong
     * DateTime:2022/7/11
     * @param string $username 用户名
     * @return Users | null 用户信息
     */
    public function getUsernameInfo(string $username);

    /**
     * Notes:获取用户信息
     * Author:tanyong
     * DateTime:2022/7/11
     * @param int $id 用户id
     * @param string|null $targetModel 指定模型
     * @return Users | null 用户信息
     */
    public function get(int $id,string $targetModel=null);

    /**
     * Notes:用户注册
     * Author:tanyong
     * DateTime:2022/7/11
     * @param array $data
     * @return Users | null 用户信息
     */
    public function registerUser(array $data);

    /**
     * Notes:用户信息更新
     * Author:tanyong
     * DateTime:2022/7/11
     * @param string $username 用户名
     * @param array $data 要更新的数据
     * @return boolean 是否更新成功
     */
    public function update(string $username,array $data);

    /**
     * Notes:用户更新
     * Author:tanyong
     * DateTime:2022/7/11
     * @param Users $user 用户对象
     * @return boolean 是否更新成功
     */
    public function updateObj(Users $user);

    /**
     * Notes:获得模型最大id
     * Author:tanyong
     * DateTime:2022/7/12
     * @param string $model 模型
     * @return int $id
     */
    public function getUserModelMaxId(string $model);

    /**
     * Notes:根据邮箱获取用户信息
     * Author:tanyong
     * DateTime:2022/7/12
     * @param string $email 邮箱地址
     * @return Users
     */
    public function getEmailInfo(string $email);
}

<?php
/**
 * @copyright Copyright&copy;2022
 * Notes:描述该文件的用途
 * History:文件历史
 * tanyong 2022/7/15
 */

namespace AppFactory;

use AppExceptionsAppException;
use AppExceptionsCodes;
use AppModelsUsers;
use AppServicesUserUserIdGenerateInterface;

class UserFactory implements UserModelFactoryInterface
{
    public UserIdGenerateInterface $idGenerateService;

    public function __construct()
    {
        $this->idGenerateService = app()->get(UserIdGenerateInterface::class);
    }

    public function getUsernameInfo(string $username)
    {
        $models = $this->idGenerateService->hashRelationModel($username);

        foreach($models as $model)
        {
            $user = $model::query()->where('username',$username)->first();
            if(!empty($user))
                return $user;
        }

        return null;
    }

    public function get(int $id, string $targetModel = null)
    {
        if(empty($model))
        {
            foreach($this->idGenerateService->getModels() as $model)
            {
                $user = $model::query()->where('id',$id)->first();
                if(!empty($user))
                    return $user;
            }
        }else{
            return $targetModel::query()->where('id',$id)->first();
        }

        return null;
    }

    public function registerUser(array $data)
    {
        if(!isset($data['username']) || empty($data['username']))
            throw new AppException('not get username',Codes::BUSINESS_ERROR);

        $relation = $this->idGenerateService->getId($data['username']);
        if(empty($relation))
            throw new AppException('not get relation username:' . $data['username'],Codes::BUSINESS_ERROR);

        $data = array_merge($data,[
            'member_id'    =>  $relation['id']
        ]);

        return $relation['model']::create($data);
    }

    public function update(string $username, array $data)
    {
        $user = $this->getUsernameInfo($username);

        foreach ($data as $k=>$v)
            $user->{$k} = $v;

        return $this->updateObj($user);
    }

    public function updateObj(Users $user)
    {
        return $user->save();
    }

    public function getUserModelMaxId(string $model)
    {
        $id = $model::query()->max('id');

        return $id ?? 0;
    }

    public function getEmailInfo(string $email)
    {
        foreach($this->idGenerateService->getModels() as $model)
        {
            $user = $model::query()->where('email',$email)->first();
            if(!empty($user))
                return $user;
        }

        return null;
    }
}

ID雪花算法

现在的服务基本是分布式、微服务形式的,而且大数据量也导致分库分表的产生,对于水平分表就需要保证表中 id 的全局唯一性。

对于 MySQL 而言,一个表中的主键 id 一般使用自增的方式,但是如果进行水平分表之后,多个表中会生成重复的 id 值。那么如何保证水平分表后的多张表中的 id 是全局唯一性的呢?

如果还是借助数据库主键自增的形式,那么可以让不同表初始化一个不同的初始值,然后按指定的步长进行自增。例如有3张拆分表,初始主键值为1,2,3,自增步长为3。

当然也有人使用 UUID 来作为主键,但是 UUID 生成的是一个无序的字符串,对于 MySQL 推荐使用增长的数值类型值作为主键来说不适合。

也可以使用 Redis 的自增原子性来生成唯一 id,但是这种方式业内比较少用。

当然还有其他解决方案,不同互联网公司也有自己内部的实现方案。雪花算法是其中一个用于解决分布式 id 的高效方案,也是许多互联网公司在推荐使用的。

PHP扩展 - 雪花算法
https://github.com/godruoyi/php-snowflake