SlideShare a Scribd company logo
1 of 49
2010-02-26       4   Erlang
1/2
    No Erlang
 


 
                 3

 
         Chord
         VectorClocks
         …
2/2
 
      


 
                         

                          
               
          
       Chord
          EpiChord
              
   BASE            Sinfonia:
                   VectorClocks                         
          
       Bloom       
   ZDD
                                         EpiChord
Lookup
 
 
                                          1
                        0-10
    1
              5?
                        11-20
   2
       2
                        21-30
   3
                                          3
 
      
      
 
                   !
         ?
B. Leong et al. http://www.comp.nus.edu.sg/~bleong/slides/icon-epichord-slides.pdf
     


Address Space

                                           0-63
B. Leong et al. http://www.comp.nus.edu.sg/~bleong/slides/icon-epichord-slides.pdf
     


Mapping Keys to Nodes

                                                 




         1-6
          6
           :
     :
         52-57
        57
           :
     :
B. Leong et al. http://www.comp.nus.edu.sg/~bleong/slides/icon-epichord-slides.pdf
    


Chord
                               


            35    
    36-40
       40
    41-47
       47
    48-50
       49
    51-2
        57
    3-30
        6




                       •      log

                      •      log
B. Leong et al. http://www.comp.nus.edu.sg/~bleong/slides/icon-epichord-slides.pdf
     


EpiChord Lookup Algorithm
B. Leong et al. http://www.comp.nus.edu.sg/~bleong/slides/icon-epichord-slides.pdf
     


EpiChord Lookup Algorithm
B. Leong et al. http://www.comp.nus.edu.sg/~bleong/slides/icon-epichord-slides.pdf
     


EpiChord Lookup Algorithm
B. Leong et al. http://www.comp.nus.edu.sg/~bleong/slides/icon-epichord-slides.pdf
     


EpiChord Lookup Algorithm
B. Leong et al. http://www.comp.nus.edu.sg/~bleong/slides/icon-epichord-slides.pdf
     


EpiChord Lookup Algorithm
B. Leong et al. http://www.comp.nus.edu.sg/~bleong/slides/icon-epichord-slides.pdf
     


EpiChord Lookup Algorithm
B. Leong et al. http://www.comp.nus.edu.sg/~bleong/slides/icon-epichord-slides.pdf
     


EpiChord Lookup Algorithm
B. Leong et al. http://www.comp.nus.edu.sg/~bleong/slides/icon-epichord-slides.pdf
     


EpiChord Lookup Algorithm
B. Leong et al. http://www.comp.nus.edu.sg/~bleong/slides/icon-epichord-slides.pdf
     EpiChord


Division of Address Space


                   ?
J. Xu et al., On the Fundamental Tradeoffs between Routing Table Size and Network Diameter in Peer-to-Peer Networks
    


                                                                                           Lookup

                         
                                                                                                                         
                                                                                (Dynamo?)


                                                EpiChord?
 
 
         ACID:
                           1.  SELECT …
                           2.  INSERT …
                           3.     :
          DB

 
         1                               ?
 
                      !
                 ?
S. Shinohara http://www.slideshare.net/shino/conflict-resolution-in-kai-presentation
       VectorClocks


 “happens-before” (->)




BASE                              VectorClocks
S. Shinohara http://www.slideshare.net/shino/conflict-resolution-in-kai-presentation
       VectorClocks


 “concurrent” (||)




BASE                              VectorClocks
T.Yamamuro
     


(postgresql’s) 2-phase commit
T.Yamamuro
     Sinfonia


2-phase commit’s optimization




 
                                      ?
T.Yamamuro
      Sinfonia


mini-transaction primitives
T.Yamamuro
     Sinfonia


Sinfonia’s 2-phase commit
                 =
T.Yamamuro
     Sinfonia


Sinfonia 2-phase commit 5
T.Yamamuro
     Sinfonia


Sinfonia 2-phase commit 5
T.Yamamuro
     Sinfonia


Sinfonia 2-phase commit 5
T.Yamamuro
              Sinfonia


 Evaluation: Scalability

                                    NFS,   




250                             
          2               100
VectorClocks




                Sinfonia
                        2-phase commit

                                              
        BASE
         ACID
 
 


            {apple, banana} + {orange}            Is apple a member?
          = {apple, banana, orange}
             {apple, banana, orange}
                             
                                
 
      
      
 
                        !
         ?                      Q.          ?
                                 A. BigTable
                                        Bloom
Bloom filter
 
               
       
      BF
                      m          
             0
 0
 0
 0
 0
 0
 0
 0
      ZF
                          m           
      hi
          i               0<i   k 
                                         [0,m-1]                  hi(x)
 
                                                        0
 1
 0
 0
 1
 0
 0
 0
         BF = ZF
 
         BF[ hi(x) ] = 1                                         hi(y)

                                                        0
 1
 0
 0
 1
 1
 0
 0

                           
                       Bloom filter m=8, k=2   x, y
Bloom filter
              membership query
         F = ZF
                                          hi(x)
   included
         F[ hi(x) ] = 1
         BF & F == F             0
 1
 0
 0
 1
 1
 0
 0


                                          hi(z)
   not included

                                  0
 1
 0
 0
 1
 1
 0
 0

                                                      false positive!
                                          hi(w)
 included

                                  0
 1
 0
 0
 1
 1
 0
 0
Bloom filter
 
         O k
                   n
      
Bloom filter
              OR AND
             m,            hi           

                                 0
 1
 0
 0
 1
 1
 0
 0



                                 0
 0
 0
 1
 1
 0
 0
 1


                                 0
 1
 0
 1
 1
 1
 0
 1
Bloom filter                              false positive
                                         p
                      1  kn    kn 
                 p = 1−  ≈ exp − 
                      m        m

                                 f   

€                             k
                 f = (1− p)



€
                                                        m = 256, n = 32
Bloom filter                            false positive
        f                     k                        
             f        k
                       m
              k = ln2 ⋅ 
                       n
             floor
                 k
                   
€

                              f
       
                               m
                  f ≈ 0.6185   n

                           k
Bloom filter
        n, f                             m   

                 m = −1.44n log 2 f
                          k           



€
Bloom filter
                                             b       

                  b = −1.44 log 2 f
                                      k           
                                     
                  b = −log 2 f                                  9.6       1%
€            1.44                                                    
                   


€                                                         9.6   

                      Bloom filter
                                         b
                                                                          1%
Bloom filter
                     k                                     p
                     1
                  p=                                 0
 1
 0
 0
 1
 1
 0
 1
                     2
                      k       
                            Bloom filter   

                                 [mitzenmacher02]
€
                     k
             0   1
          
S. Minato http://www-alg.ist.hokudai.ac.jp/~minato/alg2009-j.html
      ZDD
BDD (Binary Decision Diagram)


                          {abc, ab, ac, b, } 
           trie                  



 0 (false)
   1 (true)
S. Minato http://www-alg.ist.hokudai.ac.jp/~minato/alg2009-j.html
     ZDD


BDD
S. Minato http://www-alg.ist.hokudai.ac.jp/~minato/alg2009-j.html
     ZDD


BDD
S. Minato http://www-alg.ist.hokudai.ac.jp/~minato/alg2009-j.html
    ZDD
S. Minato http://www-alg.ist.hokudai.ac.jp/~minato/alg2009-j.html
    ZDD
S. Minato http://www-alg.ist.hokudai.ac.jp/~minato/alg2009-j.html
    ZDD
           BDD
ZDD: Zero-suppressed BDD
S. Minato http://www-alg.ist.hokudai.ac.jp/~minato/alg2009-j.html
     ZDD


ZDD
S. Minato http://www-alg.ist.hokudai.ac.jp/~minato/alg2009-j.html
     ZDD


ZDD
S. Minato http://www-alg.ist.hokudai.ac.jp/~minato/alg2009-j.html
     ZDD


ZDD
 
      


 
         EpiChord
              B. Leong et al., “EpiChord: Parallelizing the Chord lookup algorithm with reactive
               routing state management,” Comput. Commun., vol.29, no.9, pp.1243-1259, 2006.
 
         Sinfonia
              M.K. Aguilera et al., “Sinfonia: a new paradigm for building scalable distributed systems,”
               Proc. of SOSP’07, pp.159-174, 2007.
 
         ZDD
              S. Minato, “Zero-suppressed BDDs for set manipulation in combinatorial problems,”
               Proc. of DAC’93, pp. 272-277, 1993.

 

More Related Content

Recently uploaded

Crea il tuo assistente AI con lo Stregatto (open source python framework)
Crea il tuo assistente AI con lo Stregatto (open source python framework)Crea il tuo assistente AI con lo Stregatto (open source python framework)
Crea il tuo assistente AI con lo Stregatto (open source python framework)Commit University
 
Babel Compiler - Transforming JavaScript for All Browsers.pptx
Babel Compiler - Transforming JavaScript for All Browsers.pptxBabel Compiler - Transforming JavaScript for All Browsers.pptx
Babel Compiler - Transforming JavaScript for All Browsers.pptxYounusS2
 
Introduction to Quantum Computing
Introduction to Quantum ComputingIntroduction to Quantum Computing
Introduction to Quantum ComputingGDSC PJATK
 
UWB Technology for Enhanced Indoor and Outdoor Positioning in Physiological M...
UWB Technology for Enhanced Indoor and Outdoor Positioning in Physiological M...UWB Technology for Enhanced Indoor and Outdoor Positioning in Physiological M...
UWB Technology for Enhanced Indoor and Outdoor Positioning in Physiological M...UbiTrack UK
 
Empowering Africa's Next Generation: The AI Leadership Blueprint
Empowering Africa's Next Generation: The AI Leadership BlueprintEmpowering Africa's Next Generation: The AI Leadership Blueprint
Empowering Africa's Next Generation: The AI Leadership BlueprintMahmoud Rabie
 
Anypoint Code Builder , Google Pub sub connector and MuleSoft RPA
Anypoint Code Builder , Google Pub sub connector and MuleSoft RPAAnypoint Code Builder , Google Pub sub connector and MuleSoft RPA
Anypoint Code Builder , Google Pub sub connector and MuleSoft RPAshyamraj55
 
IESVE Software for Florida Code Compliance Using ASHRAE 90.1-2019
IESVE Software for Florida Code Compliance Using ASHRAE 90.1-2019IESVE Software for Florida Code Compliance Using ASHRAE 90.1-2019
IESVE Software for Florida Code Compliance Using ASHRAE 90.1-2019IES VE
 
RAG Patterns and Vector Search in Generative AI
RAG Patterns and Vector Search in Generative AIRAG Patterns and Vector Search in Generative AI
RAG Patterns and Vector Search in Generative AIUdaiappa Ramachandran
 
Artificial Intelligence & SEO Trends for 2024
Artificial Intelligence & SEO Trends for 2024Artificial Intelligence & SEO Trends for 2024
Artificial Intelligence & SEO Trends for 2024D Cloud Solutions
 
IaC & GitOps in a Nutshell - a FridayInANuthshell Episode.pdf
IaC & GitOps in a Nutshell - a FridayInANuthshell Episode.pdfIaC & GitOps in a Nutshell - a FridayInANuthshell Episode.pdf
IaC & GitOps in a Nutshell - a FridayInANuthshell Episode.pdfDaniel Santiago Silva Capera
 
Computer 10: Lesson 10 - Online Crimes and Hazards
Computer 10: Lesson 10 - Online Crimes and HazardsComputer 10: Lesson 10 - Online Crimes and Hazards
Computer 10: Lesson 10 - Online Crimes and HazardsSeth Reyes
 
Cloud Revolution: Exploring the New Wave of Serverless Spatial Data
Cloud Revolution: Exploring the New Wave of Serverless Spatial DataCloud Revolution: Exploring the New Wave of Serverless Spatial Data
Cloud Revolution: Exploring the New Wave of Serverless Spatial DataSafe Software
 
Machine Learning Model Validation (Aijun Zhang 2024).pdf
Machine Learning Model Validation (Aijun Zhang 2024).pdfMachine Learning Model Validation (Aijun Zhang 2024).pdf
Machine Learning Model Validation (Aijun Zhang 2024).pdfAijun Zhang
 
Comparing Sidecar-less Service Mesh from Cilium and Istio
Comparing Sidecar-less Service Mesh from Cilium and IstioComparing Sidecar-less Service Mesh from Cilium and Istio
Comparing Sidecar-less Service Mesh from Cilium and IstioChristian Posta
 
Introduction to Matsuo Laboratory (ENG).pptx
Introduction to Matsuo Laboratory (ENG).pptxIntroduction to Matsuo Laboratory (ENG).pptx
Introduction to Matsuo Laboratory (ENG).pptxMatsuo Lab
 
Designing A Time bound resource download URL
Designing A Time bound resource download URLDesigning A Time bound resource download URL
Designing A Time bound resource download URLRuncy Oommen
 
Cybersecurity Workshop #1.pptx
Cybersecurity Workshop #1.pptxCybersecurity Workshop #1.pptx
Cybersecurity Workshop #1.pptxGDSC PJATK
 
UiPath Platform: The Backend Engine Powering Your Automation - Session 1
UiPath Platform: The Backend Engine Powering Your Automation - Session 1UiPath Platform: The Backend Engine Powering Your Automation - Session 1
UiPath Platform: The Backend Engine Powering Your Automation - Session 1DianaGray10
 
Digital magic. A small project for controlling smart light bulbs.
Digital magic. A small project for controlling smart light bulbs.Digital magic. A small project for controlling smart light bulbs.
Digital magic. A small project for controlling smart light bulbs.francesco barbera
 
Videogame localization & technology_ how to enhance the power of translation.pdf
Videogame localization & technology_ how to enhance the power of translation.pdfVideogame localization & technology_ how to enhance the power of translation.pdf
Videogame localization & technology_ how to enhance the power of translation.pdfinfogdgmi
 

Recently uploaded (20)

Crea il tuo assistente AI con lo Stregatto (open source python framework)
Crea il tuo assistente AI con lo Stregatto (open source python framework)Crea il tuo assistente AI con lo Stregatto (open source python framework)
Crea il tuo assistente AI con lo Stregatto (open source python framework)
 
Babel Compiler - Transforming JavaScript for All Browsers.pptx
Babel Compiler - Transforming JavaScript for All Browsers.pptxBabel Compiler - Transforming JavaScript for All Browsers.pptx
Babel Compiler - Transforming JavaScript for All Browsers.pptx
 
Introduction to Quantum Computing
Introduction to Quantum ComputingIntroduction to Quantum Computing
Introduction to Quantum Computing
 
UWB Technology for Enhanced Indoor and Outdoor Positioning in Physiological M...
UWB Technology for Enhanced Indoor and Outdoor Positioning in Physiological M...UWB Technology for Enhanced Indoor and Outdoor Positioning in Physiological M...
UWB Technology for Enhanced Indoor and Outdoor Positioning in Physiological M...
 
Empowering Africa's Next Generation: The AI Leadership Blueprint
Empowering Africa's Next Generation: The AI Leadership BlueprintEmpowering Africa's Next Generation: The AI Leadership Blueprint
Empowering Africa's Next Generation: The AI Leadership Blueprint
 
Anypoint Code Builder , Google Pub sub connector and MuleSoft RPA
Anypoint Code Builder , Google Pub sub connector and MuleSoft RPAAnypoint Code Builder , Google Pub sub connector and MuleSoft RPA
Anypoint Code Builder , Google Pub sub connector and MuleSoft RPA
 
IESVE Software for Florida Code Compliance Using ASHRAE 90.1-2019
IESVE Software for Florida Code Compliance Using ASHRAE 90.1-2019IESVE Software for Florida Code Compliance Using ASHRAE 90.1-2019
IESVE Software for Florida Code Compliance Using ASHRAE 90.1-2019
 
RAG Patterns and Vector Search in Generative AI
RAG Patterns and Vector Search in Generative AIRAG Patterns and Vector Search in Generative AI
RAG Patterns and Vector Search in Generative AI
 
Artificial Intelligence & SEO Trends for 2024
Artificial Intelligence & SEO Trends for 2024Artificial Intelligence & SEO Trends for 2024
Artificial Intelligence & SEO Trends for 2024
 
IaC & GitOps in a Nutshell - a FridayInANuthshell Episode.pdf
IaC & GitOps in a Nutshell - a FridayInANuthshell Episode.pdfIaC & GitOps in a Nutshell - a FridayInANuthshell Episode.pdf
IaC & GitOps in a Nutshell - a FridayInANuthshell Episode.pdf
 
Computer 10: Lesson 10 - Online Crimes and Hazards
Computer 10: Lesson 10 - Online Crimes and HazardsComputer 10: Lesson 10 - Online Crimes and Hazards
Computer 10: Lesson 10 - Online Crimes and Hazards
 
Cloud Revolution: Exploring the New Wave of Serverless Spatial Data
Cloud Revolution: Exploring the New Wave of Serverless Spatial DataCloud Revolution: Exploring the New Wave of Serverless Spatial Data
Cloud Revolution: Exploring the New Wave of Serverless Spatial Data
 
Machine Learning Model Validation (Aijun Zhang 2024).pdf
Machine Learning Model Validation (Aijun Zhang 2024).pdfMachine Learning Model Validation (Aijun Zhang 2024).pdf
Machine Learning Model Validation (Aijun Zhang 2024).pdf
 
Comparing Sidecar-less Service Mesh from Cilium and Istio
Comparing Sidecar-less Service Mesh from Cilium and IstioComparing Sidecar-less Service Mesh from Cilium and Istio
Comparing Sidecar-less Service Mesh from Cilium and Istio
 
Introduction to Matsuo Laboratory (ENG).pptx
Introduction to Matsuo Laboratory (ENG).pptxIntroduction to Matsuo Laboratory (ENG).pptx
Introduction to Matsuo Laboratory (ENG).pptx
 
Designing A Time bound resource download URL
Designing A Time bound resource download URLDesigning A Time bound resource download URL
Designing A Time bound resource download URL
 
Cybersecurity Workshop #1.pptx
Cybersecurity Workshop #1.pptxCybersecurity Workshop #1.pptx
Cybersecurity Workshop #1.pptx
 
UiPath Platform: The Backend Engine Powering Your Automation - Session 1
UiPath Platform: The Backend Engine Powering Your Automation - Session 1UiPath Platform: The Backend Engine Powering Your Automation - Session 1
UiPath Platform: The Backend Engine Powering Your Automation - Session 1
 
Digital magic. A small project for controlling smart light bulbs.
Digital magic. A small project for controlling smart light bulbs.Digital magic. A small project for controlling smart light bulbs.
Digital magic. A small project for controlling smart light bulbs.
 
Videogame localization & technology_ how to enhance the power of translation.pdf
Videogame localization & technology_ how to enhance the power of translation.pdfVideogame localization & technology_ how to enhance the power of translation.pdf
Videogame localization & technology_ how to enhance the power of translation.pdf
 

分散ストレージに使えるかもしれないアルゴリズム