问题请教

[菜菜/am]

最近学习yuntable，hbase，关于compact和split操作有点不理解，
1,合并，刷入文件的数据都是经过row-key排序的，那么文件的合并，是否是将所有文件重新读入内存，然后再进行排序刷新，合并是否是将原来的文件都删除，重新生成文件
2，split，这个split是物理上的，还是逻辑上的呀，是不是将文件切分为两个，然后将其中一个transf到其他region
yuntable0.2代码学习完了，0.9好像没有涉及这个操作把，希望专家们解答下，谢谢



------------------ 原始邮件 ------------------

发件人: "吴朱华" <ike...@gmail.com>;

发送时间: 2012年6月12日(星期二) 17:45

收件人: "yuntable" <yunt...@googlegroups.com>;

主题: Re: 回复： 回复： 算法求助

你先试试，如果有问题再沟通，这里的大牛很多^_^

在 2012年6月12日 下午5:40，余露 <cool...@gmail.com>写道：

太好了，谢谢了尖头鳗。

几万行的代码量，下去研究下。

2012/6/12 尖头鳗 <lhua...@qq.com>

redis是一个内存数据结构服务器， 支持list set map hashtable 等数据结构，可以大致满足你的要求。接口丰富c、python啥都有。

------------------原始邮件------------------

发件人:"余露"<cool...@gmail.com>;

发送时间:2012年6月12日(星期二) 中午1:55

收件人:"yuntable"<yunt...@googlegroups.com>;

主题:Re: 回复： 算法求助

redis是？

我是用C写的，木有什么比较好用的神器

2012/6/12 尖头鳗 <lhua...@qq.com>

有24w商品，那每个商品的购买用户列表必然很稀疏。

用redis把你的原始数据存进来就ok了。

------------------ 原始邮件 ------------------

发件人:"周龙亭"<njdra...@gmail.com>;

发送时间:2012年6月12日(星期二) 中午1:47

收件人:"yuntable"<yunt...@googlegroups.com>;

主题:Re: 算法求助

100W的数据，全部放在内存里就行。

建两个Hash表，

1. uid --> product_id

2. product_id --> set of uid

在 2012年6月12日 下午1:42，余露 <cool...@gmail.com>写道：

我的错，忘记说明下我的问题了。

是这样的，我在实现一个推荐算法----协同过滤（CF）

数据是二元的，第一列是用户ID，第二列是用户购买过的商品ID，整个数据表明了用户和他所购买过的商品信息

我先要计算每个用户的邻居，也就是跟他购买过相同商品的人，然后通过这些邻居预测目标用户对没有购买过的商品的打分。

我的数据集中数据记录有100多万条，10000个用户，24万多商品，数据集并非数据库，可以通过普通的编辑器就能打开的文件。每条记录格式：

123 456

123 45678

123 23679

......

计算主要消耗在寻找相似用户，预测商品打分上了

我目前没有太好的数据组织方式

我的方式：

1，分别为用户和商品库建立一个链表，每个用户节点包涵了三个链表：购买过的商品，自己的邻居，推荐列表

2，通过查找不同用户和目标用户之间是否购买过相同的商品计算他们的相似度

3，找完自己的邻居后，就开始对商品库中的商品进行预测打分

用户和商品库都是通过简单的单链表进行组织，经常进行循环查找，费时的很。

吴工有啥比较好的方法吗，有好的处理工具推荐一下也好。苦思中....

余露

2012/6/12 吴朱华 <ike...@gmail.com>

很多的计算？ 主要是那些计算？

如果不知道如何使用这些数据，那么就很难选择合适的算法了

在 2012年6月12日 上午10:05，余露 <cool...@gmail.com>写道：

大家好：

大概有100多万条的数据，要经过很多的计算，让他们推荐几个算法，有名字就行呀，当然各位要是不吝啬笔墨的话，那就更谢谢啦。

真心没头绪，光自己想到的也就是用下二叉树，或者链表的形式组织数据了，没有数据库，只有数据文件

单条数据记录格式：

123 345

134 56789

........

余露

--
Cheers！
人云科技 PeopleYun.com
只有掌握和控制最核心的云计算技术，才能在这场巨大的浪潮中处于主导！！！

--
Cheers！
人云科技 PeopleYun.com
只有掌握和控制最核心的云计算技术，才能在这场巨大的浪潮中处于主导！！！

[redchen]

1,合并，刷入文件的数据都是经过row-key排序的，那么文件的合并，是否是将所有文件重新读入内存，然后再进行排序刷新，合并是否是将原来的文件都删除，重新生成文件

合并有两个目的：

1.降低文件数目，降低IO的次数，保证有足够的内存储存Meta文件

2.过滤已经被删除的数据，节约存储空间，提高查询利用率

合并不是将所有文件读入内存，而是将需要合并的文件读入内存，扫描文件，把一些已经已经被删除的row过滤掉。如有3个文件，依次为f1，f2，f9，有一段数据row1在3个文件都存在，row1在f9中已被删除。现在我要合并f1和f2，这时，是不会删除row1这段数据的，只有当合并包括f9时，这行数据才会被删除。至于怎么选取文件合并，这里面有相关的算法。

2，split，这个split是物理上的，还是逻辑上的呀，是不是将文件切分为两个，然后将其中一个transf到其他region
yuntable0.2代码学习完了，0.9好像没有涉及这个操作把，希望专家们解答下，谢谢 

分裂目的：

1.降低文件大小，便于快速载入内存，同时节约内存空间

2.可以分配这些数据到别的机器上，降低热点的产生

分裂是一个物理过程，逻辑上这些数据仍然是一张表里面的数据，所以不会有什么改变

[菜菜/am]

非常感谢你的回复～
那么像f1,f2,f9这三个文件的合并，应该是将这三个文件读入内存，然后按row排序合并，将删除的数据过滤掉，value-key里面有字段keytype表示是否删除，不知道有没有介绍这个过程的文章呀，细到代码级别的～下载了很多都是介绍下带过，hbase代码也下载了正在研究，要是有介绍看起来清晰点，谢谢


------------------ 原始邮件 ------------------

发件人: "redchen" <redch...@gmail.com>;

发送时间: 2012年6月15日(星期五) 13:54

收件人: "yuntable" <yunt...@googlegroups.com>;

抄送: "吴朱华" <ike...@gmail.com>;

主题: Re: 问题请教

[redchen]

你指yuntable吗？

应该没有这样的文章，如果你有时间，可以把这个流程写出来，给大家review一下，大家一起来维护。

[吴朱华]

呵呵，compact和split操作应该是BigTable的概念，我等一下会和大家扩展一下，谢谢redchen和菜菜的讨论.

[菜菜/am]

是的，我学习yuntable的时候不懂的就去看了一些hbase，bigtable资料，到这里比较困惑，期待您的解答，嘿嘿


------------------ 原始邮件 ------------------

发件人: "吴朱华" <ike...@gmail.com>;

发送时间: 2012年6月15日(星期五) 15:59

收件人: "redchen" <redch...@gmail.com>;

抄送: "菜菜/am" <caiha...@qq.com>;"yuntable" <yunt...@googlegroups.com>;

主题: Re: Re: 问题请教

[吴朱华]

各位：

因为YunTable在最近的一年已经有很大的不同，如果对YunTable新的进展感兴趣的话，可以关注一下这篇文章

HBase和BigTable涉及到合并，应该和菜菜的理解比较类似，而关于split，应该是这样的，每个HBase的节点有一个200MB大小的Range（负责一定的范围的），当这个Range的大小超过一个阀值，比如250MB，这个Range会在runtime的时候立刻分为两个部分，其中一个会保留现有的节点，而另一个应该会迁移到另一节点，还有在实际操作的时候，split的时间点经常由管理员在空闲时刻手动控制。