I nte rna t io na l J o urna l o f   E lect rica l a nd   Co m p ute E ng in ee ring   ( I J E CE )   Vo l.   10 ,   No .   1 Feb r u ar y   2020 ,   p p .   3 6 0 ~ 3 7 6   I SS N:  2 0 8 8 - 8708 DOI : 1 0 . 1 1 5 9 1 / i j ec e . v 1 0 i 1 . p p 3 6 0 - 376          360       J o ur na l ho m ep a g e h ttp : //ij ec e. ia esco r e. co m/in d ex . p h p /I JE C E   A surv ey  of data   recov ery o n f la sh  m e m o ry       Va n   Da i   T ra n ,   Do ng - J o o   P a rk   De p a rtme n t   of   C o m p u ter S c ien c e   a n d   E n g in e e rin g ,   S o o n g sil  Un iv e rsity ,   Ko re a       Art icle  I nfo     AB ST RAC T     A r ticle  his to r y:   R ec eiv ed   No v   28 ,   2 0 1 8   R ev i s ed   A u g   5 ,   20 19   A cc ep ted   A u g   29 ,   2 0 19       In   re c e n y e a rs,  f l a sh   m e m o r y   h a b e c o m e   m o re   w id e l y   u se d   d u e   to   it s   a d v a n tag e s,  su c h   a fa st  d a ta  a c c e ss ,   lo w   p o we c o n su m p ti o n ,   a n d   h ig h   m o b il it y .   Ho we v e r,   f las h   m e m o ry   a lso   h a d ra w b a c k th a n e e d   to   b e   o v e rc o m e ,   su c h   a e ra se - b e f o re - w rit e ,   a n d   th e   li m it a ti o n o f   b lo c k   d e letio n .   In   o r d e t o   a d d re ss   th is   issu e ,   t h e   F T L   (F las h   T ra n sla ti o n   L a y e r)   h a b e e n   p ro p o se d   w it h   u se f u f u n c ti o n a li ti e li k e   a d d re ss   m a p p in g ,   g a rb a g e   c o ll e c ti o n ,   a n d   w e a r - le v e li n g .   D u rin g   th e   p r o c e ss   o f   u sin g ,   th e   d a ta  m a y   b e   lo st o n   p o w e f a il u re   in   th e   sto ra g e   s y ste m s.  In   so m e   s y ste m s,  th e   d a ta i s v e r y   im p o rtan t.   T h u re c o v e r y   o f   d a ta  in   th e   e v e n o f   th e   sy ste m   c r a sh   o a   su d d e n   p o w e o u tag e   is  o f   p rim e   i m p o rt a n c e .   T h is  p ro b lem   h a a tt ra c ted   a tt e n ti o n   f ro m   re s e a rc h e rs  a n d   m a n y   s tu d ies   h a v e   b e e n   d o n e .   In   t h is  p a p e r,   w e   in v e stig a te  p re v io u stu d ies   o n   d a ta  re c o v e ry   f o f las h   m e m o r y   f ro m   F TL   p ro c e ss in g   so lu ti o n t o   P L ( P o w e L o ss   Re c o v e r y so lu ti o n th a h a v e   b e e n   p ro p o se d   b y   a u th o rs  in   t h e   c o n f e re n c e   p ro c e e d in g ,   p a ten ts,   o p ro f e ss io n a jo u r n a ls.   T h is  w il p r o v id e   a   d isc u ss io n   o f   th e   p ro p o se d   so l u ti o n to   t h e   d a ta   re c o v e r y   in   f las h   m e m o r y   a w e ll   a s an   o v e rv ie w .   K ey w o r d s :   Data   r ec o v er y     Flas h   m e m o r y   FT L   P L R   Co p y rig h ©   2 0 2 0   In stit u te o A d v a n c e d   E n g i n e e rin g   a n d   S c ien c e   Al rig h ts  re se rv e d .   C o r r e s p o nd ing   A uth o r :   Do n g - J o o   P ar k ,     Dep ar t m en t   o f   C o m p u ter   Scie n ce   an d   E n g i n ee r in g ,   So o n g s il Un iv er s it y ,   3 6 9   San g d o - ro ,   Do n g j ak - gu ,   S eo u l,  ( 0 6 9 7 8 ) - Ko r ea .   E m ail:  d j p ar k @ s s u . ac . k r       1.   I NT RO D UCT I O N   Flas h   m e m o r y   i s   n o w   a v ailab le  in   m o s ar ea s   o f   th e   w o r ld ,   b ec au s o f   i ts   ad v an ta g e s   s u ch   as   f ast   d ata  ac ce s s   a n d   lo w   p o w er   co n s u m p t io n .   I a ls o   h as   s o m e   wea k n e s s e s   i n cl u d in g   er ase - b ef o r e - w r ite   o r   li m ited   lif c y c le  ( e. g . ,   th n u m b er   o f   er ases   is   li m ited   ar o u n d   1 0 0 0 0   ~   1 0 0 0 0 0   tim e s   p er   ea ch   b lo ck ) .   T o   ad d r ess   th ese  s h o r tco m i n g s   o f   f la s h   m e m o r y ,   th FT L   h as  b ee n   p r o p o s ed   w i th   u s e f u f u n ct io n alitie s   lik ad d r ess   m ap p in g ,   g ar b ag co llectio n ,   an d   w ea r - lev el in g .   I n   ad d itio n ,   th r ec o v er y   o f   d ata  i n   th e   e v en t   o f   t h s y s te m   cr ash   o r   s u d d en   p o w er   o u ta g is   o f   p r i m i m p o r tan ce .   He n ce   m a n y   m eth o d s   h a v b ee n   p r o p o s ed   to   ad d r ess   th d ata  lo s s   w h en   s u d d en   p o w er   o u tag o r   p o w er   f a ilu r o cc u r s   lik FT L   p r o ce s s i n g   s o lu tio n s   o r   P L R   s o lu tio n s .   FT L   [ 1 ,   2 ]   h as   t h r ee   f u n ct io n alitie s   i n cl u d in g   lo g ical   t o   p h y s ical  ad d r ess   m ap p in g ,   g ar b ag e   co llectio n ,   an d   w ea r - le v elin g .   So m e   FT L   al g o r ith m s   h av b ee n   p r o p o s ed   to   o v er co m e   th e   p h y s ica l   li m ita tio n s   an d   i m p r o v th e   o v er all  p er f o r m a n ce   o f   f las h   m e m o r y .   De s p ite  t h f ac t h at   t h p er f o r m a n ce   o f   f las h   m e m o r y   h as  b ee n   e n h a n ce d   b y   u s in g   FT L   alg o r it h m s ,   it  m a y   e x p er ien ce   p er f o r m a n c d eg r ad atio n   w h en   p er f o r m in g   B - tr ee   d ir ec in d ex in g   b ec a u s t h ac t iv it y   o f   f la s h   m e m o r y   o v er w r i tes  f r eq u en tl y   o cc u r s   i n   th ca s o f   u p d ate  n o d es.  T o   s o lv th i s   p r o b lem ,   s o m B - tr ee   v ar ian ts   h a v b ee n   p r o p o s ed .   So m o f   th e s e   B - tr ee s   u s t h m ai n   m e m o r y   as  b u f f er s   to   d ela y   u p d ates  o n   t h B - tr ee .   An y   i n s er ted   r ec o r d   is   te m p o r ar il y   s to r ed   in   th b u f f er .   W h e n   t h e   b u f f er   is   f u ll,  all  t h r ec o r d s   in   t h b u f f er   ar tr an s f e r r ed   to   th f las h   m e m o r y .   T h ese  B - tr ee   v ar ian ts   p r o v id g o o d   p er f o r m a n ce   as  th n u m b er   o f   f las h   ac tiv i ties   d ec r ea s es.  Ho w e v er ,   th er e   Evaluation Warning : The document was created with Spire.PDF for Python.
I n t J   E lec  &   C o m p   E n g     I SS N:  2 0 8 8 - 8708       A   s u r ve o f d a ta   r ec o ve r o n   f la s h   mem o r ( V a n   Da i Tr a n )   361   is   r i s k   o f   lo s in g   d ata   if   p o w er   o u tag e   o cc u r s   b ec au s e   m an y   r ec o r d s   ar in   th e   m a in   m e m o r y .   Mo r eo v er ,   th e y   co n s u m s o m o f   th m ai n   m e m o r y   r eso u r ce s   th a t a r lim ited   in   d i f f er en t e m b ed d ed   s y s te m s .   Ma n y   s tu d ie s   o n   th P L R   s ch e m [ 3 - 6 ]   h av b ee n   p r o p o s ed   to   h elp   th s to r ag s y s te m   a v o id   lo s in g   d ata.   T h ese  s t u d ies   ca n   b cla s s i f ied   i n to   3   g r o u p s .   T h f ir s t   g r o u p ,   I n - B lo ck   B ac k u p ,   r ese r v es  ce r tai n   b lo ck s   in   f las h   m e m o r y   f o r   m etad at an d   s to r es  m o d if ied   m etad ata  in to   b lo ck s   w h en e v er   t h e r is   an y   c h an g e.   I n   th e v en o f   s u d d en   p o w er   o cc u r ,   th s to r ag co n tr o lle r   lo ca tes  th m e tad ata  ar ea   an d   u s es  i n f o r m atio n   s to r ed   in   t h e   ar ea   d u r i n g   b o o to   r esto r th s y s te m   s tate.   T h s ec o n d   i s   ca lle d   I n - P ag e   B ac k u p .   I n   th is   ap p r o ac h ,   th p ag w h i ch   co n tai n s   th m etad ata  ass o ciate d   w it h   ea ch   p ag is   also   s to r ed   in   its   b ac k u p   ar ea .   Du r in g   t h r e s to r p r o ce s s ,   t h co n tr o ller   w ill  r eb u i ld   th s y s te m   s ta te  b y   u p d atin g   t h b ac k u p   ar ea   o f   ea ch   p ag e.   Fi n all y ,   H y b r id   B ac k u p   i s   m i x t u r o f   t h ab o v t w o   tec h n iq u es:  i p er io d icall y   s to r es  b ac k u p   o f   th m ap p ed   tab le  in   th e   m e tad ata  ar ea   an d   it  also   co p ies  th m a p   in f o r m atio n   in to   th ar ea   f o r   th co r r esp o n d in g   d ata  p ag e.   I n   f ac t,  th ese  alg o r it h m s   h e lp   th s y s te m s   r ed u ce   t h r is k   o f   lo s i n g   d ata.     Ho w e v er ,   th e s tech n iq u es  m a y   ca u s h ig h   co s t s   f o r   s to r ag s y s te m s   b ec au s t h e y   r eq u ir an   ad d itio n al  f las h   p r o g r am   f o r   ev er y   m ap p in g   u p d ate.   I n   ad d itio n ,   th e y   ta k lo n g   ti m e   to   r ep r o d u ce   th m e tad ata  f r o m   th b ac k u p   ar ea ,   esp ec iall y   b ac k in g   u p   in   t h p ag e.   T h is   ar ticle  p r o v id es  a n   o v er v ie w   o f   t h tec h n iq u e s   a n d   m e th o d s   p r o p o s ed   to   s o lv t h p r o b lem   o f   r ec o v er in g   d ata  o n   f las h   m e m o r y   i n   ter m s   o f   p o licies.   T h e   r est o f   t h is   p ap er   is   s tr u c tu r ed   as f o llo w s :   Sectio n   2   r ev ie w s   t h f u n d a m e n tal  k n o w led g e   o f   f la s h   m e m o r y ,   FT L ,   B - tr ee ,   an d   T* - tr ee .   Nex t,  Se ctio n   3   is   p r esen ted   by   t h r ec o v er y   tec h n iq u e s   o f   f las h   m e m o r y   a n d   f i n all y ,   Sec tio n   4   co n clu d es t h p ap er .       2.   B ACK G RO UND  AN RE L AT E WO RK   2 . 1 .   F la s m e m o ry   Flas h   m e m o r y   [ 1 ,   2 ]   is   n o n - v o latile  s to r ag f o r m at  u s ed   to d ay .   Un li k tr ad itio n al  h ar d   d is k   s to r ag e,   th f las h   m e m o r y   co n tain s   r a n g o f   m e m o r ies,  co n tr o ls ,   an d   S R A Ms  t h at  ar u s ed   as  in p u b u f f er s   an d   s to r li n k   in f o r m at io n .   N A N f las h   m e m o r y   co n s is t s   o f   s e v er al  b lo ck s ,   ea c h   co n ta in i n g   a   n u m b er   o f   p ag es  ( f o r   ex a m p le,   3 2 ,   6 4 ,   o r   1 2 8 ) .   T h p ag e   i s   t h e   s m all est  u n i f o r   r ea d   an d   w r ite   o p er atio n s   w h ile   t h e   b lo ck   is   th s m al lest   u n it o f   er ase  o p er atio n s .   Flas h   m e m o r y   s u p p o r ts   th r ee   b asic  o p er atio n s r ea d ,   w r ite,   an d   er ase.   R ea d   o p er atio n   is   th f a s test   o n a m o n g   t h ese  o p er atio n s ,   w h ic h   is   ab o u t 1 0   ti m e s   f a s ter   th an   w r ite  o p er atio n .   T h er ase  o p er atio n   is   v er y   ti m e - co n s u m i n g p er - b lo ck - er ase - ti m u s u all y   tak e s   ab o u 2 m s ,   o v er   1 0   ti m es  s lo w er   t h an   w r it e   o p er atio n .   Flas h   m e m o r y   is   h i g h - d e n s it y   s to r ag d ev ice   w h ic h   r eq u ir e s   a n   ad d itio n a la y er   o f   s o f t w ar ca lled   th F las h   T r an s latio n   L a y er   ( FT L )   [ 1 ,   2 ]   to   co n tr o l   an d   m an a g d ata  to   i m p r o v e   th p er f o r m an ce   o f   f las h   m e m o r y .   T h er ar t w o   ty p es  o f   f la s h   m e m o r y N OR   an d   N A ND.   NO R   f las h   m e m o r y   is   u s ed   in   th i n d u s tr y .   I p r o v id es  a n   e as y - to - u s an d   u s er - f r ien d l y   i n ter f ac f o r   co d ex ec u tio n   a n d   m a k es   g o o d   d ev ice  w it h o u d ata  s to r ag e.   Sin ce   NO R   f las h   m e m o r y   p er f o r m an ce   i s   g o o d   at  r ea d in g ,   b u n o g o o d   at   er asin g   an d   w r iti n g ,   it  i s   u s ed   as  s to r ag d ev ice.   Ho w ev e r ,   to d ay ' s   d ev ic e s   ar b ec o m i n g   s m a ller   b y   d a y ,   s o   th e y   ar e   ex p ec ted   to   o f f er   m o r f ea tu r e s ,   an d   m o r in f o r m atio n   s to r ag e.   C ap ac it y   r eq u ir e m en ts   ar m o r i m p o r tan f ac to r   th an   t h ab il it y   to   co d an d   s to r d ata,   a n d   s ig n i f ica n tl y   f a s ter   er ase  ti m es.  N AND  f la s h   m e m o r y   p r o v id es  all  th ab o v f ea tu r e s   an d   af f o r d ab le  p r ic in   ca p ac ities .   Ho w ev er ,   en g i n ee r s   d o   n o lik to   u s it   b ec au s o f   co m p le x   m a n ag e m e n a n d   n o n - s tan d ar d   in ter f ac e.   T h s tr u ct u r o f   N AN Flas h   m e m o r y   is   s h o w n   in   F ig u r 1 .                                 Fig u r 1 .   Stru ct u r o f   N A ND  f las h   m e m o r y         A p p l i c a t i o n   R e a d   &   W r i t e   Er a se   F l a sh   T r a n sl a t i o n   L a y e r   S e c t o r   0   S e c t o r   0   S e c t o r   1   S e c t o r   0   S e c t o r   1   S e c t o r   1   S e c t o r   2   S e c t o r   2   S e c t o r   2   M a p p i n g   T a b l e       S e c t o r   3 1   S e c t o r   3 1   S e c t o r   3 1   C o n t r o l l e r   B l oc 1   B l oc 0   B l oc n     Evaluation Warning : The document was created with Spire.PDF for Python.
                      I SS N :   2 0 8 8 - 8708   I n t J   E lec  &   C o m p   E n g ,   Vo l.  10 ,   No .   1 Feb r u ar y   2 0 2 0   :   3 6 0   -   376   362   2 . 2 .   F la s t ra ns la t io n la y er   ( F T L )   T h Flas h   T r an s latio n   L a y er   ( FT L )   is   g o o d   en v ir o n m en s o f t w ar m o d u le  f o r   s to r in g   d ata.   I r ec o r d s ,   an d   m o d if ie s   i n f o r m at io n   f r o m   a n   e m p t y   p a g a n d   m o v es  th e   r eq u est  t o   th n e w   ad d r ess .   FT L   en s u r es  t h at  th m o s r ec en r ec o r d   is   d is tr ib u ted   ac r o s s   all  p ag es  th a ar lik el y   to   b p r o ce s s ed .   I k ee p s   lis o f   i n v alid   p ag es,  m ar k er s ,   d eletio n s ,   an d   r eu s e.   T h m ain   p u r p o s o f   FT L   is   to   s i m u late  th f u n ctio n   o f   tr ad itio n al  d ev ice  b lo ck   w it h   i ts   c h ar ac ter is tic  f la s h   m e m o r y   clea r e d   b ef o r r ec o r d in g .   I p r o v id es   th p r o ce s s   o f   co n v er ti n g   f r o m   lo g ical  ad d r ess es  to   p h y s ic al  ad d r ess es,  g ar b ag co llectio n ,   an d   w ea r   lev eli n g   w h e n   r eq u ested   [ 2 2 ,   2 3 ] .   N A N f la s h   m e m o r y   h a s   lo g   er ase  ti m w h en   p er f o r m in g   b lo ck   d elete   o p er atio n .   W ith   FT L   lo g   er as ti m e   is   tr an s f er r ed   w h en   F T L   w r ite s   d ata  to   a n   a v ailab l p h y s ical  p a g a n d   th en   m ar k s   t h d ata  co n tain in g   th p r ev io u s   p a g as i n v al id   d ata  r ath er   th a n   d eletin g   t h en t ir b lo ck .   On o f   th m a in   f u n ctio n s   o f   FT L   is   th ad d r ess   m ap p i n g .   B asicall y ,   it  m ap s   lo g ica ad d r ess es  f r o m   th h o s to   p h y s ical  ad d r ess es   o f   f lash   m e m o r y .   T h b asic  ad d r ess   m ap p in g   alg o r it h m s   c an   b d iv id ed   in to   th r ee   s c h e m es   b ased   o n   t h m ap p in g   u n it:   s ec to r   m a p p in g ,   b lo ck   m ap p in g ,   an d   h y b r id   m ap p i n g .   Secto r   m ap p in g   is   u n it - b ased   m ap p in g ,   m ap p in g   u n i o f   b lo ck - m ap p in g   i s   b lo ck ,   an d   h y b r id   m ap p in g   is   to   r e m ed y   s h o r tco m i n g s   o f   s ec to r - m ap p in g   a n d   b lo ck   m ap p i n g .   H y b r id   m ap p in g   h a s   b ee n   wid el y   u s ed   in   lar g e   s ca le  s y s te m s .   T h H y b r id   p o lic y   h as  s h o w n   h u g e   i m p r o v e m en ts   o n   th p er f o r m an ce   o f   FT L .   T ab le  1   s h o w s   th co m p ar is o n   o f   FT L   alg o r it h m s .       T ab le  1 .   C o m p ar is o n   o f   FT L   alg o r ith m s   [ 1 ]   A l g o r i t h m   M a p p i n g   t a b l e   si z e   A d d r e ss c o mp u t a t i o n   o v e r h e a d   R e a d   c o st   S e c t o r   map p i n g   L a r g e   N o   o v e r h e a d   L o w   B l o c k   m a p p i n g   L e ss t h a n   S e c t o r   ma p p i n g   Y e s   L o w   H y b r i d   ma p p i n g   S a me   a B l o c k   m a p p i n g   Y e s   H i g h       Me tad ata   is   o n o f   th i m p o r tan co m p o n e n ts   o f   th s to r ed   d ata.   I is   u s ed   to   d escr ib w h at,   w h er e,   an d   h o w   d ata  is   s to r ed   o n   th m ed iu m .   T h ad d r ess   m ap p in g   d ata  i n   t h m etad ata   is   u s u all y   co m p o s ed   o f   th lo g ical  ad d r ess   n u m b er   an d   th p h y s ical  ad d r ess   n u m b e r .   FT L   u s es  th i s   i n f o r m atio n   t o   cr ea te  an   ad d r es s   m ap p in g   tab le.   So ,   w h e n   t h h o s a s k s   f o r   an   o p er atio n   ass o ciate d   w it h   th e   d ata  ( th i s   d at is   s to r ed   in   f la s h   m e m o r y )   FT L   u s es  a n   ad d r e s s   m ap p in g   tab le  en tr y .   Yo u   m a y   h a v n o ticed   th a th m etad ata   o f   ad d r ess   m ap p in g   is   v er y   i m p o r tan i n   th FT L   alg o r ith m .   W h e n   h o s r eq u ests   w r ite  o p er atio n ,   FT L   ch o o s es  o n o f   t w o   s ce n ar io s .   Firs t,  i f   t h er i s   n o   d ata  in   t h r eq u ested   ad d r ess ,   FT L   w r i tes  t h d ata  d ir ec tl y   to   th a ad d r ess .   Oth er w i s e,   if   th er i s   t h d ata  in   t h r eq u ir ed   ad d r ess ,   FT L   f i n d s   t h ap p r o p r iate  ad d r ess   to   co m p lete   th e   w r ite  o p er atio n ,   an d   in f o r m at io n   c h an g e   is   s to r ed   else w h er i n   t h f las h   m e m o r y .   I f   FT L   d o e s   n o s a v ch a n g ed   in f o r m atio n   it  w il b v er y   d i f f icu l to   f in d   th d ata  w h e n   th h o s w a n ts   to   f i n d   it  later .   So   F T L   w il s to r in f o r m atio n   i n   f las h   m e m o r y .   Fig u r 2   s h o w s   t h s tr u ct u r o f   Fla s h   T r an s latio n   L a y er .                             Fig u r 2 .   T h f lash   tr a n s latio n   la y er   s tr u ct u r e       2 . 3 .   B - t re   B - tr ee   [ 7 ]   is   tr ee - t y p e   d at s tr u ct u r t h at   allo w s   s ea r c h in g ,   s eq u e n tial   ac ce s s ,   in s e r tio n ,   an d   d eletio n   in   lo g ar it h m ic  ti m e.   B - tr ee   is   g en er aliza t io n   o f   t h b in ar y   s ea r ch   tr ee   in   w h ic h   n o d ca n   h a v m o r t h a n   t w o   ch i ld r en .   Un l i k s el f - b alan ci n g   b in ar y   tr ee s ,   B - tr ee s   ar o p ti m ized   f o r   la r g e   r ea d   an d   w r ite  s y s te m s .   T h e y   ar o f ten   u s ed   in   d atab ases   an d   f ile  s y s te m s .   I n   B - tr ee ,   n o n - leaf   n o d es  m a y   h av d if f er en t   n u m b er   o f   n o d es,  li m i ted   to   a   ce r tain   r an g e.   W h en   d ata  is   i n s er ted   to   o r   d elete d   f r o m   n o d e,   th n u m b er   o f   P h y si c a l   me mo r y   0   1   2   3   4   5   6   7     P a g e   0     P a g e   2   P a g e   1       P a g e   3   L o g i c a l   me mo r y   P a g e   t a b l e   P a g e   0   P a g e   1   P a g e   2   P a g e   3   0   1   2   3   1   4   3   7   Evaluation Warning : The document was created with Spire.PDF for Python.
I n t J   E lec  &   C o m p   E n g     I SS N:  2 0 8 8 - 8708       A   s u r ve o f d a ta   r ec o ve r o n   f la s h   mem o r ( V a n   Da i Tr a n )   363   its   c h ild   n o d es  i s   c h an g e d .   W h en   u s in g   a   B - tr ee ,   w e   p r escr ib an   i n te g er   f o r   t h e   m i n i m u m   d eg r ee .   E ac h   n o d i n   t h B - tr ee   ( ex ce p th r o o n o d e)   h a s   t - 1   to   2 t - 1   k e y s   w h ich   en s u r e s   t h at  n o d es  ca n   b s p lit  o r   co m b i n ed .   W ith   an   i n ter n al  n o d h av in g   2 t - 1   lo ck s ,   w ca n   g et  th m id d le  k e y ,   in s er it  i n to   th p ar en n o d e,   an d   s p lit t h r e m ain in g   2 t - 2   k e y s   i n to   t w o   n e w   n o d es,  ea ch   with   t - 1   k e y s .   Si m ilar l y ,   w h e n   e ac h   t w o   n o d es h a s   t - 1   lo ck s ,   y o u   ca n   co m b in e   t h ese  t w o   n o d es  w it h   k e y   f r o m   t h p ar en n o d in to   a   n e w   o n w it h   2 t - 1   k e y s .   T h n u m b er   o f   ch ild   n o d es  o f   n o d is   ex ac tl y   eq u al  to   th n u m b er   o f   k e y s   o f   th at  n o d p lu s   o n e.   T h er ef o r e,   th n u m b er   o f   n o d es o f   a n   in n er   n o d is   f r o m   t to   2 t.   B - tr ee   m ai n tai n s   b alan ce   b y   en s u r in g   t h at  leaf   n o d es  h av e   th s a m d ep th .   T r ee   h eig h t   in cr ea s es   g r ad u all y   a s   n e w   n o d es  ar in s er ted   in to   t h tr ee ,   b u th is   n u m b er   ch an g e s   v er y   s lo w l y .   As  th h ei g h o f   th tr ee   in cr ea s es,  t h d ep t h   o f   all   lea f   n o d es  i n cr ea s e s   at   th s a m ti m e.   B - tr ee   h as   th e   a d v an ta g o v er   o th er   s ea r ch   d ata  s tr u ct u r es  w h e n   ac ce s s   ti m is   m u c h   lar g er   th an   co n s ec u tiv r ea d s .   T h is   u s u all y   o cc u r s   w h e n   th n o d es  ar s to r ed   o n   ex ter n al  m e m o r y .   B y   i n cr ea s i n g   t h n u m b er   o f   c h ild r en   o f   ea ch   n o d e,   th h e ig h o f   th tr ee   d ec r ea s e s   a n d   th e   n u m b er   o f   h it s   d ec r ea s es.  I n   ad d itio n ,   th e   n u m b er   o f   r e - b al a n cin g   o p er atio n s   i s   r ed u ce d .   T y p icall y ,   t h p ar am eter   ( d eter m i n es  t h n u m b er   o f   k ey s   p er   n o d e)   is   s el ec ted   ac co r d in g   to   th a m o u n t o f   i n f o r m atio n   in   e ac h   k e y   a n d   t h s ize   o f   ea c h   d i s k   b lo ck .   T h B - tr ee   ter m   ca n   b u s ed   to   r ef er   t o   s p ec if ic  d esig n ,   w h i c h   ca n   also   b u s ed   to   d esig n   class   o f   d esig n s .   I n   n ar r o w   s e n s e,   th B - tr ee   s to r es  s o m lo c k s   o n   t h n o d es  a n d   d o es  n o s to r co p ies  o f   th o s lo ck s   o n   t h leaf   n o d e.   I n   b r o ad   ter m s ,   it  a ls o   in cl u d es o th er   v ar ia n ts   s u c h   as   B + - tr ee   [ 8 ]   o r   B * - tr ee .   a.   I n   th e   B+ - tr ee   all  k e y s   alo n g   w it h   ac co m p a n y i n g   d ata,   ar s to r ed   at  leaf   n o d es.  I n   ad d itio n ,   leaf   n o d es a ls o   h av p o in ter   to   th n e x t le af   n o d es to   ac ce ler ate  s eq u en tia l a cc ess .   b.   B* - tr ee   p er f o r m s   m o r r eb ala n cin g   o p er atio n s   to   s to r d en s er   d ata.   E ac h   n o d i n   t h r o o n o d m u s b e   f illed   to   t w o - t h ir d s   i n s tead   o f   o n l y   h al f   as in   B - tr ee .   Fig u r 3   s h o w s   t h s tr u ct u r o f   ap p licatio n   u s i n g   B - T r ee   o v er   Flas h   m e m o r y .           Fig u r 3 .   B - T r ee   o n   f las h   m e m o r y       2 . 4 .   T* - t ree  ind ex   t ec hn iqu e   T h is   tech n iq u u s e s   T * - tr ee ,   w h er all  d ata  is   s to r ed   in   th m ai n   m e m o r y   d e v ice  u n li k th ex is tin g   d is k - b ased   i n d ex i n g   tec h n iq u es.  T h is   i n d ex   s tr u ctu r m o d i f ies   d ef ec t s   a n d   allo w s   f a s ter   ac ce s s   to   d ata  an d   ef f icien u s o f   m e m o r y ,   w h i ch   ar ad v a n tag e s   o f   th e   T - tr ee   in d ex   s tr u c tu r u s ed   i n   b a s e   s y s te m s   o f   m ai n   m e m o r y   d ata   [ 9 ] .   T h s tr u ct u r o f   T * - tr ee   i s   s h o w n   i n   Fi g u r 4 .   I n   ad d itio n ,   u n li k e   in   t h T - tr ee ,   in s er ted   d ata   ite m s   in   t h n o d es  o f   T * - tr e ar s to r ed   in   o r d er   f r o m   t h lef t;  s o   th e m p t y   s p ac is   al w a y s   to   th le f t.   E ac h   ele m e n i n   th e   n o d is   co n f i g u r ed   w it h   s i n g le  k e y   v alu a n d   th ad d r ess   o f   th d ata  ite m   h as  k e y   v alu e,   a n d   th e y   ar re - o r d er ed   ac co r d in g   to   th s ize  o f   th ite m   [ 9 ] .   As  s h o w n   in   Fi g u r 4 ,   t h r ea r   cu r s o r   is   ad d ed   to   th T * - tr ee   p o in tin g   at  t h r ea r   n o d e s   th a ar e   c o n f i g u r ed   f o r   s u cc es s iv e   v al u es.  A s   r es u lt,  th T - tr ee ' s   m o v e m e n ts   ar i m p r o v ed   an d   d ir ec tr av er s in g   to   th n e x i s   p o s s ib le,   r ed u cin g   th len g t h   o f   t h m o v e m e n t   p ath .   I n   ad d iti o n ,   w h en   t h n o d es  ar cr ea ted ,   th f ir s ite m ,   o f   th m ax i m u m   v al u e,   is   s to r ed   f r o m   t h r ig h i n   th o r d er .   T h is   all o w s   t h m a x i m u m   o v er f lo w ed   v al u to   b s to r ed   to   th r ig h t m o s o f   t h e m p t y   s p ac o f   t h L UB   ( least  u p p er   b o u n d )   n o d in   ca s o f   o v er f lo w   d u to   d ata   in s er tio n .   I n   t h ca s o f   u n d er f lo w   b y   d e let io n s ,   t h m i n i m u m   v al u f r o m   th L UB   n o d o r   th lef t m o s t   n o d e   is   b o r r o w ed .   B y   p r ev en tin g   t h cr ea tio n   o f   ad d itio n al   d ata  alig n m en o r   m o v e m e n in   n o d es  an d   allo win g   d ir ec t   ac ce s s   to   th L UB   n o d u s in g   th r ea r   cu r s o r   w it h o u g o i n g   th r o u g h   th m id d le  n o d es,  th e   T * - tr ee   s tr u ct u r s h o w s   i m p r o v ed   p r o ce s s i n g   a lg o r it h m s .   Mo r eo v er ,   f o r   ef f icie n u s o f   s to r ag s p ac e,   a n   ad d itio n al   r e ar   cu r s o r   h a s   b ee n   ad d ed   to   th T - n o d s tr u ct u r f o r   T * - tr ee ,   w h e n   co m p ar ed   to   th e x is tin g   T - tr ee ,   w h ile   als o   h av in g   t h s a m s tr u ct u r i n s id e.   B ec au s t h r atio   o f   it e m s   p er   n o d is   n o t   m u c h   d i f f er e n t,  it r etain s   th a d v an ta g o f   T - tr ee s   f o r   its   e f f i cien t sto r ag ca p ac it y   [ 9 ] .   Evaluation Warning : The document was created with Spire.PDF for Python.
                      I SS N :   2 0 8 8 - 8708   I n t J   E lec  &   C o m p   E n g ,   Vo l.  10 ,   No .   1 Feb r u ar y   2 0 2 0   :   3 6 0   -   376   364         Fig u r 4 .   T * - tr ee       2 . 5 .   P o w er - o f f   f a ilu re   I n   t h h ar d w ar s y s te m   co n ce p t,  p o w er   is   a n   i m p o r tan t   r eso u r ce .   I f   y o u   lo s p o w er   s u p p l y   to   h ar d w ar th e n   all  s to p .   T h er ef o r th p o w er   s o u r ce   m u s t   b m an a g ed   ca r ef u l l y .   T h er ar tw o   t y p es  o f   p o w er - o f f :   n o r m al  p o w er - o f f   an d   s u d d en   p o w er - o f f .   W o n l y   ca r ab o u t   th e   ca s o f   s u d d en   p o w er   o u tag e s   an d   th e y   ar k n o w n   as  p o w er - o f f   f ail u r [ 1 0 ] .   T h is   er r o r   h as  h u g i m p ac an d   d ata.   I n   th s to r ag e   v ie w ,   f las h   m e m o r y   is   h ar d w ar c o m p o n en t,  s o   it  ca n n o t   av o id   p o w er - o f f   f ail u r e.   W h en   p o w e r   f ailu r e   h ap p en s   i n   f las h   m e m o r y ,   it  m u s t   s u f f er   u n w an ted   er r o r s .   T h er ef o r e,   m an a g i n g   t h lo s s   o f   p o w er   in   th f las h   m e m o r y   i s   i m p o r tan t.  W h en   t h m ap p in g   tab le  ch an g es  i n   th p ag m ap p in g   FT L ,   ex is ti n g   d ata  is   u p d ated   o r   er ased   f r o m   f la s h   m e m o r y .   First,  i f   ex is ti n g   d ata  i s   u p d ated ,   f la s h   m e m o r y   m u s t   w r ite  d ata  to   an o th er   ad d r ess   b ec au s o f   th f ea tu r t h at  it  ca n n o b o v er w r it ten .   A cc o r d in g l y ,   th m ap p in g   tab le  m u s also   b m o d if ied   to   r ef lect  t h ch a n g ed   ad d r ess ,   an d   if   n o m o d if ied ,   th u p d ated   d ata   ca n n o b a cc ess ed .   Nex t,  w h e n   th m ap p in g   tab le  is   m o d if ie d ,   th d ata  is   d elete d   f r o m   f l ash   m e m o r y .   I f   t h d ata  is   er ased   b y   th h o s o r   th g ar b ag co llect io n   o f   t h FT L ,   th e   m ap p i n g   tab le  m u s t   also   r e m o v ad d r ess   i n f o r m a tio n   f o r   th e   er ased   d ata.   W h en   th m ap p in g   t ab le   is   u p d ated ,   it  is   n ec e s s ar y   to   s to r th ch a n g ed   in f o r m atio n   in   f las h   m e m o r y   to   r ec o v er   p o w er - o f f   f a ilu r o cc u r r in g   later .   Ho w ev er ,   s to r in g   th m ap p i n g   i n f o r m atio n   i n   f las h   m e m o r y   e v er y   ti m d ata  is   u p d ated   ca u s es  t h p er f o r m an ce   o f   f las h   m e m o r y   to   b d eg r ad ed ,   an d   th s to r ag o f   ex ce s s i v m ap p in g   in f o r m at io n   m a y   le ad   to   ca p ac ity   s h o r ta g e.   T h er ef o r e,   in   o r d er   to   s o lv th ab o v p r o b lem ,   th FT L   p er f o r m s   d ata  b ac k u p   o p er atio n   ca l led   f lu s h ”.   FT L   g e n er ates   f lu s h   p r o ce s s es  p er io d icall y   a n d   u s u all y   s to r es  m ap p in g   i n f o r m atio n   in   t h f las h   m e m o r y s   d ata  ar ea   o r   s p ar e   ar ea .       3.   DATA R E CO V E RY  T E CH NIQU E S O F L ASH   M E M O RY   Fig u r 5   s h o w s   an   o v er v ie o f   th s o lu t io n s   to   o v er co m th d ata  r ec o v er y   p r o b le m   o n   Flas h   m e m o r y .   I n   ea ch   g r o u p ,   w e   h ad   in v esti g ated   th r ee   tec h n iq u e s   in   w h ic h   g r o u p   d eter m i n th p r o ce s s ,   alg o r ith m   o r   tec h n o lo g y   to   s o lv th e   p r o b lem   o f   d ata  r ec o v er y   o n   th p o w er - o f f   f ailu r o f   Fla s h   m e m o r y   u s i n g   B - tr ee   i n d ex   b u f f er ,   i n d ex   s e g m en lo g   d ir ec to r y ,   o r   t h ap p r o ac h   to   s u r v i v i n g   th e   u n ex p ec ted   e v en t   b y   s af el y   b ac k i n g   u p   th e   m etad ata.   T h f ir s g r o u p   i n cl u d in g   B FT L ,   I B SF ,   a n d   M R - tr ee ,   th e   s ec o n d   g r o u p   in cl u d in g   B I SL ( B + - T r ee   I n d ex   Se g m e n L o g   T ec h n i ca Dir ec to r y ) ,   T * - I S L D,   a n d   cr ash   r ec o v er y   tech n ical,   an d   t h last   g r o u p   in cl u d in g   A - P L R   ( A cc u m u l atio n   b ased   P o w er   L o s s   R ec o v er y ) ,   HYF L U R   ( HYb r id   FL Us h   R ec o v er y ) ,   a n d   C - HY F L UR   ( C o m p r es s io n   Sc h e m f o r   HYb r id   FL U s h   R ec o v er y ) .   I n   ea c h   g r o u p ,   w co m p ar ed   th tech n iq u es  i n   ea ch   o th er   in   o r d er   to   m ak d ec is io n   ab o u w h ic h   tech n iq u is   th w i n n er .                           Fig u r 5 .   Data   r ec o v er y   tec h n i q u es o n   f las h   m e m o r y   o v er v ie w     A - P L R   P o w e r   L o ss  R e c o v e r y   ( P L R )   H Y F L U R   C - H Y F L U R   MR - t r e e   D a t a   R e c o v e r y   T e c h n i q u e s   o n   F l a sh   me mo r y   B - t r e e   I n d e x   B u f f e r   R e c o v e r y   I n d e x   S e g m e n t   L og  D i r e c t o r y   T e c h n i c a l   B F TL   I B S F   T* - I S L D   B I S L D   C r a sh   r e c o v e r y   Evaluation Warning : The document was created with Spire.PDF for Python.
I n t J   E lec  &   C o m p   E n g     I SS N:  2 0 8 8 - 8708       A   s u r ve o f d a ta   r ec o ve r o n   f la s h   mem o r ( V a n   Da i Tr a n )   365   3 . 1 .   B - t ree  ind ex   bu f f er   re co v er y   m et ho d g ro up   T h is   m et h o d   g r o u p   b u ild s   s ec u r B - T r ee   w it h   l ow   co s t h at  o cc u r s   w h en   s e tti n g   u p   B - T r ee   in   f ast  SS D   b ased   o n   lo w - p o w e r   f las h   m e m o r y .   Mo r eo v er ,   it   ca n   r ed u ce   t h r ec o v er y   ti m af ter   a n   i n cid en t.   T h Flas h - b ased   B - tr ee   in d ex   u s es   f a iled   r ec o v er y   m a n a g e m e n m et h o d   to   co m m it  th d ata  th at  p ass es   th r o u g h   th e   s a v p o in ts   to   th SS D.   T h i s   h elp s   t h s y s te m   r es to r es  t h d ata  ea s il y   wh en   s o m eth in g   w e n t   w r o n g .   T o d ay   B - T r ee   is   m ai n l y   u s ed   i n   m as s   s to r ag d ev ic es  b ec au s e   o f   i ts   e f f icie n s ea r ch in g .   T h er ef o r e,   is s u es t h at  m a y   o cc u r   d u r i n g   t h B - T r ee   s etu p   in   SS Ds ca n   b f o u n d   in   s to r ag s y s te m s   u s i n g   t h B u l k   SS D.     T o   ad d r ess   th ese  is s u e s ,   s o m m e th o d s   s u ch   a s   B FT L ,   I B SF an d   MR - T r ee   tech n iq u e   h av b ee n   p r o p o s ed .   I n s tead   o f   w r iti n g   t h in d e x   u n it s   th at  o cc u r   d u r i n g   t h cr ea ti o n   of   th tr ee   to   th f la s h   d ir ec tl y ,   th ese  m et h o d s   te m p o r ar il y   s t o r th in d ex   u n its   i n   th b u f f er .   W h en   th b u f f er   is   f u ll,  t h in d ex   u n its   ar e   co llected   an d   f l u s h ed   to   t h f las h .   T h r o u g h   t h ese  p r o ce s s es,  t h e y   r ed u ce   t h n u m b er   o f   w r ite   o p er atio n s ,   lead in g   to   t h p er f o r m a n ce   en h an ce m e n t o f   B - T r ee   in d ex   o n   f las h   m e m o r y .     3 . 1 . 1 .   I B SF  t ec hn iqu e   I B SF   u s e s   s o f t w ar m o d u l th at  ca n   in s er f la s h   la y e r   o r   co n v er th f ile   s y s te m Mo r eo v er ,   th o r d er   o f   th e   f la s h   m e m o r y   is   li m ited   to   t h m o r e f f ic ien B - T r ee   co n s tr u ctio n .   I SB is   i m p le m e n ted   th r o u g h   u n its   o f   n o d in f o r m a tio n   ch a n g t h at  o cc u r s   d u to   th ac cu m u latio n   o f   B - tr ee   a n d   k ee p s   t h ca ch e   te m p o r ar il y .   On ce   t h b u f f er   i s   f u ll,  th n o d is   b u ilt   b y   co llectin g   all  th u n its   an d   co m m itted   to   o n p ag e.   I n   ad d itio n ,   I SB F r ed u ce s   th n u m b er   o f   u n its   b y   eli m i n ati n g   t h r ed u n d an u n its   ( u n its   t h at  ar d u p licated )   o r   k ee p in g   it  as  b its tr ea m   m o d e .   T h r o u g h   th i s   p r o ce s s ,   I B SF   d elay s   th ti m th a th b u f f er   is   f u ll  r ed u ci n g   th n u m b er   o f   w r ite   o p er atio n s .   T h er ef o r e,   t h I SB F   ca n   r ed u ce   t h o v er h ea d   o f   co m m itt i n g   b ec au s i t   r eq u ir es  o n l y   o n ac t iv i t y   to   co m p lete   [ 8 ].   Ho w e v er ,   I B S s u f f er s   f r o m   d ata  lo s s   i n   t h ca s e   o f   p o w er   f ail u r b ec au s s o m r ec o r d s   h av n o f l u s h ed   to   f la s h   m e m o r y   y e t,  an d ,   I B SF   also   co n s u m es  t h a m o u n o f   m ai n   m e m o r y .     Fig u r 6   s h o w s   t h ar ch itec tu r o f   I B SF   t h at  i n clu d es   in d e x   b u f f er ,   in s er tio n   p o lic y ,   d elet i o n   p o lic y ,   an d   co m m it  p o lic y .   T h in d e x   b u f f er   k ee p s   i n d ex   u n its   w h i ch   r ef lect  m o d if ied   B - tr ee   n o d es  w h e n   in s er ti n g ,   d eletin g ,   o r   m o d i f y in g   t h r ec o r d s .   A cc o r d in g   t o   t h i n s er tio n   an d   d eletio n   p o licies,  I B SF   h an d le s   in d e x   u n i ts   in   t h in d e x   b u f f er .   I f   t h in d ex   b u f f er   is   f illed ,   it  m a y   g e n er ate  th co m m it  o p er atio n   b y   th co m m it  p o lic y .   Sin ce   I B SF   s to r es  t h i n d ex   f o r   o n n o d o f   th B - tr ee   in   o n p ag e,   it  n ee d s   n o th tr a n s l atio n   tab le  w h ic h   is   an   ad d itio n al  o v er h ea d .   T h is   m a y   i m p r o v t h r ea d   p er f o r m an ce   o f   B - tr ee   a s   co m p ar ed   to   B FT L   b ec au s e   I B SF   v is it s   o n p ag to   r eb u il d   o n n o d e.             Fig u r 6 .   T h ar ch itectu r o f   I B SF       3 . 1 . 2 .   B F T L   t ec hn iq ue   B FT L   is   co m p o s ed   o f   r es er v atio n   b u f f er   a n d   n o d tr an s latio n   tab le.   E v er y   in s er ted   o r   m o d if ie d   r ec o r d   is   te m p o r ar il y   s to r ed   in   t h r eser v atio n   b u f f er .   W h en   th e   r eser v atio n   b u f f er   is   f u ll,  all   r ec o r d s   in   th b u f f er   ar f l u s h ed   to   th f lash   m e m o r y   i n   FIFO  o r d er   b y   an   i n ter n al   ope r atio n   o f   B F T L   ca lled   co m m it.  B FT L   b u ild s   a n   i n d ex   u n i t o   r ef lect  t h p r i m ar y   k e y   in s er t/d elete   to   th e   B - tr e in d e x .   Ma n y   i n d ex   u n it s   w h ic h   b elo n g   to   d if f er e n B - tr ee   n o d es   ca n   b p ac k ed   in to   f e w   s ec to r s   to   r ed u ce   th n u m b er   o f   p ag es   p h y s icall y   w r itte n .   Du e   to   t h is   p ac k i n g   m ec h a n is m ,   in d e x   u n its   o f   o n e   B - tr ee   n o d ca n   n o w   ex i s in   d if f er e n t   Evaluation Warning : The document was created with Spire.PDF for Python.
                      I SS N :   2 0 8 8 - 8708   I n t J   E lec  &   C o m p   E n g ,   Vo l.  10 ,   No .   1 Feb r u ar y   2 0 2 0   :   3 6 0   -   376   366   s ec to r s .   T o   h elp   B FT L   co llect  in d ex   u n it s   o f   t h s a m e   B - tr e n o d an d   m ai n tai n   t h i n f o r m atio n   o f   th e   p ag e s   h av i n g   t h in d e x   u n i ts   o f   t h co r r esp o n d in g   B - tr ee   n o d e,   a   n o d tr an s latio n   tab le   is   u s ed .   A   n o d tr an s la tio n   tab le  is   in tr o d u ce d   as  an   a u x il iar y   d ata  s tr u ct u r to   m a k th e   co llectin g   o f   th i n d ex   u n its   ef f ic ien t.  T h n o d e   tr an s latio n   tab le   m ap s   B - tr ee   n o d to   a   co llect io n   o f   lo g i ca p ag ad d r ess e s   w h er t h r e lated   in d ex   u n it s   r esid e.   B y   u s i n g   t h e   r eser v a tio n   b u f f er ,   B FT L   r ed u ce s   t h n u m b er   o f   f la s h   o p er atio n s .   A lt h o u g h   t h n u m b er   o f   w r it o p er atio n s   is   r ed u ce d ,   B FTL   m a y   g e n er ate  m an y   r ea d   o p er atio n s   to   ac ce s s   a   B - tr ee   n o d b ec au s e   th e   d at o f   o n n o d m a y   b s ca tter ed   i n   s ev er al   p ag es.   T h b u f f er   h o ld s   al l   g en er ated   i n d ex   u n it s   ev e n   th o u g h   th e s ar e   r ed u n d an i n d e x   u n it s ,   s o   th b u f f er   f ill s   u p   q u ick l y .   Mo r eo v er ,   th n o d e   tr an s latio n   tab le  a n d   its   lis m u s b m ain tain ed   in   R A an d   t h eir   s ize s   m a y   g r o w   r ap id l y .   T h er ef o r e,   B FT L   co n s u m e s   t h a m o u n t   o f   m ai n   m e m o r y   a n d   it s   d ata  m a y   b lo s i n   ca s e   o f   s u d d en   p o w er   f ail u r [1 1 - 1 3 ] .     Fig u r 7   s h o w s   an   e x a m p le,   t h in d e x   u n it s   ar p ac k ed   o n   p ag 2 0   an d   2 1   w h e n   in s er ti n g   th d ata   w h ic h   h a v 1 ,   7 ,   9 ,   1 7 ,   2 1 ,   an d   2 4   as  th e   k e y   v al u e.   Si n ce   th in d ex   u n i ts   ca n   b s to r ed   e ac h   o t h er   p ag es  f o r   n o d e,   th e   n o d tr an s late   tab l is   n ee d ed .   I n   o r d er   to   f o r m   a   co r r ec t lo g ical  v ie w   o f   B - tr ee   n o d e,   B FT L   v i s it  all  p ag e s   w h er r elate d   i n d ex   u n i ts   r esid a n d   t h en   co n s tr u c an   u p - to - d at e   lo g ical   v ie w   o f   th e   B - tr ee   n o d as   in   F i g u r 6   n o d E   h as to   r ef er en ce   p ag 1 3   an d   2 0 .           Fig u r 7 .   T h ar ch itectu r o f   B FT L       3 . 1 . 3 .   MR - t re t ec hn iqu   MR - T r ee   [ 1 4 ]   is   d is k - b ased   in d ex   i n   t h s p atial  i n d ex   f o r m   th at  d o es  n o t r eq u ir t h u s o f   p r i m ar y   m e m o r y   b u ca n   s till   ac ce s s   s p atial  d ata.   I n   ad d itio n ,   th MR - T r ee   h as  s p atiall y   s tr u ctu r ed   in d e x   o f   tr an s f o r m ed   s p atial  d ata  t h at   ca n   ac ce s s   t h R - T r ee   [ 1 5 ] .   I n   th m ai n   m e m o r y   s y s te m ,   as  t h d if f er en ce   b et w ee n   th s p ee d   o f   th C P an d   th s p ee d   o f   th m e m o r y   is   i n cr ea s in g ,   it  i s   i m p o r ta n to   r ed u ce   th a m o u n o f   ca s h   th a is   m is s i n g ,   an d   tak i n g   in to   ac co u n th c h ar ac ter is tic s ,   th M R - T r ee   h as  s m all   ad v an ta g o v er   t h R - T r ee   by   s p ee d in g   u p   t h u s o f   t h m i d d le  b u tto n   w h ile  lo w er in g   t h h ei g h o f   t h tr ee .   A l s o ,   th r o u g h   t h u s o f   in d ex in g   tec h n iq u e s   i n   f las h   m e m o r y ,   e f f ec tiv e   ac ce s s   a n d   m an ag e m e n o f   lar g e   a m o u n ts   o f   d ata   is   p o s s ib le.   H o w e v er ,   T r ee   I n d ex   h as   f r eq u e n t c h an g e s   i n   t h i n s er t,  d elete   an d   b r ea k   ac t io n s .   I n   ad d itio n ,   ev en   t h o u g h   node   en tr y   c h an g es,  w r ite  a n d   d elete   o p er atio n s   o cc u r   f r eq u en tl y ,   ca u s i n g   p er f o r m a n ce   d eg r ad atio n   p r o b le m s .   T h er ef o r e,   to   ad d r ess   th is   p r o b le m ,   th r ea lizatio n   o f   a n   ef f ec tiv R - T r ee   an d   r ed u cin g   th f r eq u en c y   o f   t h w r ite   o p er atio n   o f   t h e   B FT L   b u f f er   la y er   an d   f la s h   m e m o r y   s y s te m   i s   u s ed   to   tr o u b les h o o lo w   p er f o r m a n ce .   B u t h er ar p r o b lem s   w i th   s ea r ch   ac ti v itie s ,   an d   w h ile  th e f f ec t iv ap p r o ac h   an d   m an a g e m e n o f   lar g d ata  ar e   p o s s ib le,   t h er is   t h p r ess u r to   d ec o d an d   r ec o r d   s i m ila r   f ield s   i n   t h s a m e   p lace ,   w h e n   t h ac tiv i ties   o f   d y n a m ic  i n s er tio n /d eletio n   an d   r eb alan cin g   o p er atio n s   s u c h   as  s p lit/ m er g e   ar e   m ad e.   Fig u r 8   s h o w s   t h s tr u ctu r o f   MR - T r ee .     MT F   Evaluation Warning : The document was created with Spire.PDF for Python.
I n t J   E lec  &   C o m p   E n g     I SS N:  2 0 8 8 - 8708       A   s u r ve o f d a ta   r ec o ve r o n   f la s h   mem o r ( V a n   Da i Tr a n )   367       Fig u r 8 .   Stru ct u r o f   MR - t r ee       3 . 1 . 4 .   Co m pa riso n   I B SF   ca n   ef f ec ti v el y   r ed u ce   t h n u m b er   o f   w r ite / d elete   o p er atio n s .   Fu r t h er m o r e,   I B SF   eli m i n ate s   th tab le  tr an s latio n   n o d as   a n   ad d itio n al   co s t.  T h er ef o r e,   it   ca n   r ed u ce   t h n u m b er   o f   r ea d in g   ac tiv ities ,   a n d   I B SF   y ield s   b etter   p er f o r m an ce   th a n   B FT L .   T ab le  2   s h o w s   t h r atio   o f   s eq u e n ce   co m p ar is o n   f o r   t h r ea d ,   w r ite,   er ase,   an d   to tal  co s t ( ti m s )   b et w ee n   B FT L   an d   I B SL .       T ab le  2 .   R atio   o f   s eq u en ce   ( R S)  co m p ar is o n   [ 1 1 ]   RS   B F TL   I B S F   0   N u mb e r   o f   p a g e s   N u mb e r   o f   p a g e s   R e a d   ~ 2 0 0 0 0   ~ 5 0 0 0   W r i t e   ~ 1 0 0 0 0   ~ 5 0 0 0   Er a se   ~ 3 0 0   ~ 1 0 0   T o t a l   c o st   ( t i me   s)   ~ 2 0 0 0 0   ~ 1 0 0 0 0   0 . 3       R e a d   ~ 3 0 0 0 0   ~ 1 0 0 0 0   W r i t e   ~ 2 5 0 0 0   ~ 1 0 0 0 0   Er a se   ~ 6 0 0   ~ 3 5 0   T o t a l   c o st   ( t i me   s)   ~ 4 0 0 0 0   ~ 2 0 0 0 0   0 . 5       R e a d   ~ 4 0 0 0 0   ~ 1 0 0 0 0   W r i t e   ~ 3 5 0 0 0   ~ 1 5 0 0 0   Er a se   ~ 9 0 0   ~ 4 0 0   T o t a l   c o st   ( t i me   s)   ~ 5 0 0 0 0   ~ 2 0 0 0 0   0 . 7       R e a d   ~ 5 5 0 0 0   ~ 1 5 0 0 0   W r i t e   ~ 4 5 0 0 0   ~ 2 0 0 0 0   Er a se   ~ 1 2 0 0   ~ 5 0 0   T o t a l   c o st   ( t i me   s)   ~ 6 5 0 0 0   ~ 3 0 0 0 0   1       R e a d   ~ 7 5 0 0 0   ~ 2 0 0 0 0   W r i t e   ~ 6 5 0 0 0   ~ 2 5 0 0 0   Er a se   ~ 1 7 5 0   ~ 7 5 0   T o t a l   c o st   ( t i me   s)   ~ 8 0 0 0 0   ~ 4 0 0 0 0       3 . 2 .   I nd e x   s eg m ent   lo g   direct o ry   t ec hn ica l g ro up   T h is   is   g r o u p   u s i n g   t h i n d ex   s e g m e n lo g   d ir ec to r y   tec h n i q u e s   f o r   f ai lu r r ec o v er y .   T h is   g r o u p   in cl u d es   B I SL D ,   T * - I S L D ,   an d   NA ND  F las h   Fil C r ash   R ec o v er y   T ec h n iq u e.     3 . 2 . 1 .   B I SL t ec hn iqu e   B I SL D   ( B + - T r ee   I n d ex   Seg m en L o g   T ec h n ical  Dir ec to r y )   tech n iq u e   is   f ail u r r ec o v er y   m et h o d   u s i n g   th B + - tr ee   an d   th d ir e cto r y   lo g   b u f f er   [ 1 6 ].   Am o n g   th d if f er en lo g g in g   tec h n iq u es,  it  ap p lies   d ela y   tech n iq u es   f o r   r ec o v er y .   On ce   co m p leted ,   it  p er f o r m s   r ec o v er y   t h r o u g h   r e o p er atio n   an d   w it h   u p d ated   ac tiv itie s   i n   th e   lo g   d ir ec to r y .   T h B I S L D   al g o r ith m   is   as  f o llo w s .   Step   1:   Get   t h i n s e r ted   lea f   n o d es.   Evaluation Warning : The document was created with Spire.PDF for Python.
                      I SS N :   2 0 8 8 - 8708   I n t J   E lec  &   C o m p   E n g ,   Vo l.  10 ,   No .   1 Feb r u ar y   2 0 2 0   :   3 6 0   -   376   368   Step   2 :   Get  n o d w it h   v a lu less   t h an   t h k e y   v al u o f   t h in d ex   n o d e.   Step   3 :   I f   th in s er ted   k e y   i s   lar g er   th an   t h k e y   v al u o f   t h in d e x   n o d e,   f o llo w   th lar g er   v al u k e y .   Step   4 :   T ak th n e x b u tto n .   An d   th la s s tep R ep ea u n til  t h lea f   n o d to   in s er t   is   f o u n d   [ 1 6 ] .   T h is   tech n iq u u s e s   B + - tr ee   a n d   is   p r o n to   u p d atin g   th lo ca tio n   f r eq u e n tl y   i n   t h s a m ar ea   w h ile  w o r k i n g .   Fo r   th at  r ea s o n ,   co s ts   in c u r   i f   t h e   r ec o v er y   p r o ce s s   f ails .   Fi g u r 9   s h o w s   t h r ec o v er y   s tr u ct u r o f   B I S L D.   T h B + - tr ee   alg o r it h m   is   ap p lied   to   th i n s er tio n   a n d   r etr iev al  o f   p ar ticu lar   clie n t   s o   th at  it  i s   p o s s ib le  to   q u ic k l y   r etr ie v t h r ed o   lo g   in   t h ev e n o f   s p ec if ic   clien f ail u r b ec au s it i s   s u p er io r   to   o t h er   in d ex es  w h e n   s e ar ch in g .           Fig u r 9 .   R ec o v er y   s tr u ct u r in   B I SL D       3 . 2 . 2 .   T* - I SL m et ho d r ec o v er y   s y s t e m   s t ruct ure   T h r ec o v er y   s tr u ct u r o f   T * - I SLD  i n cl u d es  t h e   T * - tr ee   in d e x ;   t h lo g   d ir ec to r y   as   s h o w n   in   Fig u r 10 .   T h T * - tr ee   alg o r ith m   is   ap p lied   w h e n   i n s er ti n g   an d   r etr iev i n g   d ata  [ 9 ] .   A p p ly in g   al g o r ith m s ,   r ec o v er y   i s   p er f o r m ed   q u ick l y   b y   q u ick   ac ce s s   to   R ed o L o g ,   w h e n   er r o r s   o cc u r   w it h   s p ec if ic  f la s h   m e m o r y .   T h is   is   b ec au s T * - tr ee   ex ce l s   in   i n s er t io n   a n d   r etr iev a l,  co m p ar ed   to   o t h er   in d e x es [ 9 ].   T h c u r r en t te c h n iq u e   cr ea tes  an   i n d ex   u n it   w h e n   T * - tr ee   is   ch a n g ed ,   m ain tain s   it  i n   t h b u f f e r ,   a n d   e x ec u te s   th e   co m m it   w h en   th b u f f er   is   f u ll.  I al s o   r ec o r d s   an d   s to r es  c h an g t h i n f o r m atio n   in   th lo g ,   co m m it s   al in d ex   u n it s   w h e n   th o r ig i n al  n o d is   c h an g ed   an d   ex ec u tes t h ch ec k p o in t.           Fig u r 10.   R ec o v er y   s tr u ctu r in   T * - I S L D         Failu r r ec o v er y   al g o r ith m   i s   as  s h o w n   i n   Fi g u r 1 1 .   I n s er tio n   an d   r etr ie v al  ar ap p li ed   to   th   T* - tr ee   al g o r ith m .   T h is   a lg o r it h m   r et r iev es  R ed o L o g   in   ca s o f   f ai lu r i n   s p ec i f ic  f las h   m e m o r y   a n d   en ab les   q u ick   r ec o v er y .   T h lo g   r ec o r d   o f   th f ai lu r r ec o v er y   c an   b d i v id ed   in to   R ed o   an d   Un d o   co m m a n d s .   T h lo g   r ec o r d   is   m an a g ed   i n   th lo g   a n d   h as  t h f o r m   o f   <c o m m a n d ,   n o d n u m b er ,   k e y   n u m b er d u r i n g     Evaluation Warning : The document was created with Spire.PDF for Python.
I n t J   E lec  &   C o m p   E n g     I SS N:  2 0 8 8 - 8708       A   s u r ve o f d a ta   r ec o ve r o n   f la s h   mem o r ( V a n   Da i Tr a n )   369   th c h an g es   in   th T * - tr ee .   Fo r   ex a m p le,   <I n s er t,  A ,   2 0 is   co m m a n d   to   i n s er k e y   v a lu o f   2 0   to   th n o d A .   Fo r   f ail u r r ec o v er y ,   t h s to r ed   A ,   B ,   an d   C   n o d es  i n   t h e   f las h   m e m o r y   ar u s ed   to   b u ild   th T * - tr ee ,   an d   t h en   t h lo g   i n f o r m atio n   i s   u s ed   to   p er f o r m   r ec o v er y   b e f o r th f a ilu r e.           Fig u r 1 1 .   Failu r R ec o v er y   A lg o r ith m       3 . 2 . 3 .   NAND  f la s h f ile  cr a s h r ec o v er y   t ec hn iqu e   T h is   tech n iq u i s   u s ed   to   ef f ec tiv el y   r e s e i n   ab n o r m al   f i l s y s t e m   cr a s h   s i tu atio n s   b y   ch a n g in g   th s etti n g s   o f   t h w o r k   ar ea   s o   th at   th e   b u r n   to o o p er atio n   i s   o n l y   u s ed   i n   s p ec if ic   ar ea s   o f   th e n tire   f la s h   m e m o r y   ca p ac it y .   I n   ad d iti o n ,   th w o r k   ar ea   d ata  ca n   b s av ed   i n   th r eser v e d   s p ac e,   s o   w h e n   th i n itializa tio n   i s   d o n e,   t h u s er   ca n   ca p tu r t h co p y   o f   th m o s r ec e n s et  ac tiv it y .   T h r o u g h   t h is   s tr u ct u r e,   o n l y   t h m o s t r ec en w o r k   ar e i s   in s p ec ted   an d   in itia lized   in   ac cid en t s itu a tio n s .   T h am o u n t o f   ti m r eq u ir ed   f o r   cr ash   to   b r esto r ed   co r r esp o n d in g l y   in cr ea s e s   w i th   t h s ize   o f   th w o r k   ar ea .   T h is   tech n iq u e   s o l v es   th p r o b lem   o f   i n cr ea s i n g   s ca l ab ilit y :   n o   m atter   h o w   lar g t h a m o u n o f   f las h   m e m o r y   is ,   th r ec o v er y   ti m e   co r r esp o n d s   to   it.  Ho w e v er ,   th is   tech n iq u h a s   w ea k n e s s   i n   t h ca p ac it y   o f   f la s h   m e m o r y   t h at  i s   n o t   co m m e n s u r ate  w it h   t h r ec o v e r y   t i m [ 1 7 ].   Fig u r 1 2   s h o w s   th cr ash   r ec o v er y   tech n iq u e.                                             Fig u r 1 2 .   C r ash   r ec o v er y   tec h n iq u e         #   o f   b l o c k   0   S e a r c h i n g   s u p e r   b l o c k   C r a sh   d e t e c t i o n :   u n mo u n t   f l a g   i n   i s   n o t   se t   i n   l a t e st   L S D   S e a r c h i n g   l a t e st   l o g   b l o c k   B u i l d i n g   f i l e   sy st e m me t a d a t a   f r o m v a l i d   l o g   b l o c k s .     A t   t h e   same   t i me ,   se a r c h i n g   l a t e st   w o r k i n g   a r e a     f o r   c r a sh   r e c o v e r y   F r e e   b l oc k                           S u pe r   b l oc k   L o g   b l oc k                   D a ta  bl oc k       S e a r c h i n g   mi ss i n g   p a g e   S e a r c h i n g   a n d   r e c o v e r i n g   t h e   m i ssi n g   p a g e s i n   l a t e st   w o r k i n g   a r e a   F S   I n f o .   L o g   S e g m e n t   D i r e c t o r y   L o g   B l o c k   L i st     E C C     V       U                               M i ss i n g   b l o c k   r e a d   S p a r e   a r e a   r e a d   F u l l   p a g e   r e a d   D a t a   b l o c k                                   L a t e st   w o r k i n g   a r e a     M i ss i n g   b l o c k   L o g   b l o c k         Evaluation Warning : The document was created with Spire.PDF for Python.