Skynet

---------- ---------- 我的新 blog : liukaiyi.cublog.cn ---------- ----------

BlogJava :: 首页 :: 联系 :: 聚合

:: 管理

112 Posts :: 1 Stories :: 49 Comments :: 0 Trackbacks

常用链接

留言簿(13)

我参与的团队

随笔分类

随笔档案

相册

搜索

阅读排行榜

评论排行榜

跟我一起学 - 算法导论 - 插入排序

算法导论 - 算法入门 ,一小节（插入排序,复杂度）

#  插入排序                -         复杂度
def insertion_sort(arr):             # 1
    for j in xrange( 1,len(arr) ):   # n-1
        key = arr[j]                 # n-1
        i=j-1                        # n-1
        while i>=0 and arr[i]> key : # n(n-1)/2
            arr[i+1] = arr[i]        # n(n-1)/2
            i=i-1                    # n(n-1)/2
        arr[i+1] = key               # n-1
        print arr                    # n-1

验证结果 :
>>> arr=[5,2,4,6,1,3]
>>> insertion_sort(arr)
[2, 5, 4, 6, 1, 3]
[2, 4, 5, 6, 1, 3]
[2, 4, 5, 6, 1, 3]
[1, 2, 4, 5, 6, 3]
[1, 2, 3, 4, 5, 6]

验证复杂度：
z = 5(n-1)+1+3n(n-1)/2
我们测试数据为 n=6
当数据极端情况就是需要全部重新排列
就是 [6,5,4,3,2,1] 要排出 [1,2,3,4,5,6] 这样
>> z = 71

一种比较笨的验证方法供大家拍砖 :

def insertion_sort(arr):
    ii=0
    ii+=1
    for j in xrange( 1,len(arr) ):
        ii+=1

        key = arr[j]
        ii+=1

        i=j-1
        ii+=1

        while i>=0 and arr[i]> key :
            ii+=1

            arr[i+1] = arr[i]
            ii+=1

            i=i-1
            ii+=1

        arr[i+1] = key
        ii+=1

        print arr
        ii+=1

    print "----",str(ii)

>>> arr=[6,5,4,3,2,1]
>>> insertion_sort(arr)
[5, 6, 4, 3, 2, 1]
[4, 5, 6, 3, 2, 1]
[3, 4, 5, 6, 2, 1]
[2, 3, 4, 5, 6, 1]
[1, 2, 3, 4, 5, 6]
---- 71 #复杂度验证为 71

罗嗦下 n(n-1)/2
极端情况下
i=1 ; j 需要挪动 1次
i=2 ; j 挪动 1+2次
i=3 ; j 挪动 1+2+3次
....
i=n ; j 挪动 1+2....+n

我们又找到 (1+n)+(2+n-1)+(3+n-2).... = (1+n)n/2
我们这的 i 是从 2 次开始的也就是说 (n-1)n/2 了

def tn(ii):
    ti=0
    for i in xrange(ii) :
        for j in xrange(i) :
            ti+=1
    print ti

print tn(2)  #1 = 1
print tn(3)  #3 = 1+2
print tn(4)  #6 = 1+2+3
..

posted @ 2009-11-18 23:29 刘凯毅阅读(1663) | 评论 (0) | 编辑收藏

算法复杂度分析图

发现自己写个小程序 - 文本存储二叉结构的hashMap。那个费劲！痛下决心仔细学习算法。
（如果大家有兴趣就跟我一起 - 《算法导论》，也望大家监督我能每天拿出一小时和大家分享算法,算法代码我会尽量使用 py 和解决一些分析日志的应用上靠（其实，上面费劲的 二叉hash 是为了分析日志中 - 希望能实现多个大文件不需要合并就能根据某列排序输出! 目前的解决办法 find .. -exec cat {} \; | perl |sort 的笨方法）

1. 算法在计算中的作用（笔记） :
   算法(algorithm):就是定义良好的计算过程，它取一个或一组作为输出，并产生一个或一组自作为输出。

一些函数运行级别 # http://www.wolframalpha.com/ 函数都可在网站里运行
这里 n=一亿条数据 :
log_2(n)     30
n^0.5        31622
n            10^9
n*log_2(n)   2.9^10
n^2          10^18
n^3          10^27
2^n          无穷
n!           10^362880

需要知道的复杂度 - 在某一个临界点后合并会别插入要快的
插入排序复杂度 n^2    http://www.wolframalpha.com/input/?i=n^2
合并排序复杂度 n*log_2(n) http://www.wolframalpha.com/input/?i=n*log_2%28n%29+

网上的查找到的一些名称：参考 http://www.51testing.com/?uid-130868-action-viewspace-itemid-66729
1.1稳定排序非稳定排序 -
稳定排序是所有相等的数经过某种排序方法后，仍能保持它们在排序之前的相对次序，。反之，就是非稳定的排序。
1.2内排序外排序
在排序过程中，所有需要排序的数都在内存，并在内存中调整它们的存储顺序，称为内排序；在排序过程中，只有部分数被调入内存，并借助内存调整数在外存中的存放顺序排序方法称为外排序。
1.3算法的时间复杂度空间复杂度
所谓算法的时间复杂度，是指执行算法所需要的计算工作量。一个算法的空间复杂度，一般是指执行这个算法所需要的内存空间。

几种常见的算法复杂度：
2.1冒泡排序（Bubble Sort）    O(n^2)
2.2选择排序（Selection Sort） O(n^2 )
2.3插入排序（Insertion Sort） O(n^2)
2.4堆排序    O( nlog(n) )
2.5归并排序 O( nlog_2(n) )
2.6快速排序最好 O( nlog_2(n) ) 最坏 O(n^2)

wiki 参考：http://zh.wikipedia.org/wiki/%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95
穩定的

冒泡排序（bubble sort） — O(n²)
雞尾酒排序 (Cocktail sort, 雙向的冒泡排序) — O(n²)
插入排序（insertion sort）— O(n²)
桶排序（bucket sort）— O(n); 需要 O(k) 額外空間
計數排序 (counting sort) — O(n+k); 需要 O(n+k) 額外空間
合併排序（merge sort）— O(n log n); 需要 O(n) 額外空間
原地合併排序 — O(n²)
二叉排序樹排序（Binary tree sort） — O(n log n)期望時間; O(n²)最壞時間; 需要 O(n) 額外空間
鴿巢排序 (Pigeonhole sort) — O(n+k); 需要 O(k) 額外空間
基數排序（radix sort）— O(n·k); 需要 O(n) 額外空間
Gnome sort — O(n²)
Library sort — O(n log n) with high probability, 需要 (1+ε)n 額外空間

[編輯] 不穩定

選擇排序（selection sort）— O(n²)
希爾排序（shell sort）— O(n log n) 如果使用最佳的現在版本
Comb sort — O(n log n)
堆排序（heapsort）— O(n log n)
Smoothsort — O(n log n)
快速排序（quicksort）— O(n log n) 期望時間, O(n²) 最壞情況; 對於大的、亂數串列一般相信是最快的已知排序
Introsort — O(n log n)
Patience sorting — O(n log n + k) 最壞情況時間，需要額外的 O(n + k) 空間，也需要找到最長的遞增子序列（longest increasing subsequence）

[編輯] 不實用的排序演算法

Bogo排序 — O(n × n!) 期望時間，無窮的最壞情況。
Stupid sort — O(n³); 遞迴版本需要 O(n²) 額外記憶體
Bead sort — O(n) or O(√n), 但需要特別的硬體
Pancake sorting — O(n), 但需要特別的硬體

posted @ 2009-11-17 23:12 刘凯毅阅读(2502) | 评论 (0) | 编辑收藏

perl 使用小结

环境设置：如果有系统字符编码冲突，在当前
vim ~/.bash_profile 下加入
LANG=zh_CN
LC_ALL=zh_CN.UTF8
export LANG LC_ALL

字符编码转化:
  # 由decode解析,默认会使用系统编码输出
  # 在 linux 下面其实等价 encode("UTF-8", decode("GBK",$_));
perl -MEncode -ne 'print decode("GBK",$_);'  file.txt

判断数据是否符合输出：
  echo "121" |perl -ne 'print if /2/;'   #print 123

匹配正则group输出:
  echo "abc121a" |perl -ne 'print $1 if /(\D+)/;'   #print abc

大小写转化：
  # 全部大小转小写
  echo "ABC1C2cGJ" |perl -ne 'tr/[A-Z]/[a-z]/; print ;'  #print
  # "L 中间全部小写 "E   ; "U 中间全部大写 "E    ↓
  echo "ABC1C2cGJ" |perl -ne 's/(.*?1)(.*?)(2.*?)/$1\L$2\E$3/g; print ;'  #print ABC1c2cGJ

源文件替换：
   echo "ABC 123" > te
   sed -i 's/ABC/abc/g' te
       或者 : perl -i -pe 's/ABC/abc/g' te
   cat te # print abc 123

外部传参:
tt="cc"
echo "gg" |perl -ne ' print "'$tt'" ;'
输出：cc

  perl -e  'print "$ARGV[0]\t$ARGV[1]\n" '  'par1' 'par2'  #print par1 par2

重复列输出:
   cat xx.txt | awk -F"    " 'a[$1]++'
   或者 :
   cat xx.txt |perl -F"\t" -ane  '$a{$F[1]}++;END{
        while(($k,$v)=each(%a)){ print "$k = $v "n"; }
    }'
    结果比如：
       百度手机在线 = 7
       中兴 = 2
       万信恒通  = 2
   还比如：查看各用户有多少个进程
   ps -ef |perl  -ane  '$a{$F[0]}++;END{
      while(($k,$v)=each(%a)){ print "$k = $v \n"; }
   }'

求两项  交集
cat BuyMusic.20090525| perl -ne 'BEGIN{
$p1="600902000005416300";
$p2="600902000006211983";
$p_col=30;
$mob_col=0;

}END{
  my @inter = grep {$a{$_}} keys %b; # 求交集
  #print $p1,"=",join(",",keys %a),""n";
  #print $p2,"=",join(",",keys %b),""n";
  print "产品 $p1:",scalar keys %a," "n";
  print "产品 $p2:",scalar keys %b," "n";
  print "交集:",scalar @inter," "n";
}
chomp;
@lis=split /\|<>\|/ ;
if( $lis[ $p_col] eq $p1 ){
   $a{$lis[$mob_col]}++;
}
if( $lis[$p_col] eq $p2 ){
   $b{$lis[$mob_col]}++;
}
'

关键字 Top 10 ，输出源文本数据 :
perl -e  '
  my $num=10; # top 10
  open(MYFILE, "<$ARGV[0]");
  open(MYFILE2, "<$ARGV[0]");

  # 关键字列数
  while(<MYFILE>){@lis=split /\|<>\|/;$fck{$lis[1]}++ }

  foreach $k (sort { $fck{$b} <=> $fck{$a} } keys %fck){
     if(++$row>$num){last; }
     $arr[@arr] = $k;
  }

  while(<MYFILE2>){@lis=split /\|<>\|/;
     if(grep { $arr[$_] eq $lis[1] } 0..$#arr){
       # print "$fck{$lis[1]}:$_"; #带关键字出现次数输出
       print ;
     }
  }
' qdSearch.log

posted @ 2009-11-11 13:36 刘凯毅阅读(2039) | 评论 (0) | 编辑收藏

mysql 序列号生成器(转)

如果你不想使用mysql的自动递增，但又想实现主键序列号的功能，可以使用下面的方法，通过函数用一张表去维护生成多个表的序列号，简单又实用

1.创建生成多个表的序列号的数据维护表

CREATE TABLE seq (
name varchar(20) NOT NULL,
val int(10) UNSIGNED NOT NULL,
PRIMARY KEY (name)
) ENGINE=MyISAM DEFAULT CHARSET=UTF-8

2.插入几条初始化数据

INSERT INTO seq VALUES('one',100);
INSERT INTO seq VALUES('two',1000);

3.创建函数以生成序列号

CREATE FUNCTION seq(seq_name char (20)) returns int
begin
UPDATE seq SET val=last_insert_id(val+1) WHERE name=seq_name;
RETURN last_insert_id();
end

4.测试

mysql> SELECT seq('one'),seq('two'),seq('one'),seq('one');
+------------+------------+------------+------------+
| seq('one') | seq('two') | seq('one') | seq('one') |
+------------+------------+------------+------------+
| 102 | 1002 | 103 | 104 |
+------------+------------+------------+------------+
1 row IN SET (0.00 sec)

posted @ 2009-11-10 15:51 刘凯毅阅读(3535) | 评论 (1) | 编辑收藏

算法公式 - 图形化

在定制数学公式的时候可能希望有个直观的展现

http://www.wolframalpha.com/

我们前一段时间用到的 { 推荐分值 90 天递减公式，如果这东西早发现公式就不会错了！}

目前我们递减的公式

y=-x/90+1

在比如我们优化下 90天改成

(y*10)^2=-x+90

2009-11-05

posted @ 2009-11-05 13:09 刘凯毅阅读(1492) | 评论 (1) | 编辑收藏

文件存储 - 数据结构( py )

虽然 mysql,oracle 和 Berkeley DB，sqlite3 等数据库已经很好
但是当我初略学习下数据挖掘方面的一些知识发现，关系数据库远远不够来存储，查询 etl 后的数据

比如：我希望原始日志数据进行某一字段的排序,是不是很简单。
有人说 - 数据导入数据库 load into table ... ， select order by 。之
还有人说 - linux sort -n...

恩！很好，下面我们对大小为 1TB 的数据开始进行这个简单的操作   -- 傻眼了！！
   关于挖掘 - TB 级别的数量在我目前学习挖掘不到半年，就遇到过3-4次之多

解决办法:
对于这个问题 - 我现在希望能有个大的链表 - （大到内存装不下），
链表中的struct 结构为 :
   >> 排序属性文件归属
   >> 排序属性整条数据在文件中的起始位置 - 结束位置
   >> 在排序中的排位（链表结构,只记入比自己小的属性在此链表的位置）

比如 :
1. 文件1内容 =>

说明:
完整数据描述 : 此数据在文件中的起始位置（当然是通过程序取得的，这为了方便我标出）
..c

. 0 - 22
..a

. 23 - 55
..b

. 56- 76
..d

. 77 - 130
..f

. 131 - 220
..e

. 221 - 243

2. 数据结构预开空间 100 byte
3. 文件存储在描述 : # 链表排序我就不介绍了，数据结构的最基本技能，修改数据结构中的比自己小的指向
      我这就给出结果
{ /tmp/文件1, 0-22 , 300 }   #说明 c ：在链表位置 0
{ /tmp/文件1, 23-55 , 200 }       # a ： 100
{ /tmp/文件1, 56-76 , 0 }     # b : 200
{ /tmp/文件1, 77-130 , 500 } # d : 300
{ /tmp/文件1, 131-220 , } # f : 400
{ /tmp/文件1, 221-243 , 400 } # e : 500

4. 倒叙输出由小到到
     假设预存最小为 200 链表位置
     找出使用 open /tmp/文件1
       并使用 seek 文件游标定位 23-55 取出 ..a...
   根据链表中 200 到 seek 56 76 取出 ..b...
   等等

当然上面
数据结构你可以使用双向链表， btree , 红黑 , 斐波那契。。。（数据结构终于感觉有用了，不枉费我考的软证啊！）

通过说明，我这给大家提供个可能需要的技术细节 (py),不足之处欢迎拍砖！！

1. 二进制文件结构化写，修改

#指定修改 190 byte 处的内容
import os
from struct import *
fd = os.open( "pack1.txt", os.O_RDWR|os.O_CREAT )

ss = pack('ii11s', 3, 4, 'google')
os.lseek(fs, len(ss)*10, 0)
os.write(fs,ss)
os.fsync(fs)

#os.close( fs )

2. seek 指定位置结构化读取

from struct import *
file_object = open('pack1.txt', 'rb')

def ts(si,ss=len(ss)):
    file_object.seek(si*ss)
    chunk = file_object.read(ss)
    a,b,c=unpack('ii11s', chunk )
    print a,b,c

ts(10)
#输出 3 4 google

1. 其他语言的使用
struct 结构定义 ,在 python 中使用 struct 包，这样序列出来的数据到文件中其他语言也可以使用
参考: http://www.pythonid.com/bbs/archiver/?tid-285.html

pack1.py
from struct import *

# i 为 int（4） 11s 为预留 11 位置的 string
# 此数据类型为 19 byte ss = pack('ii11s', 1, 2, 'hello world')

f = open("pack1.txt", "wb")
f.write(ss)
f.close()

上面的代码往C的结构中写入数据，结构包括两个整型和一个字符串。
pack1.c
#include <stdio.h>
#include <string.h>

struct AA
{
    int a;
    int b;
    char    c[64];
};

int main()
{
    struct AA   aa;
    FILE    *fp;
    int     size, readsize;

    memset(&aa, 0, sizeof(struct AA));

    fp = fopen("pack1.txt", "rb");
    if (NULL == fp) {
        printf("open file error!"n");
        return 0;
    }

    readsize = sizeof(struct AA);
    printf("readsize: %d"n", readsize);

    size = fread(&aa, 1, readsize, fp);
    printf("read: %d"n", size);
    printf("a=%d, b=%d, c=%s"n", aa.a, aa.b, aa.c);

    fclose(fp);

    return 0;
}

结果输出:
C:"Documents and Settings"lky"桌面"dataStructure>a
readsize: 72
read: 57
a=1, b=2, c=hello word

最后罗嗦下：
能用数据结构了，很多东西都可以根据自己逻辑定制存储很方便。不再受关系数据库 , key 数据库或 mapreduce 的限制

参考:
http://docs.python.org/library/struct.html#module-struct #官方struct 包说明
http://blog.csdn.net/JGood/archive/2009/06/22/4290158.aspx # 使用 struct 的前辈留下的
http://www.tutorialspoint.com/python/os_lseek.htm #一个小demo
Python天天美味(17) - open读写文件

posted @ 2009-11-04 15:16 刘凯毅阅读(2100) | 评论 (0) | 编辑收藏

数据挖掘流程简介

我们这就是有企业挖掘中最常用的《流失用户分析》来说明：

数据挖掘流程:
1. 定义主题：天啊，我在干什么！（此模块绝大多数主观意识上完成，有少量客观验证）
1.1 明确主题用户在各用户群中的分布 - 流失用户在各用户群中比例
    不同客户群的流失程度如：某渠道，某软件版本,页面布局，功能等主观上去分析。
    尽量把影响流失比较大的因素详细罗列出来如：概率分布，页面布局变化影响等
1.2 明确主题用户特征 - 流失用户特征
     对流失用户影响比较大的字段如：金额，软件版本（缺少最需要的功能）,客服对问题的处理的时间

2. 数据选择：什么样的选民，选出什么样的总统！
   在此模块中有个比较难把握的地方：维度越高越能准确的定义数据，但也会越复杂度。
   你大概不会希望花3天分析出2天前的流失用户吧！！ :)
   2.1 分区收集
       在用户流失分析中，若采集时间过长，可能在流失判断出来时客户已然流失；若采集时间过于紧密或者实时采集则需要考虑运营商现有系统的支撑能力。因此对数据采集时间间隔的设置显得尤为重要。
   2.2 减少数据噪音
   2.3 剔除部分冗余数据
       此间要注意的是在客户流失分析上，从数据仓库中采集数据的主要目的是调查客户信息的变化情况。一些不必要的数据就去除掉吧

3. 分析数据 : 热身，很重要！
   3.1 数据抽样
       多说了，在这信息爆炸的时代，别说你把上百TB的数据放到应用分析库中去！
   3.2 数据转换
       比如时间方面：可以把上午转换为 1 ，中午转换为 2 等等.便于分析
   3.3 缺损数据处理
   3.4 样本生成
        建模样本:为下个阶段准备
        测试样本：对模型进行修正和检验

4. 模型建立 : 找个合得来的过这一辈子吧！
对数据进行分析并利用各种数据挖掘技术和方法在多个可供选择的模型中找出最佳模型,这个过程是一个循环迭代的过程.
建立模型通常由数据分析专家配合业务专家来完成
4.1 常用的流失分析模型主要有决策树 / 贝叶斯网络 / 神经网络等

5. 模型的评估与检验： 开花！

6. 应用模型： 终于，结出好果（结果）！

$>流失分析中需要注意的问题

>>过度抽样
      国内电信企业每月的客户流失率一般在1%～3%左右，如果直接采用某种模型(比如决策树、人工神经网络等)可能会因为数据概率太小而导致模型的失效
      因此我们需要加大流失客户在总样本中的比例，但是这种过度抽样必须谨慎小心，要充分考虑它的负面效应

>> 模型的有效性
   预测出结果，但用户已经流失，主要要关注采样时间跨度问题

>> 模型的流失后分析
数据挖掘在客户流失管理中的重要应用不仅仅应包括对客户流失的提前预警，还应包括客户流失后的问题分析。按照不同的客户信息纬度，查找最容易流失的客户群，同业务部门人员配合，辅以相关调查，力求发现客户流失的症结所在。然而，这一部分往往由于过度专注于挖掘模型本身的拟合度而忽略了流失管理的实际价值所在。

谢谢同事吴的指导,这他的原话转出来供大家学习
0. 我觉得做bi和技术最大的一点差别就是
    bi是数据导向，需求的优先级要低于数据

1. 没数据的话，需求就没戏了
2. 技术是需求导向，只要有需求，技术基本上都能做出来
3. 数据的加载、加工、清洗，叫做etl，其实和你现在做的事情很像
4. etl是挖掘里非常重要的一部分

参考：数据挖掘在电信客户流失分析中的应用
http://www.teleinfocn.com/html/2007-02-12/3448.html

posted @ 2009-11-03 17:44 刘凯毅阅读(2720) | 评论 (0) | 编辑收藏

beanstalkd 消息队列的第一手资料

beanstalk 消息队列小结
协议说明和各状态转换情况

基本知识点:
1. 对于beanstalk 消息队列中每条数据都为 job
2. beanstalk service端，会维护 tubes[多个管道]
3. client端可以监听,使用多 tube
4. client端可以指定 use 管道[ client生成一个新的job时会把此job提交到指定管道]
5. client端可以指定 watch 管道 [ client接收处理job时会到指定管道得到待处理的job]

官方示意图:
put            reserve               delete
-----> [READY] ---------> [RESERVED] --------> *poof*

一般情况:
1. 任务提交到service端,job 管理放入内存空间并为其标记状态 [READY]
2. client通过轮训竞争得到次状态, job 改为 [RESERVED]
   2.1 当在默认时间 120 秒内没处理完 , job.stats.timeouts 就会大于 0
      同时其他轮训竞争client会拿到这个job【注意了每次timeouts时,在轮训的客户端就会得到次job，状态都为 ready,timeouts>0 】
3. 随便其中一台client处理完 job.delete   , 其他 client 中的此job 都会    *poof*

deom - python beanstalkc 中 job.stats 参考:
使用 easy_install beanstalkc
API 参考 : http://github.com/earl/beanstalkc/blob/master/TUTORIAL
刚生成的 beanstalk
{'buries': 0, 'releases': 0, 'tube': 'default', 'timeouts': 0, 'ttr': 120,
'age': 6, 'pri': 2147483648L, 'delay': 0, 'state': 'reserved', 'time-left': 114,
'kicks': 0, 'id': 2}

以timeout了的 beanstalk,并且在其他client轮训到 job
{'buries': 0, 'releases': 0, 'tube': 'default', 'timeouts': 1, 'ttr': 120,
'age': 417, 'pri': 2147483648L, 'delay': 0, 'state': 'reserved', 'time-left': 110,
'kicks': 0, 'id': 2}
{'buries': 0, 'releases': 0, 'tube': 'default', 'timeouts': 1, 'ttr': 120, 'age': 415,
'pri': 2147483648L, 'delay': 0, 'state': 'reserved', 'time-left': 4294967163L,
'kicks': 0, 'id': 2}

当没所有client 的 job 都到期了状态
{'buries': 0, 'releases': 0, 'tube': 'default', 'timeouts': 2, 'ttr': 120,
'age': 417, 'pri': 2147483648L, 'delay': 0, 'state': 'ready', 'time-left': 4294967161L,
'kicks': 0, 'id': 2}
{'buries': 0, 'releases': 0, 'tube': 'default', 'timeouts': 2, 'ttr': 120, 'age': 415,
'pri': 2147483648L, 'delay': 0, 'state': 'ready', 'time-left': 4294967163L,
'kicks': 0, 'id': 2}

其中 client1 job.delete
client1 job.stats *poof*
client2 job.stats *poof*

比较全的状态说明 - [官方文档]
http://github.com/kr/beanstalkd/blob/v1.1/doc/protocol.txt?raw=true

官方示意图:

先简单说明下（完全自己理解的，欢迎拍砖。本人E人太差~看官档费劲，谅解下）:
job.stats状态 = [READY] 待处理, [RESERVED] 正处理, [DELAYED]延迟状态 , [BURIED] 隐藏状态

1. 延迟提交
py.client1.put>>> beanstalk.put('yes!', delay=10)
py.client3.reserve>>> job = beanstalk.reserve()
# 等待 10 秒

2. 管道测试
put-job到service端可以指定 put的tube管道
如:

py.client1.put>>> beanstalk.use('foo')
py.client1.put>>> beanstalk.put('hey!')

py.client2.reserve>>> job = beanstalk.reserve()
# 一直拥塞，应为他 watch 管道 'default'

py.client3.reserve>>> beanstalk.watch('foo')
# beanstalk.ignore('bar') 放弃监听 bar
py.client3.reserve>>> job = beanstalk.reserve()
py.client3.reserve>>> job.body #输出 'hey!'

3. 隐藏状态现在吧 client 1/2/3 的 use watch 的管道都调回 default
py.client2.reserve>>> job = beanstalk.reserve()
py.client3.reserve>>> job = beanstalk.reserve()
py.client1.put>>> beanstalk.put('隐藏状态!')
py.client2.reserve>>> job.bury() #2 轮训得到并且修改 job 为隐藏状态
# 120 秒后 client3 没有轮训得到此job
py.client2.reserve>>> job.stats()
{'buries': 1, 'releases': 0, 'tube': 'default', 'timeouts': 0, 'ttr': 120,
'age': 188, 'pri': 2147483648L, 'delay': 0, 'state': 'buried',
'time-left': 4294967228L, 'kicks': 0, 'id': 11}
py.client2.reserve>>> beanstalk.kick( job.stats()['id'] ) #修改状态为 reserved
# 立刻 client3 得到 job
py.client3.reserve>>> job.stats()
{'buries': 1, 'releases': 0, 'tube': 'default', 'timeouts': 0, 'ttr': 120, 'age': 313,
'pri': 2147483648L, 'delay': 0, 'state': 'reserved',
'time-left': 110, 'kicks': 1, 'id': 11}
# 这时候 client2 / 3 同时有 job 11 状态 'buries': 1,'timeouts': 0,'state': 'reserved'

4. peek 窥见
可以得到一个 stats - read 的 job ，其他 client 可以 job = beanstalk.reserve()
后马上 job.stats 会变成 [RESERVED]
py.client2.reserve>>> job = beanstalk.peek_ready()
取得 job 并看本 client 能处理能
>>> job = beanstalk.peek(3)
>>> job.body
'yes!'
>>> job.stats()['state']
'ready'
这种形式西 job 不能 bury 等修改状态，但可以 delete

peek 系类
peek_buried
peek_ready

posted @ 2009-10-30 12:05 刘凯毅阅读(3349) | 评论 (0) | 编辑收藏

消息队列 beanstalkd 介绍

首先好东西
http://kr.github.com/beanstalkd/

其次真的是好东西支持 java , python ,perl,ruby,erlang 和我不知道的语言
官方的原文介绍：

$ ./beanstalkd -d -l 10.0.1.5 -p 11300

This starts up beanstalkd as a daemon listening on address 10.0.1.5, port 11300.

Use It

Here’s an example in Ruby (see the client libraries to find your favorite language).

First, have one process put a job into the queue:

beanstalk = Beanstalk::Pool.new(['10.0.1.5:11300'])



beanstalk.put('hello')

Then start another process to take jobs out of the queue and run them:

beanstalk = Beanstalk::Pool.new(['10.0.1.5:11300'])



loop do



job = beanstalk.reserve



puts job.body # prints "hello"



job.delete



end

Thanks

Many thanks to memcached for providing inspiration for simple protocol design and for the structure of the documentation. Not to mention a fantastic piece of software!

posted @ 2009-10-28 19:21 刘凯毅阅读(2377) | 评论 (0) | 编辑收藏

使用rsync同步网络备份(转)

使用rsync同步网络备份

一. 简介
rsync常用的备份工具, 它目前是由 rsync.samba.org 维护.
rsync使用所谓的"rsync算法",提供一个非常快速的档案传输方法, 使local和远端二部主机之间的档案达到同步,它主要是传送二个档案的异动部份,而非每次都整份传送, 因此速度相当地快.
rsync它可以搭配rsh或ssh，也可以当成daemon模式使用直接的socket连接, 所以rsync可以当做一个优异的备份工具来使用.
我这简单介绍运用rsync备份远程网路主机档案的基本方法。
在这,我们是给rsync当成linux的一种daemon模式来运行.

首先,先给个简单的定义:当然要一台主机跑rsync daemon模式, 我们就称这台机器为一rsync Server, 或者说这台主机是一台备份主机( Backup Server).
备份主机会开启一个873的端口(port), 等待对方rsync连接.所以服务器记的要开这个端口

连接时, rsync Server 会检查密码是否相符, 若通过密码查核, 则开始进行档案传输.
第一次连通完成时, 会把整份档案传输一次, 下一次就只传送二个档案之间异动的部份.
以上是rsync client (欲加以备份的远程网路主机) 和rsync server 的运作方式。

藉由上述方法, 我们当然也可以设立多部备份主机, 使网路主机上重要的档案能分散至数部主机中, 以分散风险.
一旦完成备份, 我们可以对这些备份主机再做进一步的储存动作, 如使用tar打成tar的包, 把档案备份到硬盘之类.

以下内容，我用Ubuntu 7.10做客户机,Centos5做服务器测试过.


二. 安装法

rsync目前最新版是 2.6.8, 可以到rsync.samba.org 下载.
若您使用 rpm 套件,请用下面的方法安装,当然rhel5和centos5中默认就安装了
#rpm -ivh rsync*.rpm
#yum install rsync

它的设定档位置在 /etc/rsyncd.conf,奇怪，我的没有自动生成这个文件，那我们就来自己配置他

三. 设定 rsync server: (假设这台主机名称为 rsync.x111.com)

rsync server 端要设定以下四项:

   1.规划建立备份目录区

   2.启动xinetd中的rsync
   3.设定: /etc/rsyncd.conf

   4.设定: 密码档

依次说明如下:

1. 规划建立备份目录区:
建议您准备一个容量较大且独立的分割区, 并在其中开好备份目录, 如此 /blackup/x99

2. 启动xinetd中的rsync
系统默认没有安装xinetd。
# yum install xinetd
#service xinetd restart
#chkconfig rsync on

以上的操作,主要是要打开rsync这个daemon,一旦有rsync client要连接时,xinetd会把它转介给rsyncd (port 873).

3. 设定 /etc/rsyncd.conf :
全局设置
    uid = root
    gid = root
    use chroot = no                # 不使用chroot
    max connections = 4         # 最大连接数为4
    pid file = /var/run/rsyncd.pid
    lock file = /var/run/rsync.lock
    log file = /var/log/rsyncd.log    # 日志记录文件

以下的部分,代表开放给某一台rsync client 主机的设定, 简单范本如下:
    [x99]
    path = /blackup/x99/x99_backup
    auth users = x99_backup
    secrets file = /etc/rsyncd.secrets
    read only = no

以上文件的注解:

[x99] 代表要备份的主机代号, 名称自己设置.

path 用来设定备份档案要存放在那一个目录.这个可先要mkdir开好,可以自己设置
auth users 代表授权的帐号, 可以自己设置.
secrets file 代表储存帐号密码的密码档, 其放置的路径档名.

当然, 这台备份主机, 可以容纳许多 rsync client 连接, 只要在 rsyncd.conf中设置对应的多个部分即可.

以下例子,代表二个主机x99及x100欲备份进来:

    [x99]
    path = /blackup/x99/x99_backup
    comment = XXXXX
    auth users = x99_backup
    secrets file = /etc/rsyncd.secrets
    read only = no

    [x100]
    path = /blackup/x100/x100_backup
    auth users = x100_backup
    secrets file = /etc/rsyncd.secrets
    read only = no

4. 设定密码文件:

rsyncd.secrets 的内容很容易, 格式为"帐号:密码";
如以下例子:
x99_backup:x99pass
注意! 上述设定只是一个例子,你自己设置可一定千万不要直接套用.
接下来, 要将 rsyncd.secrets 这个密码档的档案属性设为root拥有, 且权限要设为600, 否则无法备份成功!

因此, 请下:
#chown root.root rsyncd.secrets
#chmod 600 rsyncd.secrets

至此, rsync的服务器这端已设定完成, 若欲查看备份日志.
#tail -f /var/log/rsyncd.log

接下来是 client 端(即欲备份的网络主机) 的设定.

四. 设定 rsync client (假设这台主机 IP 为 : 11.22.33.44)
步骤:

   1.设定密码档

   2.测试rsync命令是否可以正常

   3.将rsync指令放入定时任务(crontab)

另外, 假设x99这台主机是网路上的服务器, 现打算把/var/www/html这个目录加以备份至backup server(上面讲的rsync.x111.com),

但不想备份下面的目录中的内容/html/log，(也就是说要把/html/log目录排除), 整个操作方式如下:

1. 假设把密码档放在 /root/rsyncd.secrets, 内容只要含有密码一行即可:

x99pass

注意: rsyncd.secrets 的权限属性必须设为600,设置方法见上面.

2. 测试指令是否可以成功?

/usr/bin/rsync -rvztopglHpogDtS --progress --password-file=/root/rsyncd.secrets /var/www/html --exclude /html/log x99_backup@rsync.x111.com::x99

若出现传输目录档案的画面, 即表示测试成功.上面这个命令行中-rv里的v是verbose，z是压缩，r是递归，字目录一直，topg都是保持文件原有属性如属主、时间的参数。 --progress是指显示出详细的进度情况，--delete是指如果服务器端删除了这一文件，那么客户端也相应把文件删除，保持真正的一致。后面的 x99_backup@ip中，的x99_backup是指的用户名

3. 置入工作排程, 假设每天凌晨5点开始备份:

crontab -u root -e
0 5 * * * /usr/bin/rsync -rvlHpogDtS --password-file=/root/rsyncd.secrets /var/www/html --exclude apache /html/log x99_backup@rsync.x111.com::x99

若您有其它目录(如 /home)要备份, 则如法泡制: 20 5 * * * /usr/bin/rsync -rvlHpogDtS --password-file=/root/rsyncd.secrets /home x99_bakup@rsync.x111.com::x99

当然您觉得备份一台Backup Server不够,还可再按上述方法,自行增加任意多台Backup Server, 以分散风险!

五. 安全性:

防火墙的 iptables 指令, 来限制 rsync client 的连线范围, 例子如下:

iptables -A INPUT -p tcp -s ! xx.xx.xx.xx --dport 873 -j DROP

如此, 只有 xx.xx.xx.xx 这个 client IP 能连入这台 rsync server.

附:
详细格式说明：
-v, --verbose 详细模式输出
-q, --quiet 精简输出模式
-c, --checksum 打开校验开关，强制对文件传输进行校验
-a, --archive 归档模式，表示以递归方式传输文件，并保持所有文件属性，等于-rlptgoD
-r, --recursive 对子目录以递归模式处理
-R, --relative 使用相对路径信息
-b, --backup 创建备份，也就是对于目的已经存在有同样的文件名时，将老的文件重新命名为
~filename。可以使用--suffix选项来指定不同的备份文件前缀。
--backup-dir 将备份文件(如~filename)存放在在目录下。
-suffix=SUFFIX 定义备份文件前缀
-u, --update 仅仅进行更新，也就是跳过所有已经存在于DST，并且文件时间晚于要备份的文件。
(不覆盖更新的文件)
-l, --links 保留软链结
-L, --copy-links 想对待常规文件一样处理软链结
--copy-unsafe-links 仅仅拷贝指向SRC路径目录树以外的链结
--safe-links 忽略指向SRC路径目录树以外的链结
-H, --hard-links 保留硬链结
-p, --perms 保持文件权限
-o, --owner 保持文件属主信息
-g, --group 保持文件属组信息
-D, --devices 保持设备文件信息
-t, --times 保持文件时间信息
-S, --sparse 对稀疏文件进行特殊处理以节省DST的空间
-n, --dry-run现实哪些文件将被传输
-W, --whole-file 拷贝文件，不进行增量检测
-x, --one-file-system 不要跨越文件系统边界
-B, --block-size=SIZE 检验算法使用的块尺寸，默认是700字节
-e, --rsh=COMMAND 指定替代rsh的shell程序
--rsync-path=PATH 指定远程服务器上的rsync命令所在路径信息
-C, --cvs-exclude 使用和CVS一样的方法自动忽略文件，用来排除那些不希望传输的文件
--existing 仅仅更新那些已经存在于DST的文件，而不备份那些新创建的文件
--delete 删除那些DST中SRC没有的文件
--delete-excluded 同样删除接收端那些被该选项指定排除的文件
--delete-after 传输结束以后再删除
--ignore-errors 及时出现IO错误也进行删除
--max-delete=NUM 最多删除NUM个文件
--partial 保留那些因故没有完全传输的文件，以是加快随后的再次传输
--force 强制删除目录，即使不为空
--numeric-ids 不将数字的用户和组ID匹配为用户名和组名
--timeout=TIME IP超时时间，单位为秒
-I, --ignore-times 不跳过那些有同样的时间和长度的文件
--size-only 当决定是否要备份文件时，仅仅察看文件大小而不考虑文件时间
--modify-window=NUM 决定文件是否时间相同时使用的时间戳窗口，默认为0
-T --temp-dir=DIR 在DIR中创建临时文件
--compare-dest=DIR 同样比较DIR中的文件来决定是否需要备份
-P 等同于 --partial --progress 显示备份过程
-z, --compress 对备份的文件在传输时进行压缩处理
--exclude=PATTERN 指定排除不需要传输的文件模式
--include=PATTERN 指定不排除而需要传输的文件模式
--exclude-from=FILE 排除FILE中指定模式的文件
--include-from=FILE 不排除FILE指定模式匹配的文件
--version 打印版本信息
--address 绑定到特定的地址
--config=FILE 指定其他的配置文件，不使用默认的rsyncd.conf文件
--port=PORT 指定其他的rsync服务端口
--blocking-io 对远程shell使用阻塞IO
-stats 给出某些文件的传输状态
--progress 在传输时现实传输过程
--log-format=FORMAT 指定日志文件格式
--password-file=FILE 从FILE中得到密码
--bwlimit=KBPS 限制I/O带宽，KBytes per second
-h, --help 显示帮助信息

转自 http://blog.csdn.net/KataDoc360/archive/2009/03/16/3995559.aspx

posted @ 2009-10-28 17:55 刘凯毅阅读(314) | 评论 (0) | 编辑收藏

仅列出标题