[转]Yii PHP 框架分析

原文链接:http://bbs.phpchina.com/thread-194123-1-1.html
1. 启动

网站的唯一入口程序 index.php :

$yii=dirname(__FILE__).’/../framework/yii.php’;
$config=dirname(__FILE__).’/protected/config/main.php’;

// remove the following line when in production mode
defined(‘YII_DEBUG’) or define(‘YII_DEBUG’,true);

require_once($yii);
Yii::createWebApplication($config)->run();
复制代码

上面的require_once($yii) 引用出了后面要用到的全局类Yii,Yii类是YiiBase类的完全继承:

class Yii extends YiiBase
{
}
复制代码

系统的全局访问都是通过Yii类(即YiiBase类)来实现的,Yii类的成员和方法都是static类型。

2. 类加载

Yii利用PHP5提供的spl库来完成类的自动加载。在YiiBase.php 文件结尾处

spl_autoload_register(array(‘YiiBase’,’autoload’));
复制代码

将YiiBase类的静态方法autoload 注册为类加载器。 PHP autoload 的简单原理就是执行 new 创建对象或通过类名访问静态成员时,系统将类名传递给被注册的类加载器函数,类加载器函数根据类名自行找到对应的类文件并include 。

下面是YiiBase类的autoload方法:

public static function autoload($className)
{
// use include so that the error PHP file may appear
if(isset(self::$_coreClasses[$className]))
include(YII_PATH.self::$_coreClasses[$className]);
else if(isset(self::$_classes[$className]))
include(self::$_classes[$className]);
else
include($className.’.php’);
}
复制代码

可以看到YiiBase的静态成员$_coreClasses 数组里预先存放着Yii系统自身用到的类对应的文件路径:

private static $_coreClasses=array(
‘CApplication’ => ‘/base/CApplication.php’,
‘CBehavior’ => ‘/base/CBehavior.php’,
‘CComponent’ => ‘/base/CComponent.php’,

)
复制代码

非 coreClasse 的类注册在YiiBase的$_classes 数组中:
private static $_classes=array();

其他的类需要用Yii::import()讲类路径导入PHP include paths 中,直接
include($className.’.php’)

3. CWebApplication的创建

回到前面的程序入口的 Yii::createWebApplication($config)->run();

public static function createWebApplication($config=null)
{
return new CWebApplication($config);
}
复制代码

现在autoload机制开始工作了。
当系统 执行 new CWebApplication() 的时候,会自动
include(YII_PATH.’/base/CApplication.php’)

将main.php里的配置信息数组$config传递给CWebApplication创建出对象,并执行对象的run() 方法启动框架。

CWebApplication类的继承关系

CWebApplication -> CApplication -> CModule -> CComponent

$config先被传递给CApplication的构造函数

public function __construct($config=null)
{
Yii::setApplication($this);

// set basePath at early as possible to avoid trouble
if(is_string($config))
$config=require($config);
if(isset($config[‘basePath’]))
{
$this->setBasePath($config[‘basePath’]);
unset($config[‘basePath’]);
}
else
$this->setBasePath(‘protected’);
Yii::setPathOfAlias(‘application’,$this->getBasePath());
Yii::setPathOfAlias(‘webroot’,dirname($_SERVER[‘SCRIPT_FILENAME’]));

$this->preinit();

$this->initSystemHandlers();
$this->registerCoreComponents();

$this->configure($config);
$this->attachBehaviors($this->behaviors);
$this->preloadComponents();

$this->init();
}
复制代码

Yii::setApplication($this); 将自身的实例对象赋给Yii的静态成员$_app,以后可以通过 Yii::app() 来取得。
后面一段是设置CApplication 对象的_basePath ,指向 proteced 目录。

Yii::setPathOfAlias(‘application’,$this->getBasePath());
Yii::setPathOfAlias(‘webroot’,dirname($_SERVER[‘SCRIPT_FILENAME’]));
复制代码

设置了两个系统路径别名 application 和 webroot,后面再import的时候可以用别名来代替实际的完整路径。别名配置存放在YiiBase的 $_aliases 数组中。

$this->preinit();
预初始化。preinit()是在 CModule 类里定义的,没有任何动作。

$this->initSystemHandlers() 方法内容:

/**
* Initializes the class autoloader and error handlers.
*/
protected function initSystemHandlers()
{
if(YII_ENABLE_EXCEPTION_HANDLER)
set_exception_handler(array($this,’handleException’));
if(YII_ENABLE_ERROR_HANDLER)
set_error_handler(array($this,’handleError’),error_reporting());
}
复制代码

设置系统exception_handler和 error_handler,指向对象自身提供的两个方法。

4. 注册核心组件

$this->registerCoreComponents();
代码如下:

protected function registerCoreComponents()
{
parent::registerCoreComponents();

$components=array(
‘urlManager’=>array(
‘class’=>’CUrlManager’,
),
‘request’=>array(
‘class’=>’CHttpRequest’,
),
‘session’=>array(
‘class’=>’CHttpSession’,
),
‘assetManager’=>array(
‘class’=>’CAssetManager’,
),
‘user’=>array(
‘class’=>’CWebUser’,
),
‘themeManager’=>array(
‘class’=>’CThemeManager’,
),
‘authManager’=>array(
‘class’=>’CPhpAuthManager’,
),
‘clientScript’=>array(
‘class’=>’CClientScript’,
),
);

$this->setComponents($components);
}
复制代码

注册了几个系统组件(Components)。
Components 是在 CModule 里定义和管理的,主要包括两个数组

private $_components=array();
private $_componentConfig=array();
复制代码

每个 Component 都是 IApplicationComponent接口的实例,Componemt的实例存放在$_components 数组里,相关的配置信息存放在$_componentConfig数组里。配置信息包括Component 的类名和属性设置。

CWebApplication 对象注册了以下几个Component:urlManager, request,session,assetManager,user,themeManager,authManager,clientScript。CWebApplication的parent 注册了以下几个Component:coreMessages,db,messages,errorHandler,securityManager,statePersister。

Component 在YiiPHP里是个非常重要的东西,它的特征是可以通过 CModule 的 __get() 和 __set() 方法来访问。 Component 注册的时候并不会创建对象实例,而是在程序里被第一次访问到的时候,由CModule 来负责(实际上就是 Yii::app())创建。

5. 处理 $config 配置

继续, $this->configure($config);
configure() 还是在CModule 里:

public function configure($config)
{
if(is_array($config))
{
foreach($config as $key=>$value)
$this->$key=$value;
}
}
复制代码

实际上是把$config数组里的每一项传给 CModule 的 父类 CComponent __set() 方法。

public function __set($name,$value)
{
$setter=’set’.$name;
if(method_exists($this,$setter))
$this->$setter($value);
else if(strncasecmp($name,’on’,2)===0
&& method_exists($this,$name))
{
//duplicating getEventHandlers() here for performance
$name=strtolower($name);
if(!isset($this->_e[$name]))
$this->_e[$name]=new CList;
$this->_e[$name]->add($value);
}
else if(method_exists($this,’get’.$name))
throw new CException(Yii::t(‘yii’,’Property “{class}.{property}” is read only.’,
array(‘{class}’=>get_class($this), ‘{property}’=>$name)));
else
throw new CException(Yii::t(‘yii’,’Property “{class}.{property}” is not defined.’,
array(‘{class}’=>get_class($this), ‘{property}’=>$name)));
}
}
复制代码

我们来看看:
if(method_exists($this,$setter))
根据这个条件,$config 数组里的basePath, params, modules, import, components 都被传递给相应的 setBasePath(), setParams() 等方法里进行处理。

6、$config 之 import

其中 import 被传递给 CModule 的 setImport:

public function setImport($aliases)
{
foreach($aliases as $alias)
Yii::import($alias);
}
复制代码

Yii::import($alias)里的处理:

public static function import($alias,$forceInclude=false)
{
// 先判断$alias是否存在于YiiBase::$_imports[] 中,已存在的直接return, 避免重复import。
if(isset(self::$_imports[$alias])) // previously imported
return self::$_imports[$alias];

// $alias类已定义,记入$_imports[],直接返回
if(class_exists($alias,false))
return self::$_imports[$alias]=$alias;

// 类似 urlManager 这样的已定义于$_coreClasses[]的类,或不含.的直接类名,记入$_imports[],直接返回
if(isset(self::$_coreClasses[$alias]) || ($pos=strrpos($alias,’.’))===false) // a simple class name
{
self::$_imports[$alias]=$alias;
if($forceInclude)
{
if(isset(self::$_coreClasses[$alias])) // a core class
require(YII_PATH.self::$_coreClasses[$alias]);
else
require($alias.’.php’);
}
return $alias;
}

// 产生一个变量 $className,为$alias最后一个.后面的部分
// 这样的:’x.y.ClassNamer’
// $className不等于 ‘*’, 并且ClassNamer类已定义的, ClassNamer’ 记入 $_imports[],直接返回
if(($className=(string)substr($alias,$pos+1))!==’*’ && class_exists($className,false))
return self::$_imports[$alias]=$className;

// 取得 $alias 里真实的路径部分并且路径有效
if(($path=self::getPathOfAlias($alias))!==false)
{
// $className!==’*’,$className 记入 $_imports[]
if($className!==’*’)
{
self::$_imports[$alias]=$className;
if($forceInclude)
require($path.’.php’);
else
self::$_classes[$className]=$path.’.php’;
return $className;
}
// $alias是’system.web.*’这样的已*结尾的路径,将路径加到include_path中
else // a directory
{
set_include_path(get_include_path().PATH_SEPARATOR.$path);
return self::$_imports[$alias]=$path;
}
}
else
throw new CException(Yii::t(‘yii’,’Alias “{alias}” is invalid. Make sure it points to an existing directory or file.’,
array(‘{alias}’=>$alias)));
}
复制代码

7. $config 之 components

$config 数组里的 $components 被传递给CModule 的setComponents($components)

public function setComponents($components)
{
foreach($components as $id=>$component)
{
if($component instanceof IApplicationComponent)
$this->setComponent($id,$component);
else if(isset($this->_componentConfig[$id]))
$this->_componentConfig[$id]=CMap::mergeArray($this->_componentConfig[$id],$component);
else
$this->_componentConfig[$id]=$component;
}
}
复制代码

$componen是IApplicationComponen的实例的时候,直接赋值:
$this->setComponent($id,$component),

public function setComponent($id,$component)
{
$this->_components[$id]=$component;
if(!$component->getIsInitialized())
$component->init();
}
复制代码

如果$id已存在于_componentConfig[]中(前面注册的coreComponent),将$component 属性加进入。
其他的component将component属性存入_componentConfig[]中。

8. $config 之 params

这个很简单

public function setParams($value)
{
$params=$this->getParams();
foreach($value as $k=>$v)
$params->add($k,$v);
}
复制代码

configure 完毕!

9. attachBehaviors

$this->attachBehaviors($this->behaviors);
空的,没动作

预创建组件对象

$this->preloadComponents();

protected function preloadComponents()
{
foreach($this->preload as $id)
$this->getComponent($id);
}
复制代码

getComponent() 判断_components[] 数组里是否有 $id的实例,如果没有,就根据_componentConfig[$id]里的配置来创建组件对象,调用组件的init()方法,然后存入_components[$id]中。

10. init()

$this->init();

函数内:$this->getRequest();
创建了Reques 组件并初始化。

11. run()

public function run()
{
$this->onBeginRequest(new CEvent($this));
$this->processRequest();
$this->onEndRequest(new CEvent($this));
}

[转]Linux netstat命令详解


原文链接:http://www.cnblogs.com/ggjucheng/archive/2012/01/08/2316661.html
简介
Netstat 命令用于显示各种网络相关信息,如网络连接,路由表,接口状态 (Interface Statistics),masquerade 连接,多播成员 (Multicast Memberships) 等等。

输出信息含义
执行netstat后,其输出结果为

复制代码
Active Internet connections (w/o servers)
Proto Recv-Q Send-Q Local Address Foreign Address State
tcp 0 2 210.34.6.89:telnet 210.34.6.96:2873 ESTABLISHED
tcp 296 0 210.34.6.89:1165 210.34.6.84:netbios-ssn ESTABLISHED
tcp 0 0 localhost.localdom:9001 localhost.localdom:1162 ESTABLISHED
tcp 0 0 localhost.localdom:1162 localhost.localdom:9001 ESTABLISHED
tcp 0 80 210.34.6.89:1161 210.34.6.10:netbios-ssn CLOSE

Active UNIX domain sockets (w/o servers)
Proto RefCnt Flags Type State I-Node Path
unix 1 [ ] STREAM CONNECTED 16178 @000000dd
unix 1 [ ] STREAM CONNECTED 16176 @000000dc
unix 9 [ ] DGRAM 5292 /dev/log
unix 1 [ ] STREAM CONNECTED 16182 @000000df
复制代码

从整体上看,netstat的输出结果可以分为两个部分:

一个是Active Internet connections,称为有源TCP连接,其中”Recv-Q”和”Send-Q”指%0A的是接收队列和发送队列。这些数字一般都应该是0。如果不是则表示软件包正在队列中堆积。这种情况只能在非常少的情况见到。

另一个是Active UNIX domain sockets,称为有源Unix域套接口(和网络套接字一样,但是只能用于本机通信,性能可以提高一倍)。
Proto显示连接使用的协议,RefCnt表示连接到本套接口上的进程号,Types显示套接口的类型,State显示套接口当前的状态,Path表示连接到套接口的其它进程使用的路径名。

常见参数
-a (all)显示所有选项,默认不显示LISTEN相关
-t (tcp)仅显示tcp相关选项
-u (udp)仅显示udp相关选项
-n 拒绝显示别名,能显示数字的全部转化成数字。
-l 仅列出有在 Listen (监听) 的服務状态

-p 显示建立相关链接的程序名
-r 显示路由信息,路由表
-e 显示扩展信息,例如uid等
-s 按各个协议进行统计
-c 每隔一个固定时间,执行该netstat命令。

提示:LISTEN和LISTENING的状态只有用-a或者-l才能看到

实用命令实例

1. 列出所有端口 (包括监听和未监听的)
列出所有端口 netstat -a

复制代码
# netstat -a | more
Active Internet connections (servers and established)
Proto Recv-Q Send-Q Local Address Foreign Address State
tcp 0 0 localhost:30037 *:* LISTEN
udp 0 0 *:bootpc *:*

Active UNIX domain sockets (servers and established)
Proto RefCnt Flags Type State I-Node Path
unix 2 [ ACC ] STREAM LISTENING 6135 /tmp/.X11-unix/X0
unix 2 [ ACC ] STREAM LISTENING 5140 /var/run/acpid.socket
复制代码
列出所有 tcp 端口 netstat -at

复制代码
# netstat -at
Active Internet connections (servers and established)
Proto Recv-Q Send-Q Local Address Foreign Address State
tcp 0 0 localhost:30037 *:* LISTEN
tcp 0 0 localhost:ipp *:* LISTEN
tcp 0 0 *:smtp *:* LISTEN
tcp6 0 0 localhost:ipp [::]:* LISTEN
复制代码
列出所有 udp 端口 netstat -au

# netstat -au
Active Internet connections (servers and established)
Proto Recv-Q Send-Q Local Address Foreign Address State
udp 0 0 *:bootpc *:*
udp 0 0 *:49119 *:*
udp 0 0 *:mdns *:*

2. 列出所有处于监听状态的 Sockets
只显示监听端口 netstat -l

# netstat -l
Active Internet connections (only servers)
Proto Recv-Q Send-Q Local Address Foreign Address State
tcp 0 0 localhost:ipp *:* LISTEN
tcp6 0 0 localhost:ipp [::]:* LISTEN
udp 0 0 *:49119 *:*
只列出所有监听 tcp 端口 netstat -lt

# netstat -lt
Active Internet connections (only servers)
Proto Recv-Q Send-Q Local Address Foreign Address State
tcp 0 0 localhost:30037 *:* LISTEN
tcp 0 0 *:smtp *:* LISTEN
tcp6 0 0 localhost:ipp [::]:* LISTEN
只列出所有监听 udp 端口 netstat -lu

# netstat -lu
Active Internet connections (only servers)
Proto Recv-Q Send-Q Local Address Foreign Address State
udp 0 0 *:49119 *:*
udp 0 0 *:mdns *:*
只列出所有监听 UNIX 端口 netstat -lx

复制代码
# netstat -lx
Active UNIX domain sockets (only servers)
Proto RefCnt Flags Type State I-Node Path
unix 2 [ ACC ] STREAM LISTENING 6294 private/maildrop
unix 2 [ ACC ] STREAM LISTENING 6203 public/cleanup
unix 2 [ ACC ] STREAM LISTENING 6302 private/ifmail
unix 2 [ ACC ] STREAM LISTENING 6306 private/bsmtp
复制代码

3. 显示每个协议的统计信息
显示所有端口的统计信息 netstat -s

复制代码
# netstat -s
Ip:
11150 total packets received
1 with invalid addresses
0 forwarded
0 incoming packets discarded
11149 incoming packets delivered
11635 requests sent out
Icmp:
0 ICMP messages received
0 input ICMP message failed.
Tcp:
582 active connections openings
2 failed connection attempts
25 connection resets received
Udp:
1183 packets received
4 packets to unknown port received.
…..
复制代码
显示 TCP 或 UDP 端口的统计信息 netstat -st 或 -su

# netstat -st
# netstat -su

4. 在 netstat 输出中显示 PID 和进程名称 netstat -p
netstat -p 可以与其它开关一起使用,就可以添加 “PID/进程名称” 到 netstat 输出中,这样 debugging 的时候可以很方便的发现特定端口运行的程序。

# netstat -pt
Active Internet connections (w/o servers)
Proto Recv-Q Send-Q Local Address Foreign Address State PID/Program name
tcp 1 0 ramesh-laptop.loc:47212 192.168.185.75:www CLOSE_WAIT 2109/firefox
tcp 0 0 ramesh-laptop.loc:52750 lax:www ESTABLISHED 2109/firefox
5. 在 netstat 输出中不显示主机,端口和用户名 (host, port or user)
当你不想让主机,端口和用户名显示,使用 netstat -n。将会使用数字代替那些名称。

同样可以加速输出,因为不用进行比对查询。

# netstat -an
如果只是不想让这三个名称中的一个被显示,使用以下命令

# netsat -a –numeric-ports
# netsat -a –numeric-hosts
# netsat -a –numeric-users

6. 持续输出 netstat 信息
netstat 将每隔一秒输出网络信息。

复制代码
# netstat -c
Active Internet connections (w/o servers)
Proto Recv-Q Send-Q Local Address Foreign Address State
tcp 0 0 ramesh-laptop.loc:36130 101-101-181-225.ama:www ESTABLISHED
tcp 1 1 ramesh-laptop.loc:52564 101.11.169.230:www CLOSING
tcp 0 0 ramesh-laptop.loc:43758 server-101-101-43-2:www ESTABLISHED
tcp 1 1 ramesh-laptop.loc:42367 101.101.34.101:www CLOSING
^C
复制代码

7. 显示系统不支持的地址族 (Address Families)
netstat –verbose
在输出的末尾,会有如下的信息

netstat: no support for `AF IPX’ on this system.
netstat: no support for `AF AX25′ on this system.
netstat: no support for `AF X25′ on this system.
netstat: no support for `AF NETROM’ on this system.

8. 显示核心路由信息 netstat -r
# netstat -r
Kernel IP routing table
Destination Gateway Genmask Flags MSS Window irtt Iface
192.168.1.0 * 255.255.255.0 U 0 0 0 eth2
link-local * 255.255.0.0 U 0 0 0 eth2
default 192.168.1.1 0.0.0.0 UG 0 0 0 eth2
注意: 使用 netstat -rn 显示数字格式,不查询主机名称。

9. 找出程序运行的端口
并不是所有的进程都能找到,没有权限的会不显示,使用 root 权限查看所有的信息。

# netstat -ap | grep ssh
tcp 1 0 dev-db:ssh 101.174.100.22:39213 CLOSE_WAIT –
tcp 1 0 dev-db:ssh 101.174.100.22:57643 CLOSE_WAIT –
找出运行在指定端口的进程

# netstat -an | grep ‘:80’

10. 显示网络接口列表
# netstat -i
Kernel Interface table
Iface MTU Met RX-OK RX-ERR RX-DRP RX-OVR TX-OK TX-ERR TX-DRP TX-OVR Flg
eth0 1500 0 0 0 0 0 0 0 0 0 BMU
eth2 1500 0 26196 0 0 0 26883 6 0 0 BMRU
lo 16436 0 4 0 0 0 4 0 0 0 LRU
显示详细信息,像是 ifconfig 使用 netstat -ie:

复制代码
# netstat -ie
Kernel Interface table
eth0 Link encap:Ethernet HWaddr 00:10:40:11:11:11
UP BROADCAST MULTICAST MTU:1500 Metric:1
RX packets:0 errors:0 dropped:0 overruns:0 frame:0
TX packets:0 errors:0 dropped:0 overruns:0 carrier:0
collisions:0 txqueuelen:1000
RX bytes:0 (0.0 B) TX bytes:0 (0.0 B)
Memory:f6ae0000-f6b00000
复制代码

11. IP和TCP分析
查看连接某服务端口最多的的IP地址

复制代码
wss8848@ubuntu:~$ netstat -nat | grep “192.168.1.15:22” |awk ‘{print $5}’|awk -F: ‘{print $1}’|sort|uniq -c|sort -nr|head -20
18 221.136.168.36
3 154.74.45.242
2 78.173.31.236
2 62.183.207.98
2 192.168.1.14
2 182.48.111.215
2 124.193.219.34
2 119.145.41.2
2 114.255.41.30
1 75.102.11.99
复制代码
TCP各种状态列表

复制代码
wss8848@ubuntu:~$ netstat -nat |awk ‘{print $6}’
established)
Foreign
LISTEN
TIME_WAIT
ESTABLISHED
TIME_WAIT
SYN_SENT
复制代码
先把状态全都取出来,然后使用uniq -c统计,之后再进行排序。
复制代码
wss8848@ubuntu:~$ netstat -nat |awk ‘{print $6}’|sort|uniq -c
143 ESTABLISHED
1 FIN_WAIT1
1 Foreign
1 LAST_ACK
36 LISTEN
6 SYN_SENT
113 TIME_WAIT
1 established)
复制代码
最后的命令如下:
netstat -nat |awk ‘{print $6}’|sort|uniq -c|sort -rn
分析access.log获得访问前10位的ip地址
awk ‘{print $1}’ access.log |sort|uniq -c|sort -nr|head -10

[Laravel5.1]学习笔记(二)–建立第一个Laravel页面

之前按照laravel 5.1搭建了开发环境,现在开始建立第一个页面。
(一)创建controller
在/app/Http/Controllers下建立第一个Controller,这里我命名为HomeController.php,内容如下:

namespace App\Http\Controllers;

use App\Http\Controllers\Controller;

class HomeController extends Controller
{

    public function getIndex() {
    
        echo "hello laravel";
    }   

    public function getTest() {
        return view('test', ['name' => 'MrCat']);
    }   

}

(二)配置路由
在/app/Http下修改routes.php文件,按照laravel的开发文档,routes支持支持的功能非常强大,但是我还是喜欢MVC的模式,将逻辑放在Controller层

Route::controller('home', 'HomeController');

(三)添加view
view放在/resources/views下,默认采用的是blade模板,熟悉smarty的同学肯定比较容易上手,这里就解析是@yield和@section:
模板用 @yield 和 @section 分别定义了一个区块,然后在子模板中去定义内容,由于 @yield 不能被扩展,所以即使加上了 @parent 也不起作用,输出的内容只有“新模板的内容”。而 @section 定义的部分,由于使用了 @parent 关键字,父模板中的内容会被保留,然后再扩展后添加的内容进去,输出的内容会是 “默认的内容 扩展的内容”。实例如下:
首先建立main.blade.php


<!DOCTYPE html>
<html>
<head>
</head>
<body>
    <h1>My Test Meau</h1>
    @yield('title')

    @section('content')
    <p>this is section</p>
    @show

</body>
</html>

之后建立test.blade.php, 继承main

@extends('main')

@section('title')
<p>this is new title</p>
@stop

@section('content')
@parent
<p>this is new content</p>
<p>this is my name {{$name}}</p>
@stop

之后访问http://localhost/home/test/就可以出现预定于页面的内容了:

[Laravel5.1]学习笔记(一)–安装与使用

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]命名空间

命名空间在某些框架下很少使用,但是在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还能用吗?

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,效率不会很高。而上面的分布式方法,也可以用于单机版本,也就是将总的数据根据值的范围,划分成多个不同的子文件,然后逐个处理。处理完毕之后再对这些单词的及其出现频率进行一个归并。实际上就可以利用一个外排序的归并过程。
  另外还可以考虑近似计算,也就是我们可以通过结合自然语言属性,只将那些真正实际中出现最多的那些词作为一个字典,使得这个规模可以放入内存。

[转]LSM树由来、设计思想以及应用到HBase的索引

原文链接: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]sae上使用文件存储系统Storage

前言
在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表单,可以上传文件即可
例如

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

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

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

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