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