4462634185

Build Type

push

github

Committed by GitHub

Commit Message

Merge pull request #502 from HDFGroup/hyoklee-patch-1

Run Details

6192 of 7556 relevant lines covered (81.95%)

646387.98 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

92.11

/src/data_placement_engine.cc

/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
 * Distributed under BSD 3-Clause license.                                   *
 * Copyright by The HDF Group.                                               *
 * Copyright by the Illinois Institute of Technology.                        *
 * All rights reserved.                                                      *
 *                                                                           *
 * This file is part of Hermes. The full Hermes copyright notice, including  *
 * terms governing use, modification, and redistribution, is contained in    *
 * the COPYING file, which can be found at the top directory. If you do not  *
 * have access to the file, you may request a copy from help@hdfgroup.org.   *
 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */

#include "data_placement_engine_factory.h"

#include <assert.h>
#include <glpk.h>
#include <math.h>

#include <utility>
#include <random>
#include <map>

#include "hermes.h"
#include "hermes_types.h"
#include "metadata_management.h"
#include "metadata_management_internal.h"
#include "metadata_storage.h"

namespace hermes {

using hermes::api::Status;

std::vector<int> DPE::GetValidSplitChoices(size_t blob_size) {
  int split_option = 10;
  // Split the blob if size is greater than 64KB
  if (blob_size > KILOBYTES(64) && blob_size <= KILOBYTES(256)) {
    split_option = 2;
  } else if (blob_size > KILOBYTES(256) && blob_size <= MEGABYTES(1)) {
    split_option = 5;
  } else if (blob_size > MEGABYTES(1) && blob_size <= MEGABYTES(4)) {
    split_option = 8;
  }

  constexpr int split_range[] = { 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024 };
  std::vector<int> result(split_range, split_range + split_option - 1);

  return result;
}

bool DPE::SplitBlob(size_t blob_size) {
  bool result = false;
  std::random_device dev;
  std::mt19937 rng(dev());

  if (blob_size > KILOBYTES(64)) {
    std::uniform_int_distribution<std::mt19937::result_type> distribution(0, 1);
    if (distribution(rng) == 1) {
      result = true;
    }
  }

  return result;
}

void DPE::GetSplitSizes(size_t blob_size, std::vector<size_t> &output) {
  std::random_device dev;
  std::mt19937 rng(dev());

  std::vector<int> split_choice = GetValidSplitChoices(blob_size);

  // Random pickup a number from split_choice to split the blob
  std::uniform_int_distribution<std::mt19937::result_type>
    position(0, split_choice.size()-1);
  int split_num = split_choice[position(rng)];

  size_t blob_each_portion {blob_size/split_num};
  for (int j {0}; j < split_num - 1; ++j) {
    output.push_back(blob_each_portion);
  }
  output.push_back(blob_size - blob_each_portion*(split_num-1));
}

/** aggregate BLOB schema */
PlacementSchema AggregateBlobSchema(PlacementSchema &schema) {
  std::unordered_map<u64, u64> place_size;
  PlacementSchema result;

  for (auto [size, target] : schema) {
    place_size.insert({target.as_int, 0});
    place_size[target.as_int] += size;
  }
  for (auto [target, size] : place_size) {
    TargetID id = {};
    id.as_int = target;
    result.push_back(std::make_pair(size, id));
  }

  return result;
}

/** topology */
enum Topology {
  Topology_Local,
  Topology_Neighborhood,
  Topology_Global,

  Topology_Count
};

/** calculate data placement */
Status CalculatePlacement(SharedMemoryContext *context, RpcContext *rpc,
                          const std::vector<size_t> &blob_sizes,
                          std::vector<PlacementSchema> &output,
                          const api::Context &api_context) {
  std::vector<PlacementSchema> output_tmp;
  Status result;

  // NOTE(chogan): Start with local targets and gradually expand the target
  // list until the placement succeeds.
  for (int i = 0; i < Topology_Count; ++i) {
    std::vector<TargetID> targets;

    switch (i) {
      case Topology_Local: {
        // TODO(chogan): @optimization We can avoid the copy here when getting
        // local targets by just getting a pointer and length.
        targets = LocalGetNodeTargets(context);
        break;
      }
      case Topology_Neighborhood: {
        targets = GetNeighborhoodTargets(context, rpc);
        break;
      }
      case Topology_Global: {
        // TODO(chogan): GetGlobalTargets(context, rpc);
        break;
      }
    }

    if (targets.size() == 0) {
      result = DPE_PLACEMENTSCHEMA_EMPTY;
      continue;
    }

    std::vector<u64> node_state =
      GetRemainingTargetCapacities(context, rpc, targets);
    auto dpe = DPEFactory().Get(api_context.policy);
    dpe->bandwidths = GetBandwidths(context, targets);
    result = dpe->Placement(blob_sizes, node_state,
                   targets, api_context, output_tmp);

    if (!result.Failed()) {
      break;
    }
  }

  // Aggregate placement schemas from the same target
  if (result.Succeeded()) {
    for (auto it = output_tmp.begin(); it != output_tmp.end(); ++it) {
      PlacementSchema schema = AggregateBlobSchema((*it));
      if (schema.size() == 0) {
        result = DPE_PLACEMENTSCHEMA_EMPTY;
        LOG(ERROR) << result.Msg();
        return result;
      }
      output.push_back(schema);
    }
  }

  return result;
}

}  // namespace hermes

1	/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
2	* Distributed under BSD 3-Clause license. *
3	* Copyright by The HDF Group. *
4	* Copyright by the Illinois Institute of Technology. *
5	* All rights reserved. *
6	* *
7	* This file is part of Hermes. The full Hermes copyright notice, including *
8	* terms governing use, modification, and redistribution, is contained in *
9	* the COPYING file, which can be found at the top directory. If you do not *
10	* have access to the file, you may request a copy from help@hdfgroup.org. *
11	* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
12
13	#include "data_placement_engine_factory.h"
14
15	#include <assert.h>
16	#include <glpk.h>
17	#include <math.h>
18
19	#include <utility>
20	#include <random>
21	#include <map>
22
23	#include "hermes.h"
24	#include "hermes_types.h"
25	#include "metadata_management.h"
26	#include "metadata_management_internal.h"
27	#include "metadata_storage.h"
28
29	namespace hermes {
30
31	using hermes::api::Status;
32
33	std::vector<int> DPE::GetValidSplitChoices(size_t blob_size) {	2✔
34	int split_option = 10;	2✔
35	// Split the blob if size is greater than 64KB
36	if (blob_size > KILOBYTES(64) && blob_size <= KILOBYTES(256)) {	2✔
37	split_option = 2;	×
38	} else if (blob_size > KILOBYTES(256) && blob_size <= MEGABYTES(1)) {	2✔
39	split_option = 5;	2✔
40	} else if (blob_size > MEGABYTES(1) && blob_size <= MEGABYTES(4)) {	×
41	split_option = 8;	×
42	}
43
44	constexpr int split_range[] = { 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024 };	2✔
45	std::vector<int> result(split_range, split_range + split_option - 1);	4✔
46
47	return result;	4✔
48	}
49
50	bool DPE::SplitBlob(size_t blob_size) {	11✔
51	bool result = false;	11✔
52	std::random_device dev;	11✔
53	std::mt19937 rng(dev());	11✔
54
55	if (blob_size > KILOBYTES(64)) {	11✔
56	std::uniform_int_distribution<std::mt19937::result_type> distribution(0, 1);	7✔
57	if (distribution(rng) == 1) {	7✔
58	result = true;	2✔
59	}
60	}
61
62	return result;	22✔
63	}
64
65	void DPE::GetSplitSizes(size_t blob_size, std::vector<size_t> &output) {	2✔
66	std::random_device dev;	4✔
67	std::mt19937 rng(dev());	2✔
68
69	std::vector<int> split_choice = GetValidSplitChoices(blob_size);	4✔
70
71	// Random pickup a number from split_choice to split the blob
72	std::uniform_int_distribution<std::mt19937::result_type>
73	position(0, split_choice.size()-1);	2✔
74	int split_num = split_choice[position(rng)];	2✔
75
76	size_t blob_each_portion {blob_size/split_num};	2✔
77	for (int j {0}; j < split_num - 1; ++j) {	18✔
78	output.push_back(blob_each_portion);	16✔
79	}
80	output.push_back(blob_size - blob_each_portion*(split_num-1));	2✔
81	}	2✔
82
83	/** aggregate BLOB schema */
84	PlacementSchema AggregateBlobSchema(PlacementSchema &schema) {	34,293✔
85	std::unordered_map<u64, u64> place_size;	68,586✔
86	PlacementSchema result;	34,293✔
87
88	for (auto [size, target] : schema) {	68,658✔
89	place_size.insert({target.as_int, 0});	34,365✔
90	place_size[target.as_int] += size;	34,365✔
91	}
92	for (auto [target, size] : place_size) {	68,646✔
93	TargetID id = {};	34,353✔
94	id.as_int = target;	34,353✔
95	result.push_back(std::make_pair(size, id));	34,353✔
96	}
97
98	return result;	34,293✔
99	}
100
101	/** topology */
102	enum Topology {
103	Topology_Local,
104	Topology_Neighborhood,
105	Topology_Global,
106
107	Topology_Count
108	};
109
110	/** calculate data placement */
111	Status CalculatePlacement(SharedMemoryContext context, RpcContext rpc,	34,285✔
112	const std::vector<size_t> &blob_sizes,
113	std::vector<PlacementSchema> &output,
114	const api::Context &api_context) {
115	std::vector<PlacementSchema> output_tmp;	68,570✔
116	Status result;	34,285✔
117
118	// NOTE(chogan): Start with local targets and gradually expand the target
119	// list until the placement succeeds.
120	for (int i = 0; i < Topology_Count; ++i) {	34,303✔
121	std::vector<TargetID> targets;	34,297✔
122
123	switch (i) {	34,297✔
124	case Topology_Local: {	34,285✔
125	// TODO(chogan): @optimization We can avoid the copy here when getting
126	// local targets by just getting a pointer and length.
127	targets = LocalGetNodeTargets(context);	34,285✔
128	break;	34,285✔
129	}
130	case Topology_Neighborhood: {	6✔
131	targets = GetNeighborhoodTargets(context, rpc);	6✔
132	break;	6✔
133	}
134	case Topology_Global: {	6✔
135	// TODO(chogan): GetGlobalTargets(context, rpc);
136	break;	6✔
137	}
138	}
139
140	if (targets.size() == 0) {	34,297✔
141	result = DPE_PLACEMENTSCHEMA_EMPTY;	12✔
142	continue;	12✔
143	}
144
145	std::vector<u64> node_state =	34,285✔
146	GetRemainingTargetCapacities(context, rpc, targets);	34,285✔
147	auto dpe = DPEFactory().Get(api_context.policy);	34,285✔
148	dpe->bandwidths = GetBandwidths(context, targets);	34,285✔
149	result = dpe->Placement(blob_sizes, node_state,	34,285✔
150	targets, api_context, output_tmp);	34,285✔
151
152	if (!result.Failed()) {	34,285✔
153	break;	34,279✔
154	}
155	}
156
157	// Aggregate placement schemas from the same target
158	if (result.Succeeded()) {	34,285✔
159	for (auto it = output_tmp.begin(); it != output_tmp.end(); ++it) {	68,558✔
160	PlacementSchema schema = AggregateBlobSchema((*it));	34,279✔
161	if (schema.size() == 0) {	34,279✔
162	result = DPE_PLACEMENTSCHEMA_EMPTY;	×
163	LOG(ERROR) << result.Msg();	×
164	return result;	×
165	}
166	output.push_back(schema);	34,279✔
167	}
168	}
169
170	return result;	34,285✔
171	}
172
173	} // namespace hermes

HDFGroup / hermes / 4462634185

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous