int32bit
公告
外部文章迁移完毕文章分类
最新评论
最新留言
友情链接
RSS
功能
热门文章
随机文章
存档
访问次数
使用Docker创建数据容器
翻译自: Data-only container madness
1.什么是数据容器？
数据容器就是本身只创建一个volume供其他容器共享，创建完后即退出，不执行任何任务。比如通过以下方式创建一个postgres容器。
docker run --name dbdata postgres echo "Data-only container for postgres"
该容器运行echo "Data-only container for postgres"即退出，然而只要没有删除该容器，该容器/var/lib/postgresql/data的volume（在Dockerfile使用VOLUME指令定义)就会一直存在。
然后我们可以新建若干容器来共享数据，比如：
docker run -d --volumes-from dbdata --name db1 postgres
2.如何创建数据容器？
太简单了，创建任何容器，然后使用-v创建volume即可。但大家一定会想到用最小的镜像吧，比如hello-world,即
docker run -v /data hello-world
但这样是错误的！ 为什么呢?
我们首先创建一个简单的镜像:
FROM debian:jessie
RUN useradd mickey
RUN mkdir /foo && touch /foo/bar && chown -R mickey:mickey /foo
USER mickey
CMD ls -lh /foo
构建:
docker build -t mickey_foo -< Dockerfile
运行下:
docker run --rm -v /foo mickey_foo
输出:
total 0
-rw-r--r-- 2 mickey mickey 0 Nov 18 05:58 bar
运行正常，没有任何问题。
下面我们尝试使用busybox来作为数据容器:
docker run -v /foo --name mickey_data busybox true
docker run --rm --volumes-from mickey_data mickey_foo
输出:
total 0
# Empty WTF??
docker run --rm --volumes-from mickey_data mickey_foo ls -lh /
total 68K
drwxr-xr-x 2 root root 4.0K Nov 18 06:02 bin
drwxr-xr-x 2 root root 4.0K Oct 9 18:27 boot
drwxr-xr-x 5 root root 360 Nov 18 06:05 dev
drwxr-xr-x 1 root root 4.0K Nov 18 06:05 etc
drwxr-xr-x 2 root root 4.0K Nov 18 06:02 foo
drwxr-xr-x 2 root root 4.0K Oct 9 18:27 home
drwxr-xr-x 9 root root 4.0K Nov 18 06:02 lib
drwxr-xr-x 2 root root 4.0K Nov 18 06:02 lib64
drwxr-xr-x 2 root root 4.0K Nov 5 21:40 media
drwxr-xr-x 2 root root 4.0K Oct 9 18:27 mnt
drwxr-xr-x 2 root root 4.0K Nov 5 21:40 opt
dr-xr-xr-x 120 root root 0 Nov 18 06:05 proc
drwx------ 2 root root 4.0K Nov 18 06:02 root
drwxr-xr-x 3 root root 4.0K Nov 18 06:02 run
drwxr-xr-x 2 root root 4.0K Nov 18 06:02 sbin
drwxr-xr-x 2 root root 4.0K Nov 5 21:40 srv
dr-xr-xr-x 13 root root 0 Nov 18 06:05 sys
drwxrwxrwt 2 root root 4.0K Nov 5 21:46 tmp
drwxr-xr-x 10 root root 4.0K Nov 18 06:02 usr
drwxr-xr-x 11 root root 4.0K Nov 18 06:02 var
docker run --rm --volumes-from mickey_data mickey_foo touch /foo/ba
touch: cannot touch '/foo/bar': Permission denied
发生了什么呢？我们的/foo 仍然存在, 但是它是空的并且所有者是root？
让我们再试试使用我们刚刚构建的mickey_foo作为数据容器:
~: docker rm -v mickey_data # remove the old one
mickey_data
~: docker run --name mickey_data -v /foo mickey_foo true
~: docker run --rm --volumes-from mickey_data mickey_foo
total 0
-rw-r--r-- 1 mickey mickey 0 Nov 18 05:58 bar
# Yes!
~: docker run --rm --volumes-from mickey_data mickey_foo ls -lh /
total 68K
drwxr-xr-x 2 root root 4.0K Nov 18 06:02 bin
drwxr-xr-x 2 root root 4.0K Oct 9 18:27 boot
drwxr-xr-x 5 root root 360 Nov 18 06:11 dev
drwxr-xr-x 1 root root 4.0K Nov 18 06:11 etc
drwxr-xr-x 2 mickey mickey 4.0K Nov 18 06:10 foo
drwxr-xr-x 2 root root 4.0K Oct 9 18:27 home
drwxr-xr-x 9 root root 4.0K Nov 18 06:02 lib
drwxr-xr-x 2 root root 4.0K Nov 18 06:02 lib64
drwxr-xr-x 2 root root 4.0K Nov 5 21:40 media
drwxr-xr-x 2 root root 4.0K Oct 9 18:27 mnt
drwxr-xr-x 2 root root 4.0K Nov 5 21:40 opt
dr-xr-xr-x 121 root root 0 Nov 18 06:11 proc
drwx------ 2 root root 4.0K Nov 18 06:02 root
drwxr-xr-x 3 root root 4.0K Nov 18 06:02 run
drwxr-xr-x 2 root root 4.0K Nov 18 06:02 sbin
drwxr-xr-x 2 root root 4.0K Nov 5 21:40 srv
dr-xr-xr-x 13 root root 0 Nov 18 06:05 sys
drwxrwxrwt 2 root root 4.0K Nov 5 21:46 tmp
drwxr-xr-x 10 root root 4.0K Nov 18 06:02 usr
drwxr-xr-x 11 root root 4.0K Nov 18 06:02 var
# YES!!
~: docker run --rm --volumes-from mickey_data mickey_foo touch /foo/baz
~: docker run --rm --volumes-from mickey_data mickey_foo ls -lh /foo
total 0
-rw-r--r-- 1 mickey mickey 0 Nov 18 06:11 bar
-rw-r--r-- 1 mickey mickey 0 Nov 18 06:12 baz
# YES!!!
由于我们刚刚使用了相同的镜像作为数据容器镜像，共享的容器能够找到共享数据。为什么使用busybox不可以呢？由于busybox没有/foo这个目录，当我们使用-v创建/foo这个数据卷时，docker会以默认用户自动创建对应的目录（这里是root)，而--volumes-from仅仅是重用存在的卷，而不会对卷自动做任何事情。因此当我们尝试去写/foo时由于没有权限(root所有，mickey用户).
因此我们应该使用和共享的容器相同的镜像做数据容器镜像？是的!
那我们使用这么大的镜像不会浪费空间么?
3. 为什么不使用小镜像作为数据容器？
其中一个原因，在上一节已经解释。遗留的一个问题是使用这么大的镜像(因为一般的镜像都会比较大)会不会浪费空间呢？
首先我们需要知道Docker的文件系统是如何工作的。Docker镜像是由多个文件系统（只读层）叠加而成。当我们启动一个容器的时候，Docker会加载只读镜像层并在其上（译者注：镜像栈顶部）添加一个读写层。如果运行中的容器修改了现有的一个已经存在的文件，那该文件将会从读写层下面的只读层复制到读写层，该文件的只读版本仍然存在，只是已经被读写层中该文件的副本所隐藏。当删除Docker容器，并通过该镜像重新启动时，之前的更改将会丢失。在Docker中，只读层及在顶部的读写层的组合被称为Union File System（联合文件系统）。
因此当我们创建了一个debian容器实例时（大约150MB），根据以上的原理，我们再创建1000个debian镜像能够重用原来的只读层，需要的空间还是150MB.
容器本身并不会占任何空间，除非你修改了内容。
因此Docker无论创建一个镜像的多少实例，都不会占据更多的空间。
因此实际上，我们为了创建数据容器而使用busybox反而会占用更多的空间，这个空间就是busybox的镜像大小。
实际上我们经常这样使用:
~: docker run --name mydb-data --entrypoint /bin/echo mysql Data-only container for mydb
~: docker run -d --name mydb --volumes-from mydb-data mysql
上面的实例指行/bin/echo mysql Data-only container for mydb,能够更容易知道这是一个数据容器，利于使用grep查找.
bash字符串前美元符号的作用
problem
bash内置变量IFS作为内部单词分隔符，其默认值为<space><tab><newline>, 我想设置它仅为\n,于是：
OLD_IFS=$IFS
IFS='\n'
# do some work here
IFS=$OLD_IFS
但结果为：IFS把单独的字符当作了分隔符，即分隔符被设置成下划线和字母n 。
Why ?
Solution
通过google搜索，得知需要把\n转化成ANSI-C Quoting, 方法是把字符串放入$'string'中，即应该设置成:
IFS=$'\n'
顺便搜了下$字符的用途，在Unix & Linux, 中解释了字符串前面加$字符的两种形式，一种是单引号，一种是双引号，即
There are two different things going on here, both documented in the bash manual
$'
Dollar-sign single quote is a special form of quoting: ANSI C Quoting Words of the form $'string' are treated specially. The word expands to string, with backslash-escaped characters replaced as specified by the ANSI C standard.
$"
Dollar-sign double-quote is for localization: Locale translation A double-quoted string preceded by a dollar sign (‘$’) will cause the string to be translated according to the current locale. If the current locale is C or POSIX, the dollar sign is ignored. If the string is translated and replaced, the replacement is double-quoted.
因此单引号表示转化成ANSI-C字符，双引号则表示将字符串本地化。
以下是一个实例，ping /etc/hosts的主机名为video-开头的主机名，检查网络状况!
#!/bin/bash
trap "echo 'interrupted!';exit 1" SIGHUP SIGINT SIGTERM
OLD_IFS=$IFS
IFS=$'\n'
for i in `awk '$0!~/^$/ && $0!~/^#/ && $2~/^video/ {print $1,$2}' /etc/hosts`
do
ADDR=$(echo $i | cut -d' ' -f 1)
DOMAIN=$(echo $i | cut -d' ' -f 2)
if ping -c 2 $ADDR &>/dev/null
then
echo $DOMAIN ok!
else
echo $DOMIN dead!
fi
done
IFS=$OLD_IFS
ubuntu安装Nvidia驱动
Step1 Find out your graphics card model
使用lspci命名查看显卡系列
lspci -vnn | grep -i VGA 12
输出
01:00.0 VGA compatible controller [0300]: NVIDIA Corporation GK107 [GeForce GT 630 OEM] [10de:0fc2] (rev a1) (prog-if 00 [VGA controller])
Subsystem: Micro-Star International Co., Ltd. [MSI] Device [1462:275c]
Flags: bus master, fast devsel, latency 0, IRQ 46
Memory at f6000000 (32-bit, non-prefetchable) [size=16M]
Memory at e0000000 (64-bit, prefetchable) [size=256M]
Memory at f0000000 (64-bit, prefetchable) [size=32M]
I/O ports at e000 [size=128]
Expansion ROM at f7000000 [disabled] [size=512K]
Capabilities: <access denied>
Kernel driver in use: nouveau
可以看到显卡系列是GeForce GT 630 OEM
Step2 Find out the right driver version for your graphics card
访问Nvidia官方网址,输入显卡类型，点击search按钮,则会显示需要安装的驱动版本。
Version: 340.58
Release Date: 2014.11.5
Operating System: Linux 64-bit
Language: English (US)
File Size: 69.00 MB
Step3 Setup the xorg-edgers ppa
运行以下命令更新源：
sudo add-apt-repository ppa:xorg-edgers/ppa -y
sudo apt-get update
Step4 Install the driver
运行以下命令安装驱动：
sudo apt-get install nvidia-340
Step5 Verify the installation
运行以下命令：
lspci -vnn | grep -i VGA 12
输出
01:00.0 VGA compatible controller [0300]: NVIDIA Corporation GK107 [GeForce GT 630 OEM] [10de:0fc2] (rev a1) (prog-if 00 [VGA controller])
Subsystem: Micro-Star International Co., Ltd. [MSI] Device [1462:275c]
Flags: bus master, fast devsel, latency 0, IRQ 46
Memory at f6000000 (32-bit, non-prefetchable) [size=16M]
Memory at e0000000 (64-bit, prefetchable) [size=256M]
Memory at f0000000 (64-bit, prefetchable) [size=32M]
I/O ports at e000 [size=128]
Expansion ROM at f7000000 [disabled] [size=512K]
Capabilities: <access denied>
Kernel driver in use: nvidia
可见Kernel driver in user显示使用的内核驱动为nvidia
Step6 Nvidia settings tool
使用nvidia-settings命令配置驱动。
Removing the drivers
如果安装驱动导致系统无法启动，需要卸载驱动，运行以下命令:
sudo apt-get purge nvidia*
Additional Notes
很多教程说安装了nvidia驱动后需要把nouveau放入黑名单，其实并不需要，因为nvidia驱动会自动把它放入黑名单。 运行以下命令：
grep 'nouveau' /etc/modprobe.d/* | grep nvidia
输出:
/etc/modprobe.d/nvidia-340_hybrid.conf:blacklist nouveau
/etc/modprobe.d/nvidia-340_hybrid.conf:blacklist lbm-nouveau
/etc/modprobe.d/nvidia-340_hybrid.conf:alias nouveau off
/etc/modprobe.d/nvidia-340_hybrid.conf:alias lbm-nouveau off
/etc/modprobe.d/nvidia-graphics-drivers.conf:blacklist nouveau
/etc/modprobe.d/nvidia-graphics-drivers.conf:blacklist lbm-nouveau
/etc/modprobe.d/nvidia-graphics-drivers.conf:alias nouveau off
/etc/modprobe.d/nvidia-graphics-drivers.conf:alias lbm-nouveau off
说明已经把它放到黑名单了，即系统启动时不会自动加载这些模块。
References
参照英文博客
构建hadoop2.5.2环境下的spark1.1.1
当前已编译的spark二进制包只有hadoop2.4和cdh4版本的，如果搭的是hadoop2.5.x，则需要自己从源码中构建。
下载源码
从官网中下载源码，在Chose a package type 中选择Source Code, 下载后解压缩。
tar xvf spark-1.1.1.tgz
编译
Step1 设置maven内存限制
export MAVEN_OPTS="-Xmx2g -XX:MaxPermSize=512M -XX:ReservedCodeCacheSize=512m"
Step2 增加hadoop-2.5的profile
注意hadoop版本2.x.x需要指定profile，在根下的pom.xml下只有2.4.0的profile， 如果要在hadoop-2.5.x下，需要手动加上hadoop-2.5的profile，即添加pom.xml：
<profile>
<id>hadoop-2.5</id>
<properties>
<hadoop.version>2.5.2</hadoop.version>
<protobuf.version>2.5.0</protobuf.version>
<jets3t.version>0.9.0</jets3t.version>
</properties>
</profile>
否则编译的结果得到的protobuf版本不对，无法读取hdfs上的文件，抛java.lang.VerifyError: class org.apache.hadoop.hdfs .protocol.proto.ClientNamenodeProtocolProtos$CreateSnapshotRequestProto overrides final method getUnknownFields.() Lcom/google/protobuf/UnknownFieldSet;
Step3 编译
运行:
mvn -Pyarn -Phadoop-2.5 -Dhadoop.version=2.5.2 -Phive -DskipTests clean package
hive单机安装
安装要求
- java1.7+
- hadoop2.x
- mysql5.5+(非必须，建议使用mysql存储元数据)
安装前的环境
- JAVA_HOME: java安装目录
- HADOOP_HOME: hadoop安装目录
- CLASSPATH: 除了hadoop和hive的必须包，还需要包括mysql java驱动，这里使用的是mysql-connector-java-5.1.25.jar， 并把它放入到lib下
安装过程
Step 1 下载tar包
在hive官网下载最新的tar包，当前最新包为apache-hive-0.14.0-bin.tar.gz。
Step 2 解压包
假定安装路径为/opt/hive：
sudo mv apache-hive-0.14.0-bin.tar.gz /opt
sudo tar xvf apache-hive-0.14.0-bin.tar.gz
sudo ln -s apache-hive-0.14.0-bin hive
sudo mv mysql-connector-java-5.1.25.jar /opt/hive/lib
Step 3 配置
- 创建配置文件，直接从模板文件创建即可
sudo rename 's/\.template//' *
sudo touch hive-site.xml
- 编辑hive-env.sh文件，设置HADOOP_HOME=${HADOOP_HOME-:/opt/hadoop}
- 创建hive-site-xml文件，添加以下内容:
<property>
<name>javax.jdo.option.ConnectionURL</name>
<value>jdbc:mysql://localhost:3306/metastore?createDatabaseIfNotExist=true</value>
<description>the URL of the MySQL database</description>
</property>
<property>
<name>javax.jdo.option.ConnectionDriverName</name>
<value>com.mysql.jdbc.Driver</value>
</property>
<property>
<name>javax.jdo.option.ConnectionUserName</name>
<value>hive</value>
</property>
<property>
<name>javax.jdo.option.ConnectionPassword</name>
<value>HIVE_DBPASS</value>
</property>
<property>
<name>datanucleus.autoCreateSchema</name>
<value>true</value>
</property>
<property>
<name>datanucleus.fixedDatastore</name>
<value>false</value>
</property>
<property>
<name>datanucleus.autoCreateTables</name>
<value>true</value>
</property>
<property>
<name>datanucleus.autoCreateColumns</name>
<value>true</value>
</property>
<property>
<name>datanucleus.autoStartMechanism</name>
<value>SchemaTable</value>
</property>
<property>
<name>hive.metastore.warehouse.dir</name>
<value>/user/hive/warehouse</value>
</property>
<!--
<property>
<name>hive.metastore.uris</name>
<value>thrift://localhost:9083</value>
<description>IP address (or fully-qualified domain name) and port of the metastore host</description>
</property>
<property>
<name>hive.aux.jars.path</name>
<value>file:///opt/hive/lib/zookeeper-3.4.5.jar,file:///opt/hive/lib/hive-hbase-handler-0.14.0.jar,file:///opt/hive/lib/guava-11.0.2.jar</value>
</property>
-->
<property>
<name>hbase.zookeeper.quorum</name>
<value>localhost</value>
</property>
<property>
<name>hive.support.concurrency</name>
<description>Enable Hive's Table Lock Manager Service</description>
<value>true</value>
</property>
</configuration>
- mysql设置。修改/etc/mysql/my.cnf，修改bind-address 为0.0.0.0,重启mysql服务。
- 在hdfs创建必要目录:
$HADOOP_HOME/bin/hdfs dfs -mkdir /tmp
$HADOOP_HOME/bin/hdfs dfs -mkdir /user/hive
$HADOOP_HOME/bin/hdfs dfs -chown hive /user/hive
$HADOOP_HOME/bin/hdfs dfs -mkdir /user/hive/warehouse
$HADOOP_HOME/bin/hdfs dfs -chmod g+w /tmp
$HADOOP_HOME/bin/hdfs dfs -chmod 777 /user/hive/warehouse
$HADOOP_HOME/bin/hdfs dfs -chmod a+t /user/hive/warehouse
- 运行$HIVE_HOME/bin/hive, OK!
ubuntu14.04终端无法显示中文
不知道装了什么东西，终端突然无法输入中文，并且无法显示中文，中文显示为？？？。我切换其他用户，可以正常工作，并且nautilus中文显示正常，因此可以排除是编码设置问题。于是问题一定在于用户配置。因为我使用的是gnome-terminal，因此可能是这个app的问题。尝试修改profile preferences无果。尝试gconf，该app的配置在~/.gconf/apps/gnome-terminal下，为了还原默认设置，只需要删除gnome-terminal这个目录即可，恢复正常。
swap函数陷进
使用c语言写一个函数实现两个数交换，很简单写下以下代码：
void swap(int *a, int *b)
{
*a ^= *b;
*b ^= *a;
*a ^= *b;
}
只有三行代码，且没有引入中间变量，使用位运算，效率高！
但首先必须保证a, b 不是空指针，否则就会出现段错误。
于是代码进一步改成：
void swap(int *a, int *b)
{
if (a == NULL || b == NULL)
return;
*a ^= *b;
*b ^= *a;
*a ^= *b;
}
似乎这样就完美了？
咋一看，真没有什么问题了，不信你可以测试，无论正数，负数，还是0,基本都不会出错了。。
那么请看以下代码：
static int count = 0;
void permutation(int *a, int from, int to)
{
if (from == to) {
cout << ++count << ":";
for (int i = 0; i <= to; ++i)
cout << a[i] << " ";
cout << endl;
return;
}
for (int i = from; i <= to; ++i) {
swap(&a[from], &a[i]);
permutation(a, from + 1, to);
swap(&a[from], &a[i]);
}
}
以上代码是求一个数组全排列的递归方法，算法应该没有错？
可是输出大量0！！为什么呢？？？
答案在下面：
原因在于当swap(int *a, int *b)传的是同一个地址时，就会等于0
即若 a == b
*a ^= *b，此时 *a == 0, *b == 0
最后必然是 *a == 0, *b == 0,
for (int i = from; i <= to; ++i) {
swap(&a[from], &a[i]);
permutation(a, from + 1, to);
swap(&a[from], &a[i]);
}
上面代码没有考虑当from == i的情况，即传递的是同一个地址。
所以正确的swap函数，应该是：
void swap(int* a, int* b)
{
if (a == NULL || b == NULL || a == b)
return;
*a ^= *b;
*b ^= *a;
*a ^= *b;
}
随机数和洗牌算法
什么是随机数？通俗说法就是随机产生的一个数，这个数预先不能计算出来的，并且所有可能出现的数字，概率应该是均匀的。因此随机数应该满足至少以下两点：
- 不可计算性，即不确定性。
- 机会均等，即每个可能出现的数字必须概率相等。
如何产生随机数是一个具有挑战的问题，一般使用随机硬件产生，比如骰子、电子元件噪声、核裂变等。
在计算机编程中，我们经常调用随机数产生器函数，但我们必须清楚的一点是，一般直接调用软件的随机数产生器函数，产生的数字并不是严格的随机数，而是通过一定的算法计算出来的（不满足随机数的不可计算性），我们称它为伪随机数！由于它具有类似随机的统计特征，在不是很严格的情况，使用软件方式产生伪随机相比硬件实现方式，成本更低并且操作简单、效率也更高！
那一般伪随机数如何产生呢？ 一般是通过一个随机种子（比如当前系统时间值），通某个算法（一般是位运算），不断迭代产生下一个数。比如c语言中的stdlib中rand_r函数（用的glibc）：
/* This algorithm is mentioned in the ISO C standard, here extended
for 32 bits. */
int
rand_r (unsigned int *seed)
{
unsigned int next = *seed;
int result;
next *= 1103515245;
next += 12345;
result = (unsigned int) (next / 65536) % 2048;
next *= 1103515245;
next += 12345;
result <<= 10;
result ^= (unsigned int) (next / 65536) % 1024;
next *= 1103515245;
next += 12345;
result <<= 10;
result ^= (unsigned int) (next / 65536) % 1024;
*seed = next;
return result;
}
而java中的Random类产生方法next()为：
protected int next(int bits) {
long oldseed, nextseed;
AtomicLong seed = this.seed;
do {
oldseed = seed.get();
nextseed = (oldseed * multiplier + addend) & mask;
} while (!seed.compareAndSet(oldseed, nextseed));
return (int)(nextseed >>> (48 - bits));
}
java中还有一个更精确的伪随机产生器java.security.SecurityRandom, 它继承自Random类，可以指定算法名称，next方法为：
final protected int next(int numBits) {
int numBytes = (numBits+7)/8;
byte b[] = new byte[numBytes];
int next = 0;
nextBytes(b);
for (int i = 0; i < numBytes; i++) {
next = (next << 8) + (b[i] & 0xFF);
}
return next >>> (numBytes*8 - numBits);
}
当然这个类不仅仅是重写了next方法，在种子设置等都进行了重写。
最近有一道题：已知一个rand7函数，能够产生1～7的随机数，求一个函数，使其能够产生1～10的随机数。
显然调用一次不可能满足，必须多次调用！利用乘法原理，调用rand7() * rand7()可以产生1~49的随机数，我们可以把结果模10（即取个位数）得到0~9的数，再加1,即产生1~10的数。但我们还需要保证概率的机会均等性。显然1～49中，共有49个数，个位为0出现的次数要少1，不满足概率均等，如果直接这样计算，2~10出现的概率要比1出现的概率大！我们可以丢掉一些数字，比如不要大于40的数字，出现大于40,就重新产生。
int rand10() {
int ans;
do {
int i = rand7();
int j = rand7();
ans = i * j;
} while(ans > 40);
return ans % 10 + 1;
}
随机数的用途就不用多说了，比如取样，产生随机密码等。下面则着重说说其中一个应用--洗牌算法。
我们可能接触比较多的一种情况是需要把一个无序的列表排序成一个有序列表。洗牌算法（shuffle）则是一个相反的过程，即把一个有序的列表（当然无序也无所谓）变成一个无序的列表。
这个新列表必须是随机的，即原来的某个数在新列表的位置具有随机性！
我们假设有1～100共100个无重复数字。
很容易想到一种方案是：
从第一张牌开始，利用随机函数生成器产生1～100的随机数，比如产生88,则看第88个位置有没有占用，如果没有占用则把当前牌放到第88位置，如果已经占用，则重新产生随机数，直到找到有空位置！
首先必须承认这个方法是可以实现洗牌算法的。关键在于效率，首先空间复杂度是O(n)，时间复杂度也是O(n)，关键是越到后面越难找到空位置，大量时间浪费在求随机数和找空位置的。
第二中方案：
从第一张牌开始，设当前位置牌为第i张，利用随机函数生成器产生1～100的随机数，比如产生88，则交换第i张牌和第88张牌。
这样满足了空间是O（1）的原地操作，时间复杂度是O(n)。但是否能够保证每个牌的位置具有机会均等性呢？
首先一个常识是：n张牌，利用随机数产生N种情况，则必须满足N能够整除n，这样就能给予每个牌以N/n的机会（或者说权值），如果N不能整除n，必然机会不均等，即有些牌分配的机会多，有些少。
我们知道100的全排列有100的阶乘种情况，而调用100次随机函数，共可以产生100^100种情况，而n^n 必然不能整除n!，具体证明不在这里叙述。
那我们可以利用第二种方法改进，每次不是产生1~100的随机数，而是1~i的数字，则共有n!中情况，即N=n!，显然满足条件，且时间为O(n),空间为O(1).这也就是Fisher-Yates_shuffle算法，大多数库都使用的这种方法。
我们看看java中Collections实现：
public static void shuffle(List<?> list, Random rnd) {
int size = list.size();
if (size < SHUFFLE_THRESHOLD || list instanceof RandomAccess) {
for (int i=size; i>1; i--)
swap(list, i-1, rnd.nextInt(i));
} else {
Object arr[] = list.toArray();
// Shuffle array
for (int i=size; i>1; i--)
swap(arr, i-1, rnd.nextInt(i));
// Dump array back into list
// instead of using a raw type here, it's possible to capture
// the wildcard but it will require a call to a supplementary
// private method
ListIterator it = list.listIterator();
for (int i=0; i<arr.length; i++) {
it.next();
it.set(arr[i]);
}
}
}
除了首先判断能否随机访问，剩下的就是以上算法的实现了。
STL中实现：
// random_shuffle
template <class _RandomAccessIter>
inline void random_shuffle(_RandomAccessIter __first,
_RandomAccessIter __last) {
__STL_REQUIRES(_RandomAccessIter, _Mutable_RandomAccessIterator);
if (__first == __last) return;
for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i)
iter_swap(__i, __first + __random_number((__i - __first) + 1));
}
template <class _RandomAccessIter, class _RandomNumberGenerator>
void random_shuffle(_RandomAccessIter __first, _RandomAccessIter __last,
_RandomNumberGenerator& __rand) {
__STL_REQUIRES(_RandomAccessIter, _Mutable_RandomAccessIterator);
if (__first == __last) return;
for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i)
iter_swap(__i, __first + __rand((__i - __first) + 1));
}
如何测试洗牌算法具有随机性呢？其实很简单，调用洗牌算法N次，牌数为n，统计每个数字出现在某个位置的出现次数，构成一个矩阵n * n,如果这个矩阵的值都在N/n左右，则洗牌算法好。比如有100个数字，统计一万次，则每个数字在某个位置的出现次数应该在100左右。
洗牌算法的应用也很广，比如三国杀游戏、斗地主游戏等等。讲一个最常见的场景，就是播放器的随机播放。有些播放器的随机播放，是每次产生一个随机数来选择播放的歌曲，这样就有可能还没有听完所有的歌前，又听到已经听过的歌。另一种就是利用洗牌算法，把待播放的歌曲列表shuffle。如何判断使用的是哪一种方案呢？ 很简单，如果点上一首还能回去，则利用的是洗牌算法，如果点上一首又是另外一首歌，则说明使用的是随机产生方法。比如上一首是3,现在是18,点上一首，如果是3说明采用的洗牌算法，如果不是3，则说明不是洗牌算法（存在误判，多试几次就可以了）。
顺便提一下网上的一些抽奖活动，尤其是转盘，是不是真正的随机？答案留给看客！
openstack之filter-scheduler
上篇文章讲了nova-scheduler：openstack之nova-scheduler 。为了简单，只叙述了随机调度算法，而没有细讲filter调度算法。filter调度算法原理并不难，先层层过滤掉一些不满足条件的宿主机，然后对剩余的宿主机进行weight评分排序，多个weight得到的分数进行累加，分数较高的（注意不一定是最高，原因下面讲）作为侯选宿主机。具体算法描述可以查看官方文档：http://docs.openstack.org/trunk/config-reference/content/section_compute-scheduler.html 下面从源码逐步分析算法的运行过程。
首先看看schedule_run_instance方法：
def schedule_run_instance(self, context, request_spec,
admin_password, injected_files,
requested_networks, is_first_time,
filter_properties, legacy_bdm_in_spec):
"""This method is called from nova.compute.api to provision
an instance. We first create a build plan (a list of WeightedHosts)
and then provision.
Returns a list of the instances created.
"""
payload = dict(request_spec=request_spec)
self.notifier.info(context, 'scheduler.run_instance.start', payload)
instance_uuids = request_spec.get('instance_uuids') # 获取uuids，可有多个
LOG.info(_("Attempting to build %(num_instances)d instance(s) "
"uuids: %(instance_uuids)s"),
{'num_instances': len(instance_uuids),
'instance_uuids': instance_uuids})
LOG.debug(_("Request Spec: %s") % request_spec)
# 返回主机列表
weighed_hosts = self._schedule(context, request_spec,
filter_properties, instance_uuids)
# NOTE: Pop instance_uuids as individual creates do not need the
# set of uuids. Do not pop before here as the upper exception
# handler fo NoValidHost needs the uuid to set error state
instance_uuids = request_spec.pop('instance_uuids') # 弹出uuids，不再需要
# NOTE(comstud): Make sure we do not pass this through. It
# contains an instance of RpcContext that cannot be serialized.
filter_properties.pop('context', None)
for num, instance_uuid in enumerate(instance_uuids):
request_spec['instance_properties']['launch_index'] = num
try:
try:
weighed_host = weighed_hosts.pop(0) # 弹出第一个主机
LOG.info(_("Choosing host %(weighed_host)s "
"for instance %(instance_uuid)s"),
{'weighed_host': weighed_host,
'instance_uuid': instance_uuid})
except IndexError:
raise exception.NoValidHost(reason="")
self._provision_resource(context, weighed_host,
request_spec,
filter_properties,
requested_networks,
injected_files, admin_password,
is_first_time,
instance_uuid=instance_uuid,
legacy_bdm_in_spec=legacy_bdm_in_spec)
except Exception as ex:
# NOTE(vish): we don't reraise the exception here to make sure
# that all instances in the request get set to
# error properly
driver.handle_schedule_error(context, ex, instance_uuid,
request_spec)
# scrub retry host list in case we're scheduling multiple
# instances:
retry = filter_properties.get('retry', {})
retry['hosts'] = []
self.notifier.info(context, 'scheduler.run_instance.end', payload)
该方法在进行一些参数处理后，首先调用_schedule方法，该方法返回宿主机列表，然后对每个待启动云主机调用_provision_resource方法，并把对应的目标宿主机传入该方法。_provision_resource方法的任务是更新数据库和调用nova-compute的rpcapi指定目标宿主机启动云主机。核心方法是_schedule方法，
def _schedule(self, context, request_spec, filter_properties,
instance_uuids=None):
"""Returns a list of hosts that meet the required specs,
ordered by their fitness.
"""
elevated = context.elevated()
instance_properties = request_spec['instance_properties']
instance_type = request_spec.get("instance_type", None) # get flavor
# Get the group
update_group_hosts = False
scheduler_hints = filter_properties.get('scheduler_hints') or {}
group = scheduler_hints.get('group', None)
# --hint group SERVER_GROUP, 如果有group，则更新到数据库中
if group:
group_hosts = self.group_hosts(elevated, group)
update_group_hosts = True
if 'group_hosts' not in filter_properties:
filter_properties.update({'group_hosts': []})
configured_hosts = filter_properties['group_hosts']
filter_properties['group_hosts'] = configured_hosts + group_hosts
config_options = self._get_configuration_options()
# check retry policy. Rather ugly use of instance_uuids[0]...
# but if we've exceeded max retries... then we really only
# have a single instance.
properties = instance_properties.copy()
if instance_uuids:
properties['uuid'] = instance_uuids[0]
self._populate_retry(filter_properties, properties) # 如果超出最多尝试次数，抛出NoValidHost异常
filter_properties.update({'context': context,
'request_spec': request_spec,
'config_options': config_options,
'instance_type': instance_type})
self.populate_filter_properties(request_spec, # 把一些数据填入filter_properties中，比如project_id, os_type等
filter_properties)
# Find our local list of acceptable hosts by repeatedly
# filtering and weighing our options. Each time we choose a
# host, we virtually consume resources on it so subsequent
# selections can adjust accordingly.
# Note: remember, we are using an iterator here. So only
# traverse this list once. This can bite you if the hosts
# are being scanned in a filter or weighing function.
hosts = self.host_manager.get_all_host_states(elevated) # 获取所有主机列表,host_manager从父类init方法获取，根据CONF获取，默认为nova.scheduler.host_manager.HostManager,直接读取数据库
selected_hosts = []
if instance_uuids:
num_instances = len(instance_uuids)
else:
num_instances = request_spec.get('num_instances', 1)
# 注意range和xrange区别，range返回一个list，而xrange返回一个生成器
for num in xrange(num_instances):
# Filter local hosts based on requirements ...
hosts = self.host_manager.get_filtered_hosts(hosts,
filter_properties, index=num)
if not hosts:
# Can't get any more locally.
break
LOG.debug(_("Filtered %(hosts)s"), {'hosts': hosts})
weighed_hosts = self.host_manager.get_weighed_hosts(hosts, # 获取weight值，并按大到小排序
filter_properties)
LOG.debug(_("Weighed %(hosts)s"), {'hosts': weighed_hosts})
scheduler_host_subset_size = CONF.scheduler_host_subset_size # 截取集合到指定大小。
if scheduler_host_subset_size > len(weighed_hosts):
scheduler_host_subset_size = len(weighed_hosts)
if scheduler_host_subset_size < 1:
scheduler_host_subset_size = 1
chosen_host = random.choice(
weighed_hosts[0:scheduler_host_subset_size]) # 从截取的集合中随机选择一个作为目标宿主机，而不是一定是最大的。
selected_hosts.append(chosen_host)
# Now consume the resources so the filter/weights
# will change for the next instance.
chosen_host.obj.consume_from_instance(instance_properties) # 更新值，为下一个主机调度做准备
if update_group_hosts is True:
filter_properties['group_hosts'].append(chosen_host.obj.host)
return selected_hosts
该方法的两个核心方法是host_manager.get_filtered_hosts和host_manager.get_weighed_hosts方法，分别对应算法的过滤和计算权值两个过程。注意在计算权值后返回的是一个排好序的主机列表，但并不是选择其中一个最大值的作为目标宿主机，而是通过配置指定从topN中随机选择一个，比如设置scheduler_host_subset_size为5,过滤后返回的主机个数为10,则从top5中随机返回其中一个，这就是前面讲的为什么不是分值最高，而是较高。host_manager为可配置的，默nova.scheduler.host_manager.HostManager，
HostManagerd get_filtered_hosts主要调用两个方法：_choose_host_filters和filter_handler.get_filtered_objects，前者通过过滤器类名返回对应的类列表（相当于java中根据类名，比如"Apple"，找到对应的类，比如a.b.Apple.class，或者getClass("Apple")，过滤器类名通过nova.conf的scheduler_default_filters配置，默认为RetryFilter','AvailabilityZoneFilter','RamFilter','ComputeFilter','ComputeCapabilitiesFilter','ImagePropertiesFilter'。然后把类列表传递给filter_handler.get_filtered_objects方法，filte_handle是filters.HostFilterHandler，而HostFilterHandler继承自nova.filters.BaseFilterHandler,其实现为：
class BaseFilterHandler(loadables.BaseLoader):
"""Base class to handle loading filter classes.
This class should be subclassed where one needs to use filters.
"""
def get_filtered_objects(self, filter_classes, objs,
filter_properties, index=0):
list_objs = list(objs)
LOG.debug(_("Starting with %d host(s)"), len(list_objs))
for filter_cls in filter_classes:
cls_name = filter_cls.__name__
filter = filter_cls()
if filter.run_filter_for_index(index):
objs = filter.filter_all(list_objs,
filter_properties)
if objs is None:
LOG.debug(_("Filter %(cls_name)s says to stop filtering"),
{'cls_name': cls_name})
return
list_objs = list(objs)
LOG.debug(_("Filter %(cls_name)s returned "
"%(obj_len)d host(s)"),
{'cls_name': cls_name, 'obj_len': len(list_objs)})
if len(list_objs) == 0:
break
return list_objs
可见他会遍历所有的过滤类，实例化，并且调用它的filter_all方法，最后返回所有未被拦截的对象。下面我们看看过滤类：
我们上编文章说了，过滤器是可插除的，如果我们要自定义自己的过滤器只需要继承BaseHostFilter(在nova.schedule.filters.__init__.py中定义)并实现host_passes方法即可，如下代码:
class BaseHostFilter(filters.BaseFilter):
"""Base class for host filters."""
def _filter_one(self, obj, filter_properties):
"""Return True if the object passes the filter, otherwise False."""
return self.host_passes(obj, filter_properties)
def host_passes(self, host_state, filter_properties):
"""Return True if the HostState passes the filter, otherwise False.
Override this in a subclass.
"""
raise NotImplementedError()
可见BaseHostFilter继承filters.BaseFilter，代码：
class BaseFilter(object):
"""Base class for all filter classes."""
def _filter_one(self, obj, filter_properties):
"""Return True if it passes the filter, False otherwise.
Override this in a subclass.
"""
return True
def filter_all(self, filter_obj_list, filter_properties):
"""Yield objects that pass the filter.
Can be overriden in a subclass, if you need to base filtering
decisions on all objects. Otherwise, one can just override
_filter_one() to filter a single object.
"""
for obj in filter_obj_list:
if self._filter_one(obj, filter_properties):
yield obj
# Set to true in a subclass if a filter only needs to be run once
# for each request rather than for each instance
run_filter_once_per_request = False
def run_filter_for_index(self, index):
"""Return True if the filter needs to be run for the "index-th"
instance in a request. Only need to override this if a filter
needs anything other than "first only" or "all" behaviour.
"""
if self.run_filter_once_per_request and index > 0:
return False
else:
return True
我们只需要关注两个方法_filter_one和filter_all，_filter_one传入过滤对象和过滤参数，返回bool类型，通过返回True，拦截返回False，而filer_all是传入一个对象集合，通过调用_filter_one产生一个通过过滤器的元素生成器。因此我们只需要重写_filter_one即可，而BaseHostFilter的_filter_one调用host_passes,因此只需要重写host_passes方法。
filterHandle正是调用了filter类的filter_all方法。
filter过程到此结束，下面看看weight过程，回到_schedule方法，调用了host_manager.get_weighed_hosts，而host_manager调用了weight_handler.get_weighed_objects方法，weight_handle是HostWeightHandler实例，该类继承自nova.weights.BaseWeightHandler,其实现为：
class BaseWeightHandler(loadables.BaseLoader):
object_class = WeighedObject
def get_weighed_objects(self, weigher_classes, obj_list,
weighing_properties):
"""Return a sorted (highest score first) list of WeighedObjects."""
if not obj_list:
return []
weighed_objs = [self.object_class(obj, 0.0) for obj in obj_list]
for weigher_cls in weigher_classes:
weigher = weigher_cls()
weigher.weigh_objects(weighed_objs, weighing_properties)
return sorted(weighed_objs, key=lambda x: x.weight, reverse=True)
和过滤过程类似，也是遍历所有的weighed类，调用它的weigh_objects方法，得到一个weight值，再和之前的值累加。weight_objects方法会调用_weight_object和_weight_multiplier方法，前者对应分值，后者对应权值，二者的乘积就是最后的分值。因此weighed类必须实现_weigh_objects和_weight_multiplier方法，最后再通过weight值排序返回。如果要自定义weight类，只需继承BaseHostWeigher，重写 _weigh_object和_weight_multiplier方法，得到的值就是他们的乘积。
openstack之nova-scheduler详解
nova-scheduler的功能是负责从多宿主机中调度最适合的宿主机生成云主机。即传入需要启动的云主机列表，nova-scheduler根据云主机的数量、参数等进行调度，选择合适的物理机（hypervisor，宿主机，即运行nova-compute的节点)启动这些云主机。在H版本中实现的调度算法有两个，即过滤（filter）调度算法和随机调度算法（chance）。目前的默认调度算法是 filter-scheduler，即过滤调度器，其思想是先进行一些条件过滤一些宿主机，比如要求可用内存大于2GB，小于2GB的直接过滤，过滤器可以串联多个，即层层过滤。然后对过滤后的宿主机进行权值计算，权值计算就是根据宿主机的状态进行评分（weight），最后根据评分（weight）排序，评分最高的为最佳候选宿主机，评分也是可以串联的，即层层评分。注意openstack的设计原则是可扩展，意味着调度算法、过滤函数、评分函数都是可插除的，用户可以自定义自己的调度器，过滤器，评分方法，而只需在配置文件中配置即可，无需修改核心代码。实现的过滤器很多，而评分函数目前只有内存评分，即根据内存使用量进行评分。
注意：启动云主机时宿主机的位置并不是完全由scheduler控制，用户可以指定availability-zone，aggregate以及通过设置--hint来控制宿主机在某个集合中（本质还是过滤，即通过用户设定的条件进行过滤）。
下面从入口manager开始看看nova-scheduler如何工作的，部分代码：
def run_instance(self, context, request_spec, admin_password,
injected_files, requested_networks, is_first_time,
filter_properties, legacy_bdm_in_spec=True):
"""Tries to call schedule_run_instance on the driver.
Sets instance vm_state to ERROR on exceptions
"""
instance_uuids = request_spec['instance_uuids']
with compute_utils.EventReporter(context, conductor_api.LocalAPI(),
'schedule', *instance_uuids):
try:
return self.driver.schedule_run_instance(context,
request_spec, admin_password, injected_files,
requested_networks, is_first_time, filter_properties,
legacy_bdm_in_spec)
except exception.NoValidHost as ex:
# don't re-raise
self._set_vm_state_and_notify('run_instance',
{'vm_state': vm_states.ERROR,
'task_state': None},
context, ex, request_spec)
except Exception as ex:
with excutils.save_and_reraise_exception():
self._set_vm_state_and_notify('run_instance',
{'vm_state': vm_states.ERROR,
'task_state': None},
context, ex, request_spec)
方法先获取需要创建云主机的uuid，然后直接调用driver的schedule_run_instance，这个driver即调度器，所有的调度器必须继承自driver.Schduler, 并且实现三个抽象方法：schedule_run_instance，select_destinations，select_hosts。driver是由配置文件配置，默认为nova.scheduler.filter_scheduler.FilterScheduler，如下：
scheduler_driver_opt = cfg.StrOpt('scheduler_driver',
default='nova.scheduler.filter_scheduler.FilterScheduler',
help='Default driver to use for the scheduler')
CONF = cfg.CONF
CONF.register_opt(scheduler_driver_opt)
class SchedulerManager(manager.Manager):
"""Chooses a host to run instances on."""
def __init__(self, scheduler_driver=None, *args, **kwargs):
if not scheduler_driver:
scheduler_driver = CONF.scheduler_driver
self.driver = importutils.import_object(scheduler_driver)
self.compute_rpcapi = compute_rpcapi.ComputeAPI()
super(SchedulerManager, self).__init__(service_name='scheduler',
*args, **kwargs)
### 省略其他代码
由此可见入口函数直接调用driver（调度器）的scheduler_run_instance方法，为了简单起见，下面以chance调度器为例，看看它如何工作。首先查看chance调度器的scheduler_run_instance代码：
def schedule_run_instance(self, context, request_spec,
admin_password, injected_files,
requested_networks, is_first_time,
filter_properties, legacy_bdm_in_spec):
"""Create and run an instance or instances."""
instance_uuids = request_spec.get('instance_uuids')
for num, instance_uuid in enumerate(instance_uuids):
request_spec['instance_properties']['launch_index'] = num
try:
host = self._schedule(context, CONF.compute_topic,
request_spec, filter_properties)
updated_instance = driver.instance_update_db(context,
instance_uuid)
self.compute_rpcapi.run_instance(context,
instance=updated_instance, host=host,
requested_networks=requested_networks,
injected_files=injected_files,
admin_password=admin_password,
is_first_time=is_first_time,
request_spec=request_spec,
filter_properties=filter_properties,
legacy_bdm_in_spec=legacy_bdm_in_spec)
except Exception as ex:
# NOTE(vish): we don't reraise the exception here to make sure
# that all instances in the request get set to
# error properly
driver.handle_schedule_error(context, ex, instance_uuid,
request_spec)
该方法首先获取所有需要启动的云主机列表uuid，对每个待启动云主机调用_schedule方法，该方法返回一个宿主机，更新数据库，然后调用nova-compute的远程方法api（rpcapi）调用run_instance方法，在选择的宿主机中启动该云主机，nova-scheduler任务完成。下面看看_schedule实现：
def _schedule(self, context, topic, request_spec, filter_properties):
"""Picks a host that is up at random."""
elevated = context.elevated()
hosts = self.hosts_up(elevated, topic) # 父类Schduler方法，返回所有nova-compute状态为up的主机列表。
if not hosts:
msg = _("Is the appropriate service running?")
raise exception.NoValidHost(reason=msg)
hosts = self._filter_hosts(request_spec, hosts, filter_properties) # 过滤一些主机黑名单列表。
if not hosts:
msg = _("Could not find another compute")
raise exception.NoValidHost(reason=msg)
return random.choice(hosts) # 随机返回其中一个主机
该方法非常简单，首先获取所有服务状态为up的宿主机列表，然后过滤一些黑名单，最后调用random.choice方法随机从中返回一个宿主机。
文中只对简单chance算法进行了简单叙述，而filter算法由于比较复杂，后面以另一篇文章进行叙述。