CS 190 Lecture Notes: Understanding Index Lookups
Dive into the CS 190 Lecture Notes which cover topics such as useless comments, missing information, an index lookup example, class documentation, and documenting APIs. Explore the implementation of client-side frameworks for index range lookups, managing LookupIndexKeys RPCs, and more. Understand the significance of isReady() function for making progress in indexed reads and handling rule-based approaches for checking object availability.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Useless Comments // Increment i i += 1; // Restart timer this->start(Cycles::rdtsc() + clock->updateIntervalCycles); updater->start(0); // Start immediately. CS 190 Lecture Notes: Comments Slide 1
Missing Information // Value of counter when a particular event occurred. uint64_t count; CS 190 Lecture Notes: Comments Slide 2
Index Lookup Example query = new IndexLookup(index, key1, key2); while (true) { object = query.getNext(); if (object == null) { break; } ... } CS 190 Lecture Notes: Comments Slide 3
Class Documentation /* * This class implements the client side framework for index range * lookups. It manages a single LookupIndexKeys RPC and multiple * IndexedRead RPCs. Client side just includes "IndexLookup.h" in * its header to use IndexLookup class. * Several parameters can be set in the config below: * - The number of concurrent indexedRead RPCs * - The max number of PKHashes a indexedRead RPC can hold at a time * - The size of the active PKHashes * * To use IndexLookup, the client creates an object of this class * by providing all necessary information. After construction of * IndexLookup, client can call getNext() function to move to next * available object. If getNext() returns false, it means we reached the * last object. Client can use getKey/getKeyLength/getValue/getValueLength * to get object data of current object. */ class IndexLookup { ... private: /// Max number of concurrent indexedRead RPCs static const uint8_t NUM_READ_RPC = 10; /// Max number of PKHashes that can be sent in one indexedRead RPC static const uint32_t MAX_PKHASHES_PERRPC = 256; /// Max number of PKHashes that activeHashes can hold at once. static const size_t MAX_NUM_PK = (1 << LG_BUFFER_SIZE); } CS 190 Lecture Notes: Comments Slide 4
Documenting APIs /** * Check if the next object is RESULT_READY. This function is implemented * in a DCFT module, each execution of isReady() tries to make small * progress, and getNext() invokes isReady() in a while loop, until * isReady() returns true. * * isReady() is implemented in a rule-based approach. We check different * rules by following a particular order, and perform certain actions if * some rule is satisfied * * \return * True means the next Object is available. Otherwise, return false. */ bool IndexLookup::isReady() { ... } * This method returns an indication of whether the indexed read * has made enough progress that getNext can return immediately * without blocking. In addition, this method does most of the * real work for indexed reads, so it must be invoked (either * directly, or indirectly by calling getNext) in order for the * indexed read to make progress. * * \return * True means at least one object is available, so getNext will * not block if it is invoked; false means getNext may block. CS 190 Lecture Notes: Comments Slide 5
Missing Information // Value of counter when a particular event occurred. uint64_t count; // Cumulative count of last-level cache misses when // this event was recorded. uint64_t missCount; CS 190 Lecture Notes: Comments Slide 6
Comment Not Specific Enough /// Current offset in resp Buffer uint32_t offset; /// Offset in this buffer of the first object that hasn t /// been returned to the client. uint32_t offset; CS 190 Lecture Notes: Comments Slide 7
Good Loop Comment // Each iteration extracts one request from request rpc, increments the // corresponding object, and appends the response to the response rpc. for (uint32_t i = 0; ; i++) { const WireFormat::MultiOp::Request::IncrementPart *currentReq = rpc->requestPayload->getOffset< WireFormat::MultiOp::Request::IncrementPart>(reqOffset); if (currentReq == NULL) { respHdr->common.status = STATUS_REQUEST_FORMAT_ERROR; break; } reqOffset += sizeof32(WireFormat::MultiOp::Request::IncrementPart); const void* stringKey = rpc->requestPayload->getRange( reqOffset, currentReq->keyLength); reqOffset += currentReq->keyLength; ... } CS 190 Lecture Notes: Comments Slide 8
Comments at Wrong Level // If there is a LOADING readRpc using the same session as PKHash // pointed by assignPos, and the last PKHash in that readRPC is // smaller than current assigning PKHash, then we put assigning // PKHash into that readRPC. uint8_t readActiveRpcId = RPC_ID_NOT_ASSIGNED; for (uint8_t i = 0; i < NUM_READ_RPC; i++) { if (session == readRpc[i].session && readRpc[i].status == LOADING && readRpc[i].maxPos < assignPos && readRpc[i].numHashes < MAX_PKHASHES_PERRPC) { readActiveRpcId = i; break; } } // Try to piggyback the current key hash onto an existing // RPC to the desired server. CS 190 Lecture Notes: Comments Slide 9
Higher Level Documentation if (numProcessedPKHashes < readRpc[i].numHashes) { // Some of the key hashes couldn't be looked up in this // request (either because they aren't stored by the // server, because the server crashed, or because there // wasn't enough space in the response message). Mark // the unprocessed hashes so they will get reassigned to // new RPCs. for (size_t p = removePos; p < insertPos; p ++) { if (activeRpcId[p] == i) { if (numProcessedPKHashes > 0) { numProcessedPKHashes--; } else { if (p < assignPos) assignPos = p; activeRpcId[p] = RPC_ID_NOT_ASSIGNED; } } } } CS 190 Lecture Notes: Comments Slide 10
Design Notes File ... Zombies ------- A zombie is a server that is considered dead by the rest of the cluster; any data stored on the server has been recovered and will be managed by other servers. However, if a zombie is not actually dead (e.g. it was just disconnected from the other servers for a while) two forms of inconsistency can arise: * A zombie server must not serve read requests once replacement servers have taken over; otherwise it may return stale data that does not reflect writes accepted by the replacement servers. * The zombie server must not accept write request once replacement servers have begun replaying its log during recovery; if it does, these writes may be lost (the new values may not be stored on the replacement servers and thus will not be returned by reads). RAMCloud uses two techniques to neutralize zombies. First, ... ... Timing-Dependent Tests ---------------------- Several unit tests have timing dependencies. For example, ... CS 190 Lecture Notes: Comments Slide 11
Design Notes File, contd if (probesWithoutResponse >= MAX_FAILED_PROBES) { // See "Zombies" in designNotes. MasterService::Disabler disabler(context->masterService); CoordinatorClient::verifyMembership(context, ourServerId); probesWithoutResponse = 0; } CS 190 Lecture Notes: Comments Slide 12
Cross-Module Checklist typedef enum Status { STATUS_OK = 0, STATUS_UNKNOWN_TABLET = 1, STATUS_TABLE_DOESNT_EXIST = 2, ... STATUS_INVALID_PARAMETER = 30, STATUS_MAX_VALUE = 30, // Note: if you add a new status value you must make the following // additional updates: // * Modify STATUS_MAX_VALUE to have a value equal to the largest // defined status value, and make sure its definition is the last one // in the list. STATUS_MAX_VALUE is used primarily for testing. // * Add new entries in the tables "messages" and "symbols" in Status.cc. // * Add a new exception class to ClientException.h // * Add a new "case" to ClientException::throwException to map from // the status value to a status-specific ClientException subclass. // * In the Java bindings, add a static class for the exception to // ClientException.java // * Add a case for the status of the exception to throw the exception in // ClientException.java // * Add the exception to the Status enum in Status.java, making // sure the status is in the correct position corresponding to its // status code. } CS 190 Lecture Notes: Comments Slide 13
Name Not Precise Enough /** * Obtain the total number of indexlets this object is managing. * * \return * Total number of indexlets this object is managing. */ size_t IndexletManager::getCount() CS 190 Lecture Notes: Comments Slide 14
