## TEKNIK REGENERATING CODE PADA PENYIMPANAN DISTRIBUSI

## REGENERATING CODETECHNIQUE IN DISTRIBUTED STORAGE
Agus Maman Abadi * , Karyati, Musthofa  dan Emut
Jurusan Pendidikan Matematika, Fakultas MIPA, Universitas Negeri Yogyakarta
*email: agusmaman@uny.ac.id

## Diterima 15 Januari 2016 disetujui 4 Maret 2016

## Abstrak
Peningkatan  kebutuhan  akan  sebuah  cara  untuk  menyimpan  data  dalam  jumlah  yang  besar menghadirkan sebuah tantangan baru. Salah satu cara untuk menghadapi tantangan ini adalah menggunakan sistem  penyimpanan  data  terdistribusi  ( Distributed  Storaged  Systems ).  Salah  satu  strategi  yang  diterapkan dalam  sistem  penyimpanan  data  terdistribusi  adalah  menggunakan  teknik regenerating code. Kode  yang digunakan  pada  teknik  ini  didasarkan  pada  struktur  aljabar  berupa  field.  Beberapa  penelitian  juga  telah dilakukan untuk  membuat  kode yang didasarkan pada struktur aljabar lain,  yaitu  modul. Pada penelitian ini dicoba untuk mengkaji penerapan kode modul pada teknik regenerating code. Hasil pengkajian menunjukkan ada potensi yang dapat dimanfaatkan dari kode atas modul pada teknik regenerating code .
Kata kunci: penyimpanan data terdistribusi, teknik regenerating code , kode modul

## Abstract
The Increasing need of storing large amounts of data presents a new challenge. One way to address this challenge is to use distributed data storage system. One of the strategies implemented in the distributed data storage system is using the technique of regenerating code. The code used in this technique is based on the algebraic structure of fields. Some studies have also been carried out to create code that is based on the other algebraic  structure  namely  module.  In  this  study,  we  attempted  to  assess  the  implementation  of  the  code module  at  regenerating  technique  code.  The  study  showed  there  is  a  potential  properties  code  based  on module that can be used in regenerating code technique.
Keywords: Distributed storage, regenerating code technique, module code

## Pendahuluan
Perkembangan  teknologi  informasi  khususnya dalam hal penggunaan data berukuran besar seperti video,  gambar  dan jejaring  sosial  telah  melahirkan tantangan  baru,  yaitu  bagaimana  strategi  untuk mengelola  data  yang  sedemikian  besar  tersebut. Selain memanfaatkan teknologi media penyimpanan seperti harddisk dan DVD, penyimpanan  data  dalam  jumlah  besar  dilakukan dengan teknik distributed storage system ( DSS). Melalui DSS, data dipecah-pecah dan kemudian  disimpan  dalam  sistem  penyimpanan terdistribusi  yang  terkoneksi  melalui  sistem jaringan  komunikasi.  Masalah  yang  terjadi  dalam DSS adalah selalu terjadi bagian penyimpan data ( node ) yang gagal atau error. Oleh karena itu proses perbaikan  data  secara  sistematis  menjadi  perhatian
utama. Skema sistem DSS disajikan dalam Gambar 1 [1].
Gambar1 . Sistem Penyimpanan terdistribusi (DSS)
Berdasarkan penelitian yang dilakukan peneliti sebelumnya [11], struktur aljabar yang lebih umum seperti  modul  dan  semimodul.  Namun  dalam penelitian  tersebut  belum  dilakukan  ujicoba menggunakan teknik pengkodean seperti regenerating  code.  Seperti  dibahas  dalam  [10], salah  satu  teknik  pengkodean  yang  digunakan dalam  komunikasi  data  secara  terdistribusi  melalui jaringan  internet  adalah regenerating  code . Beberapa penelitian yang telah dilakukan, menunjukkan  bahwa  dengan  teknik  ini  bandwith yang digunakan lebih optimal.

## Penyimpanan Data Terdistribusi
Meningkatnya
penggunaan media penyimpanan  data  seiring  dengan  meningkatnya penggunaan  email,  foto,  video    dan  data-data berukuran  besar  lainya  membutuhkan  solusi  yang tidak  mudah.  Jika  data-data  tersebut  disimpan dalam  satu  tempat,  maka  akan  sangat  berbahaya dikarenakan  media  penyimpanan  dapat  rusak sehingga mengakibatkan hilangnya data.
Solusi  yang  dapat  dilakukan  untuk  mengatasi hal  tersebut  antara  lain  [6]:  menyimpan  data dengan  menyediakan  cadangan  data  dalam  banyak media  penyimpana  (  disk  ).  Jika  salah  satu  disk mengalami  kerusakan,  maka  tinggal  mengganti disk  tersebut  dengan  yang  baru  sehingga  data  bisa terselamatkan.  Teknik  ini  dinamakan  sistem penyimpanan  terdistribusi  ( distributed  storage system ( DSS)).
Namun, masalah yang terjadi  tidaklah sesederhana ini.  Pusat data yang akan menyimpan data  dalam  jumlah  besar  membutuhkan  banyak sekali  piranti  penyimpan.  Akibatnya  kerusakan pada  piranti  penyimpan  menjadi  hal  yang  tak terhindarkan  yang  dapat  menimbulkan  masalah baru.  Oleh  karena  itu  diperlukan  strategi  dalam mengelola penyimpanan data.

## Network Coding
Network coding adalah  suatu  pendekatan untuk meningkatkan efisiensi dari proses komunikasi  [2]. Network coding adalah  suatu bagian  (  node)  dalam  proses  komunikasi  yang terletak  di  antara  sumber  data( source )  dan penerima ( receiver ) yang selain mampu menyimpan  dan  meneruskan  data,  juga  mampu mengkombinasikan  secara  independen  data  yang masuk menjadi data yang siap dikirim.
Melalui network coding ,  bagian  penyimpan data  yang  rusak  dalam  sistem  DSS,  diperbaiki dengan  langkah-langkah  tertentu.  Skema  dari network coding dalam [4] adalah sebagai berikut:
Penggunaan
Network Coding
dapat meningkatkan  meningkatkan Troughput  , yaitu kapasitas informasi yang dialirkan melalui jaringan yang  diukur  dengan  satuan  waktu  tertentu  dan kondisi jaringan tertentu.

## Erasure Code
Dalam  proses  komunikasi  melalui  jaringan atau  chanel,  seringkali  terjadi  beberapa  error  atau gagalnya    suatu  proses  pengiriman  data.  Suatu teknik pengkodean yang berkaitan dengan komunikasi  melalaui  jaringan  atau  chanel  yang bersifat demikian dinamakan erasure code . Dengan teknik erasure code ,    ketika  salah  satu  pihak  akan mengakses  suatu  data  tertentu  melalui  jaringan yang  dapat  mengalami  gagal  akses,  data  tersebut dipecah  pecah  dalam k bagian.Setiap k bagian encoding ,  kemudian  disimpan  secara  terdistribusi pada n node .  Untuk  mengakses  data  asli  dpat dilakukan dengan mengakses sebarang k node .
Ketika  terjadi  kegagalan  atau  error  dalam proses  rekonstruksi  data,  maka  salah  satu  strategi yang  dapat  dilakukan  adalah  menggunakan MDS code ,  yaitu  sejumlah  misalnya  terjadi  gagal  akses pada  node  1,  maka  dibuat    node  baru  yang dikontruksi  dari  node    yang  lain.  Menggunakan cara  ini,  bandwith  yang  dibutuhkan  dalam  proses rekonstruksi  data  berukuran  sama  dengan  ukuran data semula.
Oleh  karena  itu  dalam  [10],  diperkenalkan teknik regenerating  code yang  bisa  mengurangi kebutuhan  bandwith  dalam  proses  rekonstruksi data.  Secara  umum  proses  rekontruksi  data  dalam teknik  ini  dilakukan  dengan  mengakses  node  lain yang  tidak  mengalami  error  untuk  kemudian dihasilkan  suatu  node  berisi  kode  yang  sama dengan node yang mengalami gagal akses.  Dalam [5] hal ini dapat diilustrasikan sebagai berikut:
A2 A1 B2 B1 A2+B2 A1+B1 A1+A2+B2 A2+B1 x A1 A2 NODE BARU NODE 1 NODE 2 NODE 3 NODE 4

## Metode Penelitian
Dalam  penelitian  ini  digunakan  metode penelitian studi literatur berupa jurnal-jurnal ilmiah yang  terkait  dengan  topik  penelitian,  dan  buku- buku  referensi  yang  mendukung.  Pada  tahap  awal dipelajari  konsep-konsep  dasar  tentang distributed storage  system (  DSS)  dan network coding serta pengkonstruksian  kode  menggunakan MDS  Code dan Regenerating Code yang  didasarkan  ada struktur  aljabar  berupa  field  .  Konsep-konsep  ini nantinya digunakan sebagai dasar untuk mengkontruksi  kode  pada  struktur  aljabar  yang lebih umum, yaitu pada modul.
Selanjutnya, dipelajari beberapa teknik pengkodean menggunakan modul. Langkah berikutnya  adalah  mempelajari  penerapan  kode yang  didasarkan  atas  modul  apakah  dapat diterapkan  untuk  melakukan  rekontruksi  data dengan teknik regenerating code .

## Hasil dan Pembahasan
Teknik Regenerating Code atas Field.
Berikut adalah skema dari teknik regenerating code  dengan    teknik exact  repair yang  didasarkan pada  struktur  aljabar  atas  lapangan  hingga F q . Suatu  file  dengan  ukuran B dalam  penyimpanan terdistribusi  dipecah-pecah  dan  disimpan  dalam n buah node dengan  ketentuan  setiap  node  dapat menyimpan sejumlah  . Suatu data collector dapat terkoneksi  dengan  setiap  node,  dan  kemudian merekontruksi  file  semula.  Untuk  merekontruksi file,  data  collector  cukup  terhubung  ke  sejumlah k < n node yang ada. Ketika misalnya ada node yang error,  maka  data  collector  akan  terhubung  ke sejumlah d > k dari n -1  node  yang  tersisa  untuk membentuk  node  baru  menggantikan  node  yang error. Pada teknik regenerating code, secara umum node  yang  baru  tidak  harus  sama  persis  dengan node  yang  error,  tetapi  memiliki  sifat  yang  sama, yaitu  untuk  merekontruksi  data  semula,  cukup
dibentuk dari sejumlah k < n node yang ada. Dalam [Rashmi],  telah  dikenalkan  suatu teknik  exact repair ,  yaitu  ketika  membentuk  node  yang  baru pada  saat  ada  node  yang  error,  maka  node  yang baru  tesebut  identik  dengan  node  yang  error tersebut.
Secara  umum  teknik  regenerating  code  untuk meminimalkan  penyimpanan  (  minimum  storage regeneration)  yang  didasarkan  atas  struktur  aljabar lapangan hingga adalah sebagai berikut.
a) File  atau  objek O =  ( o 1 , o 2 ,  …, o B )  dipecah  menjadi  2,  yaitu  O 1 =  (o 1 ,  o 2 ,  …,  o k ) dan  O 2 =  (  o k+1 ,  o k+2, …,  o B ).  Dalam  hal  ini  B merupakan  bilangan  genap  sehingga  O 1 dan  O 2 mempunyai ukuran yang sama.
b) Node ke- i akan menyimpan  = ( O 1 p i T , O 2 p i T +  O 1 v i T ),  dengan  p i dan  v i merupakan  vektor baris yang digunakan untuk melakukan encoding,  i  =  1,2,…,  n.  Lebih  khusus, p i T merupakan  vektor  yang  merupakan  generator untuk G ’ dari suatu (n,k) MDS code , yaitu G’= [ p 1 T …. p n T ]
c) Secara keseluruhan kode yang dihasilkan adalah (2n, 2k) kode yang disajikan sebagai
[O 1 ,  O 2 ] [ ] dengan V =  [ v 1 T … v n T ]
adalah suatu matriks.
d) Untuk  merekontruksi  data/file,  data  collector mendownload  dari k buah  node.  Karena  G ’ merupakan  generator  untuk  (n,k)  MDS  code, maka diperoleh O 1 . Karena O 1 dan  v i diketahui, maka  data  collector  tinggal  menyisakanO 2 p i T . Karena G ’ generator , maka dapat diperoleh O 2 .
e) Misalkan node ke-j error, yaitu ( O 1 p j T , O 2 p j T + O 1 v i T ) tidak dapat diakses.Node baru kemudian mendownload  =1  simbol  dari    d  =  k+1  buah node, yaitu w i = a i ( O 1 p i T ) + O 2 p i T + O 1 v i T , dengan a i  F q .
Node  baru  menghitung  2  simbol  dari  d  symbol yang  didownload,  dengan  membuat  kombinasi linear dari (∑
∑ ) dengan I dan  I dipilih  sedemikian  sehingga memenuhi ∑  dan ∑ .
Contoh :
Untuk n = 5, k = 3, d = k+1 = 4, maka B = 2k = 6. Objek/file = ( o 1 , …, o 6 )  F q 6.
Dipilih q = 8, jadi F q = F 8 =  { 0, 1, w, w+1, w 2 ,w 2 + 1, w 2 +w, w 2 +w + 1} dan w 3 = w+1.
Diperoleh enkodingnya adalah :
Agus  dkk. / J. Sains Dasar 2016 5(1)   57 – 61
60 [o 1 o 2 o 3 ] [ ]
Suatu  teknik  kontruksi  yang  lain  adalah sebagaimana yang telah dibahas dalam [12] adalah sebagai berikut.
1) File  berukuran  B,  dipecah  pecah  ke  dalam bagian-bagian ( f 0 , f 1 , …, f B-1 ).
2) Didefinisikan    d  =  n-1  dan  matriks  V berukuran  n   dengan  =  ½  d  (  d+1)  dan memenuhi:
(i) Elemen dari V adalah 0 atau 1;
(ii) Setiap  baris  mempunyai  elemen  1  tepat sebanyak d;
(iii) Setiap  kolom  mempunyai  elemen  1  tepat sebanyak dua;
(iv) Sebarang  dua  baris,  mempunyai  irisan  1, tepat sebanyak 1.
Berdasarkan  ketentuan  tersebut,  matriks  V merupakan  graf  matriks  insidensi  dari  graf  tak berarah  dengan n titik.    Himpunan  vektor  { v 1 , v 2 , …, v  }  membentuk  MDS  code  dengan  dimensi B . elemen-elemen  dari  setiap  v i merupakan  elemen dari  lapangan  hingga F q .  Node j menyimpan f t ( v i ) jika dan hanya jika V ( j , i ) = 1.
Contoh : Misal  n = 5 , k = 3 . Diperoleh d = n – 1 = 4 dan  = ½  4  5  = 10. Node 1 Node 2 Node 3 Node 4 Node 5 Gambar 3 Skema encoding
Matriks V merupakan  matriks  insidensi  dari graf tak berarah pada gambar 3 di atas, yaitu :
v1 v2 v3 v4 v5 v6 v7 v8 v9 v10 n1 1 1 1 1 0 0 0 0 0 0 n2 1 0 0 0 1 1 1 0 0 0 n3 0 1 0 0 1 0 0 1 1 0 n4 0 0 1 0 0 1 0 1 0 1 n5 0 0 0 1 0 0 1 0 1 1
Berdasarkan  teknik  konstruksi  di  atas,  maka  tiap node akan menyimpan :
Node 1: {f t v1; f t v2; f t v3; f t v4} Node 2: {f t v1; f t v5; f t v6; f t v7}
Node 3: {f t v2; f t v5; f t v8; f t v9}
Node 4: {f t v3; f t v6; f t v8; f t v10}
Node 5: {f t v4; f t v7; f t v9; f t v10}
Untuk  proses  rekonstruksi  data,  misal  data collector  menghubungi  ke    node  1,  2  dan  3.  Dari ketiga  node  tersebut  akan  diperoleh  f t v1,  f t v2,  …, f t v9.  Demikian  pula  jika  misalnya  node  2 bermasalah,  maka  node  1  akan  memberikan informasi f t v1, node 3 akan memberikan informasi f t v5,  node  4  akan  memberikan  informasi  f t v6,  dan node 4 akan memberikan informasi f t v7.

## Teknik Regenerating Code atas Modul
Pada bagian ini akan dikaji tentang pemanfaatan  struktur  aljabar  berupa  modul  pada teknik  regenerating  code.  Di  awal  bagian  ini  akan terlebih dahulu dibahas tentang kode modul seperti yang dibahas dalam [2].

## Definisi 1
Misalkan M 1 dan M 2 adalah suatu modul atas ring R  dan E : M 1  M 2 adalah  suatu  fungsi  encoding. Suatu kode C = E ( M 1 ) dinamakan kode modul jika E ( M 1 ) merupakan submodul dari M 2 .
Contoh 2. Diberikan modul B 2 = { 00, 01, 10, 11} dan B 5 = { 00000, 10000, 10001, 10011, 10010, 10101, 10110, 10111, 11000, 11001, 11010, 11011, 11100, 11100, 11101, 11110, 00001, 00011, 00010, 00100, 00110, 00111, 01000, 01001, 01010, 01011, 01100, 01101, 01110, 01110, 01111, 11111}.
terhadap  operasi  penjumlahan  modulo  2  dan pergandaaan skalar atas B = {0,1}.
Selanjutnya didefinisikan fungsi encoding E : B 2  B 5 sebagai : E (00) = 00000 E (01) = 01110 E (10) = 10101 E (11) = 11011 E ( B 2 ) merupakan suatu submodul dari B 5 sebab :
1) Tertutup terhadap penjumlahan, yaitu:
01110 + 10101= 11011 01110 + 11011 =10101 10101 + 11011 = 01110 01110 + 01110 = 00000 10101 + 10101 = 00000 11011 + 11011 = 00000
Agus  dkk. / J. Sains Dasar 2016 5(1)   57 – 61
11011 + 11011 = 00000
2) Tertutup  terhadap  perkalian  skalar  {0,  1}, yaitu
0  (10101 ) = 00000 dan
1  ( 10101) = 10101 Jadi,  E(B 2 )    =  {  00000,  01110,  10101,  11011}  di atas  adalah  kode  modul  sebab  merupakan submodul dari B 5 .
Contoh 3 Diberikan B 2 dan B 4 seperti  pada  contoh  4.2. Didefinisikan  fungsi  enkoding E : B 2  B 4 sebagai berikut : E(00) = 0000 E(01) = 0101 E(10) = 1010 E(11) = 1111
E ( B 2 )  =  {  0000,  0101,  1010,  1111}  merupakan submodul dari B 4 sebab:
1) Tertutup terhadap penjumlahan, yaitu:
0101 + 1010 = 1111 1010 + 1111 = 0101 0101 + 1111 = 1010 0101 + 0101= 0000 1010 + 1010 = 0000 1111 + 1111 = 0000 2) Tertutup terhadap perkalian skalar B = { 0, 1}, yaitu :
1  ( 1010 ) = 1010
0  ( 1010 ) = 0000
Jadi  , E ( B 2 )  =  {  0000,  1010,  0101,  1111} merupakan kode modul.
Selanjutnya,  gagasan  untuk  menerapkan  kode modul  pada  teknik  regenerating  kode  adalah sebagai berikut:
1) File  dipecah-pecah  menjadi,  misalnya  {  00, 01,  10,  11}  B 2 .  Selanjutnya  file  tersebut disimpan  dalam  4  node  {  0000,  0101,  1010, 1111}  B 4 .
2) Untuk  proses  rekontruksi  file,  data  collector mengontak  sebarang  tiga  node  tersebut, misalnya  node  1,  2  dan  3,  maka  data  pada node ke 4 akan diperoleh dari node 2 dan 3. Bila ada node yang bermasalah, misalnya node
2 (0101), maka node 2 dapat direkontruksi dengan mengambil informasi dari node 3 dan 4, yaitu 1010 + 1111 = 0101 ( node 2).

## Simpulan
Penelitian  ini  mencoba  suatu  gagasan  untuk menerapkan  kode  modul  pada  teknik  regenerating code  untuk  penyimpanan  terdistribusi.  Hasil  yang diperoleh  melalui  pengkajian  menunjukkan  ada
sebuah  potensi  untuk  mengimplementasikan  kode atas  modul  pada  teknik  regenerating  code.  Hal  ini perlu terus dikembangkan dengan menyelidiki sifat yang  lebih  lanjut  pada  kode  atas  modul,    aspek kepraktisan dan kemudahan dalam teknik komputasi.

## Ucapan Terima Kasih
Tim Peneliti mengucapkan terimakasih kepada
Universitas Negeri Yogyakarta, khususnya Fakultas  MIPA  yang  telah  mendanai  kegiatan penelitian ini.

## Pustaka
[1]  F.  Oggier . 2013, On  Coding  Techniques  for Networked  Distributed  Storage  Systems. First European  Training  School  on  Network Coding, Barcelona February.
[2]  F . Oggier.,  A.  Datta.  2012 Coding  Techniques for  Repairability  in  Networked  Distributed Storage Systems . [3]  T. Chareonvisal . 2012 Implementing
Distributed  Storage  System  by  Network Coding  in  Presence  of  Link  Failure. Master Thesis Report .
[4]  A.  G.  Dimakis,  P.  B.  Godfrey,  Y.  Wu,  M.  J. Wainwright,  and  K.  Ramchandran,  2010, Network  coding  for  distributed  storage systems," IEEE Trans. on Info. Theory , Sep.
[5]  A. G. Dimakis, K. Ramchandran, Y. Wu, and C. Su, 2010, A Survey on Network Codes for Distributed  Storage, The  Proceedings  of  the IEEE , vol. 99, pp. 476–489
[6]  V.  Venkatesan,  2011, Distributed  storage systems , IBM Zurich Research Lab.EPFL
[7]  C.  Fragouli  and  E.  Soljanin,  2007, Network coding fundamentals , Now Publishers, Jun.
[8]  R.Dougherty,  C.Freiling,  dan  K.  Zeger.  2005, Insufficiency  of  Linear  Coding  in  Network Information  Flow. IEEE  transactions  on information theory , vol. 51, no. 8, August
[9]  M.  Gadouleau,  2009,  Algebraic  Codes  for Random  Linear  Network  Coding. P.hD dissertation , Lehigh University.
[10]  K. V. Rashmi , N. B. Shah , K. Ramchandran and  P.  V.  Kumar,  2012,    Regenerating  codes for errors anderasures in distributed storage,  Proc. IEEE ISIT,  pp.1202 -1206
[11]  Agus  Maman  Abadi,  Musthofa,  Emut. (2014)Studi  Awal  Penerapan  Aljabar  Max Plus  pada  Sistem  Penyimpanan  Terdistribusi (Distributed Storage System) Melalui
Network  Coding. Penelitian  DIPA  FMIPA UNY .
[12]  K. V. Rashmi, N. B. Shah, P. Vijay Kumar, K. Ramchandran,  2009, Explicit  Construction  of Optimal Exact Regenerating Codesfor Distributed Storage , Allerton