Hasing algorithm
วันนี้ขอพูดเรื่อง performance อีกสักที สำหรับคนที่เคยจับ application ที่ใหญ่ๆ หน่อย ที่มีจำนวน file upload มหาศาล หรือ เอาง่ายๆ แค่หลัก 2-3 หมื่นขึ้นไป ก็จะเห็นได้ว่า หลังจากนั้น application จะทำงาน ค่อยๆ ช้าลงๆๆๆ จนในที่สุด ก็ทะลุ node ที่เป็น limit ของ UNIX ไป (จำไม่ได้ 5 หรือ 6 หมื่นนี่ล่ะ)
วิธีแก้ที่ดีที่สุดก็คือการ ซอย folder ออกเป็น ย่อยๆ เพื่อไม่ให้ไฟล์ ไปรวมกันอยู่ที่เดียว เช่น
-
parent –
-
|- child1
-
|- child2
แบบนี้ไฟล์ก็จะไม่รวมอยู่ที่เดียวกัน แต่ จะมีปัญหาตามมาว่า แล้วเราจะ บริหารจัดการยังไง T_T
ตรงนี้แหละที่ ต้องมี hashing algorithm แบบต่างๆ ขึ้นมา ผมจะลอง ไล่ไปดูทีละแบบละกัน
แบบที่นึง hash ตัวเลข
-
function int_hash($no, $max=5000)
-
{
-
}
แบบนี้จะเป็นการ 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)
-
{
-
}
วิธี 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;
-
}
-
-
for ($i=1; $i<=$this->level; $i++)
-
{
-
}
-
}
-
-
function _makePathRecursive($dir)
-
{
-
-
return TRUE;
-
}
-
-
}
-
-
/*
-
##### Example Usage #####
-
$string = "IWannaBeARockStar";
-
$hashing = new Hashing;
-
$path = $hashing->do_hash($string);
-
file_put_contents($path, $string);
-
*/
-
?>
You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.
เหมาะสำหรับเอาไปทำ hash folder log file หรือ picture upload อย่างมาก
Hasing algorithm อยากทราบว่ามันคืออะไรหรอครับ
อ่านแล้วไม่เข้าใจ
แล้วถ้า file system ที่ directory contents มันใช้โครงสร้างข้อมูลแบบต้นไม้อยู่แล้วแทนที่จะเป็นตาราง เช่น HAMMER ของ dragonfly BSD ซึ่ง B-tree อยู่แล้ว ก็ไม่ต้องทำ sub-folders เอง แบบนี้ ใช่ไหมครับ
ใช่ครับผม
บทความแต่ละบทความไม่เคยผิดหวังจิงๆ ครับ เทคนิคเยอะดีครับ