Storage Exchange: A Global Platform for Trading
`
`Distributed Storage Services
`
`by
`
`Martin Placek
`
`Submitted in total fulfilment of
`
`the requirements for the degree of
`
`Master of Engineering Science
`
`Department of Computer Science and Software Engineering
`
`The University of Melbourne
`
`Australia
`
`July, 2006
`
`CSCO-1033
`Page 1 of 185
`
`

`

`Page 2 of 185
`
`Page 2 of 185
`
`

`

`Storage Exchange: A Global Platform for Trading
`
`Distributed Storage Services
`
`Martin Placek
`
`Supervisor: Dr Rajkumar Buyya
`
`ABSTRACT
`
`The Storage Exchange is a new platform allowing storage to be treated as a
`
`tradeable resource. Organisations with varying storage requirements can use the
`
`Storage Exchange platform to trade and exchange storage services. Organisations
`
`have the ability to federate their storage, be-it dedicated or scavenged and advertise
`
`it to a global storage market.
`
`This thesis provides a detailed account of the Storage Exchange and presents
`
`three main contributions in the field of distributed storage and the process required
`
`to realise a global storage utility. The first is a taxonomy of distributed storage
`
`systems covering a wide array of topics from the past and present. The second
`
`contribution involves proposing and developing the Storage Exchange, a global
`
`trading platform for distributed storage services. The development of the Storage
`
`Exchange platform identifies challenges and the necessary work required to make
`
`the global trading and sharing of distributed storage services possible.
`
`The third and final contribution consists of proposing and evaluating Double
`
`Auction clearing algorithms which allow goods with indivisible demand constraints
`
`to be allocated in polynomial time. The process of optimally clearing goods of this
`
`nature in a Double Auction normally requires solving an NP-hard problem and is
`
`thus considered computationally intractable.
`
`Page 3 of 185
`
`

`

`Page 4 of 185
`
`Page 4 of 185
`
`

`

`This is to certify that
`
`(i) the thesis comprises only my original work,
`
`(ii) due acknowledgement has been made in the text to all other material used,
`
`(iii) the thesis is less than 30,000 words in length, exclusive of tables, maps,
`
`bibliographies, appendices and footnotes.
`
`Martin Placek
`
`July 2006
`
`Page 5 of 185
`
`

`

`Page 6 of 185
`
`Page 6 of 185
`
`

`

`ACKNOWLEDGMENTS
`
`The work described in this thesis was conducted with the assistance and support
`
`of many people to whom I would like to express my thanks. The most notable
`
`influence on my research activities has been my supervisor Dr Rajkumar Buyya. I’d
`
`also like to thank Professor Kotagiri Ramamohanarao and Dr Shanika Karunasekera
`
`who as committee members challenged the way I viewed my research, helping me to
`
`broaden my approach and adopt a different perspective when faced with problems
`
`which otherwise seemed insurmountable. I would like to thank Dr Charles Milligan
`
`and the Storage Technology Corporation (StorageTek) as early discussions with
`
`Charles provided the seed with which this research began. I would also like to thank
`
`Dr Jayant Kalagnanam (IBM T.J. Watson Research Center) for his time in answering
`
`my questions regarding his work on complexity analysis of double auctions.
`
`My family have always been a significant influence. Their understanding and
`
`encouragement provided me with the confidence to pursue postgraduate work above
`
`other considerations. Their position made me focus on giving my best efforts during
`
`this candidature.
`
`I would also like to collectively thank the members of the Department of
`
`Computer Science and Software Engineering. All the staff and students with whom
`
`I have had contact have always been very cordial and engaging. They helped to
`
`provide an environment where one is comfortable, care free and able to unobtrusively
`
`work towards an objective, all of this I have found invaluable.
`
`I’d like to especially thank Thomas Manoukian for taking the time out of his
`
`busy schedule to provide me with feedback in many aspects of my research. I’d also
`
`like to thank the many people at Ceroc and City Salsa dance studios, especially
`
`Stephanie, Jen, Damien, Amy, Nadia and Peter who have listened to all my tales
`
`of research adventures and provided me with much encouragement throughout my
`
`v
`
`Page 7 of 185
`
`

`

`research candidature. They have helped me to enjoy my time outside of research
`
`and allow me to come back with a fresh outlook on things. Last, but by no means
`
`the least, Dr Anthony Senyard, who started my interest in research during my time
`
`as an undergraduate student.
`
`This work was supported by an Australian Postgraduate Award (APA) and
`
`NICTA Victoria Laboratory whom I’d like to both thank whole-heartedly for making
`
`this experience possible.
`
`I’d also like to thank StorageTek for sponsoring the
`
`Grid computing Fellowship at the University of Melbourne, which was held by my
`
`supervisor from 2004-2005.
`
`Martin Placek
`
`Melbourne, Australia
`
`July 2006.
`
`Page 8 of 185
`
`

`

`CONTENTS
`
`1 Introduction
`1.1 Background Research . . . . . . . . . . . . . . . . . . . . . . . . . . .
`1.2 Autonomic Storage Management
`. . . . . . . . . . . . . . . . . . . .
`1.3 Significance and Motivation . . . . . . . . . . . . . . . . . . . . . . .
`1.4 Contribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`1.5 Thesis Organisation . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`
`1
`1
`2
`3
`4
`5
`
`7
`2 Distributed Storage Systems
`7
`. . . . . . . . . . . . . . .
`2.1 Taxonomy of Distributed Storage Systems
`9
`2.1.1
`System Function . . . . . . . . . . . . . . . . . . . . . . . . .
`2.1.2
`Storage Architecture . . . . . . . . . . . . . . . . . . . . . . . 11
`2.1.3 Operating Environment
`. . . . . . . . . . . . . . . . . . . . . 15
`2.1.4 Usage Patterns
`. . . . . . . . . . . . . . . . . . . . . . . . . . 17
`2.1.5 Consistency . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
`2.1.6
`Security . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
`2.1.7 Autonomic Management . . . . . . . . . . . . . . . . . . . . . 29
`2.1.8 Federation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
`2.1.9 Routing and Network Overlays
`. . . . . . . . . . . . . . . . . 33
`2.2 Survey of Distributed Storage Systems
`. . . . . . . . . . . . . . . . . 36
`2.2.1 OceanStore . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
`2.2.2 Free Haven . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
`2.2.3 Farsite . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
`2.2.4 Coda . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
`2.2.5
`Ivy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
`2.2.6 Frangipani . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
`2.2.7 GFS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
`2.2.8
`SRB . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
`2.2.9 Freeloader . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
`2.2.10 PVFS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
`2.3 Survey of markets in Distributed Storage Systems . . . . . . . . . . . 70
`2.3.1 Mungi
`. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
`2.3.2
`Stanford Archival Repository Project . . . . . . . . . . . . . . 72
`2.3.3 MojoNation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
`2.3.4 OceanStore . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
`2.4 Discussion and Summary . . . . . . . . . . . . . . . . . . . . . . . . . 76
`
`79
`3 Storage Exchange Platform
`3.1
`Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
`3.2 System Architecture
`. . . . . . . . . . . . . . . . . . . . . . . . . . . 81
`3.2.1
`Storage Provider
`. . . . . . . . . . . . . . . . . . . . . . . . . 82
`
`vii
`
`Page 9 of 185
`
`

`

`Storage Client . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
`3.2.2
`Storage Broker
`. . . . . . . . . . . . . . . . . . . . . . . . . . 83
`3.2.3
`Storage Marketplace . . . . . . . . . . . . . . . . . . . . . . . 84
`3.2.4
`3.2.5 Virtual Volume . . . . . . . . . . . . . . . . . . . . . . . . . . 84
`3.2.6 Mounting a Virtual Volume . . . . . . . . . . . . . . . . . . . 86
`3.2.7 Trading Virtual Volumes
`. . . . . . . . . . . . . . . . . . . . 88
`3.3 Storage Provider
`. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
`3.3.1 Architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
`3.3.2 Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
`3.4 Storage Client . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
`3.4.1 Architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
`3.4.2 Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
`3.5 Storage Broker
`. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
`3.5.1 Architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
`3.5.2 Object Oriented Design . . . . . . . . . . . . . . . . . . . . . 102
`3.5.3 Data Modelling . . . . . . . . . . . . . . . . . . . . . . . . . . 104
`3.6 Storage Marketplace
`. . . . . . . . . . . . . . . . . . . . . . . . . . . 105
`3.6.1 Architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
`3.6.2 Object Oriented Design . . . . . . . . . . . . . . . . . . . . . 107
`Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
`3.7
`3.8 Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
`3.8.1 Experiment Setup . . . . . . . . . . . . . . . . . . . . . . . . . 110
`3.8.2 Benchmark . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110
`3.9 Discussion and Summary . . . . . . . . . . . . . . . . . . . . . . . . . 111
`
`113
`4 Storage Exchange Clearing Algorithms
`4.1 Auctions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
`4.2 One Sided Auctions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114
`4.2.1 English Auction . . . . . . . . . . . . . . . . . . . . . . . . . . 115
`4.2.2 First Price Sealed Bid . . . . . . . . . . . . . . . . . . . . . . 117
`4.2.3 Vickrey . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118
`4.2.4 Dutch Auction . . . . . . . . . . . . . . . . . . . . . . . . . . 119
`4.2.5
`Summary: One Sided Auctions
`. . . . . . . . . . . . . . . . . 120
`4.3 Double Auction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
`4.4 Storage Exchange: A Market Perspective . . . . . . . . . . . . . . . . 124
`4.5 Clearing Algorithms
`. . . . . . . . . . . . . . . . . . . . . . . . . . . 127
`4.5.1 First Fit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127
`4.5.2 Maximise Surplus . . . . . . . . . . . . . . . . . . . . . . . . . 127
`4.5.3 Optimise Utilisation . . . . . . . . . . . . . . . . . . . . . . . 128
`4.5.4 Max-Surplus/Optimise Utilisation . . . . . . . . . . . . . . . . 128
`4.6 Performance and Evaluation . . . . . . . . . . . . . . . . . . . . . . . 129
`4.6.1 Experiment Setup . . . . . . . . . . . . . . . . . . . . . . . . . 131
`4.6.2 Performance Results
`. . . . . . . . . . . . . . . . . . . . . . . 133
`4.6.3 Market Results
`. . . . . . . . . . . . . . . . . . . . . . . . . . 133
`4.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140
`
`Page 10 of 185
`
`

`

`143
`5 Conclusion
`5.1 Lessons Learnt About Research . . . . . . . . . . . . . . . . . . . . . 145
`5.2 Future Directions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145
`
`A Storage Broker Data Dictionary
`
`163
`
`165
`B Storage Event Protocol
`B.1 Storage Event Message . . . . . . . . . . . . . . . . . . . . . . . . . . 165
`B.1.1 Header . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165
`B.1.2 Payload . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165
`B.2 Storage Event Types . . . . . . . . . . . . . . . . . . . . . . . . . . . 166
`B.2.1 Handshakes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166
`B.2.2 Trading Protocol
`. . . . . . . . . . . . . . . . . . . . . . . . . 168
`B.2.3 Storage Protocol
`. . . . . . . . . . . . . . . . . . . . . . . . . 168
`
`Page 11 of 185
`
`

`

`Page 12 of 185
`
`Page 12 of 185
`
`

`

`LIST OF FIGURES
`
`9
`system function taxonomy . . . . . . . . . . . . . . . . . . . . . . . .
`2.1
`architecture taxonomy . . . . . . . . . . . . . . . . . . . . . . . . . . 12
`2.2
`architecture evolution . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
`2.3
`operating environment and usage taxonomy . . . . . . . . . . . . . . 15
`2.4
`strong vs optimistic consistency . . . . . . . . . . . . . . . . . . . . . 24
`2.5
`security taxonomy . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
`2.6
`autonomic management taxonomy . . . . . . . . . . . . . . . . . . . . 30
`2.7
`2.8 OceanStore architecture
`. . . . . . . . . . . . . . . . . . . . . . . . . 38
`2.9 Free Haven architecture
`. . . . . . . . . . . . . . . . . . . . . . . . . 41
`2.10 Farsite architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
`2.11 Coda architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
`2.12 Coda implementation architecture . . . . . . . . . . . . . . . . . . . . 51
`2.13 Ivy architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
`2.14 Frangipani architecture . . . . . . . . . . . . . . . . . . . . . . . . . . 56
`2.15 GFS architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
`2.16 SRB architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
`2.17 Freeloader architecture . . . . . . . . . . . . . . . . . . . . . . . . . . 66
`2.18 PVFS architecture
`. . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
`
`3.1 Storage Exchange: platform overview . . . . . . . . . . . . . . . . . . 80
`3.2 Storage Exchange: architecture
`. . . . . . . . . . . . . . . . . . . . . 82
`3.3 System architecture: virtual volume . . . . . . . . . . . . . . . . . . . 86
`3.4 System architecture: mounting a virtual volume . . . . . . . . . . . . 87
`3.5 System architecture: trading virtual volumes . . . . . . . . . . . . . . 89
`3.6 Storage Provider: component diagram . . . . . . . . . . . . . . . . . 90
`3.7 Storage Provider: threading and message passing . . . . . . . . . . . 94
`3.8 Storage Client: component diagram . . . . . . . . . . . . . . . . . . . 94
`3.9 Storage Client: threading and message passing . . . . . . . . . . . . . 98
`3.10 Storage Broker: component diagram . . . . . . . . . . . . . . . . . . 100
`3.11 Storage Broker: UML class diagram . . . . . . . . . . . . . . . . . . . 102
`3.12 Storage Broker: entity relationship diagram . . . . . . . . . . . . . . 104
`3.13 Storage Marketplace: component diagram . . . . . . . . . . . . . . . 106
`3.14 Storage Marketplace: UML class diagram . . . . . . . . . . . . . . . . 107
`3.15 Storage Exchange: sequential read performance - varying block size . 111
`
`4.1 English Auction: messages relayed . . . . . . . . . . . . . . . . . . . . 117
`4.2 First Price Sealed Bid Auction: messages relayed . . . . . . . . . . . 118
`4.3 Dutch Auction: messages relayed . . . . . . . . . . . . . . . . . . . . 120
`4.4 Double Auction: messages relayed . . . . . . . . . . . . . . . . . . . . 124
`4.5 Optimise Utilisation Algorithm . . . . . . . . . . . . . . . . . . . . . 129
`4.6 Scenario A: auction surplus
`. . . . . . . . . . . . . . . . . . . . . . . 136
`
`xi
`
`Page 13 of 185
`
`

`

`4.7 Scenario A: percentage of ask budget met, unsold storage and
`unfeasible bids . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137
`4.8 Scenario B: auction surplus
`. . . . . . . . . . . . . . . . . . . . . . . 137
`4.9 Scenario B: percentage of ask budget met . . . . . . . . . . . . . . . . 138
`4.10 Scenario B: percentage of unsold storage . . . . . . . . . . . . . . . . 138
`4.11 Scenario B: percentage of unfeasible bids . . . . . . . . . . . . . . . . 139
`4.12 Scenario C: auction surplus and percentage of ask budget met
`. . . . 139
`4.13 Scenario C: percentage of unsold storage and percentage of unfeasible
`bids
`. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140
`
`Page 14 of 185
`
`

`

`LIST OF TABLES
`
`strong consistency - impact on architecture and environment . . . . . 25
`2.1
`autonomic computing and distributed storage . . . . . . . . . . . . . 32
`2.2
`comparison of routing mechanisms
`. . . . . . . . . . . . . . . . . . . 35
`2.3
`routing and architecture taxonomy . . . . . . . . . . . . . . . . . . . 36
`2.4
`2.5 distributed storage systems surveyed . . . . . . . . . . . . . . . . . . 37
`
`3.1 Storage Exchange: sequential read performance - varying block size . 111
`
`comparison of auction market models . . . . . . . . . . . . . . . . . . 126
`4.1
`experiment parameters . . . . . . . . . . . . . . . . . . . . . . . . . . 131
`4.2
`experiment scenarios . . . . . . . . . . . . . . . . . . . . . . . . . . . 133
`4.3
`clearing algorithm performance
`. . . . . . . . . . . . . . . . . . . . . 134
`4.4
`4.5 market allocation results . . . . . . . . . . . . . . . . . . . . . . . . . 135
`
`A.1 user table description . . . . . . . . . . . . . . . . . . . . . . . . . . . 163
`A.2 available storage table description . . . . . . . . . . . . . . . . . . . . 163
`A.3 contract table description . . . . . . . . . . . . . . . . . . . . . . . . 164
`A.4 virtual volume table description . . . . . . . . . . . . . . . . . . . . . 164
`A.5 segment table description . . . . . . . . . . . . . . . . . . . . . . . . . 164
`A.6 segment available store table description . . . . . . . . . . . . . . . . 164
`
`B.1 storage event message structure . . . . . . . . . . . . . . . . . . . . . 165
`B.2 storage client and storage broker handshake
`. . . . . . . . . . . . . . 166
`B.3 primary storage provider and secondary storage provider handshake . 167
`B.4 primary storage provider and storage client handshake
`. . . . . . . . 167
`B.5 storage provider and storage broker handshake . . . . . . . . . . . . . 167
`B.6 storage protocol operations . . . . . . . . . . . . . . . . . . . . . . . . 169
`
`xiii
`
`Page 15 of 185
`
`

`

`Page 16 of 185
`
`Page 16 of 185
`
`

`

`Chapter 1
`
`INTRODUCTION
`
`This chapter begins by introducing areas of research relevant to the work presented
`
`in this thesis. It discusses how aspects of distributed storage, grid computing and
`
`autonomic computing intersect and form the basis for the Storage Exchange, a
`
`globally distributed storage trading platform. This is followed by a discussion of
`
`the underlying motivating factors and primary contributions made. This chapter
`
`concludes with a discussion on the organisation of the remainder of the thesis.
`
`1.1 Background Research
`
`Storage plays a fundamental role in computing, a key element, ever present from
`
`registers and RAM to hard-drives and optical drives. Functionally, storage may
`
`service a range of requirements, from caching (expensive, volatile and fast) to archival
`
`(inexpensive, persistent and slow). Combining storage with networking has created
`
`a platform with endless possibilities allowing Distributed Storage Systems (DSSs)
`
`to adopt vast and varied roles, well beyond data storage.
`
`Networking infrastructure and distributed storage systems share a close rela-
`
`tionship. Advances in networking are typically followed by new distributed storage
`
`systems, which better utilise the network’s capability. To illustrate, when networks
`
`evolved from primarily being private Local Area Networks (LANs) to public global
`
`Wide Area Networks (WANs) such as the Internet, a whole new generation of DSSs
`
`emerged, capable of servicing a global audience. The Internet has proven to be a
`
`source of many exciting and innovative applications and has enabled users to share
`
`and exchange resources across geographic boundaries. Terms such as pervasive,
`
`ubiquitous and federate were coined and heralded the rise of Grid Computing [108],
`
`which focuses on addressing the challenges associated with coordinating and sharing
`
`1
`
`Page 17 of 185
`
`

`

`2
`
`Chapter 1.
`
`INTRODUCTION
`
`heterogeneous resources across multiple geographic and administrative domains [53].
`
`One of these challenges is data management, whose requirements led to the Data
`
`Grid [22]. Other issues concerning managing globally distributed data include
`
`providing a standard uniform interface across a heterogeneous set of systems [106],
`
`coordinating and processing of data [144] and managing necessary meta-data [73].
`
`Distributed systems designed to successfully operate on the Internet are faced
`
`with many obstacles such as longer delays, unreliability, unpredictable and poten-
`
`tially malicious behaviour, associated with operating in a public shared environment.
`
`To cope with this, innovative architectures and algorithms have been proposed and
`
`developed, providing a stream of improvements to security, consistency and routing.
`
`As systems continue to advance, they increase in complexity and the expertise
`
`required to operate them [72]. Unfortunately, the continuing increase in complexity
`
`is unsustainable and ultimately limited by human cognitive capacity [134]. To
`
`address this problem, the Autonomic Computing [80] initiative has emerged aiming
`
`to simplify and automate the management of large scale complex systems.
`
`1.2 Autonomic Storage Management
`
`Distributed Storage Systems are rapidly evolving into complex systems, requiring
`
`increasingly more resources to be spent on maintenance and administration. The
`
`problem has been recognised by industry, where as much as 90% spent of the
`
`storage budget is allocated to its management [136]. This makes distributed storage
`
`systems a primary candidate for Autonomic Computing, which can be used to
`
`simplify and reduce the effort spent on maintenance and administration. One way
`
`to autonomically manage resource allocation in computer systems is through the use
`
`of economic principles [15]. Based on these principles we propose a platform capable
`
`of trading and automatically allocating distributed storage services.
`
`Let us imagine a global storage marketplace, allowing storage to be traded much
`
`like any other service. Consumers are able to purchase storage services without being
`
`concerned about the underlying complexities. From the consumer’s perspective
`
`this greatly simplifies the process of acquiring storage services. A process that
`
`Page 18 of 185
`
`

`

`1.3. SIGNIFICANCE AND MOTIVATION
`
`3
`
`involves selecting hardware, configuration and continuous maintenance is simplified
`
`to recognising a need for storage and setting a budget. The problem of finding a
`
`suitable storage service and maintenance becomes the platform’s responsibility. The
`
`work presented in this thesis provides an important step towards realising this ideal
`
`and proposes the Storage Exchange platform.
`
`The Storage Exchange allows distributed storage to be treated as a tradeable
`
`resource. Organisations with varying storage requirements can use the Storage
`
`Exchange platform to trade and exchange storage services. Organisations have the
`
`ability to federate their storage, be-it dedicated or scavenged and advertise it to a
`
`global storage market. The centre piece of the Storage Exchange is its market model,
`
`which is responsible for automatically allocating trades based upon consumer and
`
`provider requirements. We envisage the Storage Exchange platform could be further
`
`automated by extending brokers to apply multi-agent [122] principles to purchase or
`
`lease storage in an autonomic manner. The ultimate goal being a platform capable
`
`of autonomic management of distributed storage services.
`
`1.3 Significance and Motivation
`
`In this section we discuss the factors motivating our research and the significant
`
`possibilities which arise from realising the Storage Exchange. The Storage Exchange
`
`platform can be used in a collaborative manner, where participants exchange services
`
`for credits, or alternatively in an open marketplace where enterprises trade storage
`
`services. Whether in a collaborative or enterprise environment, the incentives for an
`
`organisation to use our Storage Exchange platform include:
`
`1. Monetary Gain: Organisations providing storage services (Providers) are able
`
`to better utilise existing storage infrastructure in exchange for monetary gain.
`
`Organisations consuming these storage services (Consumers) have the ability
`
`to negotiate for storage services as they require them, without needing to incur
`
`the costs associated with purchasing and maintaining storage hardware.
`
`2. Common Objectives: There may be organisations who may wish to exchange
`
`Page 19 of 185
`
`

`

`4
`
`Chapter 1.
`
`INTRODUCTION
`
`storage services as they may have a mutual goal such as preservation of
`
`information [26].
`
`3. Spikes in Storage Requirements: Research organisations may require tempo-
`
`rary access to mass storage [143] (e.g. temporarily store data generated from
`
`scientific experiments) and in exchange may provide access to their storage
`
`services.
`
`4. Economies of Scale: Consumers are able to acquire cheaper distributed storage
`
`services from providers dedicated to selling large quantities of storage, rather
`
`than building in-house storage solutions.
`
`5. Donate: Organisations may wish to donate storage services, particularly if
`
`these services will assist a noble cause.
`
`6. Autonomic Storage Management: Future brokers will trade based upon an
`
`organisation’s storage requirements and budget, simplifying storage manage-
`
`ment.
`
`The Storage Exchange is a dynamic platform which can be applied in many
`
`different ways whilst providing organisations with incentives to participate. This
`
`thesis discusses the design of the Storage Exchange, including an investigation of the
`
`Double Auction market model and a computationally practical clearing algorithm.
`
`1.4 Contribution
`
`This thesis makes three key contributions towards the understanding of distributed
`
`storage systems and by applying market principles, moves closer towards a storage
`
`utility. These include:
`
`1. A taxonomy of distributed storage systems, discussing key topics affecting
`
`the design and development of distributed storage systems. Topics covered
`
`by the taxonomy include functionality, architecture, operating environment,
`
`usage patterns, autonomic management, federation, consistency and routing.
`
`Page 20 of 185
`
`

`

`1.5. THESIS ORGANISATION
`
`5
`
`The taxonomy is followed by a survey of distributed storage systems serving to
`
`exemplify classifications made in our taxonomy. The taxonomy also identifies
`
`challenges facing distributed storage systems and relevant research.
`
`2. The design and development of the Storage Exchange, an innovative platform
`
`allowing storage services to be traded across a global environment. Organ-
`
`isations with varying storage requirements can use the Storage Exchange
`
`platform to trade and exchange services. As a provider, an organisation has
`
`the ability to harness unused storage on their workstations and advertise it to
`
`a global market, better utilising their existing storage infrastructure. From
`
`a consumer’s perspective, organisations seeking storage services can do so
`
`without incurring the initial expense and labour associated with maintaining
`
`their own storage infrastructure.
`
`3. A set of unique clearing algorithms enabling goods with multiple attributes
`
`and divisible constraints to be cleared in polynomial time under a sealed
`
`Double Auction market model. The process of optimally clearing goods of this
`
`nature in a Double Auction model is computationally intractable, requiring
`
`solving an NP-hard optimisation problem [79]. Clearing algorithms proposed
`
`include Maximise Surplus, Optimise Utilisation and a hybrid scheme. These
`
`are incorporated into the Storage Exchange and evaluated through the use of
`
`simulations.
`
`1.5 Thesis Organisation
`
`The remainder of this thesis is organised as follows: Chapter 2 presents a taxonomy
`
`of distributed storage systems, including a survey of distributed storage systems
`
`which apply market principles to manage various facets of their operation. Chapter
`
`3 is dedicated to the Storage Exchange, providing a system overview and details
`
`of the architecture and design. Chapter 4 introduces and compares various auction
`
`market models before presenting and evaluating Double Auction clearing algorithms,
`
`allowing goods with multiple attributes and divisible constraints to be cleared in
`
`Page 21 of 185
`
`

`

`6
`
`Chapter 1.
`
`INTRODUCTION
`
`polynomial time. We conclude and present ideas for future work in Chapter 5.
`
`Core chapters of this thesis are based upon a technical report and a conference
`
`paper, detailed below:
`
`Chapter 2 is mostly derived from:
`
`• Martin Placek and Rajkumar Buyya.
`A Taxonomy of Distributed Storage Systems, Technical Report, GRIDS-TR-
`2006-11, Grid Computing and Distributed Systems Laboratory, The University
`of Melbourne, Australia, July 3, 2006.
`
`Chapters 3 and 4 are partially derived from:
`
`• Martin Placek and Rajkumar Buyya.
`In
`Storage Exchange: A Global Trading Platform for Storage Services.
`Proceedings of the Twelfth European Conference on Parallel Computing, Euro-
`Par 2006, Dresden, Germany, 29 August - 1st September.
`
`Page 22 of 185
`
`

`

`Chapter 2
`
`DISTRIBUTED STORAGE SYSTEMS
`
`This chapter presents a taxonomy of key topics affecting research and development
`
`of distributed storage systems. The taxonomy shows distributed storage systems
`
`to offer a wide array of functionality, employ architectures with varying degrees of
`
`centralisation and operate across environments with varying trust and scalability.
`
`Furthermore, taxonomies on autonomic management, federation, consistency and
`
`routing provide an insight into the challenges faced by distributed storage systems
`
`and the research carried out to overcome them. The chapter continues by providing
`
`a survey of distributed storage systems which exemplify topics covered in the
`
`taxonomy. Our focus then shifts to surveying distributed storage systems which
`
`employ market models to manage various aspects of their operation. This chapter
`
`concludes by summarising our discussion of distributed storage systems, which leads
`
`to the proposal of the Storage Exchange, detailed in the next chapter.
`
`2.1 Taxonomy of Distributed Storage Systems
`
`We introduce each of the topics covered in our taxonomy and provide a brief insight
`
`into the relevant research findings:
`
`1. System Function (Section 2.1.1): A classification of DSS functionality uncovers
`
`a wide array of behaviour, well beyond typical store and retrieve.
`
`2. Storage Architecture (Section 2.1.2): We discuss various architectures em-
`
`ployed by DSSs. Our investigation shows an evolution from centralised to the
`
`more recently favoured decentralised approach.
`
`3. Operating Environment (Section 2.1.3): We identify various categories of op-
`
`erating environments and discuss how each influence design and architecture.
`
`7
`
`Page 23 of 185
`
`

`

`8
`
`Chapter 2. DISTRIBUTED STORAGE SYSTEMS
`
`4. Usage Patterns (Section 2.1.4): A discussion and classification of various
`
`workloads experienced by DSSs. We observe that the operating environment
`
`has a major influence on usage patterns.
`
`5. Consistency (Section 2.1.5): Distributing, replicating and supporting con-
`
`current access are factors which challenge consistency. We discuss various
`
`approaches used to enforce consistency and the respective trade offs in
`
`performance, availability and choice of architecture.
`
`6. Security (Section 2.1.6): With attention turning towards applications operat-
`
`ing on the Internet, establishing a secure system is a challenging task which is
`
`made increasingly more difficult as DSSs adopt decentralised architectures.
`
`Our investigation covers traditional mechanisms as well as more recent
`
`approaches that have been developed for enforcing security in decentralised
`
`architectures.
`
`7. Autonomic Management (Section 2.1.7): Systems are increasing in complexity
`
`at an unsustainable rate. Research into autonomic computing [80] aims
`
`to overcome this dilemma by automating and abstracting away system
`
`complexity, simplifying maintenance and administration.
`
`8. Federation (Section 2.1.8): Many different formats and protocols are employed
`
`to store and access data, creating a difficult environment in which to share
`
`data and resources. Federation middleware aims to provide a single uniform
`
`homogeneous interface to what would otherwise be a heterogeneous cocktail of
`
`interfaces and protocols. Federation enables multiple institutions to share
`
`services,
`
`fostering collaboration whilst helping to reduce effort otherwise
`
`wasted on duplication.
`
`9. Routing and Network Overlays (Section 2.1.9): This section discusses the
`
`various routing methods employed by distributed storage systems.
`
`In our
`
`investigation we find that the development of routing shares a close knit
`
`relationship with the architecture; from a static approach as employed by
`
`Page 24 of 185
`
`

`

`2.1. TAXONOMY OF DISTRIBUTED STORAGE SYSTEMS
`
`9
`
`Archival
`
`General purpose Filesystem
`
`Functi