Browsed by
分类: 数据库

Cuckoo Filter:设计与实现

Cuckoo Filter:设计与实现

(感谢网友 @我的上铺叫路遥 投稿)

对于海量数据处理业务,我们通常需要一个索引数据结构,用来帮助查询,快速判断数据记录是否存在,这种数据结构通常又叫过滤器(filter)。考虑这样一个场景,上网的时候需要在浏览器上输入URL,这时浏览器需要去判断这是否一个恶意的网站,它将对本地缓存的成千上万的URL索引进行过滤,如果不存在,就放行,如果(可能)存在,则向远程服务端发起验证请求,并回馈客户端给出警告。

索引的存储又分为有序和无序,前者使用关联式容器,比如B树,后者使用哈希算法。这两类算法各有优劣:比如,关联式容器时间复杂度稳定O(logN),且支持范围查询;又比如哈希算法的查询、增删都比较快O(1),但这是在理想状态下的情形,遇到碰撞严重的情况,哈希算法的时间复杂度会退化到O(n)。因此,选择一个好的哈希算法是很重要的。

时下一个非常流行的哈希索引结构就是bloom filter,它类似于bitmap这样的hashset,所以空间利用率很高。其独特的地方在于它使用多个哈希函数来避免哈希碰撞,如图所示(来源wikipedia),bit数组初始化为全0,插入x时,x被3个哈希函数分别映射到3个不同的bit位上并置1,查询x时,只有被这3个函数映射到的bit位全部是1才能说明x可能存在,但凡至少出现一个0表示x肯定不存在。

Bloom_filter

阅读全文 Read More

好烂啊有点差凑合看看还不错很精彩 (52 人打了分,平均分: 4.13 )
Loading...
性能调优攻略

性能调优攻略

关于性能优化这是一个比较大的话题,在《由12306.cn谈谈网站性能技术》中我从业务和设计上说过一些可用的技术以及那些技术的优缺点,今天,想从一些技术细节上谈谈性能优化,主要是一些代码级别的技术和方法。本文的东西是我的一些经验和知识,并不一定全对,希望大家指正和补充

在开始这篇文章之前,大家可以移步去看一下酷壳以前发表的《代码优化概要》,这篇文章基本上告诉你——要进行优化,先得找到性能瓶颈! 但是在讲如何定位系统性能瓶劲之前,请让我讲一下系统性能的定义和测试,因为没有这两件事,后面的定位和优化无从谈起。

一、系统性能定义

让我们先来说说如何什么是系统性能。这个定义非常关键,如果我们不清楚什么是系统性能,那么我们将无法定位之。我见过很多朋友会觉得这很容易,但是仔细一问,其实他们并没有一个比较系统的方法,所以,在这里我想告诉大家如何系统地来定位性能。 总体来说,系统性能就是两个事:

  1. Throughput ,吞吐量。也就是每秒钟可以处理的请求数,任务数。
  2. Latency, 系统延迟。也就是系统在处理一个请求或一个任务时的延迟。

一般来说,一个系统的性能受到这两个条件的约束,缺一不可。比如,我的系统可以顶得住一百万的并发,但是系统的延迟是2分钟以上,那么,这个一百万的负载毫无意义。系统延迟很短,但是吞吐量很低,同样没有意义。所以,一个好的系统的性能测试必然受到这两个条件的同时作用。 有经验的朋友一定知道,这两个东西的一些关系:

  • Throughput越大,Latency会越差。因为请求量过大,系统太繁忙,所以响应速度自然会低。
  • Latency越好,能支持的Throughput就会越高。因为Latency短说明处理速度快,于是就可以处理更多的请求。

二、系统性能测试

经过上述的说明,我们知道要测试系统的性能,需要我们收集系统的Throughput和Latency这两个值。

阅读全文 Read More

好烂啊有点差凑合看看还不错很精彩 (52 人打了分,平均分: 4.27 )
Loading...
NoSQL 数据建模技术

NoSQL 数据建模技术

全文译自墙外文章“NoSQL Data Modeling Techniques”,译得不好,还请见谅。这篇文章看完之后,你可能会对NoSQL的数据结构会有些感觉。我的感觉是,关系型数据库想把一致性,完整性,索引,CRUD都干好,NoSQL只干某一种事,但是牺牲了很多别的东西。总体来说,我觉得NoSQL更适合做Cache。下面是正文——

NoSQL 数据库经常被用作很多非功能性的地方,如,扩展性,性能和一致性的地方。这些NoSQL的特性在理论和实践中都正在被大众广泛地研究着,研究的热点正是那些和性能分布式相关的非功能性的东西,我们都知道 CAP 理论被很好地应用于了 NoSQL 系统中(陈皓注:CAP即,一致性(Consistency), 可用性(Availability), 分区容忍性(Partition tolerance),在分布式系统中,这三个要素最多只能同时实现两个,而NoSQL一般放弃的是一致性)。但在另一方面,NoSQL的数据建模技术却因为缺乏像关系型数据库那样的基础理论没有被世人很好地研究。这篇文章从数据建模方面对NoSQL家族进行了比较,并讨论几个常见的数据建模技术。

要开始讨论数据建模技术,我们不得不或多或少地先系统地看一下NoSQL数据模型的成长的趋势,以此我们可以了解一些他们内在的联系。下图是NoSQL家族的进化图,我们可以看到这样的进化:Key-Value时代,BigTable时代,Document时代,全文搜索时代,和Graph数据库时代:(陈皓注:注意图中SQL说的那句话,NoSQL再这样发展下去就是SQL了,哈哈。)


NoSQL Data Models

首先,我们需要注意的是SQL和关系型数据模型已存在了很长的时间,这种面向用户的自然性意味着:

阅读全文 Read More

好烂啊有点差凑合看看还不错很精彩 (17 人打了分,平均分: 3.76 )
Loading...
千万别用MongoDB?真的吗?!

千万别用MongoDB?真的吗?!

某人发了一篇Don’t use MongoDB的血泪控诉,我把原文翻译如下,你可以看看。不过,我想我们还要去看看10gen CTO的对此事的回复,我们还要去在Reddit上看看大家的说法,10gen CTO的对此事的回复后面也有一堆人在讨论这个事,还有一些程序员开始去读MongoDB的源码了,呵呵。看样子,说MongoDB的这些事并不是真的。

10gen CTO 对此事的并不完全知道,其在回复,对些文中的每一条都做了回复。我把其回复的大体意思也放在原文中。不过,很有意思的是那些程序员的讨论。建议大家看看。

正文

因为各种政治原因,我这段时间没有说什么,但是现在我觉得因为要对社会负责,所以我要阻止大家不要把你们的业务放在MongoDB上。

我的团队在一个有巨大用户量(一个有千万用户级的大型的公司)系统上使用的MongoDB,这个系统上让MongoDB有非常大的负载。早期,我们以为使用MongoDB会像10gen公司(MongoDB背后的公司)宣扬其在长期性能扩展有很多好处。但是,我们错了,而这个rant(长篇抱怨)就是为了让你不要相信那些所谓的成功经验而和我们一样犯了大错。如果有人能避免你上当,那么就得我写这么多。希望能警醒更多的人。

注意,对于和10gen打交道的经历来说,他们给予了我们充分了热情和帮助,而且非常地好。但是这并不能成为我不告诉大家他们的产品失败的理由。

阅读全文 Read More

好烂啊有点差凑合看看还不错很精彩 (21 人打了分,平均分: 3.57 )
Loading...
图解SQL的Join

图解SQL的Join

对于SQL的Join,在学习起来可能是比较乱的。我们知道,SQL的Join语法有很多inner的,有outer的,有left的,有时候,对于Select出来的结果集是什么样子有点不是很清楚。Coding Horror上有一篇文章(实在不清楚为什么Coding Horror也被墙)通过 文氏图 Venn diagrams 解释了SQL的Join。我觉得清楚易懂,转过来。

假设我们有两张表。

  • Table A 是左边的表。
  • Table B 是右边的表。

其各有四条记录,其中有两条记录是相同的,如下所示:

id name       id  name
-- ----       --  ----
1  Pirate     1   Rutabaga
2  Monkey     2   Pirate
3  Ninja      3   Darth Vader
4  Spaghetti  4   Ninja

下面让我们来看看不同的Join会产生什么样的结果。

阅读全文 Read More

好烂啊有点差凑合看看还不错很精彩 (28 人打了分,平均分: 4.39 )
Loading...
6个有用的MySQL语句

6个有用的MySQL语句

以前本站给大家介绍过《MySQL性能优化的最佳20+条经验》,今天给大家介绍六条比较有用的MySQL的SQL语句,可能很多人都通过PHP来实现这些功能。

1. 计算年数

你想通过生日来计算这个人有几岁了。


SELECT DATE_FORMAT(FROM_DAYS(TO_DAYS(now()) - TO_DAYS(@dateofbirth)), '%Y') + 0;

2. 两个时间的差

取得两个 datetime 值的差。假设 dt1 和 dt2 是 datetime 类型,其格式为 ‘yyyy-mm-dd hh:mm:ss’,那么它们之间所差的秒数为:


UNIX_TIMESTAMP( dt2 ) - UNIX_TIMESTAMP( dt1 )

除以60就是所差的分钟数,除以3600就是所差的小时数,再除以24就是所差的天数。

3. 显示某一列出现过N次的值


SELECT id
FROM tbl
GROUP BY id
HAVING COUNT(*) = N;

阅读全文 Read More

好烂啊有点差凑合看看还不错很精彩 (11 人打了分,平均分: 2.73 )
Loading...
五个免费开源的数据挖掘软件

五个免费开源的数据挖掘软件

在网上看到一篇文章介绍五个免费开源的数据挖掘软件,转过来。

Orange

Orange 是一个基于组件的数据挖掘和机器学习软件套装,它的功能即友好,又很强大,快速而又多功能的可视化编程前端,以便浏览数据分析和可视化,基绑定了Python以进行脚本开发。它包含了完整的一系列的组件以进行数据预处理,并提供了数据帐目,过渡,建模,模式评估和勘探的功能。其由C++ 和 Python开发,它的图形库是由跨平台的Qt框架开发。

RapidMiner

RapidMiner, 以前叫 YALE (Yet Another Learning Environment), 其是一个给机器学习和数据挖掘和分析的试验环境,同时用于研究了真实世界数据挖掘。它提供的实验由大量的算子组成,而这些算子由详细的XML 文件记录,并被RapidMiner图形化的用户接口表现出来。RapidMiner为主要的机器学习过程提供了超过500算子,并且,其结合了学习方案和Weka学习环境的属性评估器。它是一个独立的工具可以用来做数据分析,同样也是一个数据挖掘引擎可以用来集成到你的产品中。

阅读全文 Read More

好烂啊有点差凑合看看还不错很精彩 (11 人打了分,平均分: 2.91 )
Loading...
MySQL性能优化的最佳20+条经验

MySQL性能优化的最佳20+条经验

今天,数据库的操作越来越成为整个应用的性能瓶颈了,这点对于Web应用尤其明显。关于数据库的性能,这并不只是DBA才需要担心的事,而这更是我们程序员需要去关注的事情。当我们去设计数据库表结构,对操作数据库时(尤其是查表时的SQL语句),我们都需要注意数据操作的性能。这里,我们不会讲过多的SQL语句的优化,而只是针对MySQL这一Web应用最多的数据库。希望下面的这些优化技巧对你有用。

1. 为查询缓存优化你的查询

大多数的MySQL服务器都开启了查询缓存。这是提高性最有效的方法之一,而且这是被MySQL的数据库引擎处理的。当有很多相同的查询被执行了多次的时候,这些查询结果会被放到一个缓存中,这样,后续的相同的查询就不用操作表而直接访问缓存结果了。

这里最主要的问题是,对于程序员来说,这个事情是很容易被忽略的。因为,我们某些查询语句会让MySQL不使用缓存。请看下面的示例:

// 查询缓存不开启
$r = mysql_query("SELECT username FROM user WHERE signup_date >= CURDATE()");

// 开启查询缓存
$today = date("Y-m-d");
$r = mysql_query("SELECT username FROM user WHERE signup_date >= '$today'");

上面两条SQL语句的差别就是 CURDATE() ,MySQL的查询缓存对这个函数不起作用。所以,像 NOW() 和 RAND() 或是其它的诸如此类的SQL函数都不会开启查询缓存,因为这些函数的返回是会不定的易变的。所以,你所需要的就是用一个变量来代替MySQL的函数,从而开启缓存。

阅读全文 Read More

好烂啊有点差凑合看看还不错很精彩 (68 人打了分,平均分: 4.43 )
Loading...
如何比较两个数据表

如何比较两个数据表

有些时候,我们可能想要比较一下两个数据表,以找到其中不同的数据。比如,在进行数据移植的时候,或是在合并数据的时候,或是在比对验证数据的时候。当然比较两个表,需要这两个表结构是一样的。

我们先假设一下有如下表结构:

CREATE TABLE jajal
(
    user_id integer NOT NULL,
    first_name character varying(255),
    last_name character varying(255),
    grade character(1),
    CONSTRAINT jajal_pkey PRIMARY KEY (user_id)
)

阅读全文 Read More

好烂啊有点差凑合看看还不错很精彩 (7 人打了分,平均分: 3.29 )
Loading...