<commit_before>/* Copyright (c) 2009-2010 Stanford University
 *
 * Permission to use, copy, modify, and distribute this software for any
 * purpose with or without fee is hereby granted, provided that the above
 * copyright notice and this permission notice appear in all copies.
 *
 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR(S) DISCLAIM ALL WARRANTIES
 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL AUTHORS BE LIABLE FOR
 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
 */

#include <boost/scoped_ptr.hpp>

#include "BackupClient.h"
#include "BackupManager.h"
#include "Buffer.h"
#include "MasterServer.h"

namespace RAMCloud {

// --- SegmentLocatorChooser ---

/**
 * \param list
 *      A list of servers along with the segment id they have backed up.
 *      See Recovery for details on this format.
 */
SegmentLocatorChooser::SegmentLocatorChooser(const ProtoBuf::ServerList& list)
    : map()
    , ids()
{
    foreach (const ProtoBuf::ServerList::Entry& server, list.server()) {
        if (!server.has_segment_id()) {
            LOG(WARNING,
                "List of backups for recovery must contain segmentIds");
            continue;
        }
        if (server.server_type() != ProtoBuf::BACKUP) {
            LOG(WARNING,
                "List of backups for recovery shouldn't contain MASTERs");
            continue;
        }
        map.insert(make_pair(server.segment_id(), server.service_locator()));
    }
    std::transform(map.begin(), map.end(), back_inserter(ids),
                   &first<uint64_t, string>);
    // not the most efficient approach in the world...
    SegmentIdList::iterator newEnd = std::unique(ids.begin(), ids.end());
    ids.erase(newEnd, ids.end());
    std::random_shuffle(ids.begin(), ids.end());
}

/**
 * Provide locators for potential backup server to contact to find
 * segment data during recovery.
 *
 * \param segmentId
 *      A segment id for a segment that needs to be recovered.
 * \return
 *      A service locator string indicating a location where this segment
 *      can be recovered from.
 * \throw SegmentRecoveryFailedException
 *      If the requested segment id has no remaining potential backup
 *      locations.
 */
const string&
SegmentLocatorChooser::get(uint64_t segmentId)
{
    LocatorMap::size_type count = map.count(segmentId);

    ConstLocatorRange range = map.equal_range(segmentId);
    if (range.first == range.second)
        throw SegmentRecoveryFailedException(HERE);

    LocatorMap::size_type random = generateRandom() % count;
    LocatorMap::const_iterator it = range.first;
    for (LocatorMap::size_type i = 0; i < random; ++i)
        ++it;
    return it->second;
}

/**
 * Returns a randomly ordered list of segment ids which acts as a
 * schedule for recovery.
 */
const SegmentLocatorChooser::SegmentIdList&
SegmentLocatorChooser::getSegmentIdList()
{
    return ids;
}

/**
 * Remove the locator as a potential backup location for a particular
 * segment.
 *
 * \param segmentId
 *      The id of a segment which could not be located at the specified
 *      backup locator.
 * \param locator
 *      The locator string that should not be returned from future calls
 *      to get for this particular #segmentId.
 */
void
SegmentLocatorChooser::markAsDown(uint64_t segmentId, const string& locator)
{
    LocatorRange range = map.equal_range(segmentId);
    if (range.first == map.end())
        return;

    for (LocatorMap::iterator it = range.first;
         it != range.second; ++it)
    {
        if (it->second == locator) {
            map.erase(it);
            return;
        }
    }
}

// --- BackupManager ---

/**
 * Create a BackupManager, initially with no backup hosts to communicate
 * with.  See addHost() to add remote backups.
 */
BackupManager::BackupManager(CoordinatorClient* coordinator, uint32_t replicas)
    : coordinator(coordinator)
    , hosts()
    , openHosts()
    , replicas(replicas)
    , segments()
{
}

/// Free up all BackupClients.
BackupManager::~BackupManager()
{
    foreach (BackupClient* host, openHosts)
        delete host;
}

// See BackupClient::closeSegment.
void
BackupManager::closeSegment(uint64_t masterId,
                            uint64_t segmentId)
{
    TEST_LOG("%lu, %lu", masterId, segmentId);
    foreach (BackupClient* host, openHosts) {
        // TODO(stutsman) Exception during one of the closes?
        host->closeSegment(masterId, segmentId);
        delete host;
    }
    openHosts.clear();
}

// See BackupClient::freeSegment.
void
BackupManager::freeSegment(uint64_t masterId,
                           uint64_t segmentId)
{
    TEST_LOG("%lu, %lu", masterId, segmentId);
    uint32_t count = 0;
    pair<SegmentMap::iterator, SegmentMap::iterator> iters(
        segments.equal_range(segmentId));
    SegmentMap::iterator& it = iters.first;
    while (it != iters.second) {
        BackupClient host(it->second);
        host.freeSegment(masterId, segmentId);
        SegmentMap::iterator current = it;
        it++;
        segments.erase(current);
        count++;
    }
    if (count != replicas)
        LOG(WARNING, "Freed %u segments rather than %u", count, replicas);
}

// See BackupClient::openSegment.
void
BackupManager::openSegment(uint64_t masterId,
                           uint64_t segmentId)
{
    LOG(DEBUG, "openSegment %lu, %lu", masterId, segmentId);
    selectOpenHosts();
    foreach (BackupClient* host, openHosts) {
        LOG(DEBUG, "Opening %lu, %lu on an open backup", masterId, segmentId);
        host->openSegment(masterId, segmentId);
        segments.insert(SegmentMap::value_type(segmentId, host->getSession()));
    }
}

/**
 * Collect all the filtered log segments from backups for a set of tablets
 * formerly belonging to a crashed master which is being recovered and pass
 * them to the recovery master to have them replayed.
 *
 * \param recoveryMaster
 *      A reference to the Master which owns this BackupManager and which will
 *      be responsible for the tablets.  This is used to provide a callback
 *      for the Master to replay individual segments.
 * \param masterId
 *      The id of the crashed master for which recoveryMaster will be taking
 *      over ownership of tablets.
 * \param tablets
 *      A set of tables with key ranges describing which poritions of which
 *      tables recoveryMaster should have replayed to it.
 * \param backups
 *      A list of backup locators along with a segmentId specifying for each
 *      segmentId a backup who can provide a filtered recovery data segment.
 *      A particular segment may be listed more than once if it has multiple
 *      viable backups, hence a particular backup locator can also be listed
 *      many times.
 */
void
BackupManager::recover(MasterServer& recoveryMaster,
                       uint64_t masterId,
                       const ProtoBuf::Tablets& tablets,
                       const ProtoBuf::ServerList& backups)
{
    LOG(NOTICE, "Recovering master %lu, %u tablets, %u hosts",
        masterId, tablets.tablet_size(), backups.server_size());

    if (!mockRandomValue)
        srand(rdtsc());
    else
        srand(0);
#ifdef PERF_DEBUG_RECOVERY_SERIAL<commit_msg>Fix for random seeding on non-testing compiles.<commit_after>/* Copyright (c) 2009-2010 Stanford University
 *
 * Permission to use, copy, modify, and distribute this software for any
 * purpose with or without fee is hereby granted, provided that the above
 * copyright notice and this permission notice appear in all copies.
 *
 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR(S) DISCLAIM ALL WARRANTIES
 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL AUTHORS BE LIABLE FOR
 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
 */

#include <boost/scoped_ptr.hpp>

#include "BackupClient.h"
#include "BackupManager.h"
#include "Buffer.h"
#include "MasterServer.h"

namespace RAMCloud {

// --- SegmentLocatorChooser ---

/**
 * \param list
 *      A list of servers along with the segment id they have backed up.
 *      See Recovery for details on this format.
 */
SegmentLocatorChooser::SegmentLocatorChooser(const ProtoBuf::ServerList& list)
    : map()
    , ids()
{
    foreach (const ProtoBuf::ServerList::Entry& server, list.server()) {
        if (!server.has_segment_id()) {
            LOG(WARNING,
                "List of backups for recovery must contain segmentIds");
            continue;
        }
        if (server.server_type() != ProtoBuf::BACKUP) {
            LOG(WARNING,
                "List of backups for recovery shouldn't contain MASTERs");
            continue;
        }
        map.insert(make_pair(server.segment_id(), server.service_locator()));
    }
    std::transform(map.begin(), map.end(), back_inserter(ids),
                   &first<uint64_t, string>);
    // not the most efficient approach in the world...
    SegmentIdList::iterator newEnd = std::unique(ids.begin(), ids.end());
    ids.erase(newEnd, ids.end());
    std::random_shuffle(ids.begin(), ids.end());
}

/**
 * Provide locators for potential backup server to contact to find
 * segment data during recovery.
 *
 * \param segmentId
 *      A segment id for a segment that needs to be recovered.
 * \return
 *      A service locator string indicating a location where this segment
 *      can be recovered from.
 * \throw SegmentRecoveryFailedException
 *      If the requested segment id has no remaining potential backup
 *      locations.
 */
const string&
SegmentLocatorChooser::get(uint64_t segmentId)
{
    LocatorMap::size_type count = map.count(segmentId);

    ConstLocatorRange range = map.equal_range(segmentId);
    if (range.first == range.second)
        throw SegmentRecoveryFailedException(HERE);

    LocatorMap::size_type random = generateRandom() % count;
    LocatorMap::const_iterator it = range.first;
    for (LocatorMap::size_type i = 0; i < random; ++i)
        ++it;
    return it->second;
}

/**
 * Returns a randomly ordered list of segment ids which acts as a
 * schedule for recovery.
 */
const SegmentLocatorChooser::SegmentIdList&
SegmentLocatorChooser::getSegmentIdList()
{
    return ids;
}

/**
 * Remove the locator as a potential backup location for a particular
 * segment.
 *
 * \param segmentId
 *      The id of a segment which could not be located at the specified
 *      backup locator.
 * \param locator
 *      The locator string that should not be returned from future calls
 *      to get for this particular #segmentId.
 */
void
SegmentLocatorChooser::markAsDown(uint64_t segmentId, const string& locator)
{
    LocatorRange range = map.equal_range(segmentId);
    if (range.first == map.end())
        return;

    for (LocatorMap::iterator it = range.first;
         it != range.second; ++it)
    {
        if (it->second == locator) {
            map.erase(it);
            return;
        }
    }
}

// --- BackupManager ---

/**
 * Create a BackupManager, initially with no backup hosts to communicate
 * with.  See addHost() to add remote backups.
 */
BackupManager::BackupManager(CoordinatorClient* coordinator, uint32_t replicas)
    : coordinator(coordinator)
    , hosts()
    , openHosts()
    , replicas(replicas)
    , segments()
{
}

/// Free up all BackupClients.
BackupManager::~BackupManager()
{
    foreach (BackupClient* host, openHosts)
        delete host;
}

// See BackupClient::closeSegment.
void
BackupManager::closeSegment(uint64_t masterId,
                            uint64_t segmentId)
{
    TEST_LOG("%lu, %lu", masterId, segmentId);
    foreach (BackupClient* host, openHosts) {
        // TODO(stutsman) Exception during one of the closes?
        host->closeSegment(masterId, segmentId);
        delete host;
    }
    openHosts.clear();
}

// See BackupClient::freeSegment.
void
BackupManager::freeSegment(uint64_t masterId,
                           uint64_t segmentId)
{
    TEST_LOG("%lu, %lu", masterId, segmentId);
    uint32_t count = 0;
    pair<SegmentMap::iterator, SegmentMap::iterator> iters(
        segments.equal_range(segmentId));
    SegmentMap::iterator& it = iters.first;
    while (it != iters.second) {
        BackupClient host(it->second);
        host.freeSegment(masterId, segmentId);
        SegmentMap::iterator current = it;
        it++;
        segments.erase(current);
        count++;
    }
    if (count != replicas)
        LOG(WARNING, "Freed %u segments rather than %u", count, replicas);
}

// See BackupClient::openSegment.
void
BackupManager::openSegment(uint64_t masterId,
                           uint64_t segmentId)
{
    LOG(DEBUG, "openSegment %lu, %lu", masterId, segmentId);
    selectOpenHosts();
    foreach (BackupClient* host, openHosts) {
        LOG(DEBUG, "Opening %lu, %lu on an open backup", masterId, segmentId);
        host->openSegment(masterId, segmentId);
        segments.insert(SegmentMap::value_type(segmentId, host->getSession()));
    }
}

/**
 * Collect all the filtered log segments from backups for a set of tablets
 * formerly belonging to a crashed master which is being recovered and pass
 * them to the recovery master to have them replayed.
 *
 * \param recoveryMaster
 *      A reference to the Master which owns this BackupManager and which will
 *      be responsible for the tablets.  This is used to provide a callback
 *      for the Master to replay individual segments.
 * \param masterId
 *      The id of the crashed master for which recoveryMaster will be taking
 *      over ownership of tablets.
 * \param tablets
 *      A set of tables with key ranges describing which poritions of which
 *      tables recoveryMaster should have replayed to it.
 * \param backups
 *      A list of backup locators along with a segmentId specifying for each
 *      segmentId a backup who can provide a filtered recovery data segment.
 *      A particular segment may be listed more than once if it has multiple
 *      viable backups, hence a particular backup locator can also be listed
 *      many times.
 */
void
BackupManager::recover(MasterServer& recoveryMaster,
                       uint64_t masterId,
                       const ProtoBuf::Tablets& tablets,
                       const ProtoBuf::ServerList& backups)
{
    LOG(NOTICE, "Recovering master %lu, %u tablets, %u hosts",
        masterId, tablets.tablet_size(), backups.server_size());

#if TESTING
    if (!mockRandomValue)
        srand(rdtsc());
    else
        srand(0);
#else
    srand(rdtsc());
#endif

#ifdef PERF_DEBUG_RECOVERY_SERIAL
{'fraction_non_alphanumeric': 0.0960519342872284, 'fraction_numerical': 0.004636989931107578, 'mean_word_length': 2.9823265629121605, 'pattern_counts': {'":': 0, '<': 11, '<?xml version=': 0, '>': 21, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '7180438', 'n_tokens_mistral': 4332, 'n_tokens_neox': 4212, 'n_words': 1446}