王春伟的技术博客

laravel也是一款非常流行的php框架，从最基础开始，准备使用一下这个框架。
首先是安装laravel:
1，在linux机器上 wget https://github.com/laravel/laravel/archive/master.zip
现在安装包，之后解压，在目录下执行composer install，就会进行相应的安装，成功后会多一个vender文件夹，一般vender文件夹为外部的扩展。
2，配置nginx
还是老样子配置nginx，指定的位置为public文件夹，事例如下：
3, laravel 5的配置文件在config/app.php
现在机器上执行php artisan key:generate，生成一个KEY
之后打开app.php
(1)修改’key’ => env(‘APP_KEY’, ‘自己的KEY’)
(2)’debug’ => env(‘APP_DEBUG’, true)将debug打开，便于调试~
之后访问自己的localhost就可以看到安装成功了！！

命名空间在某些框架下很少使用，但是在PHP 5 >= 5.3.0时就已经支持，下面是官方的文档。
http://www.php.net/manual/zh/language.namespaces.php

The keyword 'use' has two different applications, but the reserved word table links to here.

It can apply to namespace constucts:

file1:
<?php namespace foo;
  class Cat { 
    static function says() {echo 'meoow';}  } ?>

file2:
<?php namespace bar;
  class Dog {
    static function says() {echo 'ruff';}  } ?>

file3:
<?php namespace animate;
  class Animal {
    static function breathes() {echo 'air';}  } ?>

file4:
<?php namespace fub;
  include 'file1.php';
  include 'file2.php';
  include 'file3.php';
  use foo as feline;
  use bar as canine;
  use animate;
  echo \feline\Cat::says(), "<br />\n";
  echo \canine\Dog::says(), "<br />\n";
  echo \animate\Animal::breathes(), "<br />\n";  ?>

Note that 
felineCat::says()
should be
\feline\Cat::says()
(and similar for the others)
but this comment form deletes the backslash (why???) 

The 'use' keyword also applies to closure constructs:

<?php function getTotal($products_costs, $tax)
    {
        $total = 0.00;
        
        $callback =
            function ($pricePerItem) use ($tax, &$total)
            {
                
                $total += $pricePerItem * ($tax + 1.0);
            };
        
        array_walk($products_costs, $callback);
        return round($total, 2);
    }
?>

In addition to using namespaces and closures, the use keyword has another new meaning as of PHP 5.4 – using traits:

trait Hello {
    public function sayHello() {
        echo 'Hello ';
    }
}

trait World {
    public function sayWorld() {
        echo 'World';
    }
}

class MyHelloWorld {
    use Hello, World;
    public function sayExclamationMark() {
        echo '!';
    }
}

$o = new MyHelloWorld();
$o->sayHello();
$o->sayWorld();
$o->sayExclamationMark();

Cookie与 Session，一般认为是两个独立的东西，Session采用的是在服务器端保持状态的方案，而Cookie采用的是在客户端保持状态的方案。但为什么禁用Cookie就不能得到Session呢？因为Session是用Session ID来确定当前对话所对应的服务器Session，而Session ID是通过Cookie来传递的，禁用Cookie相当于失去了Session ID，也就得不到Session了。

是不是Cookie让禁用了，Session就一定不能用了呢？

1. ASP

在ASP中，Session必须倚赖Cookie才可用，Session是存储在服务器端的，而Cookie是存储在客户端的，相对而言，Session的安全性和可靠程度都比Cookie高。

2. PHP

在PHP中，通过相关的配置，可以让Session不依赖Cookie而存在。这是因为：

Session，储存于服务器端（默认以文件方式存储Session），根据客户端提供的Session ID来得到用户的文件，取得变量的值，Session ID可以使用客户端的Cookie或者Http1.1协议的Query_String（就是访问的URL的“?”后面的部分）来传送给服务器，然后服务器读取Session的目录……。也就是说，Session ID是取得存储在服务上的Session变量的身份证。当代码session_start();运行的时候，就在服务器上产生了一个Session文件，随之也产生了与之唯一对应的一个Session ID，定义Session变量以一定形式存储在刚才产生的Session文件中。通过Session ID，可以取出定义的变量。跨页后，为了使用Session，你必须又执行session_start();将又会产生一个Session文件，与之对应产生相应的Session ID，用这个session id是取不出前面提到的第一个Session文件中的变量的，因为这个Session ID不是打开它的“钥匙”。如果在session_start();之前加代码session_id($session id);将不产生新的Session文件，直接读取与这个id对应的Session文件。

PHP中的Session在默认情况下是使用客户端的Cookie来保存Session ID的，所以当客户端的cookie出现问题的时候就会影响Session了。必须注意的是：Session不一定必须依赖Cookie，这也是Session相比Cookie的高明之处。当客户端的Cookie被禁用或出现问题时，PHP会自动把Session ID附着在URL中，这样再通过Session ID就能跨页使用Session变量了。但这种附着也是有一定条件的，即“php.ini中的session.use_trans_sid = 1“，或者编译时打开打开了“–enable-trans-sid”选项。

用过论坛的朋友都知道，在进入论坛的时候，往往会提示你检查Cookie是否打开，这是因为大多数论坛都是基于Cookie的，论坛用它来保存用户名、密码等用户信息，方便使用。而且很多朋友都认为Cookie不安全（其实不是这样），往往禁用它。其实在PHP程序中，我们完全可以用Session来代替Cookie，它可以不依赖于客户端是否开启Cookie。

所以，我们可以抛开Cookie使用Session，即假定用户关闭Cookie的情况下使用Session，其实现途径有以下几种：

1. 设置php.ini配置文件中的“session.use_trans_sid = 1”，或者编译时打开打开了“–enable-trans-sid”选项，让PHP自动跨页传递Session ID。
2. 手动通过URL传值、隐藏表单传递Session ID。
3. 用文件、数据库等形式保存Session ID，在跨页过程中手动调用。

原文地址：http://blog.csdn.net/v_july_v/article/details/7382693
第一部分、十道海量数据处理面试题
　　1、海量日志数据，提取出某日访问百度次数最多的那个IP。
　　此题，在我之前的一篇文章算法里头有所提到，当时给出的方案是：IP的数目还是有限的，最多2^32个，所以可以考虑使用hash将ip直接存入内存，然后进行统计。
　　再详细介绍下此方案：首先是这一天，并且是访问百度的日志中的IP取出来，逐个写入到一个大文件中。注意到IP是32位的，最多有个2^32个IP。同样可以采用映射的方法，比如模1000，把整个大文件映射为1000个小文件，再找出每个小文中出现频率最大的IP（可以采用hash_map进行频率统计，然后再找出频率最大的几个）及相应的频率。然后再在这1000个最大的IP中，找出那个频率最大的IP，即为所求。
　　2、搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来，每个查询串的长度为1-255字节。
　　假设目前有一千万个记录（这些查询串的重复度比较高，虽然总数是1千万，但如果除去重复后，不超过3百万个。一个查询串的重复度越高，说明查询它的用户越多，也就是越热门。），请你统计最热门的10个查询串，要求使用的内存不能超过1G。
　　典型的Top K算法，还是在这篇文章里头有所阐述。 文中，给出的最终算法是：第一步、先对这批海量数据预处理，在O（N）的时间内用Hash表完成排序；然后，第二步、借助堆这个数据结构，找出Top K，时间复杂度为N‘logK。 即，借助堆结构，我们可以在log量级的时间内查找和调整/移动。因此，维护一个K(该题目中是10)大小的小根堆，然后遍历300万的Query，分别和根元素进行对比所以，我们最终的时间复杂度是：O（N） + N’*O（logK），（N为1000万，N’为300万）。ok，更多，详情，请参考原文。
　　或者：采用trie树，关键字域存该查询串出现的次数，没有出现为0。最后用10个元素的最小推来对出现频率进行排序。
　　3、有一个1G大小的一个文件，里面每一行是一个词，词的大小不超过16字节，内存限制大小是1M。返回频数最高的100个词。
　　方案：顺序读文件中，对于每个词x，取hash(x)%5000，然后按照该值存到5000个小文件（记为x0,x1,…x4999）中。这样每个文件大概是200k左右。
　　如果其中的有的文件超过了1M大小，还可以按照类似的方法继续往下分，直到分解得到的小文件的大小都不超过1M。 对每个小文件，统计每个文件中出现的词以及相应的频率（可以采用trie树/hash_map等），并取出出现频率最大的100个词（可以用含100个结点的最小堆），并把100个词及相应的频率存入文件，这样又得到了5000个文件。下一步就是把这5000个文件进行归并（类似与归并排序）的过程了。
　　4、有10个文件，每个文件1G，每个文件的每一行存放的都是用户的query，每个文件的query都可能重复。要求你按照query的频度排序。
　　还是典型的TOP K算法，解决方案如下： 方案1： 顺序读取10个文件，按照hash(query)%10的结果将query写入到另外10个文件（记为）中。这样新生成的文件每个的大小大约也1G（假设hash函数是随机的）。 找一台内存在2G左右的机器，依次对用hash_map(query, query_count)来统计每个query出现的次数。利用快速/堆/归并排序按照出现次数进行排序。将排序好的query和对应的query_cout输出到文件中。这样得到了10个排好序的文件（记为）。
　　对这10个文件进行归并排序（内排序与外排序相结合）。
　　方案2： 一般query的总量是有限的，只是重复的次数比较多而已，可能对于所有的query，一次性就可以加入到内存了。这样，我们就可以采用trie树/hash_map等直接来统计每个query出现的次数，然后按出现次数做快速/堆/归并排序就可以了。
　　方案3： 与方案1类似，但在做完hash，分成多个文件后，可以交给多个文件来处理，采用分布式的架构来处理（比如MapReduce），最后再进行合并。
　　5、 给定a、b两个文件，各存放50亿个url，每个url各占64字节，内存限制是4G，让你找出a、b文件共同的url？
　　方案1：可以估计每个文件安的大小为5G×64=320G，远远大于内存限制的4G。所以不可能将其完全加载到内存中处理。考虑采取分而治之的方法。
　　遍历文件a，对每个url求取hash(url)%1000，然后根据所取得的值将url分别存储到1000个小文件（记为a0,a1,…,a999）中。这样每个小文件的大约为300M。
　　遍历文件b，采取和a相同的方式将url分别存储到1000小文件（记为b0,b1,…,b999）。这样处理后，所有可能相同的url都在对应的小文件（a0vsb0,a1vsb1,…,a999vsb999）中，不对应的小文件不可能有相同的url。然后我们只要求出1000对小文件中相同的url即可。
　　求每对小文件中相同的url时，可以把其中一个小文件的url存储到hash_set中。然后遍历另一个小文件的每个url，看其是否在刚才构建的hash_set中，如果是，那么就是共同的url，存到文件里面就可以了。
　　方案2：如果允许有一定的错误率，可以使用Bloom filter，4G内存大概可以表示340亿bit。将其中一个文件中的url使用Bloom filter映射为这340亿bit，然后挨个读取另外一个文件的url，检查是否与Bloom filter，如果是，那么该url应该是共同的url（注意会有一定的错误率）。
　　Bloom filter日后会在本BLOG内详细阐述。
　　6、在2.5亿个整数中找出不重复的整数，注，内存不足以容纳这2.5亿个整数。
　　方案1：采用2-Bitmap（每个数分配2bit，00表示不存在，01表示出现一次，10表示多次，11无意义）进行，共需内存内存，还可以接受。然后扫描这2.5亿个整数，查看Bitmap中相对应位，如果是00变01，01变10，10保持不变。所描完事后，查看bitmap，把对应位是01的整数输出即可。
　　方案2：也可采用与第1题类似的方法，进行划分小文件的方法。然后在小文件中找出不重复的整数，并排序。然后再进行归并，注意去除重复的元素。
　　7、腾讯面试题：给40亿个不重复的unsigned int的整数，没排过序的，然后再给一个数，如何快速判断这个数是否在那40亿个数当中？
　　与上第6题类似，我的第一反应时快速排序+二分查找。以下是其它更好的方法： 方案1：oo，申请512M的内存，一个bit位代表一个unsigned int值。读入40亿个数，设置相应的bit位，读入要查询的数，查看相应bit位是否为1，为1表示存在，为0表示不存在。
　　dizengrong： 方案2：这个问题在《编程珠玑》里有很好的描述，大家可以参考下面的思路，探讨一下：又因为2^32为40亿多，所以给定一个数可能在，也可能不在其中；这里我们把40亿个数中的每一个用32位的二进制来表示假设这40亿个数开始放在一个文件中。
　　然后将这40亿个数分成两类: 1.最高位为0 2.最高位为1 并将这两类分别写入到两个文件中，其中一个文件中数的个数<=20亿，而另一个>=20亿（这相当于折半了）；与要查找的数的最高位比较并接着进入相应的文件再查找
再然后把这个文件为又分成两类: 1.次最高位为0 2.次最高位为1
　　并将这两类分别写入到两个文件中，其中一个文件中数的个数<=10亿，而另一个>=10亿（这相当于折半了）； 与要查找的数的次最高位比较并接着进入相应的文件再查找。 ……. 以此类推，就可以找到了,而且时间复杂度为O(logn)，方案2完。
　　附：这里，再简单介绍下，位图方法： 使用位图法判断整形数组是否存在重复 判断集合中存在重复是常见编程任务之一，当集合中数据量比较大时我们通常希望少进行几次扫描，这时双重循环法就不可取了。
　　位图法比较适合于这种情况，它的做法是按照集合中最大元素max创建一个长度为max+1的新数组，然后再次扫描原数组，遇到几就给新数组的第几位置上1，如遇到5就给新数组的第六个元素置1，这样下次再遇到5想置位时发现新数组的第六个元素已经是1了，这说明这次的数据肯定和以前的数据存在着重复。这种给新数组初始化时置零其后置一的做法类似于位图的处理方法故称位图法。它的运算次数最坏的情况为2N。如果已知数组的最大值即能事先给新数组定长的话效率还能提高一倍。
　　8、怎么在海量数据中找出重复次数最多的一个？
　　 方案1：先做hash，然后求模映射为小文件，求出每个小文件中重复次数最多的一个，并记录重复次数。然后找出上一步求出的数据中重复次数最多的一个就是所求（具体参考前面的题）。
　　9、上千万或上亿数据（有重复），统计其中出现次数最多的钱N个数据。
　　方案1：上千万或上亿的数据，现在的机器的内存应该能存下。所以考虑采用hash_map/搜索二叉树/红黑树等来进行统计次数。然后就是取出前N个出现次数最多的数据了，可以用第2题提到的堆机制完成。
　　10、一个文本文件，大约有一万行，每行一个词，要求统计出其中最频繁出现的前10个词，请给出思想，给出时间复杂度分析。
　　方案1：这题是考虑时间效率。用trie树统计每个词出现的次数，时间复杂度是O(n*le)（le表示单词的平准长度）。然后是找出出现最频繁的前10个词，可以用堆来实现，前面的题中已经讲到了，时间复杂度是O(n*lg10)。所以总的时间复杂度，是O(n*le)与O(n*lg10)中较大的哪一个。
　　附、100w个数中找出最大的100个数。
　　方案1：在前面的题中，我们已经提到了，用一个含100个元素的最小堆完成。复杂度为O(100w*lg100)。
　　方案2：采用快速排序的思想，每次分割之后只考虑比轴大的一部分，知道比轴大的一部分在比100多的时候，采用传统排序算法排序，取前100个。复杂度为O(100w*100)。
　　方案3：采用局部淘汰法。选取前100个元素，并排序，记为序列L。然后一次扫描剩余的元素x，与排好序的100个元素中最小的元素比，如果比这个最小的要大，那么把这个最小的元素删除，并把x利用插入排序的思想，插入到序列L中。依次循环，知道扫描了所有的元素。复杂度为O(100w*100)。
第二部分、十个海量数据处理方法大总结
　　ok，看了上面这么多的面试题，是否有点头晕。是的，需要一个总结。接下来，本文将简单总结下一些处理海量数据问题的常见方法。
　　下面的方法全部来自http://hi.baidu.com/yanxionglu/blog/博客，对海量数据的处理方法进行了一个一般性的总结，当然这些方法可能并不能完全覆盖所有的问题，但是这样的一些方法也基本可以处理绝大多数遇到的问题。下面的一些问题基本直接来源于公司的面试笔试题目，方法不一定最优，如果你有更好的处理方法，欢迎讨论。
　　一、Bloom filter
　　适用范围：可以用来实现数据字典，进行数据的判重，或者集合求交集
　　基本原理及要点：
　　对于原理来说很简单，位数组+k个独立hash函数。将hash函数对应的值的位数组置1，查找时如果发现所有hash函数对应位都是1说明存在，很明显这个过程并不保证查找的结果是100%正确的。同时也不支持删除一个已经插入的关键字，因为该关键字对应的位会牵动到其他的关键字。所以一个简单的改进就是 counting Bloom filter，用一个counter数组代替位数组，就可以支持删除了。
　　还有一个比较重要的问题，如何根据输入元素个数n，确定位数组m的大小及hash函数个数。当hash函数个数k=(ln2)*(m/n)时错误率最小。在错误率不大于E的情况下，m至少要等于n*lg(1/E)才能表示任意n个元素的集合。但m还应该更大些，因为还要保证bit数组里至少一半为0，则m应该>=nlg(1/E)*lge 大概就是nlg(1/E)1.44倍(lg表示以2为底的对数)。
　　举个例子我们假设错误率为0.01，则此时m应大概是n的13倍。这样k大概是8个。
　　注意这里m与n的单位不同，m是bit为单位，而n则是以元素个数为单位(准确的说是不同元素的个数)。通常单个元素的长度都是有很多bit的。所以使用bloom filter内存上通常都是节省的。
　　扩展：
　　Bloom filter将集合中的元素映射到位数组中，用k（k为哈希函数个数）个映射位是否全1表示元素在不在这个集合中。Counting bloom filter（CBF）将位数组中的每一位扩展为一个counter，从而支持了元素的删除操作。Spectral Bloom Filter（SBF）将其与集合元素的出现次数关联。SBF采用counter中的最小值来近似表示元素的出现频率。
　　问题实例：给你A,B两个文件，各存放50亿条URL，每条URL占用64字节，内存限制是4G，让你找出A,B文件共同的URL。如果是三个乃至n个文件呢？
　　根据这个问题我们来计算下内存的占用，4G=2^32大概是40亿*8大概是340亿，n=50亿，如果按出错率0.01算需要的大概是650亿个bit。现在可用的是340亿，相差并不多，这样可能会使出错率上升些。另外如果这些urlip是一一对应的，就可以转换成ip，则大大简单了。
　　二、Hashing
　　适用范围：快速查找，删除的基本数据结构，通常需要总数据量可以放入内存
　　基本原理及要点：
　　hash函数选择，针对字符串，整数，排列，具体相应的hash方法。
　　碰撞处理，一种是open hashing，也称为拉链法；另一种就是closed hashing，也称开地址法，opened addressing。
　　扩展：
　　d-left hashing中的d是多个的意思，我们先简化这个问题，看一看2-left hashing。2-left hashing指的是将一个哈希表分成长度相等的两半，分别叫做T1和T2，给T1和T2分别配备一个哈希函数，h1和h2。在存储一个新的key时，同时用两个哈希函数进行计算，得出两个地址h1[key]和h2[key]。这时需要检查T1中的h1[key]位置和T2中的h2[key]位置，哪一个位置已经存储的（有碰撞的）key比较多，然后将新key存储在负载少的位置。如果两边一样多，比如两个位置都为空或者都存储了一个key，就把新key存储在左边的T1子表中，2-left也由此而来。在查找一个key时，必须进行两次hash，同时查找两个位置。
　　问题实例：
　　1).海量日志数据，提取出某日访问百度次数最多的那个IP。
　　IP的数目还是有限的，最多2^32个，所以可以考虑使用hash将ip直接存入内存，然后进行统计。
　　三、bit-map
　　适用范围：可进行数据的快速查找，判重，删除，一般来说数据范围是int的10倍以下
　　基本原理及要点：使用bit数组来表示某些元素是否存在，比如8位电话号码
　　扩展：bloom filter可以看做是对bit-map的扩展
　　问题实例：
　　1)已知某个文件内包含一些电话号码，每个号码为8位数字，统计不同号码的个数。
　　8位最多99 999 999，大概需要99m个bit，大概10几m字节的内存即可。
　　2)2.5亿个整数中找出不重复的整数的个数，内存空间不足以容纳这2.5亿个整数。
　　将bit-map扩展一下，用2bit表示一个数即可，0表示未出现，1表示出现一次，2表示出现2次及以上。或者我们不用2bit来进行表示，我们用两个bit-map即可模拟实现这个2bit-map。
　　四、堆
　　适用范围：海量数据前n大，并且n比较小，堆可以放入内存
　　基本原理及要点：最大堆求前n小，最小堆求前n大。方法，比如求前n小，我们比较当前元素与最大堆里的最大元素，如果它小于最大元素，则应该替换那个最大元素。这样最后得到的n个元素就是最小的n个。适合大数据量，求前n小，n的大小比较小的情况，这样可以扫描一遍即可得到所有的前n元素，效率很高。
　　扩展：双堆，一个最大堆与一个最小堆结合，可以用来维护中位数。
　　问题实例：
　　1)100w个数中找最大的前100个数。
　　用一个100个元素大小的最小堆即可。
　　五、双层桶划分—-其实本质上就是【分而治之】的思想，重在分的技巧上！
　　适用范围：第k大，中位数，不重复或重复的数字
　　基本原理及要点：因为元素范围很大，不能利用直接寻址表，所以通过多次划分，逐步确定范围，然后最后在一个可以接受的范围内进行。可以通过多次缩小，双层只是一个例子。
　　扩展：
　　问题实例：
　　1).2.5亿个整数中找出不重复的整数的个数，内存空间不足以容纳这2.5亿个整数。
　　有点像鸽巢原理，整数个数为2^32,也就是，我们可以将这2^32个数，划分为2^8个区域(比如用单个文件代表一个区域)，然后将数据分离到不同的区域，然后不同的区域在利用bitmap就可以直接解决了。也就是说只要有足够的磁盘空间，就可以很方便的解决。
　　2).5亿个int找它们的中位数。
　　这个例子比上面那个更明显。首先我们将int划分为2^16个区域，然后读取数据统计落到各个区域里的数的个数，之后我们根据统计结果就可以判断中位数落到那个区域，同时知道这个区域中的第几大数刚好是中位数。然后第二次扫描我们只统计落在这个区域中的那些数就可以了。
　　实际上，如果不是int是int64，我们可以经过3次这样的划分即可降低到可以接受的程度。即可以先将int64分成2^24个区域，然后确定区域的第几大数，在将该区域分成2^20个子区域，然后确定是子区域的第几大数，然后子区域里的数的个数只有2^20，就可以直接利用direct addr table进行统计了。
　　六、数据库索引
　　适用范围：大数据量的增删改查
　　基本原理及要点：利用数据的设计实现方法，对海量数据的增删改查进行处理。
　　七、倒排索引(Inverted index)
　　适用范围：搜索引擎，关键字查询
　　基本原理及要点：为何叫倒排索引？一种索引方法，被用来存储在全文搜索下某个单词在一个文档或者一组文档中的存储位置的映射。
　以英文为例，下面是要被索引的文本： T0 = “it is what it is” T1 = “what is it” T2 = “it is a banana”
我们就能得到下面的反向文件索引：
“a”: {2} “banana”: {2} “is”: {0, 1, 2} “it”: {0, 1, 2} “what”: {0, 1}
　检索的条件”what”,”is”和”it”将对应集合的交集。
　　正向索引开发出来用来存储每个文档的单词的列表。正向索引的查询往往满足每个文档有序频繁的全文查询和每个单词在校验文档中的验证这样的查询。在正向索引中，文档占据了中心的位置，每个文档指向了一个它所包含的索引项的序列。也就是说文档指向了它包含的那些单词，而反向索引则是单词指向了包含它的文档，很容易看到这个反向的关系。
　　扩展：
　　问题实例：文档检索系统，查询那些文件包含了某单词，比如常见的学术论文的关键字搜索。
　　八、外排序
　　适用范围：大数据的排序，去重
　　基本原理及要点：外排序的归并方法，置换选择败者树原理，最优归并树
　　扩展：
　　问题实例：
　　1).有一个1G大小的一个文件，里面每一行是一个词，词的大小不超过16个字节，内存限制大小是1M。返回频数最高的100个词。
　　这个数据具有很明显的特点，词的大小为16个字节，但是内存只有1m做hash有些不够，所以可以用来排序。内存可以当输入缓冲区使用。
　　九、trie树
　　适用范围：数据量大，重复多，但是数据种类小可以放入内存
　　基本原理及要点：实现方式，节点孩子的表示方式
　　扩展：压缩实现。
　　问题实例：
　　1).有10个文件，每个文件1G，每个文件的每一行都存放的是用户的query，每个文件的query都可能重复。要你按照query的频度排序。
　　2).1000万字符串，其中有些是相同的(重复),需要把重复的全部去掉，保留没有重复的字符串。请问怎么设计和实现？
　　3).寻找热门查询：查询串的重复度比较高，虽然总数是1千万，但如果除去重复后，不超过3百万个，每个不超过255字节。
　　十、分布式处理 mapreduce
　　适用范围：数据量大，但是数据种类小可以放入内存
　　基本原理及要点：将数据交给不同的机器去处理，数据划分，结果归约。
　　扩展：
　　问题实例：
　　1).The canonical example application of MapReduce is a process to count the appearances ofeach different word in a set of documents:
　　2).海量数据分布在100台电脑中，想个办法高效统计出这批数据的TOP10。
　　3).一共有N个机器，每个机器上有N个数。每个机器最多存O(N)个数并对它们操作。如何找到N^2个数的中数(median)？
　　经典问题分析
　　上千万or亿数据（有重复），统计其中出现次数最多的前N个数据,分两种情况：可一次读入内存，不可一次读入。
　　可用思路：trie树+堆，数据库索引，划分子集分别统计，hash，分布式计算，近似统计，外排序
　　所谓的是否能一次读入内存，实际上应该指去除重复后的数据量。如果去重后数据可以放入内存，我们可以为数据建立字典，比如通过 map，hashmap，trie，然后直接进行统计即可。当然在更新每条数据的出现次数的时候，我们可以利用一个堆来维护出现次数最多的前N个数据，当然这样导致维护次数增加，不如完全统计后在求前N大效率高。
　　如果数据无法放入内存。一方面我们可以考虑上面的字典方法能否被改进以适应这种情形，可以做的改变就是将字典存放到硬盘上，而不是内存，这可以参考数据库的存储方法。
　　当然还有更好的方法，就是可以采用分布式计算，基本上就是map-reduce过程，首先可以根据数据值或者把数据hash(md5)后的值，将数据按照范围划分到不同的机子，最好可以让数据划分后可以一次读入内存，这样不同的机子负责处理各种的数值范围，实际上就是map。得到结果后，各个机子只需拿出各自的出现次数最多的前N个数据，然后汇总，选出所有的数据中出现次数最多的前N个数据，这实际上就是reduce过程。
　　实际上可能想直接将数据均分到不同的机子上进行处理，这样是无法得到正确的解的。因为一个数据可能被均分到不同的机子上，而另一个则可能完全聚集到一个机子上，同时还可能存在具有相同数目的数据。比如我们要找出现次数最多的前100个，我们将1000万的数据分布到10台机器上，找到每台出现次数最多的前 100个，归并之后这样不能保证找到真正的第100个，因为比如出现次数最多的第100个可能有1万个，但是它被分到了10台机子，这样在每台上只有1千个，假设这些机子排名在1000个之前的那些都是单独分布在一台机子上的，比如有1001个，这样本来具有1万个的这个就会被淘汰，即使我们让每台机子选出出现次数最多的1000个再归并，仍然会出错，因为可能存在大量个数为1001个的发生聚集。因此不能将数据随便均分到不同机子上，而是要根据hash 后的值将它们映射到不同的机子上处理，让不同的机器处理一个数值范围。
　 而外排序的方法会消耗大量的IO，效率不会很高。而上面的分布式方法，也可以用于单机版本，也就是将总的数据根据值的范围，划分成多个不同的子文件，然后逐个处理。处理完毕之后再对这些单词的及其出现频率进行一个归并。实际上就可以利用一个外排序的归并过程。
　 另外还可以考虑近似计算，也就是我们可以通过结合自然语言属性，只将那些真正实际中出现最多的那些词作为一个字典，使得这个规模可以放入内存。

一本介绍几本网站架构的书~
缓存的基本原理,RAID,分布式哈希和虚拟节点等知识~

原文链接：http://www.cnblogs.com/yanghuahui/p/3483754.html
之前分析过关系型数据库的BTree，对于非关系型数据库，可以使用LSM树结构，这里摘抄下原理：
讲LSM树之前，需要提下三种基本的存储引擎，这样才能清楚LSM树的由来：

哈希存储引擎 是哈希表的持久化实现，支持增、删、改以及随机读取操作，但不支持顺序扫描，对应的存储系统为key-value存储系统。对于key-value的插入以及查询，哈希表的复杂度都是O(1)，明显比树的操作O(n)快,如果不需要有序的遍历数据，哈希表就是your Mr.Right
B树存储引擎是B树（关于B树的由来，数据结构以及应用场景可以看之前一篇博文）的持久化实现，不仅支持单条记录的增、删、读、改操作，还支持顺序扫描（B+树的叶子节点之间的指针），对应的存储系统就是关系数据库（Mysql等）。
LSM树（Log-Structured Merge Tree）存储引擎和B树存储引擎一样，同样支持增、删、读、改、顺序扫描操作。而且通过批量存储技术规避磁盘随机写入问题。当然凡事有利有弊，LSM树和B+树相比，LSM树牺牲了部分读性能，用来大幅提高写性能。
通过以上的分析，应该知道LSM树的由来了，LSM树的设计思想非常朴素：将对数据的修改增量保持在内存中，达到指定的大小限制后将这些修改操作批量写入磁盘，不过读取的时候稍微麻烦，需要合并磁盘中历史数据和内存中最近修改操作，所以写入性能大大提升，读取时可能需要先看是否命中内存，否则需要访问较多的磁盘文件。极端的说，基于LSM树实现的HBase的写性能比Mysql高了一个数量级，读性能低了一个数量级。

LSM树原理把一棵大树拆分成N棵小树，它首先写入内存中，随着小树越来越大，内存中的小树会flush到磁盘中，磁盘中的树定期可以做merge操作，合并成一棵大树，以优化读性能。

以上这些大概就是HBase存储的设计主要思想，这里分别对应说明下：

因为小树先写到内存中，为了防止内存数据丢失，写内存的同时需要暂时持久化到磁盘，对应了HBase的MemStore和HLog
MemStore上的树达到一定大小之后，需要flush到HRegion磁盘中（一般是Hadoop DataNode），这样MemStore就变成了DataNode上的磁盘文件StoreFile，定期HRegionServer对DataNode的数据做merge操作，彻底删除无效空间，多棵小树在这个时机合并成大树，来增强读性能。

关于LSM Tree，对于最简单的二层LSM Tree而言，内存中的数据和磁盘你中的数据merge操作，如下图

图来自lsm论文

lsm tree，理论上，可以是内存中树的一部分和磁盘中第一层树做merge，对于磁盘中的树直接做update操作有可能会破坏物理block的连续性，但是实际应用中，一般lsm有多层，当磁盘中的小树合并成一个大树的时候，可以重新排好顺序，使得block连续，优化读性能。

hbase在实现中，是把整个内存在一定阈值后，flush到disk中，形成一个file，这个file的存储也就是一个小的B+树，因为hbase一般是部署在hdfs上，hdfs不支持对文件的update操作，所以hbase这么整体内存flush，而不是和磁盘中的小树merge update，这个设计也就能讲通了。内存flush到磁盘上的小树，定期也会合并成一个大树。整体上hbase就是用了lsm tree的思路。

前言
在sae上开发小的项目时，发现move_uploaded_file()函数permission denied,原来是新浪的sae服务并不允许上传上传文件。但是wordpress这类服务明明是可以上传图片的，发现原来使用sae的Storage服务。
（一）开通storage服务
首先到http://sae.sina.com.cn/?m=storage&app_id=circlegame&ver=
开通一个domain,例如我建立的domain名字叫shulan,以后就可以往这个domain下添加文件了。
(二）前端代码
前端一个简单的form表单，可以上传文件即可
例如

<form id="myForm" name="myForm" method="post" action="/shulan/cms/fPost/" enctype="multipart/form-data">
      <div class="form-group">
        <label2 for="exampleInputText" style="color:white">文字标题</label2>
        <input type="text" class="form-control" id="title" name="title" placeholder="必填">
      </div>                       
      <div class="form-group">
        <label2 for="exampleInputText" style="color:white">图    片</label2>
        <input type="file" class="form-control" id="pic" name="pic" placeholder="必填">
      </div>
         <input type="submit" id="post" style="color:white" align="center" value="提交"/>
</form>

(三）后端代码
后端通过php调用他的接口即可，因为他给的API文档看起来有些麻烦，这里简单调用即可

$path = time().".jpg"; //文件名
$s = new SaeStorage();
$result=$s->upload("shulan",$path, $_FILES["pic"]["tmp_name"]);
$picUrl=$s->getUrl("shulan",$path);

结束
新浪的sae服务还是比较好用的，如果PV不大的情况下完全是免费的。而且提供mysql,memcache，kv,cron等一系列服务，可以在上面做一些小应用。

一 安装redis
1.安装tcl支持

yum install tcl
　　
2.安装redis我们以最新的2.8.9为例

$ wget http://download.redis.io/releases/redis-2.8.9.tar.gz
$ tar xzf redis-2.8.9.tar.gz
$ cd redis-2.8.9
$ make
$ make test
$ make install

测试通过后安装，安装后会自动把redis-server,redis-cli,redis-benchmark,redis-check-aof,redis-check-dump复制到/usr/local/bin目录下。
chmod +x /etc/init.d/redis
设置开机自动启动服务

sudo chkconfig redis on

启动服务：

service redis start
停止服务：

service redis stop

二 安装phpredis

1、安装redis

下载：https://github.com/nicolasff/phpredis/archive/2.2.4.tar.gz

上传phpredis-2.2.4.tar.gz到/usr/local/src目录

cd /usr/local/src #进入软件包存放目录

tar zxvf phpredis-2.2.4.tar.gz #解压

cd phpredis-2.2.4 #进入安装目录

/usr/local/php/bin/phpize #用phpize生成configure配置文件

./configure –with-php-config=/usr/local/php/bin/php-config #配置

make #编译

make install #安装

安装完成之后，出现下面的安装路径

/usr/local/php/lib/php/extensions/no-debug-non-zts-20090626/

2、配置php支持

vi /usr/local/php/etc/php.ini #编辑配置文件，在最后一行添加以下内容

添加

extension=”redis.so”

3 重启服务

sudo service nginx restart

sudo /etc/init.d/php-fpm restart

三 安装memcached

(一）由于memcached安装时，需要使用libevent类库，所以先安装libevent

1.下载
#wget http://www.monkey.org/~provos/libevent-2.0.12-stable.tar.gz
2.解压缩
#tar xzfv libevent-2.0.12-stable.tar.gz
3.进入目录
#cd libevent-2.0.12-stable
4. 编译，安装
# ./configure
# make
# make install
注：默认安装到/usr/local/lib/目录
(二)：安装Memcached
http://memcached.org/ 是Memcached的官方网站
1.下载
# wget http://memcached.googlecode.com/files/memcached-1.4.5.tar.gz
2.解压缩
#tar xzfv memcached-1.4.5.tar.gz
3.进入目录
#cd memcached-1.4.5

4. 编译，安装
./configure –prefix=/local/memcached
make
make install

安装完成后，会在 /local/memcached 出现 bin和share目录
进行 bin目录，启动 memcache
方法如下:
./memcached -d -u nobody -m 512 127.0.0.1 -p 11211

(三)：安装memcache PHP模块

#wget http://pecl.php.net/get/memcache-2.2.4.tgz

# tar zxvf memcache-2.2.4.tgz
# cd memcache-2.2.4

找phpize

#whereis phpize

本机是/usr/bin/phpize

# /usr/bin/phpize
# ./configure –with-php-config=/usr/local/php/bin/php-config #自己的配置文件位置
# make
# make install

在php.ini文件添加一行
php.ini在/etc下
extension=memcache.so
重启httpd
#service httpd restart

关于memecache重启的一些参数
启动和停止Memcache的服务器端：
# /usr/local/bin/memcached -d -m 200 -u root -l 127.0.0.1 -p 11211-c 1000 -P /tmp/memcached.pid

相关解释如下：
-d选项是启动一个守护进程，
-m是分配给Memcache使用的内存数量，单位是MB，这里是200MB
-u是运行Memcache的用户，我这里是root
-l是监听的服务器IP地址，如果有多个地址的话，我这里指定了服务器的IP地址
-p是设置Memcache监听的端口，最好是1024以上的端口
-c选项是最大运行的并发连接数，默认是1024，我这里设置了256
-P是设置保存Memcache的pid文件，我这里是保存在 /tmp/memcached.pid
测试一下

<?php
$mem = new Memcache;
$mem->connect("127.0.0.1", 11211);
$mem->set('key', 'This is a test!', 0, 60);  //key var 是否压缩, 过期时间
$val = $mem->get('key');
echo $val;
?>

至此就可以通过phpinfo()看到redis和memcached的扩展信息了！

性能优化总是一个需要时间和经验积累的问题，这里先摘抄下前人的经验，之后再做自己的总结。
一
一般来说,解决WEB高并发的有效手段都是采用可线性扩展的多层分布式架构，
Webserver (Nginx) ：
这一层是可以轻松分布式部署的，结合智能DNS解析可以简易地防止单点故障、实现区域访问加速，结合LVS很容易实现负载均衡。这一层主要是负责处理静态请求和转发PHP请求至第二层的PHP处理节点，至于静态资源地址(http://misc.xxxx.com)可以单独拿出来部署，或者直接使用商用的云存储服务（国内七牛不错，国外有Amazon S3）
PHP处理节点：
一个节点其实就是一个监听特定端口的系统进程，webserver的请求通过负载均衡器（我用的AWS的loadbalancer)进行分发，很好实现分布式和负载均衡。我现在用的还是php自带的php-fpm,其实facebook出的hhvm性能非常强悍，但是还不能100%通过我项目的单元测试，等hhvm成熟过后可以平滑替换
高速缓存：
用的memcached，这一层的作用主要是减轻数据库IO和加快热数据访问，缓存策略与程序耦合度较高，不赘述，但简单地说有两种方式，一种是在程序的全局层面加一个缓存处理，这种方法代码耦合度低，但是有效命中率不高，有些项目不一定适应，另一种是在具体的数据存取处加缓存处理，这种办法程序耦合度较高，但是缓存命中率非常高，几乎没有无效缓存存在，我用的是这种。
数据库 ：
我现在的项目数据规模不大，暂时只用了单台数据库，但是程序逻辑上已做好了数据库线性扩展的准备。其实数据库层的扩展是老生常谈了，常用手段是分库分表，这一块需要在前期的代码就打下基础，另外更平滑地手段是使用中间件，比如360的Atlas，阿里巴巴的cobar，淘宝的TDDL，中间件可以在不大范围变更代码的情况下扩展，但是具体的使用场景还是有限的，具体项目还需单独考察。
其他：
根据不同的项目，架构还可以选择性地使用队列，我现在用的beantalkd，Redis也是一个很好的选择。队列常用的使用环境是邮件发送和站内消息推送上面，但是在某些场景下也可以作为核心数据库的缓冲，对应对大并发或者突发性流量也是不错的选择
二
以下的架构都是在假设已经优化过linux内核的情况下进行

初级篇：（单机模式）

假设配置：（Dual core 2.0GHz,4GB ram,SSD）

基础框架：apache(PHP) + Mysql / IIS + MSSQL
（最基础框架，处理一般访问请求）

进阶1：替换Apache为Nginx，并在数据库前加上cache层【数据库的速度是最大的瓶颈】
Nginx(PHP) + Memcache + Mysql
（此时已经具备处理小型访问量的能力）

进阶2：随着访问量的上涨，最先面临的问题就来了：CGI无法匹配上Nginx的高IO性能，这时候可以通过写扩展来替代脚本程序来提升性能，C扩展是个好办法，但是大家更喜欢用简单的脚本语言完成任务，Taobao团队开源了一个Nginx_lua模块，可以用lua写Nginx扩展，这时候可处理的并发已经超越进阶1 一个档次了。
Nginx(nginx_lua or C) + Memcache + Mysql
（此时处理个同时在线三四千人没有问题了）

进阶3：随着用户的增多，Mysql的写入速度成了又一大瓶颈，读取有memcache做缓存，但写入是直接面对Mysql，性能受到了很大阻碍，这时候，要在Nginx和Mysql中间加入一层写缓存，队列系统就出场了,就以RabbitMQ为例，所有写入操作全部丢到这只兔子的胃里面，然后屁股后面写个接应程序，一条条的拉出来再写入mysql。而RabbitMQ的写入效率是Mysql的N倍，此时架构的处理能力又上一阶层。
|—-write——>RabbitMQ——–
Nginx（lua or c）—– |———>Mysql
|—-read——>Memcache——–

(此时的并发吞吐能力已经可以处理万人左右在线)

中级篇：（分而治之）

此时我们在单机优化上已经算是达到极限，接下来就要集群来显示作用了。

数据库篇： 数据库总是在整个环节中是吞吐能力最弱的，最常见的方法就是sharding。
sharding可以按多种方法来分，没有定式，看情况。可以按用户ID区段分，按读写分等等，可用参考软件：mysql proxy（工作原理类似lvs）

缓存篇：memcache一般采用的是构建memcache pool，将缓存分散到多台memcache节点上，如何将缓存数据均匀分散在各节点，一般采用将各节点顺序编号，然后hash取余对应到各个节点上去。这样可以做到比较均匀的分散，但是有一个致命点就是，如果节点数增加或减少，将会带来几乎80%的数据迁移，解决方案我们在高级篇再提。

WEB服务器篇： web服务器集群的建设，最常见的就是lvs方式(memcache pool同样可以如此组建)，lvs的核心就是调度节点，调度节点负责将流量通过算法分散到各个节点上，因调度所耗资源很少，所以可以产生很高的吞吐率，后台节点数量可以任意增删，但此法弊病就是如果调度节点挂了，则整个集群都挂了，解决方案我们在高级篇提。

高级篇：（高可用性+高可扩展性的集群）

单点调度故障解决：
集群的好处显而易见，但是有一个弊端就是单节点进行调度，如果节点出现故障，则整个集群全部都无法服务，对此的解决方案，我们使用keepalived来解决。Keepalived for Linux
keepalived是基于VRRP协议（VRRP协议介绍）的，请一定先了解VRRP协议后再进行配置。
keepalived可以把多台设备虚拟出一个IP，并自动在故障节点与备用节点之间实现failover切换。这样我们配置两台货多台lvs调度节点，然后配置好keepalived就可以做到lvs调度节点出现故障后，自动切换到备用调度节点。（同样适用于mysql）

memcache集群扩展解决：
memcache因为我们一般采用的都是hash后除以节点数取余，然后分配到对应节点上，如果节点数出现变化，以前的缓存数据将基本都不能命中。

一 背景
网上有的说，fastcgi是一个协议，php-fpm实现了这个协议； 有的说，php-fpm是fastcgi进程的管理器，用来管理fastcgi进程的； 有的说，php-fpm是php内核的一个补丁; 有的说，修改了php.ini配置文件后，没办法平滑重启，所以就诞生了php-fpm； 还有的说PHP-CGI是PHP自带的FastCGI管理器，那这样的话干吗又弄个php-fpm出来
二 回答
首先，CGI是干嘛的？CGI是为了保证web server传递过来的数据是标准格式的，方便CGI程序的编写者。

web server（比如说nginx）只是内容的分发者。比如，如果请求/index.html，那么web server会去文件系统中找到这个文件，发送给浏览器，这里分发的是静态数据。好了，如果现在请求的是/index.php，根据配置文件，nginx知道这个不是静态文件，需要去找PHP解析器来处理，那么他会把这个请求简单处理后交给PHP解析器。Nginx会传哪些数据给PHP解析器呢？url要有吧，查询字符串也得有吧，POST数据也要有，HTTP header不能少吧，好的，CGI就是规定要传哪些数据、以什么样的格式传递给后方处理这个请求的协议。仔细想想，你在PHP代码中使用的用户从哪里来的。

当web server收到/index.php这个请求后，会启动对应的CGI程序，这里就是PHP的解析器。接下来PHP解析器会解析php.ini文件，初始化执行环境，然后处理请求，再以规定CGI规定的格式返回处理后的结果，退出进程。web server再把结果返回给浏览器。
好了，CGI是个协议，跟进程什么的没关系。那fastcgi又是什么呢？Fastcgi是用来提高CGI程序性能的。

提高性能，那么CGI程序的性能问题在哪呢？”PHP解析器会解析php.ini文件，初始化执行环境”，就是这里了。标准的CGI对每个请求都会执行这些步骤（不闲累啊！启动进程很累的说！），所以处理每个时间的时间会比较长。这明显不合理嘛！那么Fastcgi是怎么做的呢？首先，Fastcgi会先启一个master，解析配置文件，初始化执行环境，然后再启动多个worker。当请求过来时，master会传递给一个worker，然后立即可以接受下一个请求。这样就避免了重复的劳动，效率自然是高。而且当worker不够用时，master可以根据配置预先启动几个worker等着；当然空闲worker太多时，也会停掉一些，这样就提高了性能，也节约了资源。这就是fastcgi的对进程的管理。
那PHP-FPM又是什么呢？是一个实现了Fastcgi的程序，被PHP官方收了。

大家都知道，PHP的解释器是php-cgi。php-cgi只是个CGI程序，他自己本身只能解析请求，返回结果，不会进程管理（皇上，臣妾真的做不到啊！）所以就出现了一些能够调度php-cgi进程的程序，比如说由lighthttpd分离出来的spawn-fcgi。好了PHP-FPM也是这么个东东，在长时间的发展后，逐渐得到了大家的认可（要知道，前几年大家可是抱怨PHP-FPM稳定性太差的），也越来越流行。
好了，最后来回来你的问题。

网上有的说，fastcgi是一个协议，php-fpm实现了这个协议
对。

有的说，php-fpm是fastcgi进程的管理器，用来管理fastcgi进程的
对。php-fpm的管理对象是php-cgi。但不能说php-fpm是fastcgi进程的管理器，因为前面说了fastcgi是个协议，似乎没有这么个进程存在，就算存在php-fpm也管理不了他（至少目前是）。

有的说，php-fpm是php内核的一个补丁
以前是对的。因为最开始的时候php-fpm没有包含在PHP内核里面，要使用这个功能，需要找到与源码版本相同的php-fpm对内核打补丁，然后再编译。后来PHP内核集成了PHP-FPM之后就方便多了，使用–enalbe-fpm这个编译参数即可。

有的说，修改了php.ini配置文件后，没办法平滑重启，所以就诞生了php-fpm
是的，修改php.ini之后，php-cgi进程的确是没办法平滑重启的。php-fpm对此的处理机制是新的worker用新的配置，已经存在的worker处理完手上的活就可以歇着了，通过这种机制来平滑过度。
还有的说PHP-CGI是PHP自带的FastCGI管理器，那这样的话干吗又弄个php-fpm出

不对。php-cgi只是解释PHP脚本的程序而已。

php-cgi与php-fpm一样，也是一个fastcgi进程管理器，php-cgi的问题在于 1、php-cgi变更php.ini配置后需重启php-cgi才能让新的php-ini生效，不可以平滑重启 2、直接杀死php-cgi进程,php就不能运行了。(PHP-FPM和Spawn-FCGI就没有这个问题,守护进程会平滑从新生成新的子进程。） 针对php-cgi的不足，php-fpm应运而生。