《系统软件与软件安全》课程教学课件（PPT讲稿，英文）Lecture-7-big-volume-data-accesses

Fast Accesses to Big Data in Memoryand Storage Systems

1 Fast Accesses to Big Data in Memory and Storage Systems

FastData Accesses in ln-Memory Key-Value Stores2

Fast Data Accesses in In-Memory Key-Value Stores 2

Informationprocessingwithouttables:KeyValueStoresAsimplebuteffectivemethodindataprocessingwhereadatarecord(or a value) is stored and retrieved with its associated keyvariabletypesandlengthsofrecord(value).simpleornoschemaeasysoftwaredevelopmentformanyapplicationsKey-valuestoreshavebeenwidelyused inproductionsystems:GooglefacebookTamazon风LEVELDBTDynamoDBRocksDBLinkedinMProjectVoldemortAdistributeddatabase.redisMEMCACHED

Information processing without tables: Key Value Stores ๏ A simple but effective method in data processing where a data record (or a value) is stored and retrieved with its associated key • variable types and lengths of record (value) • simple or no schema • easy software development for many applications ๏ Key-value stores have been widely used in production systems:

Simple andEasyInterfaces of Key-Value Stores: value = get (key)put (key,value)Variable-lengthkeys&values38John_ageIndexget(key)Client

Simple and Easy Interfaces of Key-Value Stores • value = get (key) • put (key, value) Index John_age 38 . Variable-length keys & values Client get (key)

Key-Value Store:A Data Model Supporting Scale-outCommandOperationGET(key)Read valueSET(key, value)WriteaKVitemDEL(key)DeleteaKVitemHash (Key)>ServerIDItishorizontallyscalableItcanbepotentiallyof(very)highperformance

Key-Value Store: A Data Model Supporting Scale-out Data Servers Command Operation GET(key) Read value SET(key, value) Write a KV item DEL(key) Delete a KV item ▪ It is horizontally scalable, ▪ It can be potentially of (very) high performance. Hash (Key) → Server ID

Workflowof an in-memory Key-Value StoreNetworkProcessingMemoryManagementIndexOperationsAccessValue

Workflow of an in-memory Key-Value Store Network Processing Memory Management Index Operations Access Value

Workflowofa Typical Key-Value StoreTcP/IPProcessingRequestParsingNetwork ProcessingSETGETDELETEExtractKeysExtractKeysExtractKey&ValueMemoryMemoryNotFullFullMemoryManagementEvictAllocateInsert intoSearchinDeletefromIndexOperationsIndexIndexIndexRead&SendValueAccessValue

Workflow of a Typical Key-Value Store DELETE SET GET Extract Keys TCP/IP Processing Request Parsing Extract Keys Extract Key&Value Network Processing Memory Full Memory Not Full Evict Allocate Memory Management Delete from Index Insert into Index Search in Index Index Operations Read & Send Value Access Value

Where does time go in KV-Store MICA [NSDI'14]Networkprocessing&MemoryManagement0.75IndexOperations0.50.2501)128BKey2)32BKey4) 8B Key3)16BKey1024BValue512BValue8BValue64BValueAccessValueFourDataSetsIndexoperation becomesoneofthemajorbottlenecks

Where does time go in KV-Store MICA [NSDI’14] 0 0.25 0.5 0.75 1 1) 128B Key 1024B Value 2) 32B Key 512B Value 3) 16B Key 64B Value 4) 8B Key 8B Value Execution Time Percentage Four Data Sets Index operation becomes one of the major bottlenecks 9 Network processing & Memory Management Index Operations Access Value

Data Workflow of Key-Value StoresQueryNetworkProcessing&MemoryManagementHashTableRandom80MemoryAccesses口IndexOperationAccessValue

Data Workflow of Key-Value Stores Query Network Processing & Memory Management Index Operation Access Value Random Memory Accesses Hash Table

Random MemoryAccesses ofIndexing areExpensiveSequentialmemoryaccessRandommemoryaccessasoe300240180120CPU:IntelXeonE5-2650v260Memory:1600MHzDDR3036812574910.11.1213141516Number ofMemoryAccesses

Random Memory Accesses of Indexing are Expensive 0 60 120 180 240 300 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Time (nanosecond) Number of Memory Accesses Sequential memory access Random memory access 2 7 3 16 CPU: Intel Xeon E5-2650v2 Memory: 1600 MHz DDR3