Hasing algorithm
วันนี้ขอพูดเรื่อง performance อีกสักที สำหรับคนที่เคยจับ application ที่ใหญ่ๆ หน่อย ที่มีจำนวน file upload มหาศาล หรือ เอาง่ายๆ แค่หลัก 2-3 หมื่นขึ้นไป ก็จะเห็นได้ว่า หลังจากนั้น application จะทำงาน ค่อยๆ ช้าลงๆๆๆ จนในที่สุด ก็ทะลุ node ที่เป็น limit ของ UNIX ไป (จำไม่ได้ 5 หรือ 6 หมื่นนี่ล่ะ)
วิธีแก้ที่ดีที่สุดก็คือการ ซอย folder ออกเป็น ย่อยๆ เพื่อไม่ให้ไฟล์ ไปรวมกันอยู่ที่เดียว เช่น
แบบนี้ไฟล์ก็จะไม่รวมอยู่ที่เดียวกัน แต่ จะมีปัญหาตามมาว่า แล้วเราจะ บริหารจัดการยังไง T_T
ตรงนี้แหละที่ ต้องมี hashing algorithm แบบต่างๆ ขึ้นมา ผมจะลอง ไล่ไปดูทีละแบบละกัน
แบบที่นึง hash ตัวเลข
แบบนี้จะเป็นการ hash 2 level ง่ายๆ แต่ว่า ได้ผลดีทีเดียว โดยที่ ชั้นแรกจะ hash ได้สูงสุดถึง 25 ล้าน ก่อนที่จะสร้าง folder ใหม่ นั่นก็คือ ค่าตั้งแต่
1 - 25000000 จะถูกเก็บเข้า Folder 1 ถ้ามากกว่า จะถูกสร้าง Folder 2 ขึ้นมา ส่วนในชั้นที่ 2 จะถูกสร้าง folder มาสูงสุดตามที่เรากำหนดค่า max ลงไป โดยในที่นี้ก็จะมี 0001 - 5000
จากนั้น data ที่ลงท้ายด้วย 1 ก็จะจัดเก็บเข้า folder 1 และ เป็นอย่างนี้เรื่อยไป
วิธีนี้เหมาะกับการ hash ค่าอะไรก็ตามที่เป็นตัวเลข เช่น auto increment หารทำงานจะค่อนข้างดีทีเดียว เพราะ data จะค่อยๆ หยอดไปทีละ 1 และมีขนาดพอๆ กันเกือบทุก folder แต่ว่า มัน hash ได้เฉพาะ ตัวเลข ลองมาดูวิธีต่อมากัน
แบบที่ 2 hash โดยใช้ crc32
วิธี hash แบบนี้สาารถนำไป hash string ได้ด้วย โดยอาศัย ความสามารถของ CRC32 ซึ่งเป็น algorithm hash ในรูปแบบ 32-bit checksum โดยค่าที่เหมือนกัน จะได้ค่าเดียวกันเสมอ จากนั้น เอามาเข้า สมการเพื่อให้ได้ folder ไม่เกินตามที่เรากำหนด เราก็จะได้ สูตรง่ายๆ มาแล้ว อันนี้เอาไว้ hash แบบชั้นเดียวง่ายๆ แต่ใครอยากไป เพิ่ม level ก็เขียนต่อเอาครับ
แล้วก็วิธีสุดท้ายที่ผมจะแนะนำ โดยอันนี้ผมแกะออกมาก จาก Zend Cache ในส่วนของการ hash level
โดยคราวนี้เราจะใช้ algorithm adler32
หลักการก็โครตจะแสนง่าย แต่ว่า ปะสิทธิภาพค่อนข้างจะดี
สมมุติผมมี string คำว่า " I wanna be a star. "
พอทำการ hash
จากนั้นผมก็มาคำนวน level โดยถ้า 1 level ผมก็จะทำการ ตัด string ที่ตำแหน่งแรกออกมาสร้าง dir ย่อย ก็จะได้ผลลัพธ์ ออกมาดังนี้
ลอง save แล้วเอาไปประยุกต์ใช้งานดูนะครับ
วิธีแก้ที่ดีที่สุดก็คือการ ซอย folder ออกเป็น ย่อยๆ เพื่อไม่ให้ไฟล์ ไปรวมกันอยู่ที่เดียว เช่น
parent --
|- child1
|- child2
แบบนี้ไฟล์ก็จะไม่รวมอยู่ที่เดียวกัน แต่ จะมีปัญหาตามมาว่า แล้วเราจะ บริหารจัดการยังไง T_T
ตรงนี้แหละที่ ต้องมี hashing algorithm แบบต่างๆ ขึ้นมา ผมจะลอง ไล่ไปดูทีละแบบละกัน
แบบที่นึง hash ตัวเลข
function int_hash($no, $max=5000)
{
if (!is_numeric($no)) die('Value must be numeric');
$p0 = ceil($no / ($max * $max));
$p1 = ceil($no % $max);
return $p0.'/'.sprintf('%0'.strlen($max).'d', $p1);
}
แบบนี้จะเป็นการ hash 2 level ง่ายๆ แต่ว่า ได้ผลดีทีเดียว โดยที่ ชั้นแรกจะ hash ได้สูงสุดถึง 25 ล้าน ก่อนที่จะสร้าง folder ใหม่ นั่นก็คือ ค่าตั้งแต่
1 - 25000000 จะถูกเก็บเข้า Folder 1 ถ้ามากกว่า จะถูกสร้าง Folder 2 ขึ้นมา ส่วนในชั้นที่ 2 จะถูกสร้าง folder มาสูงสุดตามที่เรากำหนดค่า max ลงไป โดยในที่นี้ก็จะมี 0001 - 5000
จากนั้น data ที่ลงท้ายด้วย 1 ก็จะจัดเก็บเข้า folder 1 และ เป็นอย่างนี้เรื่อยไป
วิธีนี้เหมาะกับการ hash ค่าอะไรก็ตามที่เป็นตัวเลข เช่น auto increment หารทำงานจะค่อนข้างดีทีเดียว เพราะ data จะค่อยๆ หยอดไปทีละ 1 และมีขนาดพอๆ กันเกือบทุก folder แต่ว่า มัน hash ได้เฉพาะ ตัวเลข ลองมาดูวิธีต่อมากัน
แบบที่ 2 hash โดยใช้ crc32
function crc32_hash($key, $max=5000)
{
return (crc32($key) & 0x7fffffff) % $max;
}
วิธี hash แบบนี้สาารถนำไป hash string ได้ด้วย โดยอาศัย ความสามารถของ CRC32 ซึ่งเป็น algorithm hash ในรูปแบบ 32-bit checksum โดยค่าที่เหมือนกัน จะได้ค่าเดียวกันเสมอ จากนั้น เอามาเข้า สมการเพื่อให้ได้ folder ไม่เกินตามที่เรากำหนด เราก็จะได้ สูตรง่ายๆ มาแล้ว อันนี้เอาไว้ hash แบบชั้นเดียวง่ายๆ แต่ใครอยากไป เพิ่ม level ก็เขียนต่อเอาครับ
แล้วก็วิธีสุดท้ายที่ผมจะแนะนำ โดยอันนี้ผมแกะออกมาก จาก Zend Cache ในส่วนของการ hash level
โดยคราวนี้เราจะใช้ algorithm adler32
หลักการก็โครตจะแสนง่าย แต่ว่า ปะสิทธิภาพค่อนข้างจะดี
สมมุติผมมี string คำว่า " I wanna be a star. "
พอทำการ hash
hash('adler32', 'I wanna be a star.');
// ค่าที่ได้คือ ef050538จากนั้นผมก็มาคำนวน level โดยถ้า 1 level ผมก็จะทำการ ตัด string ที่ตำแหน่งแรกออกมาสร้าง dir ย่อย ก็จะได้ผลลัพธ์ ออกมาดังนี้
path: e/ef050538.hash
ถ้า 2 level ล่ะ
path: e/ef/ef050538.hash
และก็เป็นแบบนี้ไล่ๆ ไป ตามแต่ ที่เรากำหนด level
สำหรับวิธีนี้ node structure เราก็จะออกมาในรูปแบบ “สามเหลี่ยม” โดยยิ่งมี level มาก มันก็จะยิ่งซอยเยอะมาก แต่ว่า ถ้าเยอะมากไป มันก็เท่ากับว่า เราไม่ได้ hash อะไรเลย ดังนั้น สำหรับ application ระดับ กลาง – ใหญ่ ผมขอแนะนำที่ 2 level ก็พอครับ
สุดท้าย ผมเอา algorithm แบบที่ 3 มาเขียน ในรูปแบบ class เรียบร้อยแล้ว จะเอาไปใช้เลยก็ได้นะครับ โดยตัวอย่างที่ผมเอาไปใส่ไว้ ด้านล่างไฟล์ เป็นการทำ hash เพื่อ save text ธรรมดา ผมว่าเอาไป ประยุกต์ใช้งานกับระบบ cache หรือ file upload จะเห็นผลมากกว่า
<?php
/**
* Hashin library
* @Author Tee++;
* @Published 03/06/2009
*/
class Hashing {
var $parent_dir = ‘temp’;
var $prefix = "prefix_";
var $level = 2;
var $algorithm = ‘adler32′;
var $make_dir = TRUE;
// file tailer
var $show_file = TRUE;
var $extension = ‘hash’;
function do_hash($string)
{
$hashing = $this->hash_algorithm($string);
$path = $this->parent_dir;
if ($hash_dirs = $this->_path($hashing))
{
$path .= ‘/’.$hash_dirs;
if ($this->make_dir)
$this->_makePathRecursive($path);
}
if ($this->show_file)
{
$path .= ‘/’.$hashing.‘.’.$this->extension;
}
return $path;
}
function hash_algorithm($string)
{
return hash($this->algorithm, $string);
}
function _path($string)
{
if ($this->level <= 0)
{
return;
}
$directories = array();
for ($i=1; $i<=$this->level; $i++)
{
array_push($directories, $this->prefix.substr($string, 0, $i));
}
return implode(‘/’, $directories);
}
function _makePathRecursive($dir)
{
if (!is_dir($dir))
mkdir($dir, 0777, TRUE);
return TRUE;
}
}
/*
##### Example Usage #####
$string = "IWannaBeARockStar";
$hashing = new Hashing;
$path = $hashing->do_hash($string);
file_put_contents($path, $string);
*/
?>
ลอง save แล้วเอาไปประยุกต์ใช้งานดูนะครับ
0 comments