我正在寻找一种对字符串进行唯一约束的最佳方法。
我的用例是通过SMTP提要上的"Message-ID"answers"In-Reply-To"字段将所有电子邮件链接在一起。
然而,因为消息的数量可以增长到数百万,我们没有计划删除任何东西,我需要一种方法来快速索引它们。问题是,我的印象是字符串天生就比数字索引慢(如果我错了,请解释)。
到目前为止,我的解决方案是将消息ID转换为sha256
哈希,然后转换为8 x 32位块256位数字,如下所示:
// Its not actually written in C
struct message_id {
int32_t id;
char[255] originalMessageId;
int32_t p01;
int32_t p02;
int32_t p03;
int32_t p04;
int32_t p05;
int32_t p06;
int32_t p07;
int32_t p08;
}
然后在所有节点上设置唯一约束。
现在,在任何人谈论消息ID的唯一性质量之前,我知道,但是这个系统的设计不是为了具有高完整性,而是为了具有高性能。
我的问题是:
这就足够了,或者有一个技巧,索引字符串在MySql,我错过了吗?
编辑:添加模型设计
MessageIdentity.php
/**
* MessageIdentity
*
* @ORM'Table(name="inbox_message_identity",
* uniqueConstraints={
* @ORM'UniqueConstraint(columns={
* "p01", "p02", "p03", "p04",
* "p05", "p06", "p07", "p08"
* })
* })
* @ORM'Entity(repositoryClass="AppBundle'Entity'Inbox'MessageIdentityRepository")
*/
class MessageIdentity
{
/**
* @var integer
*
* @ORM'Column(name="id", type="integer")
* @ORM'Id
* @ORM'GeneratedValue(strategy="AUTO")
*/
private $id;
/**
* @var string
*
* @ORM'Column(name="originalMessageId", type="string", length=255)
*/
private $originalMessageId;
/**
* @var integer
*
* @ORM'Column(name="p01", type="integer")
*/
private $p01;
/**
* @var integer
*
* @ORM'Column(name="p02", type="integer")
*/
private $p02;
/**
* @var integer
*
* @ORM'Column(name="p03", type="integer")
*/
private $p03;
/**
* @var integer
*
* @ORM'Column(name="p04", type="integer")
*/
private $p04;
/**
* @var integer
*
* @ORM'Column(name="p05", type="integer")
*/
private $p05;
/**
* @var integer
*
* @ORM'Column(name="p06", type="integer")
*/
private $p06;
/**
* @var integer
*
* @ORM'Column(name="p07", type="integer")
*/
private $p07;
/**
* @var integer
*
* @ORM'Column(name="p08", type="integer")
*/
private $p08;
/**
* @param $string
*/
public function __construct($string)
{
parent::__construct();
$bits = self::createBits($this->originalMessageId = $string);
$this->p01 = $bits[0];
$this->p02 = $bits[1];
$this->p03 = $bits[2];
$this->p04 = $bits[3];
$this->p05 = $bits[4];
$this->p06 = $bits[5];
$this->p07 = $bits[6];
$this->p08 = $bits[7];
}
public static function createBits($string)
{
$hash = hash('sha256', $string);
$bits = array();
// Bits are packed in pairs of 16 bit chunks before unpacking as signed 32 bit chunks
// in order to guarrentee there is no overflow when converting the unsigned hex number into a
// PHP integer on 32 bit machines.
$bits[] = self::pluck(unpack('l', pack('s', hexdec(substr($hash, 0, 4))) . pack('s', hexdec(substr($hash, 4, 4)))));
$bits[] = self::pluck(unpack('l', pack('s', hexdec(substr($hash, 8, 4))) . pack('s', hexdec(substr($hash, 12, 4)))));
$bits[] = self::pluck(unpack('l', pack('s', hexdec(substr($hash, 16, 4))) . pack('s', hexdec(substr($hash, 20, 4)))));
$bits[] = self::pluck(unpack('l', pack('s', hexdec(substr($hash, 24, 4))) . pack('s', hexdec(substr($hash, 28, 4)))));
$bits[] = self::pluck(unpack('l', pack('s', hexdec(substr($hash, 32, 4))) . pack('s', hexdec(substr($hash, 36, 4)))));
$bits[] = self::pluck(unpack('l', pack('s', hexdec(substr($hash, 40, 4))) . pack('s', hexdec(substr($hash, 44, 4)))));
$bits[] = self::pluck(unpack('l', pack('s', hexdec(substr($hash, 48, 4))) . pack('s', hexdec(substr($hash, 52, 4)))));
$bits[] = self::pluck(unpack('l', pack('s', hexdec(substr($hash, 56, 4))) . pack('s', hexdec(substr($hash, 60, 4)))));
return $bits;
}
protected static function pluck($array)
{
return $array[1];
}
}
MessageIdentityRepository.php
class MessageIdentityRepository extends 'Doctrine'ORM'EntityRepository
{
public function getExisting($string)
{
$bits = MessageIdentity::createBits($string);
$qb = $this->createQueryBuilder('i');
$qb
->where($qb->expr()->andX(
$qb->expr()->eq('i.p01', $qb->expr()->literal($bits[0])),
$qb->expr()->eq('i.p02', $qb->expr()->literal($bits[1])),
$qb->expr()->eq('i.p03', $qb->expr()->literal($bits[2])),
$qb->expr()->eq('i.p04', $qb->expr()->literal($bits[3])),
$qb->expr()->eq('i.p05', $qb->expr()->literal($bits[4])),
$qb->expr()->eq('i.p06', $qb->expr()->literal($bits[5])),
$qb->expr()->eq('i.p07', $qb->expr()->literal($bits[6])),
$qb->expr()->eq('i.p08', $qb->expr()->literal($bits[7]))
))
->setMaxResults(1)
;
return $qb->getQuery()->getOneOrNullResult();
}
}
MessageRepository.php
class MessageRepository extends 'Doctrine'ORM'EntityRepository
{
public function getLastWithMessageID(MessageIdentity $messageIdentity)
{
$qb = $this->createQueryBuilder('m');
$qb
->where('m.messageIdentity = :identity')
->setParameter(':identity', $messageIdentity)
->orderBy('m.date', 'DESC')
->setMaxResults(1)
;
return $qb->getQuery()->getOneOrNullResult();
}
}
这是一个使用Doctrine2构建的模型。消息本身持有MessageIdentity
表的外键。
MessageIdentity
通过重构位集来搜索,并且搜索应该完全利用表上的唯一约束的所有列。
根据映射的标识搜索消息,按降序排列日期,并且只获取单行。
你在解决一个根本不存在的问题。
当然比较两个字符串比比较两个INTs
要慢一些。但还不够慢,不足以保证用MD5/SHA1等站在你的头上。所有这些开销会比字符串比较更慢。
另一方面,如果您计划拥有一个长度超过767字节的唯一字符串,则需要做一些事情。如果是这样的话,我将讨论一些解决办法。
同时,我认为SHA256是过分的。对于128位MD5,"在包含9万亿个字符串的表中,有9万亿分之一的机会出现错误重复。"就"百万"而言,几率就更小了。
另一个点…BINARY(20)
和CHAR(20) COLLATE ..._bin
的处理方式相同。更复杂的排序需要付出一些的努力。
附录
背景:基本上MySQL中唯一的索引类型是b树。这是一个有序列表。对于"点查询"(给定一个键,查找记录),它也非常有效。对于InnoDB, b树块是16KB的块。对于一百万行,b树将大约 3层深度。1万亿——6.
SHA256/UUID/GUID/其他摘要——当你有非常多的行时,所有这些都表现得很糟糕。这是因为它们非常随机,在非常大的表的情况下,您不太可能将所需的块缓存在RAM中。
这是一个折衷的解决方案,以一个人工表为例:
CREATE TABLE foo (
in_reply_to VARCHAR(500) NOT NULL CHARACTER SET ...,
...
KEY(in_reply_to(20))
PRIMARY KEY (...)
) ENGINE=InnoDB;
SELECT ... FROM foo
WHERE in_reply_to = '...';
请注意,我没有sha256或其他摘要。
KEY(in_reply_to(20))
用该字段的前20个字符建立索引。UNIQUE(in_reply_to(20))
也会这样做,但也限制20个字符是唯一的。这是不是你想要的。
下面是我的SELECT
的工作原理:
- 查找该键,找到1或2或可能匹配前20个字符的几行。
- 验证整个
in_reply_to
与搜索字符串完全匹配。 - 发送结果集
选择"20"作为一个很好的折衷
- 足够长,通常是唯一的
- 足够短,以保持键的b树小。(更小->更多可缓存->更快)。
你可能已经注意到一件事缺失——MySQL没有做唯一性检查;你的代码将不得不通过执行我的SELECT
的一些变体来做到这一点。
SHA256有256位,所以它需要BINARY(32)
。即使有1e25个不同的文档,仍然有大约1e25分之一的机会存在虚假副本。