Implementasi Key-Value Store dengan Struktur Data List dan Tree Menggunakan Python Mukhammad Miftakhuddin, Wahyu Suadi, Baskoro Adi Pratomo Jurusan Teknik Informatika, Fakultas Teknologi Informasi, Institut Teknologi Sepuluh Nopember
1
[email protected] 2
[email protected]
3
[email protected]
tingginya akses ke database sehingga RDBMS kewalahan untuk melayani request data. Beruntunglah pada tahun 2009 muncul trend baru penyimpanan data, NoSQL. NoSQL ini merupakan kepanjangan dari Not Only SQL. Sesuai kepanjangannya NoSQL tidak menggunakan sintaks SQL untuk memyimpan data. Sebenarnya NoSQL ini dikembangkan pertama kali pada tahun 1998 oleh Carlo Strozzi. Lalu, pada tahun 2009, Eric Evans memperkenalkan kembali teknologi NoSQL. NoSQL ini jauh berbeda dengan relational database. Penyimpanan data dalam NoSQL tidak memerlukan skema tabel yang tetap seperti relational database. Metode yang digunakan NoSQL ini bermacam-macam, salah satunya key-value store. Dalam key-value store tidak ada skema tabel yang tetap seperti database relasional. Data disimpan dalam sebuah dictionary dengan key tertentu. Isi dari value ini bisa berupa string, list atau pun tree. Bentuk struktur data list dan tree ini memungkinkan bagi kita untuk memasukkan data yang tidak linier dimana suatu record dalam list dapat memiliki list lagi di dalamnya. Satu hal lagi yang membuat key-value store lebih unggul dibandingkan database relasional, dalam key-value store, data tidak langsung disimpan dalam disk seperti database pada umumnya. Data disimpan dalam memori komputer dan sesekali data dalam memori ditulis ke disk. Penyimpanan data dalam memori menyebabkan proses I. PENDAHULUAN pengambilan data akan lebih cepat, karena tidak perlu lagi mengambil data dari disk. Pada aplikasi web yang memiliki 1.1 Latar belakang masalah intensitas transaksi data yang tinggi, biasanya akan Tidak dapat dipungkiri bahwa database merupakan media menggunakan key-value store untuk penyimpanan datanya penyimpanan data yang paling banyak digunakan oleh disamping menggunakan database relasional, contohnya web aplikasi-aplikasi yang ada saat ini. Hal ini menimbulkan LiveJournal, Wikipedia, Twitter, Youtube, dan Wordpress kecenderungan bahwa untuk menyimpan data harus di yang menggunakan Memcached. database. Memang, data harus disimpan di database sehingga Tujuan jika suatu saat data tersebut diperlukan, maka diambil lagi. 1.2 Tujuan dari pembuatan tugas akhir ini adalah untuk Namun, apakah bentuk database yang digunakan harus seperti mengimplementasikan key-value store sebagai alternatif media relational database yang sering digunakan aplikasi pada penyimpanan data dengan menggunakan bahasa pemrograman umumnya. Selama bertahun-tahun, semenjak tahun 1990-an aplikasi Python. Adapun manfaat yang dapat diambil dari aplikasi yang baik aplikasi desktop maupun aplikasi berbasis web dibangun pada tugas akhir ini adalah memberikan sumbangsih bergantung pada relational database untuk menyimpan pemikiran dan aplikasi bagi masyarakat, khususnya yang datanya. Banyak website-website di dunia dengan jumlah menginginkan media penyimpanan data yang fleksibel, tidak pengakses mencapai jutaan yang menggunakan MySQL, terbatasi oleh struktur database yang sudah ada dan tentunya seperti Facebook. Namun, seiring meningkatnya jumlah cepat dalam proses query data. pengakses internet, maka situs-situs tersebut lama-lama akan melambat juga kecepatannya. Dan penyebab dari melambatanya kecepatan akses tersebut, tidak lain karena bstract— Kemunculan teknologi NoSQL sebagai alternatif database sangat membantu situs-situs dengan jumlah pengakses yang tinggi. Metode yang digunakan NoSQL ini ada bermacammacam, yakni table-oriented, graph-oriented, document-oriented dan key-value store. Dalam tugas akhir ini penulis akan mencoba mengimplementasikan NoSQL dengan menggunakan metode key-value store. Key-value store merupakan NoSQL yang paling sederhana. Bentuk dari key-value store berupa ordered tuple yang berisi key dan value. Nama lain dari key-value ini adalah associative array, map, atau dictionary. Sepasang data, key dan value, dimasukkan ke database berupa dictionary dan value dapat diambil kembali berdasarkan key yang dimiliki. Value yang disimpan bisa berupa string dan list. Dalam tugas akhir ini, penulis mencoba untuk menyimpan sebuah list dalam list, sehingga membentuk struktur data tree. Penulis menggunakan aplikasi key-value store Redis sebagai aplikasi acuan. Protokol yang digunakan sama dengan Redis, sehingga aplikasi yang sebelumnya terhubung dengan Redis, bisa terhubung juga dengan aplikasi key-value store yang dibuat penulis, PyRedis, tanpa melakukan perubahan apapun di sisi aplikasi. Pada uji coba, aplikasi PyRedis sedikit lebih lambat dari aplikasi Redis. Hal ini dikarenakan PyRedis yang dibangun dengan bahasa Python memang lebih lambat dibandingkan Redis yang dibangun dengan bahasa C. Keywords— NoSQL, key-value store, dictionary
1
Dalam key value store, skemanya adalah string, semua Batasan masalah Permasalahan yang dibahas dalam Tugas Akhir ini value dianggap blob. Aplikasi client lah yang memiliki beberapa batasan, diantaranya sebagai berikut: menentukan bagaimana mem-parsing data. Aplikasi key-value store dapat menyimpan value Penggunaan yang berupa list dan tree. Key-value store sangat berguna ketika pengaksesan data dilakukan menggunakan sebuah key. Aplikasi key-value store dapat melakukan Pengaksesan data menggunakan key sudah cukup pemindahan data dari memori komputer ke file dalam umum digunakan. Pada beberapa bagian aplikasi seperti user disk (dump) dan juga sebaliknya. Pengembangan aplikasi key-value store ini profiles, user sessions, shopping carts, dan lain-lain, data/value disimpan dalam sebuah data store sehingga mudah menggunakan bahasa pemrograman Python ditangani (one request to read, one request to write), hanya dengan menerjemahkan suatu key. II. TINJAUAN PUSTAKA 1.3
A.
NoSQL NoSQL adalah sebuah konsep mengenai penyimpanan data non-relasional. Teknologi dikembangkan pertama kali oleh Carlo Strozzi pada tahun 1998. Penggunaanya tidak menerapkan SQL interface. Karena tidak ada konsep relasional, maka disebut juga NoREL. Namun teknologi NoSQL kalah populer dibandingkan relational database seperti MySQL. Nama NoSQL kembali terdengar setelah bermunculan situs-situs dengan jumlah pengakses yang banyak hingga membebani server database. Pada tahun 2009 Eric Evans mengangkat kembali teknologi NoSQL. Namun kemunculan NoSQL ini bukan berarti akan menggantikan relational database. Pada kebanyak situs besar, NoSQL digunakan bersamaan dengan RDBMS. Hal ini ditujukan untuk mengurangi beban server database. Metode yang digunakan NoSQL bermacam-macam, tapi ada satu kesamaan yaitu tidak menggunakan struktur table yang tetap layaknya relational database. Metode yang digunakannya, adalah sebagai berikut: Table-oriented, contoh: Google dengan Big Table, Facebook dengan Cassandra Graph-oriented Document-oriented database, contoh: MongoDB dan CouchDB. Key-value store, contoh: Redis.
C.
Redis Redis merupakan contoh aplikasi yang menangani manajemen key-value store. Sering disebut juga server data structure karena sebuah key dapat berisi string, hash, list dan set. Untuk mencapai kinerja yang luar biasa, Redis bekerja di dataset memori. Semua data disimpan di memori, sehingga proses pemasukan dan pengambilan data dapat dilakukan lebih cepat. Tetapi, untuk menjaga data agar tidak hilang, data di memori tersebut dapat disimpan (dump) ke dalam disk. Redis ini ditulis dengan menggunakan bahasa C dan bekerja dalam POSIX systems seperti Linux, *BSD, OS X dan Solaris. D.
Python Python dikenal sebagai bahasa pemograman interpreter, karena Python dieksekusi dengan sebuah interpreter. Satu hal yang telah kita ketahui bahwa bahasa pemograman Python adalah bahasa pemograman yang mudah dibaca dan terstruktur, hal ini karena di gunakannya sistem identasi. Yaitu memisahkan blok - blok program susunan identasi. Jadi untuk memasukan sub - sub program dalam suatu blok, sub-sub program tersebut diletakkan satu atau lebih spasi dari kolom suatu blok program. Diakui oleh pembuatnya sendiri, Guido Van Rossum bahwa Python memproses suatu program lebih lambat dibandingkan dengan C, bahasa tingkat tinggi lainnya seperti Perl, C++, JAVA, Pascal berada satu tingkat dengan Python. Akan tetapi pada kenyataannya python boleh dibilang bahasa pemograman yang kecepatannya melebihi C. Hal ini dikarenakan karena para pengembang software lebih cenderung memilih kecepatan dalam menyelesaikan suatu proyek dibandingkan dengan kecepatan proses dari program tersebut, mengenai kecepatan program di jawab dengan kecepatan prosesor dan memori yang sangat berkembang saat ini, mengakibatkan tidak terlihatnya kelambatan dari program python, dalam kata lain kecepatan suatu program python dapat sebanding dengan program yang dibuat dengan bahasa C.
B.
Key-Value Store Database NoSQL yang paling sederhana adalah keyvalue store. Sebuah key dapat menyimpan sebuah value, tanpa memperdulikan jenis value. Dengan kata lain, tidak ada skema tabel yang tetap, tetapi aplikasi client harus mendefinisikan semantik untuk mengetahui jenis data tersebut. Bentuk dari key-value store berupa ordered tuple yang berisi key dan value. Nama lain dari key-value ini adalah associative array, map, atau dictionary. Ketika menggunakan key-value store, sepasang data, key dan value, dimasukkan ke database berupa dictionary dan value dapat diambil kembali berdasarkan key yang dimiliki. Ada beberapa hal yang harus diperhatikan dalam keyvalue store, antara lain Query Tidak ada proses query data dalam key-value store, kecuali berdasarkan key. Skema
III. PERANCANGAN PERANGKAT LUNAK Pengerjaan tugas akhir ini akan membangun aplikasi PyRedis, sebuah aplikasi key-value store dengan bahasa
2
Python. Untuk menyimpan semua data tersebut digunakan sebuah dictionary yang menjadi dictionary utama dan akan GET mykey\r\n menjadi root/parent bagi semua value yang tersimpan. Dari Gambar 3 Request dari client ke server dictionary utama dibuat sebuah key dengan value string atau Lalu server akan membalas perintah dengan berbagai jenis list. Dan dari list yang ada dalam dictionary utama tadi, bisa reply. Reply yang diterima client bisa diketahui jenisnya dibuat lagi sebuah sub list, sehingga membentuk sebuah tree berdasarkan dari byte pertama yang dikirim oleh server. seperti pada gambar 1. Reply berupa single line diawali dengan tanda "+" Reply dengan error message diawali dengan tanda "-" Reply dengan nilai integer diawali dengan tanda ":" Reply dengan disertai data/value (bulk reply) akan diawali tanda "$" Reply dengan disertai data/value yang lebih dari satu (multi bulk reply) akan diawali tanda “*” Sebagai contoh hasil dari perintah sebelumnya dapat Gambar 1 Key-value berupa list dilihat pada gambar 4. Semua data dalam key-value store ini disimpan di dalam Client: GET mykey memori komputer, sehingga proses pengambilan dan Server: $6\r\nfoobar\r\n pengubahan data dapat dilakukan dengan cepat. Namun Gambar 4 Reply dari server penyimpanan data dalam memori juga beresiko kehilangan data jika terjadi kegagalan sistem. Oleh karena itu, sesekali IV. IMPLEMENTASI PERANGKAT LUNAK data dalam memori tersebut disimpan atau di-dump dalam sebuah file. Jika terjadi kegagalan system, aplikasi ini dapat 1. Operasi Dump dan Load Dataset me-load data kembali dari file ke memori. Karena aplikasi PyRedis menyimpan key-value di dataset memori, maka diperlukan tempat penyimpanan yang persistent untuk mencegah hilangnya data ketika sistem mati. Oleh karena itu dibuat suatu operasi untuk menge-dump data dari memori ke disk dengan menggunakan modul python yang sudah ada, yaitu cPickle. Semua objek yang ada di memori Gambar 2 Proses dump key-value Proses dump key-value store ini menggunakan modul akan di-dump menjadi suatu file. SET file_descriptor python cPickle. Modul cPickle ini merupakan pengembangan CALL cPickle.dump(dictionary, file_descriptor) dari pickle, dan performanya 1000 kali lebih cepat Close file descriptor dibandingkan pickle. Dalam python, pickle merupakan sebuah Gambar 5 Pseudocode dump data objek yang disimpan ke dalam sebuah file. Objek tersebut bisa berupa variable, instance of class, list, dictionary atau tuple. SET file_descriptor Aplikasi PyRedis ini hanya mengimplementasikan CALL cPickle.load(file_descriptor) beberapa perintah Redis, terutama yang berkaitan dengan RETURNING dictionary string dan list. Berikut ini daftar perintah aplikasi PyRedis: Close file descriptor 1. EXISTS Gambar 6 Pseudocode load data 2. SET 2. Operasi Key-Value Store Yang Diimplementasikan 3. GET Operasi-operasi key-value store ini meliputi operasi 4. DEL dictionary dengan value berupa string dan list, sedangkan tree 5. INCR merupakan pengembangan dari list. 6. INCRBY 7. DECR 2.1 Operasi EXISTS 8. DECRBY Berfungsi untuk mengecek apakah key tersebut sudah 9. LPUSH dipakai atau belum. Dalam pseudocode pada gambar 7, jika 10. LPOP key ditemukan, server akan mengirim nilai integer 1, dan 11. RPUSH untuk kondisi sebaliknya akan mengirim nilai integer 0. 12. RPOP Parameter: key 13. LRANGE Return Value: Reply berupa nilai integer dengan ketentuan sebagai Komunikasi antara server dengan client dilakukan secara berikut: plain-text. Protokol yang digunakan sesuai dengan protokol - :1\r\n, jika key sudah ada. Redis. Untuk lebih memperjelas, akan diberikan contoh - :0\r\n, jika key belum ada. sebagai berikut, misalkan, dari aplikasi client akan mengambil sebuah value. Perintah yang diketikkan seperti ini pada gambar FUNCTION exists(key) 3.
3
Parameter: key [key ...] Return Value: Reply berupa nilai integer, jumlah key yang dihapus - :1\r\n, jumlah key yang dihapus satu. - :N\r\n, jumlah key yang dihapus sebanyak N.
IF key found RETURN 1 ELSE RETURN 0 ENDIF
Gambar 7 Pseudocode operasi EXISTS
FUNCTION delete(list_keys)
2.2 Operasi SET SET deleteCount to 1 Operasi SET merupakan operasi untuk memberikan FOR each key in list_keys value pada suatu key. Jika key tersebut sudah memiliki value, IF key found Delete dictionary[key] maka value yang lama akan di-overwrite, tidak peduli dengan INCREMENT deleteCount tipe datanya. ENDIF Parameter: key, value ENDFOR Return Value: RETURN deleteCount Reply berupa status code dengan ketentuan sebagai Gambar 10 Pseudocode Operasi DEL berikut: Untuk melakukan operasi penghapusan, akan - +OK, selalu berhasil karena SET tidak pernah dilakukan looping pencarian key sebanyak input key yang akan gagal dihapus. Jika key ditemukan maka akan dihapus. Return value yang diberikan ke client berupa jumlah key yang dihapus. Jika FUNCTION set(key, value) tidak ada key dihapus, maka return value-nya 0. SET dictionary[key] = value RETURN “OK”
2.5 Operasi LPUSH Operasi LPUSH adalah operasi penambahan elemen baru pada bagian head dari list. Perintah LPUSH ini memiliki dua parameter, yaitu key dan value. Jika key ditemukan dan value berupa list, maka fungsi insert dari dictionary akan dipanggil dengan indeks ke-0. Jika key bukan list maka akan diberi pesan error. Dan, jika key tidak ditemukan, maka otomatis akan dibuatkan sebuah key dengan value berupa list. Untuk lebih jelasnya bisa dilihat pseudocode pada gambar 11. Parameter: key, value Return Value: Reply berupa nilai status code dengan ketentuan sebagai berikut: - +OK, jika berhasil - -ERR, jika key tidak berisi list.
Gambar 8 Pseudocode operasi SET
2.3 Operasi GET Operasi GET merupakan operasi pembacaan value dari suatu key. Operasi GET ini hanya menangani key dengan value berupa string saja. Jika key tidak ditemukan, maka balasan yang dikirim server berupa special value ‘nil’. Jika ditemukan, value akan dikirimkan ke client. Parameter: key Return Value: Reply berupa bulk-reply dengan ketentuan sebagai berikut: - $(jumlah bit value)\r\n (value)\r\n , jika key ditemukan. Contoh $5\r\nvalue\r\n - $-1\r\n diterjemahkan sebagai nil, jika key tidak ditemukan.
FUNCTION lpush(key, value) IF key found IF value is list CALL dictionary[key].insert(0, value) RETURN “OK” ELSE RETURN “ERROR” ENDIF ELSE SET new_list CALL new_list.append(value) SET dictionary[key] = new_list RETURN “OK” ENDIF
FUNCTION get(key) IF key found IF value is string SET bulk_reply to empty string Append byte number of value to bulk_reply Append value to bulk_reply RETURN bulk_reply ELSE RETURN error ENDIF ELSE RETURN -1 or null ENDIF
Gambar 11 Pseudocode operasi LPUSH
2.6 Operasi RPUSH Operasi RPUSH adalah operasi penambahan elemen baru pada bagian tail dari list. Perintah RPUSH ini memiliki dua parameter, yaitu key dan value. Jika key ditemukan dan value berupa list, maka fungsi append dari dictionary akan dipanggil. Jika key bukan list maka akan diberi pesan error. Dan, jika key tidak ditemukan, maka otomatis akan dibuatkan
Gambar 9 Pseudocode Operasi GET
2.4 Operasi DEL Operasi DEL merupakan operasi penghapusan key dengan parameter key itu sendiri. Jumlah key yang dihapus bisa lebih dari satu.
4
sebuah key dengan value berupa list. Untuk lebih jelasnya bisa dilihat pseudocode pada gambar 12. Parameter: key, value Return Value: Reply berupa nilai integer dengan ketentuan sebagai berikut: - +OK, jika berhasil - -ERR, jika key tidak berisi list.
Pada gambar 13, dijelaskan pseudocode dari fungsi LPOP. Jika key tidak ada, maka akan dianggap empty list dengan reply dari server berupa integer -1. Jika key tidak berisi list maka client akan mendapat pesan error. Jika key berhasil dihapus, maka reply dari server berupa bulk reply yang terdiri dari jumlah byte dari value dan value itu sendiri. 2.8 Operasi RPOP Operasi RPOP adalah operasi penghapusan elemen pada bagian tail dari list. Perintah RPOP ini memiliki dua parameter, yaitu key dan value. Jika setelah operasi RPOP, jumlah elemen list sama dengan 0 atau kosong, maka key dari list tersebut akan dihapus. Balasan dari server berupa jumlah elemen list tersebut. Parameter: key Return Value: Reply berupa bulk reply dengan ketentuan sebagai berikut: - $(jumlah bit value dari tail list)\r\n (value dari tail list)\r\n. Contoh $5\r\nvalue\r\n - $-1\r\n diterjemahkan sebagai nil, jika key tidak ditemukan. - -ERR, jika key tidak berisi list.
FUNCTION rpush(key, value) IF key found IF value is list CALL dictionary[key].append(value) RETURN “OK” ELSE RETURN “ERROR” ENDIF ELSE SET new_list CALL new_list.append(value) SET dictionary[key] = new_list RETURN “OK” ENDIF
Gambar 12 Pseudocode fungsi RPUSH
2.7 Operasi LPOP Operasi LPOP adalah operasi penghapusan elemen pada bagian head dari list. Perintah LPOP ini memiliki satu parameter, yaitu key. Jika setelah operasi LPOP, jumlah elemen list sama dengan 0 atau kosong, maka key dari list tersebut akan dihapus. Balasan dari server berupa jumlah element list tersebut. Parameter: key Return Value: Reply berupa bulk reply dengan ketentuan sebagai berikut: - $(jumlah bit value dari head list)\r\n(value dari head list)\r\n. Contoh $5\r\nvalue\r\n - $-1\r\n diterjemahkan sebagai nil, jika key tidak ditemukan. - -ERR, jika key tidak berisi list.
FUNCTION rpop(key) IF key found IF value is list SET deleted_value to tail of list CALL dictionary[key].pop() IF list is empty Delete dictionary[key] ENDIF SET bulk_reply to empty string Append byte number of deleted_value to bulk_reply Append value to bulk_reply RETURN bulk_reply ELSE RETURN “ERROR” ENDIF ELSE RETURN -1 or null ENDIF
FUNCTION lpop(key) IF key found IF value is list SET deleted_value to head of list Delete head of list IF list is empty Delete dictionary[key] ENDIF SET bulk_reply to empty string Append byte number of deleted_value to bulk_reply Append value to bulk_reply RETURN bulk_reply ELSE RETURN “ERROR” ENDIF ELSE RETURN -1 or null ENDIF
Gambar 14 Pseudocode operasi RPOP Pada gambar 14, dijelaskan pseudocode dari fungsi RPOP. Jika key tidak ada, maka akan dianggap empty list dengan reply dari server berupa integer -1. Jika key tidak berisi list maka client akan mendapat pesan error. Proses penghapusan value dengan memanggil fungsi pop dari dictionary. Jika key berhasil dihapus, maka reply dari server berupa bulk reply yang terdiri dari jumlah byte dari value yang dihapus dan value itu sendiri. 2.9 Operasi LRANGE Perintah ini digunakan untuk melihat anggota/elemen dari list. Perintah LRANGE memiliki tiga parameter, yakni key, start dan end. Sama seperti operasi list lainnya, sebelum akan dicek key ada dan value-nya berupa list. Setelah itu nilai start akan dicek, jika nilai start melebihi nilai end atau panjang
Gambar 13 Pseudocode fungsi LPOP
5
list maka dianggap empty list. Sedangkan jika nilai end lebih besar dari panjang list, maka end dianggap sama dengan panjang list. Hasil dari perintah LRANGE yang dikirimkan ke client ini berupa multi bulk reply yang terdiri dari jumlah list yang ditampilkan, jumlah byte masing-masing elemen diikuti elemen list sendiri, dan masing-masing dipisahkan CRLF (\r\n). Parameter: key, start (indeks awal), end (indeks akhir) Return Value: Reply berupa multi bulk reply dengan ketentuan sebagai berikut: - *(jumlah elemen list)\r\n $(jumlah bit value dari elemen list ke-1)\r\n (value dari elemen list ke-1)\r\n. ... ... $(jumlah bit value dari elemen list ke-N)\r\n (value dari elemen list ke-N)\r\n. Contoh : *N\r\n$5\r\nvalue\r\n...$5\r\nvalue\r\n - $-1\r\n diterjemahkan sebagai nil, jika key tidak ditemukan. - -ERR, jika key tidak berisi list.
Reply berupa multi bulk reply dengan ketentuan sebagai berikut: - +OK, jika berhasil. - -ERR, jika key tidak berisi list. FUNCTION tadd(parent, child) IF child key not found RETURN -1 or null ENDIF IF parent and child dot not contain list RETURN “ERROR” ENDIF IF parent key not found SET dict[parent] = new empty list ENDIF dict[parent].append(dict[child]) RETURN “OK”
Gambar 16 Pseudocode operasi TADD
2.11 Operasi TDEL Perintah TDEL digunakan untuk menghapuskan list dari daftar parent list. Seperti biasa, baik parent key maupun child key dicek keberadaanya dalam dictionary dan jenis value-nya. Selanjutnya server akan melakukan perulangan sebanyak anggota parent list untuk mencari child list. Jika child list ditemukan maka reply yang diberikan berupa multi bulk reply yang terdiri dari jumlah list yang ditampilkan, jumlah byte masing-masing elemen diikuti elemen list sendiri, dan masing-masing dipisahkan CRLF (\r\n). Parameter: parent key, child key Return Value: Reply berupa multi bulk reply dengan ketentuan sebagai berikut: - *(jumlah elemen list)\r\n $(jumlah bit value dari elemen list ke-1)\r\n (value dari elemen list ke-1)\r\n. ... ... $(jumlah bit value dari elemen list ke-N)\r\n (value dari elemen list ke-N)\r\n. Contoh : *N\r\n$5\r\nvalue\r\n...$5\r\nvalue\r\n - $-1\r\n diterjemahkan sebagai nil, jika key tidak ditemukan. - -ERR, jika key tidak berisi list.
FUNCTION lrange(key, start, end) IF key found IF value is list IF start > end RETURN 0 or empty list ENDIF IF start > length of list RETURN 0 or empty list ENDIF IF end > length of list end = length of list ENDIF SET multi_bulk to empty string Append length of to multi_bulk FOR each element in list Append element byte number to multi_bulk Append element to multi_bulk ENDFOR RETURN multi_bulk ELSE RETURN “ERROR” ENDIF ELSE RETURN -1 or null ENDIF
Gambar 15 Pseudocode operasi LRANGE
FUNCTION tdel(parent, child) IF child or parent key not found RETURN -1 or null ENDIF IF parent and child dot not contain list RETURN “ERROR” ENDIF SET parent_list = dictionary[parent] FOR each element in parent_list IF element = child SET delete_list = element Delete element BREAK ENDIF ENDFOR SET multi_bulk to empty string Append length of delete_list to multi_bulk
2.10 Operasi TADD Perintah TADD digunakan untuk menambahkan list ke dalam list. Seperti operasi list, ada pengecekan apakah value dari parent maupun child berisi list atau tidak. Jika parent key tidak ditemukan, maka akan dibuat dictionary dengan parent key yang berisi empty list. Proses penambahan list ke dalam list dengan menggunakan fungsi append dengan parameter berupa child list. Untuk selengkapnya dapat dilihat pada gambar 16. Parameter: parent key, child key Return Value:
6
terdiri dari jumlah list dari parent list, jumlah byte dari nama child list diikuti nama child list sendiri, dan masing-masing dipisahkan CRLF (\r\n). Parameter: parent key Return Value: Reply berupa multi bulk reply dengan ketentuan sebagai berikut: - *(jumlah elemen list)\r\n $(jumlah bit value dari elemen list ke-1)\r\n (value dari elemen list ke-1)\r\n. ... ... $(jumlah bit value dari elemen list ke-N)\r\n (value dari elemen list ke-N)\r\n. Contoh : *N\r\n$5\r\nvalue\r\n...$5\r\nvalue\r\n - $-1\r\n diterjemahkan sebagai nil, jika key tidak ditemukan. - -ERR, jika key tidak berisi list.
FOR each element in delete_list Append byte number of element to multi_bulk Append element to multi_bulk ENDFOR RETURN multi_bulk
Gambar 17 Pseudocode operasi TDEL
2.12 Operasi TGET Perintah TGET digunakan untuk mendapatkan elemen child list. Sama seperti TDEL, setelah parent key dan child key dicek keberadaanya dalam dictionary dan jenis value-nya, server akan melakukan perulangan sebanyak anggota parent list untuk mencari child list. Jika child list ditemukan maka reply yang diberikan berupa multi bulk reply yang terdiri dari jumlah list yang ditampilkan, jumlah byte masing-masing elemen diikuti elemen list sendiri, dan masingmasing dipisahkan CRLF (\r\n). Parameter: parent key, child key Return Value: Reply berupa multi bulk reply dengan ketentuan sebagai berikut: - *(jumlah elemen list)\r\n $(jumlah bit value dari elemen list ke-1)\r\n (value dari elemen list ke-1)\r\n. ... ... $(jumlah bit value dari elemen list ke-N)\r\n (value dari elemen list ke-N)\r\n. Contoh : *N\r\n$5\r\nvalue\r\n...$5\r\nvalue\r\n - $-1\r\n diterjemahkan sebagai nil, jika key tidak ditemukan. - -ERR, jika key tidak berisi list.
FUNCTION tmember(parent) IF parent key not found RETURN -1 or null ENDIF IF parent dot not contain list RETURN “ERROR” ENDIF SET parent_list = dictionary[parent] SET members to elements of parent_list SET multi_bulk to empty string Append length of members to multi_bulk FOR each element in members Append element byte number to multi_bulk Append element to multi_bulk ENDFOR RETURN multi_bulk
Gambar 19 Pseudocode operasi TMEMBER
FUNCTION tget(parent, child) IF child or parent key not found RETURN -1 or null ENDIF IF parent and child dot not contain list RETURN “ERROR” ENDIF SET parent_list = dictionary[parent] SET get_list to empty list FOR each element in parent_list IF element = child get_list = element BREAK ENDIF ENDFOR SET multi_bulk to empty string Append length of get_list to multi_bulk FOR each element in get_list Append element byte number of to multi_bulk Append element to multi_bulk ENDFOR RETURN multi_bulk
3.
Penanganan Reply dari Server oleh Client Reply dari server masih berupa data mentah (bulk reply). Agar dapat dibaca harus diolah dulu di client. Pada gambar 20 dijelaskan pseudocode penanganan replay dari server oleh client. Jenis reply dari server dapat diketahui pada byte pertama yang diterima. Ada lima macam reply, yakni error, ok, bulk replay, multi bulk replay, dan integer. Error replay ditandai dengan “-”. Sedangkan ditandai dengan “+”. Untuk replay yang berupa value dari suatu key ditandai dengan “$” dan disebut bulk reply. Jika byte selanjutnya dari bulk reply bukan -1 atau nil, maka akan ditampilkan value dari key yang dicari tapi terlebih dahulu reply harus di-split berdasar CRLF (\r\n). Untuk penanganan multi bulk reply hampir sama dengan bulk reply. Hanya saja pada multi bulk ditandai dengan “*”. Karakter pada byte selanjutnya menunjukkan jumlah value yang dikirim. Pada bulk replay, value yang dikirim hanya satu, sedangkan pada multi bulk reply, value yang dikirim bisa lebih dari satu. Masing-masing antar value dipisahkan oleh CRLF (\r\n).
Gambar 18 Pseudocode operasi TGET
2.13 Operasi TMEMBER Perintah TMEMBER digunakan untuk melihat daftar list (key) dari suatu list. Setelah parent key dicek keberadaanya dalam dictionary dan jenis value-nya adalah list, server akan memberikan reply berupa multi bulk reply yang
FUNCTION unpack(reply) IF first byte = “-”
7
Split replay by space SET replay_array to split result of reply SET error_message to replay_array[2] RETURN error_message ELSEIF first byte = “+” RETURN “OK” ELSEIF first byte = “$” IF next byte = -1 RETURN nil ELSE split reply by “\r\n” SET replay_array = split result of reply SET value = replay_arry[1] RETURN value ENDIF ELSEIF first byte = “*” IF next byte = -1 RETURN nil ELSEIF next byte = 0 RETURN empty list ELSE split reply by “\r\n” SET list_value = split result of reply SET all_value to empty string FOR each value in list_value Append value to all_value Append “\r\n” to all_value ENDFOR RETURN all_value ENDIF ELSEIF first byte = “:” RETURN next byte ENDIF
Gambar 22 Perintah LPUSH, RPUSH dan LRANGE
Gambar 23 Perintah TMEMBER dan TGET Uji fungsionaltias yang kedua dengan menggunakan aplikasi web yang sebelumnya menggunakan aplikasi Redis sebagai penyimpanan data. Penyimpanan data dari aplikasi web ini akan dipindahkan dari Redis ke PyRedis. Hasilnya seperti pada gambar 24.
Gambar 20 Pseudocode penanganan reply dari server oleh client Gambar 24 Aplikasi web yang terhubung ke PyRedis
V. UJI COBA DAN EVALUASI 2.
Uji kecepatan Uji coba ini ditujukan untuk mengetahui waktu komputasi yang dibutuhkan ketika sistem dijalankan. Pengujian dilakukan dengan melakukan insert dan retrieve 50000 data baik data string maupun list. Hasilnya dapat dilihat pada tabel 1.
Pada bagian ini akan dibahas uji coba aplikasi PyRedis. Uji coba dibagi menjadi 2 studi kasus meliputi uji fungsionalitas dan uji kecepatan. 1. Uji fungsionalitas Uji coba ini bertujuan untuk mengetahui apakah masing-masing perintah berjalan sebagaimana mestinya. Pada uji coba fungsionalitas ini akan dibagi menjadi dua, pertama uji coba dengan menggunakan aplikasi client-server PyRedis. Hasil dari pengujian baik dengan menggunakan aplikasi clientserver PyRedis menunjukkan semua fungsionalitas telah bekerja dengan baik, beberapa diantaranya tampak seperti pada gambar–gambar di bawah ini.
Tabel 1 Hasil uji kecepatan Perintah
Gambar 21 Perintah SET, GET dan DEL
8
Redis (detik)
PyRedis (detik)
Set
15.1442
17.3756
Get
14.8359
18.4823
Rpush
14.5413
17.5239
Lpush
14.4568
26.2447
Gambar 25 Hasil uji kecepatan Hasil uji coba menunjukaan PyRedis sedikir lebih lambat dibandingkan Redis. Hal ini dikarenakan PyRedis yang dibangun dengan bahasa Python memang lebih lambat dibandingkan Redis yang dibangun dengan bahasa C. VI. KESIMPULAN DAN SARAN Dari serangkaian uji coba dan analisa yang dilakukan terhadap sistem dan telah dibandingkan dengan sistem sejenis yang lain, maka dapat dibuat sebuah kesimpulan antara lain: 1. Penerapan NoSQL Database dengan metode key-value store, memungkinkan untuk menyimpan data berupa list dan tree. 2. Dengan modul pickle yang ada di python, semua keyvalue store yang tersimpan di memori bisa di-dump ke file dan bisa di-load kembali ke memori. VII. DAFTAR PUSTAKA [1] Swaroop C.H., 2005. A Byte of Python,
. [2] Hellman, D., 2011. Python Module of the Week,
. [3] Sanfilippo, S., 2011. Redis, . [4] Magnocavallo, L., 2009. Simple Twitter clone written in PHP and Redis, . [5] Monash Research, 2010. Toward a NoSQL taxonomy, .
[6] Rahien, A., 2010. That No SQL Thing – Key/Value Stores, .
9