牙殇

2015-02-20 • 个人情感

未曾料,第一个倒下的却是你。

悲,泣。

名词解释:ETL、CAP和MESI

2015-01-25 • 技术文章

ETL

ETL即Extract-Transform-Load,用来描述将数据从来源端经过萃取(Extract)、转置(Transform)、加载(Load)至目的端的过程。ETL这个词常用在但不限于数据仓库。ETL是极为复杂的过程,而手写程序不易管理,有愈来愈多的企业采用工具协助ETL的开发,并运用其内置的元数据功能来存储来源与目的的映射以及转换规则。 工具并可以提供较强大的功能来连接来源及目的端,开发人员不用去熟悉各种相异的平台及数据的结构,亦能进行开发。例子:taskctl+kettle的免费解决方案。

CAP

最近在做分布式数据库方面的工作,不可避免地讨论到CAP定理,CAP即一致性(Consistency)、可用性(Availability)和分区容忍性(Partition Tolerance)。

CAP定理指的是在分布式的环境下设计和部署系统时,有三个核心的系统需求,这三个要素最多只能同时实现两点,不可能三者兼顾。因此在进行分布式架构设计时,必须做出取舍。其中一致性和可用性很容易理解,那么什么是分区容忍性呢?其定义为除了整个网络的故障外,其他的故障(集)都不能导致整个系统无法正确响应。比如说,机器网线断了,那么partition就形成了。理解CAP定理的最简单方式是想象两个节点分处分区两侧。允许至少一个节点更新状态会导致数据不一致,即丧失了C性质。如果为了保证数据一致性,将分区一侧的节点设置为不可用,那么又丧失了A性质。除非两个节点可以互相通信,才能既保证C又保证A,这又会导致丧失P性质。

这个定理起源于加州大学伯克利分校(University of California, Berkeley)的计算机科学家埃里克·布鲁尔(Eric Brewer),故也称布鲁尔定理。

MESI

MESI是Modified、Exclusive、Shared、Invalid的首字母缩写,在大学的计算机组成原理教材里都有,讲的是缓存一致性的问题,这里再写出来就作为复习吧。

失效(Invalid)缓存段,要么已经不在缓存中,要么它的内容已经过时。为了达到缓存的目的,这种状态的段将会被忽略。一旦缓存段被标记为失效,那效果就等同于它从来没被加载到缓存中。

共享(Shared)缓存段,它是和主内存内容保持一致的一份拷贝,在这种状态下的缓存段只能被读取,不能被写入。多组缓存可以同时拥有针对同一内存地址的共享缓存段,这就是名称的由来。

独占(Exclusive)缓存段,和S状态一样,也是和主内存内容保持一致的一份拷贝。区别在于,如果一个处理器持有了某个E状态的缓存段,那其他处理器就不能同时持有它,所以叫“独占”。这意味着,如果其他处理器原本也持有同一缓存段,那么它会马上变成“失效”状态。

已修改(Modified)缓存段,属于脏段,它们已经被所属的处理器修改了。如果一个段处于已修改状态,那么它在其他处理器缓存中的拷贝马上会变成失效状态,这个规律和E状态一样。此外,已修改缓存段如果被丢弃或标记为失效,那么先要把它的内容回写到内存中——这和回写模式下常规的脏段处理方式一样。

参考资料

http://zh.wikipedia.org/wiki/ETL

http://zh.wikipedia.org/wiki/CAP%E5%AE%9A%E7%90%86

http://www.infoq.com/cn/articles/cache-coherency-primer

算法:环形公路加油站问题

2015-01-15 • 技术文章

现有一圆环形路,路上有n个加油站,第i个加油站储存有N[i]升容量的油,与下一个加油站之间有一定的距离g[i],一汽车初始无油,假设该车每公里消耗1升油,请问该车从哪个加油站出发可以绕该环形路行驶一圈。

方法一:从左往右遍历,在油量和最少的位置的下一个位置出发。

1
2
3
4
5
6
7
8
9
10
int res = 0, min = N[0] - g[0], sum = min, i = 1;
while(i < n) {
    sum += N[i] - g[i];
    if(sum < min) {
        min = sum;
        res = i;
    }
    ++i;
}
return sum >= 0 ? (res + 1) % n : -1;

方法二:开辟一个长度为N的数组v,记录N[i]-g[i]。从后往前遍历数组v,如果v[i]小于零,将其与v[i-1]合并,因为此时i不可能作为起点。如果v[i]不小于零,记入sum,并记录该位置pos(有可能作为起点)。最后,如果v[0]大于等于零,说明整个路段已经没有负的v[i]。返回0即可。如果v[0]+sum>=0,有满足条件的加油站,返回pos。否则,返回-1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int v[n];
for(int i = 0; i < n; ++i)
    v[i] = N[i] - g[i];
int sum = 0, pos = -1;
for(int i = n-1; i > 0; --i) {
    if(v[i] >= 0) {
        sum += v[i];
        pos = i;
    } else {
        v[i-1] += v[i];
    }
}
if(v[0] >= 0) 
    return 0;
else if(v[0] + sum >= 0)
    return pos;
else 
    return -1;

方法三:开辟一个长度为2*n-1的数组v,记录N[i]-g[i],这样就把一个环转化为一条线。使用两个指针start和end。如果[start,end]区间和小于0,令start=end+1并继续。直至找到长度为N的区间[start,end],并且区间和大于等于0。找到返回start,找不到返回-1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int v[2 * n];
for (int i = 0; i < n; ++i) {
    v[i] = N[i] - g[i];
    v[i+n] = N[i] - g[i];
}
int sum = 0;
for (int start = 0, end = 0; start <= n && end < 2 * n; end++) {
    if(sum + v[end] < 0) {
        start = end + 1;
        sum = 0;
    } else {
        if(end - start == n - 1) 
            return start;
        sum += v[end];
    }
}
return -1;

以上三种解法的时间复杂度均为O(n)。对于任意一个O(n)复杂度的DP题目,必有辅助数组仅与n有关,若刨除不需要计算的量还与两个以上的量有关,则不可能做到O(n)。

Ubuntu安装MySQL无法设置密码的处理一例

2015-01-09 • 技术文章

同学买了个VPS,自己装不上MySQL,遂请我帮忙。

简单地使用apt-get install来安装,在设置密码时终端返回信息fopen: Permission denied,很显然是权限问题。查看/var/log/mysql/error.log,发现ERROR: 1005 Can't create table 'tmp_db' (errno: 13)这个错误,具体定位到/usr/sbin/mysqld: Can't create/write to file '/tmp/iblrF3x1' (Errcode: 13)。也就是说,可以确定mysqld的进程无法对/tmp目录进行读写,再进一步说就是mysql用户无法对/tmp进行读写,遂授予权限。

再重新安装,安装没有再提示无法设置密码,但是在终端用root登录时提示ERROR 1045 (28000): Access denied for user 'root'@'localhost' (using password: YES),使用/etc/mysql/debian.cnf中提供的用户名和密码进行登录,查看mysql数据库的user表,发现根本没有root这个用户。这时我们或许可以insert一个root进去,但是这样是否会带来其它的问题不得而知。怀疑是起初设置密码失败遗留的原有data目录下的数据库造成的,遂彻底删除mysql所有的数据和配置再重新安装。重新安装后,root终于出现了,设置密码也可以登录了。

由于这个VPS的是暴露在公网上的,有两个独立IP,之前尝试性处理时直接用了root作为root的密码,我们可以登录后,修改mysql库user表中的root密码即可:UPDATE user SET password=PASSWORD('新密码') WHERE user='root'; FLUSH PRIVILEGES;,退出然后重新登录就行了。

以上是已知密码的情况,假如我们忘了MySQL的密码又该怎么办呢?没错,上面提到了debian.cnf这个文件中有一个预设用户可以利用,但对更广谱的操作系统而言,假如没有这个用户怎么办?执行service mysql stop停掉服务,然后设定跳过检查mysqld_safe --user=mysql --skip-grant-tables --skip-networking &,登录并使用mysql库:mysql -u root mysql,后面同上面的UPDATE和FLUSH后重启mysql服务即可。

删除文档末表格后空白行或空白页的方法

2015-01-04 • 技术文章

我们有时在使用办公文档软件(如永中文字、Microsoft Word)时经常遇到文末是一个表格的情况,恰恰满一页,造成表格后的一行被放在了下一页中,也就是产生了一个空白页,看上去不爽,打印时还得专门处理一下设置。这个问题的解决方案有如下几种。

微软官方推荐的方案:将表格末自动生成的一个空行的字体大小设定为1,然后将表格后空行的段落行距设定为固定值1磅。显然,该方法有一个比较大的缺陷就是表格末尾要有至少1磅的空白可以利用,否则无效。

此外还有一个比较好的办法是选中最后那个空行末的换行符,打开“字体”对话框,在效果中有一个“隐藏文字”选项,勾选后确定这一行即可消失,整个空白页也会随之消失。如果想让隐藏文字再被看到,点击“段落”中的¶按钮即可控制隐藏字符的隐现。