My Octopress Blog

life and I

github.com Connection Timeout

| Comments

基于github.com上面进行push, pull操作遇到如下问题

ssh: connection to host port: 22: Connection timed out lost connection

解决步骤如下:

测试ssh

输入:

ssh -v git@github.com

如果输出如下

    OpenSSH_5.8p1, OpenSSL 1.0.0d 8 Feb 2011
    debug1: Connecting to github.com [207.97.227.239] port 22.
    debug1: connect to address 207.97.227.239 port 22: Connection timed out
    ssh: connect to host github.com port 22: Connection timed out
    ssh: connect to host github.com port 22: Bad file number

linux的Bad file numberTimeout

检测ssh端口是否被封

输入

nmap -sS github.com -p 22

可能看到如下输出:

    Starting Nmap 5.35DC1 ( http://nmap.org ) at 2011-11-05 10:53 CET
    Nmap scan report for github.com (207.97.227.239)
    Host is up (0.10s latency).
    PORT   STATE    SERVICE
    22/tcp ***filtered*** ssh

    Nmap done: 1 IP address (1 host up) scanned in 2.63 seconds

如果看到filtered则表明22端口被防火墙封闭了

解决问题

在~/.ssh/config(windows是C:\Users\USERNAME.ssh\config)内添加(config文件没有就创建之)

Host github.com
User git
Hostname ssh.github.com
PreferredAuthentications publickey
IdentityFile ~/.ssh/id_rsa
Port 443

运行:

ssh -T github.com

Bitcask

| Comments

来自riak的bitcask[zz]

bitcask是啥

bitcask来自于riak,是一个日志(log-structured)存储系统。用在riak的分布式数据库的底层key-value的存储

bitcask的存储模型

bitcask的存储模型抽象之后非常简单。

insert过程 一个bitcask就是一个文件夹。任意时间点,只会有一个进程来写这个文件夹中的一个文件。 所有对文件的写操作都以追加的形式执行。这样的好处是不需要在磁盘上寻找数据,所有的操作都是顺序地写。 每次都会写入一个记录的实体。更改和删除也只是新数据的追加。每个数据实体的结构如下

- crc是数据体的校检码
- tstamp是时间戳
- ksz是key的长度
- valuesz是value的长度
- 最后紧接着key和value

一个文件由顺序的一系列数据实体构成,如下

此外,内存中会存着一份key的列表,如下

小结

bitcask是一个典型用空间换时间来提高写入性能的产品。因为省去了磁盘seek时间,io性能很好。 而且在写入数据的时候不修改数据,不会产生碎片,所以也就省去了让人讨厌的碎片清理的过程。 但是它的缺点也显而易见,由于数据清理都统一在merge过程中做,这时延迟会比较明显。 这也是各种类似bitcask思路的存储系统实现各显神通的地方了。 优化方法比较好想,比如只merge已经被关闭的文件等,这里就不赘述了

参考

Hadoop

| Comments

简介

Apache Hadoop是一个开源的基于集群的分布式处理大数据的计算框架。 它用于将一个机器处理的问题切分为若干提供存储和计算资源的机器共同处理的问题,对于集群来说, 集群中的任何机器都可能失效,它提供基于应用层的异常处理功能。

Apache Hadoop项目分为三个子项目

  • [Hadoop Common]

hadoop主要克隆了Google运行系统的框架,包括

  • 文件系统HDFS
  • 计算框架MapReduce
  • 结构化数据处理HBase

基于此的其他开源项目

  • Pig
  • Zookeeper
  • HIVE

大数据存储和访问

关系型数据库和MapReduce差异

网格计算

大规模分布式的主要问题是处理失效和错误

MapReduce简介

一种用于数据处理的编程模型,本质是并行的 分为两个阶段

  • Map
  • Reduce

分支化

  • map任务
  • reduce任务

两种类型节点控制作业执行

  • jobtracker
  • tasktracker

输入输出流

Apache Hadoop 提供了API允许除JAVA外语言运行MapReduce,

分布式文件系统

HDFS设计

特点

  • 针对超大文件而设计的文件系统
  • 流式数据访问
  • 商用硬件

缺点

  • 低延迟访问(如果需要低延迟HBase更好)
  • 大量小文件
  • 多用户写入,任意修改

HDFS概念

  • 默认64M

名称节点和数据节点

  • 管理者 命名空间
  • 工作者 定位块

命名空间损坏会造成系统失效,保证其可用有以下两种方式

  1. 复制组成文件系统元数据的持久文件
  2. 二级名称节点

命令行接口

  • hadoop fs -help
  • hadoop fs -copyFromLocal input/docs/qu.txt hdfs://localhost/user/tom/qu.txt
  • md5 input/docs/qu.txt qu.copy.txt
  • hadoop fs -mkdir books
  • hadoop fs ls

接口

  • Thrift
  • libhdfs
  • fuse
  • webdav
  • http
  • ftp

Java接口

数据流

hadoop的I/O

序列化

writable是MapReduce数据路径的核心。

序列化框架

基于文件的数据结构

SequenceFile

key/value结构

MapFile

sorted SequenceFile

MapReduce开发

大致流程

  • 编写map, reduce函数
  • 单元测试
  • 运行驱动作业
  • 集群运行
  • 调试错误
  • 调整性能

配置环境

单元测试

本地运行

集群运行

不需要修改,直接打包后运行

拥有网络观察界面

调试方法,日志解析方法

调优列表

  • mapper数量
  • reducer数量
  • 是否利用combainer
  • 中间值
  • 自定义序列
  • shuffle运行

MapReduce工作流

高级语言

  • Pig
  • HIHV
  • Cascading

MapReduce工作原理

运行作业

  • 提交作业
  • 作业初始化
  • 任务分配
  • 任务执行
  • 进度状态更新
  • 作业完成

失败的处理

作业调度

早期FIFO使用整个

后来优先级队列

Fair Scheduler

shuffle和排序

shuffle– 系统排序的过程

优化的关键

很多时候是MapReduce的核心

任务的执行

MapReduce类型和格式

key/value输入输出

java本身问题导致的类型摩擦

输入格式

大量小文件会降低MapReduce性能,因为会增加seek操作,而且每次新map会造成性能损失,MapReduce最佳处理速度最好与数据在集群中传播速度 相同。所以将大量的小文件打包成一个整块的文件

hadoop擅长处理结构化的数据

文本和文件格式的输入

数据库输入

输出格式

一个分区对应一个固定的分区不好,导致分区不均。

让很多reducer去做较轻的工作也不佳,更好的是用少量的reducer,每个做更多的活,这样便于管理reducer.

MapReduce特性

  • 计数器
  • 排序
  • 数据集链接

对数据排序是MapReduce的核心。

HBase

分布式的面向列的存储系统。对于实时写和随机访问大的数据有效。

公认的用例是webtable。

背景

最初由Powerset的chad walter等从2006年开发,基于google的论文”Bigtable; A distributed Storage System for structured Data”. 最初是haddop的一部分,2008年成为apache的一个子项目。

概念

数据模型

表的行作为主键,被排序

列被分为列族

所有列族成员被存储在一起

区域

自动横向切分区域

区域是分散在hbase内的单元

锁定

行的更新是原子的

实现

一个主节点和多个区域服务器

依赖于zookeeper

运行

-ROOT-和.MEAT.目录表

客户端缓存已知的-ROOT-和.MEAT.

安装

解压

设置路径

1
2
$export HBASE_HOME=/home/hbase
$export PATH=$PATH:$HBASE_HOME/bin

运行

1
$hbase

测试驱动

1
$start-hbase.sh

客户端

java

REST thrift

同RDBMS比较

  • HBase:分布式,面向列,hdfs上读写,自动横向分区和复制。
  • RDBMS:满足ACID的,面向行的,通过SQL查询,

HBase特点

  • 无真正索引
  • 自动分区
  • 创建新节点时自动线性扩展
  • 商用硬件
  • 容错性
  • 批处理性

实践

缺点

  • 文件描述信息块耗尽”Too many open files”
  • 数据节点线程用尽
  • 不良块

用户界面

web界面,默认60010端口

度量

架构

类似RDMBS,但是单元有版本,行排序

参考

HBase技术介绍

Zookeeper简介

分布式协调管理

特性

  • 简易
  • 易表达
  • 高可用
  • 简化松耦合
  • 开源库

安装运行

解压

设置路径

单机版测试

联机版测试

范例说明

znode

watcher

服务

数据模型

  • znode ACL
  • 临时znode
  • 序号:全局唯一
  • watch
  • API绑定

操作

  • create
  • delete
  • exists
  • getACL, setACL
  • getChildren
  • getData, setData
  • sync

watch触发

ACL

运行

集群内多数可用即可,5台容忍坏2台,6台允许坏2台,所以一般选择奇数个机器组成 集群

采用了zab协议

  • 领导者选举 200ms
  • 原子广播

一致性

  • zxid
  • 顺序一致性
  • 原子性
  • 单系统映像
  • 容错性
  • 合时性

内存提供读写操作

sync只能被异步调用

会话

和临时znode相关

time参数

  • tick time: 基本时长

状态

使用

配置服务

读写,监视

可恢复的应用

  • InterruptedException
  • KeeperException

锁服务

  1. znode下创建, znode-child-x
  2. 获取znode的children并设置watch
  3. 如果步骤1中的路径名和步骤2中的路径名的最小值相同,得到锁,否则等待或退出
  4. 一旦znodechildren改变则被watch到,继续步骤3的比较

集群影响问题

解决:提高发送消息的条件,不是每次都发送。

可恢复的异常

创建锁的客户端异常,没有释放。则死锁。

解决:在znode名称中嵌入标识符。

不可恢复的异常

WriteLock

其他分布式协议

BookKeeper

日志模块

工业中的Zookeeper

  • 集群限制在单一的数据中心
  • Zookeeper单独运行在服务器上,不合其他服务竞争资源
  • 配置Zookeeper保存不同磁盘上的快照驱动的日志。
  • 进程与磁盘进行交换。性能受影响。通过设置java堆大小和减少物理机器内存避免。

参考

Ubuntu上搭建Hadoop环境

BuildBot Test Framework

| Comments

简介

BuildBot 是一个持续集成工具,用于系统的自动化编译,测试。

特点:

  • 安装使用简单,但是拓展性良好,并且不限制于特定语言的构建工具
  • 多平台支持,如果开发人员在无法方便在其环境中进行测试,可以提交给版本管理工具后很快收到编译及测试结果
  • slave端依赖较少,只需要: virtualenv, Python
  • slave端可以运行于NAT防火墙后并和Master端进行通信
  • 多种状态汇集工具

安装

运行

Redis Note

| Comments

安装

1
2
3
4
$ wget http://redis.googlecode.com/files/redis-2.4.15.tar.gz
$ tar xzf redis-2.4.15.tar.gz
$ cd redis-2.4.15
$ make

简单测试

run server

1
$src/redis-server

run client

1
2
3
4
5
$ src/redis-cli
redis> set foo bar
OK
redis> get foo
"bar"

简单教程

这里是一个在线教程

基本数据类型及操作

作为一个key:value类型的nosql,基本的key, value 对应操作如下

  • set
  • get

多用户操作统一key对应的value时,简单的原子操作

  • incr
  • del

数据支持超时操作

  • expire
  • ttl

复杂数据类型及操作

Redis 同其他缓存系统一个较大区别是支持若干复杂数据类型

list

有序链表

  • rpush
  • lpush
  • lrange
  • lpop
  • rpop
  • llen

set

无序不重复

  • sadd
  • sismember
  • smembers
  • srem
  • sunion

sorted set

有序集合

  • zadd
  • zrange

Data Min Book Reading Noe

| Comments

数据挖掘:概念与技术

数据仓库和数据挖掘的OLAP

数据仓库意义

OLAP基本概念,一般结构

数据仓库概念

数据仓库是一个面向主题的,集成的,时变的,非易失的数据集合

构造 * 数据集成 * 数据清理 * 数据统一

多维数据模型

OLAP操作

- 上卷
- 下钻
- 切片分片
- 转轴

星行查询

数据仓库系统结构

设计视图

- 自顶向下
- 数据源
- 数据仓库
- 商务查询

步骤

  • 选取商务模型
  • 选取商务处理粒度
  • 选取维
  • 选取度量

三层结构

  • 服务器
  • OLAP服务器
  • 客户

结构模型

  • 企业仓库
  • 数据集市
  • 虚拟仓库

OLAP服务器种类

  • 关系OLAP
  • 多维OLAP
  • 混合OLAP
  • 特殊SQL服务器

数据仓库实现

核心是有效计算多个维度上的聚集

compute cube

  • 扩充SQL

    • 多数OLAP借助于多维聚集的预计算
    • 部分物化
    • 并行机制和渐进更新
  • ROLAP 使用元组和关系列表

    • 排序,散列,分组
    • 部分分组
    • 基于预计算的进一步计算
  • MOLAP 多维数据模型数组 多路数组聚集

    • 数据分块
    • 优化访问方单元
  • ROLAP vs MOLAP

    • 借助稀疏数组压缩以及方体计算顺序,MOLAP快得多
    • MOLAP不需要查找关键字
    • MOLAP使用数组寻址

索引OLAP数据

  • 位图索引
    • 允许快速检索
    • 比较,链接, 聚集操作变为位运算
  • 链接索引
    • 星型模式
    • 复合链接索引

高效OLAP查询

  • 确定可以在方体上完成的操作
  • 确定使用的物化方体

元数据存储

关于数据的数据

  • 数据仓库描述
  • 操作元数据
  • 汇总算法
  • 操作环境到数据仓库的映射
  • 系统性能数据
  • 商务元数据

后端工具和实用程序

  • 数据提取
  • 数据清理
  • 数据变换
  • 装入
  • 刷新

数据方进一步发展

发现驱动探查

  • selfexp
  • inexp
  • pathexp

三遍计算

多粒度复杂聚集: 多特征方

其他进展

  • 联机查询,返回至今为止的信息,提供交互的,周期性更新的信息
  • 最高N查询

数据仓库到数据挖掘

一般数据仓库使用的时间越长,进化的越好

数据仓库应用

- 信息处理
- 分析处理
- 数据挖掘

OLAP和数据挖掘

  • 不相交
    • OLAP是数据汇总/聚集工具,目的是简化和支持交互数据分析
    • 数据挖掘尽可能自动处理,允许用户指导该过程
  • 数据挖掘包含数据描述和数据建模,比OLAP宽泛,复杂性也大得多

联机分析处理到联机数据挖掘

联机分析处理重要性 - 数据仓库数据的高质量 - 环绕数据仓库的有价值的信息处理基础 - 基于OLAP探测式数据分析 - 数据挖掘的联机选择

数据预处理

  • 数据清理
  • 数据集成和转换
  • 数据归约

数据清理

遗漏值处理

噪声数据

数据集成和变换

  • 数据集成
  • 数据变换

数据归约

数据挖掘原语,语言和结构

数据挖掘无法在无人干预到情况下自动的挖掘出人们想要信息。更现实的做法是提供一系列原语供用户进行使用

数据挖掘原语

  • 任务相关数据
  • 挖掘类型
  • 背景知识
  • 兴趣度量
  • 发现模式和可视化

数据查询语言

  • DMQL
  • MSQL
  • DM OLE DB
  • CRIS-DM

图形界面

标准化到GUI还不清晰

数据挖掘系统

同传统DB/DW是否耦合

  • 不耦合 组织数据麻烦,
  • 松耦合 可以使用其某些机制,但是基于内存,大数据集表现不佳
  • 半紧耦合 比较好
  • 紧密耦合 高度期望的

概念描述:特征和描述

描述式数据挖掘和预测式数据挖掘

概念描述产生数据到特征和比较描述

大型数据库到概念描述和OLAP区别额

  • 复杂的数据类型和聚集
  • 用户控制和自动处理

数据泛化和基于汇总的特征

数据泛化将大的任务相关到数据集从较低概念抽象到较高概念的过程。

面向属性归纳

搜寻相关数据,然后考察属性不同值个数进行泛化

  • 属性删除
  • 属性优化

如何实现

  • 查询关系
  • 在关系上统计

解析特征:属性相关性分析

引入属性或者维度的相关性分析,过滤掉不相关或者弱相关的属性

步骤如下:

  • 数据收集
  • 用保守到AOI进行预先分析
  • 使用选定的相关分析度量去除弱相关和不相关的度量
  • 使用AOI产生概念

挖掘类比较:区分不同的类

具体实现

  • 数据收集
  • 维相关分析
  • 同步泛化
  • 导出比较

大型数据库中挖掘描述统计度量

度量中心趋势

度量数据发散

基本统计图形显示

Rest vs Markdown

| Comments

Table of Contents

概述

介绍配置使用Markdown和RestructuredText以及相关对比。 以及这两天配置和使用的部分经验,所有资料来自于网络,最开始想要使用这两种工具的起因是ppt对于代码高亮支持不够理想, 然后发现若干网络上面的代码高亮很不错

Markdown 安装以及工具链

需要安装 Pandoc ,这个比较好使,幻灯,代码高亮,pdf以及docx生成都可以使用这个工具也可以转换restructuredtext格式,但是似乎对于Markdown格式更加亲和。ubuntu的软件管理中存在该工具,如果需要更新到最新版本的进行如下操作:

1
2
3
sudo apt-get install haskell-platform
sudo cabal update
sudo cabal install pandoc

在该网站上有若干 Example 可以供参考

Markdown 语法

Markdown简明教程

RestructuredText安装以及工具链

依赖

texlive

在ubuntu上面有texlive 2009,如果希望安装更新的版本的话需要按照Texlive官方安装文档手动安装,没有特殊的apt-get可用,需要下载 install-tl-unx.tar.gz

在ubuntu 12.04上运行如下命令

1
1 $sudo tar -xvf install-tl-unx.tar.gz && cd install-tl-unx && sudo ./install-tl

RestructuredText 安装

在官网 Document 下载对应的`Python`源码文件,然后运行

1
1 $sudo python setup.py install

RestructuredText 语法

主要语法参见 Document, Primer, QuickRef, Directives

目录级别

一般按照:

= - ` : ’ ” ~ ^ _ * + # < >

的顺序进行目录配置

链接

  • 当前链接:
1
 `test <http://google.com.hk>`__
  • 匿名链接:
1
2
test anynomous link `link`__
__ http://google.com.hk
  • 外部链接:
1
2
test global link example_link_
.. _example_link: http://google.com.hk

图片

  • 当前图片:
1
2
3
4
5
.. image:: img/test.png
    :align: center
    :scale: 150%
    :alt: 额是
    :target: http://baidu.com
  • 全局图片:
1
2
3
4
5
.. |TestImg| image:: img/test.png
    :align: top
    :scale: 105%
    :alt: ceshi
    :target: http://baidu.com

文字中使用图片 |TestImg|

Markdown,RestructuredText技巧和应用

这里记录一些Markdown和RestructuredText的一些技巧和应用

RestructuredText

生成html

可以用pandoc, sphinx以及rst2html生成html。这三个工具特点如下:

  1. pandoc : Haskell语言库,转化格式较多,但是需要Haskell

  2. sphinx : Python官方文档库,比较强大,对中文支持好, ~ 但是比较复杂转化pdf借助于texlive,texlive-2011对中文支持更好

  3. rst2html : 官方的转化程序,使用简单,对中文支持好,我们一直用它!

语法高亮

可以利用如下代码进行语法高亮

1
2
3
4
.. code:: lang-name
    :number-lines:

    source

在新的Docutils中可以支持 code 指令,但是需要Pygments进行解析和高亮官方安装利用下面的命令

1
1 $sudo apt-get install python-pygments

但是官方比较老,支持代码高亮的只在Docutils 0.9版本上,所以最好源码安装根据官方安装文档 Pygments-installation 进行安装

首先生成对应的sheet

1
1 $pygmentize -S default -f html -a .highlight > style.css

然后利用生成的css进行渲染

1
1 $rst2html --stylesheet=style.css test.rst test.html

Slides

rst2slides, landslide, rst2s5等均支持ReST转化为幻灯片,但是从格式支持上来说,rst2s5更为合理

Markdown

语法高亮

输入格式为

1
2
3
~~~~~~~~~~{.lang-name, .numberLines}
 source
 ~~~~~~~~~~

其中 \~ 需要上下一致,lang-name 代表语言名称,.numberLines 代表是否标识代码行数

然后利用pandoc指定选项可以生成不同风格的代码高亮,例子如下

1
pandoc code.txt -s --highlight-style pygments[tango|kate|..] -o example.html

在线博客

利用octopress和github可以编写markdown格式的在线博客,具体步骤见 Octopress

值得注意的是其语法高亮模式有多种,只有 Backtick Code Blockspandoc 兼容具体格式如下

1
2
3
4
>``` [language] [title] [url] [link text]
>code snippet
>```
>其中`只能是3个

Markdown, RestructuredText的中文相关问题

Markdown

利用 pandoc -s source -o target 可以处理大部分中文问题,注意需要指定-s, -o选项,否则会出现乱码

RestructuredText

利用 rst2html , rst2tex 等工具可以直接转化,不需要特殊注意中文问题

中文pdf

无论Markdown或者RestructuredText默认使用pdflatex处理pdf文档,所以都无法完美解决中文问题,这里我们需要使用xelatex解决中文字体问题,在texlive安装目录对应版本下的texmf-dist/tex/xelatex/目录下,新建zhfontcfg目录,在该目录中创建zhfontcfg.sty宏包内容如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
\ProvidesPackage{zhfontcfg}
\usepackage{fontspec,xunicode}
\defaultfontfeatures{Mapping=tex-text} %如果没有它,会有一些 tex 特殊字符无法正常使用,比如连字符。

% 中文断行
\XeTeXlinebreaklocale "zh"
\XeTeXlinebreakskip = 0pt plus 1pt minus 0.1pt

%将系统字体名映射为逻辑字体名称,主要是为了维护的方便
\newcommand\fontnamehei{WenQuanYi Micro Hei}
%\newcommand\fontnamesong{SimSun}
%\newcommand\fontnamekai{KaiTi_GB2312}
\newcommand\fontnamemono{WenQuanYi Micro Hei Mono}
%\newcommand\fontnameroman{Bitstream Vera Serif}

%设置文档正文字体为宋体
\setmainfont[BoldFont=\fontnamehei]{\fontnamehei}
\setsansfont[BoldFont=\fontnamehei]{\fontnamehei}
\setmonofont{\fontnamemono}

%楷体
%\newfontinstance\KAI{\fontnamekai}
%\newcommand{\kai}[1]

%黑体
\newfontinstance\HEI{\fontnamehei}
\newcommand{\hei}[1]

%英文
%\newfontinstance\ENF{\fontnameroman}
%\newcommand{\en}[1]{\,{\ENF #1}\,}
%\newcommand{\EN}{\,\ENF\,}S5_

然后运行

1
sudo mktexlsr

其中设置正文字体通过

1
fc-list :lang=zh-cn

获取

利用Markdown和RestructuredText生成.tex文件,然后在文件前面添加`usepackage{zhfontcfg}`

最后用

1
xelatex file.tex

生成相应的pdf文件

中文换行

如果在编辑器中直接打一个回车进行换行,那么在生成的文件中会回车处出现一个空格这使W3C的一个标准,但是可以进行屏蔽

在Markdown中在末尾处直接打’\n’然后回车可以屏蔽该现象

在RestructuredText中末尾处直接打个’'然后回车可以屏蔽该现象

Markdown, RestructuredText对比

Markdown是github主推的格式,比较简洁,就是一个text to html的格式其思想主要来源于email。ReST是Docutils的标记语法,Docutils是Python世界的文档工具集,Sphinx可以生成多种格式,有默认的生成工程过程,可以用`Makefile`进行管理 [m_or_r]

但是在Stackflow上还有人说因为在mac上有实时的预览工具而选择Markdown

参考

[m_or_r]

http://ieqi.net/2012/04/13/markdown-%E8%BF%98%E6%98%AF-restructuredtext/