Advanced Computer Systems (ACS), 2017/2018
Final Exam
This is your final 5-day take home exam for Advanced Computer Systems, block 2, 2017/2018. This exam is due via Digital Exam on January 22, 2018, 23:59. The exam will be evaluated on the 7-point grading scale with external grading, as announced in the course description.
Hand-ins for this exam must be individual. Cooperation on or discussion of the contents of the exam with other students is strictly forbidden. The solution you provide should reflect your knowledge of the material alone. The exam is open-book and you are allowed to make use of the book and other reading material of the course. If you use on-line sources for any of your solutions, they must be cited appropriately. While we require the individual work policy outlined above, we will allow students to ask clarification questions on the formulation of the exam during the exam period. A clarification question should not include any solution ideas to questions in the exam, but only pertain to the meaning of theproblem formulations and associated assumptions in the exam text itself. These questions will only be accepted through the forums on Absalon, and will be answered by the TAs or your lecturer. The goal of the latter policy is to give all students fair access to the same information during the exam period.
A well-formed solution to this exam should include a PDF file with answers to all scenario questions as well as questions posed in the programming part of the exam. In addition, you must submit your code along with your written solution. Evaluation of the exam will take both into consideration.
Do not get hung up in a single question. It is best to make an effort on every question and write down all your solutions than to get a perfect solution for only one or two of the questions. Nevertheless, keep in mind that a concise and well-written paragraph in your solution is always better than a long paragraph.
Note that your solution has to be submitted via Digital Exam (https://eksamen.ku.dk/) in electronic format. In the unlikely event that Digital Exam is unavailable during the exam period, we will publish the exam in Absalon and expect any issues to be reported to the email y.wang@di.ku.dk. It is your responsibility to make sure in time that the upload of your files succeeds. We strongly suggest composing your solution using a text editor or LaTeX and creating a PDF file for submission. Paper submissions will not be accepted, and submissions will only be accepted in Digital Exam.
Learning Goals of ACS
We attempt to touch on many of the learning goals of ACS. Recall that the learning goals of ACS are:
(LG1) Describe the design of transactional and distributed systems, including techniques for modularity,performance, and fault tolerance.
(LG2) Explain how to employ strong modularity through a client-service abstraction as a paradigm tostructure computer systems, while hiding complexity of implementation from clients.
(LG3) Explain techniques for large-scale data processing.
(LG4) Implement systems that include mechanisms for modularity, atomicity, and fault tolerance. (LG5) Structure and conduct experiments to evaluate a system's performance.
(LG6) Discuss design alternatives for a modular computer system, identifying desired system propertiesas well as describing mechanisms for improving performance while arguing for their correctness.
(LG7) Analyze protocols for concurrency control and recovery, as well as for distribution and replication.
(LG8) Apply principles of large-scale data processing to analyze concrete information-processingproblems.
Scenarios
Question 1: Data Processing (LG3, LG8)
A car rental company BestCars maintains an operational database storing information on their customers, cars, as well as rental records.
The management of BestCars would like to analyze the interest of their customers in terms of the size of cars. In particular, they assign a bunch of data analysis tasks to you, the best data scientist and developer in BestCars. One of the tasks is as follows: “Produce a list of ids of the users who have only rent big cars, but not small cars.”
Since the analysis is very heavy, to avoid any interference with the operational system, the necessary data for your task has been pre-extracted outside of the database and stored separately. For the aforementioned task, you are provided with two heap files storing two tables whose schemas are as follows: (1)
Cars(car_id, make, model, size_category), and (2) Rentals(user_id, car_id, time). You can assume thevalues of size_category can be either “small” or “big”. You are provided with one server with memory larger than the square root of any table, but insufficient to hold any one of them completely. This applies to any temporary tables that are generated by your algorithm. Therefore, you have to resort to external memory algorithms to solve the problem. If you need to make any further assumptions in your answers, please state them clearly as part of your solution. Please write down your solutions to the following questions.
1. State an external memory algorithm with the minimum cost in terms of I/O to answer the query above. Argue for the algorithm’s correctness and efficiency.
2. State the I/O cost of the algorithm you designed. You can make your own notation of the size of each attribute in any table.
NOTE 1: To state an algorithm, you can reference existing sort-based or hash-based external memoryalgorithms. You should not state all the steps of these existing algorithms from scratch again, but you should clearly state the steps that you need to change in the algorithms you reference, and also how you change these steps. To describe how you change a step, refer to the step and list the sub-steps that need to be executed to achieve your goal.
NOTE 2: Instead of just using several existing external memory algorithms in sequence as black boxes,you should design a single algorithm that addresses the whole task holistically. That is why in NOTE 1 we expect that you will need to show changes to steps of existing algorithms, if necessary.
NOTE 3: Your solution will be graded partly according to the optimality of your algorithm and the qualityof the justifications. That is to say, a solution with justified lower I/O cost will in general help you get a better grade.
Question 2: Replication (LG7)
Three processes, P1, P2, and P3, replicate a common object. The object is updated asynchronously by three different clients, and each client happens to dispatch its update to a different process out of P1, P2, and P3. After receiving each update, the respective processes incorporates the update in its local replica
and then propagates the new value to the other processes. The precise exchange of messages is shown in the following figure:
Figure 1: Exchange of messages among processes
Note that P1 got a client update at A, P2 at B, and P3 at D; the clients are omitted from the figure to avoid cluttering. The system uses vector clocks to keep track of the object version internally. You may assume that all local clock values start at zero at the beginning of the interaction shown. In addition, assume that only updates from clients cause an increment of a local clock, i.e., not every event causes an increment of the local clock except for original client updates. Therefore, (1,1,1) is the maximum vector clock possible in the given interaction. The latter policy ensures that, if update propagation reaches all processes, then we expect the object’s version to converge as either overwriting or merging through a commutative associative function takes place.
Every time an update is received by a process P, the process chooses one out of the following actions to incorporate the update:
(A1) Keep P’s own value;
(A2) Overwrite P’s value with the latest value from the message;
(A3) Call an application-specific merge function to combine both values consistently.
For each point in the execution from A to K shown in Figure 1, give the value of the vector clock at the corresponding process before the update event is processed, the value of the vector clock received in the incoming message or sent in the outgoing message, the action taken by the process to incorporate the update, and the value of the vector clock after the update is processed. Use a table with the following format to report your answer:
|
Event |
Vector Clock at |
Message Vector |
Action Taken by |
Vector Clock at |
|
Process Before |
Clock |
Process |
Process After |
|
|
A |
… |
… |
… |
… |
|
B |
… |
… |
… |
… |
|
… |
… |
… |
… |
… |
In addition to the table, provide a paragraph with a brief justification for your reasoning for constructing the table, i.e., discuss when each action should be taken depending on the vector clock values at the given message and event.
Question 3: ARIES Recovery (LG7)
In the recovery scenario described in the following, we ask you to explain the functioning and justification behind the ARIES recovery algorithm. At the beginning of time, there are no transactions active in the system and no dirty pages. A checkpoint is taken. After that, four transactions, T1, T2, T3, and T4, enter the system and perform various operations. The detailed log follows:
|
LOG |
|||||
|
LSN |
PREV_LSN |
XACT_ID |
TYPE |
PAGE_ID |
UNDONEXTLSN |
|
— |
——– |
——- |
—- |
——- |
———– |
|
1 |
– |
– |
begin CKPT |
– |
– |
|
2 |
– |
– |
end CKPT |
– |
– |
|
3 |
NULL |
T1 |
update |
P3 |
– |
|
4 |
3 |
T1 |
update |
P1 |
– |
|
5 |
NULL |
T2 |
update |
P1 |
– |
|
6 |
NULL |
T3 |
update |
P3 |
– |
|
7 |
5 |
T2 |
update |
P2 |
– |
|
8 |
NULL |
T4 |
update |
P2 |
– |
|
9 |
4 |
T1 |
update |
P4 |
– |
|
10 |
8 |
T4 |
commit |
– |
– |
|
11 |
9 |
T1 |
abort |
– |
– |
|
12 |
7 |
T2 |
abort |
– |
– |
|
13 |
12 |
T2 |
CLR |
P2 |
A |
|
14 |
10 |
T4 |
end |
– |
– |
|
15 |
11 |
T1 |
CLR |
P4 |
B |
|
16 |
15 |
T1 |
CLR |
P1 |
C |
|
17 |
13 |
T2 |
CLR |
P1 |
D |
|
18 |
16 |
T1 |
CLR |
P3 |
E |
|
19 |
18 |
T1 |
end |
– |
– |
|
——– XXXXXXX —— CRASH! |
—— XXXXXXX ——– |
||||
A crash occurs at the end of the log as shown. Considering again that the system employs the ARIES recovery algorithm, answer the following questions and justify each of your answers.
1. In the log, the undonextLSN values for several CLRs are represented by the letters A–E. For each letter, state the value of the corresponding undonextLSN and why it has the given value.
2. What are the states of the transaction table and of the dirty page table after the analysis phase of recovery? Explain why.
3. Show the additional contents of the log after the recovery procedure completes. Provide a brief explanation for why any new log records shown need to be added.
4. In the system shown, let us assume that the database is memory-resident, i.e., upon start-up all contents of nonvolatile storage are loaded into volatile storage (which is large enough to cache everything). Thus, no page replacements are ever necessary during normal operation. Furthermore, assume plenty of log buffer space is available and no background page writes are performed. Under these conditions, answer the following:
a. Which log records could trigger writes to stable storage during normal operation in the scenario above? Why?
b. Following the ARIES log record structure introduced in the course for update records, is there any information that would not need to be written to stable storage in such a scenario? If so, explain which information and why. Otherwise, justify why all information in these records needs to reach stable storage.
Programming Task
In this programming task, you will develop a simplified edge-to-cloud distributed interpreter abstraction in a scenario inspired by emerging self-checkout supermarkets. Through the multiple questions below, you will describe your design (LG1), expose abstractions as a services (LG2), design and implement these services (LG4, LG6, LG7), and evaluate your implementation with an experiment (LG5).
As with assignments in this course, you should implement this programming task in Java, compatible with JDK 8. As an RPC mechanism, you are only allowed to use Jetty together with XStream and/or Kryo, and we expect you to abstract the use of these libraries behind clean proxy classes as in the assignments of the course. You are allowed to reuse communication code from the assignments when building your proxy classes. You are also allowed to use skeleton code from Assignment 3 to orchestrate experimental workload and measurements as well as JUnit testing skeleton code from the assignments.
In contrast to a complex code handout, in this exam you will be given simple interfaces to adhere to, described in detail below. We expect the implementation that you provide of these interfaces to follow the description given, and to employ architectural elements and concepts you have learned during the course. We also expect you to respect the usual restrictions given in the qualification assignments with respect to libraries allowed in your implementation (i.e., Jetty, XStream, Kryo, JUnit, and the Java built-in libraries, especially java.util.concurrent).
The Self-Checkout Supermarket Scenario
We focus on a scenario inspired by recent developments in self-checkout supermarkets.1,2 In this near-future scenario, a machine learning component is deployed at each store of the fictitious acertainsupermarket.com firm to automatically identify items that are added or removed from each customer’s cart. These events trigger function calls to an edge service that keeps track of the state of the carts for the multiple customers. Many edge service instances are run to account for geographical distribution and reduce latency on queries to the cart state. As such, an edge service instance can support the activities of a number of nearby supermarkets. However, a supermarket interacts with one and only one edge service instance.3 The edge service instances, in turn, invoke function calls on a centralized cloud service that keeps track of item prices and stocks to support the supply chain operation of the supermarket. These calls to the cloud service comprise queries for price and other details for single items as well as updates to item stocks.
Two kinds of client components interact with the edge service. In order to allow the customer to see the current status of her shopping, mobile clients query edge service instances. Moreover, mobile clients trigger checkout operations when the customer is ready to leave the store. These client components are expected to run on a customer’s mobile phone and on tablet devices attached to physical shopping carts. In addition to the mobile clients, the machine learning components also act as store clients that add or remove items from the shopping cart state kept by edge service instances.
1 Amazon Go store concept website (July 2017). https://www.amazon.com/b?node=16008589011.
2 Planet Money Episode 730: Self Checkout. Online podcast (May 2017). http://www.npr.org/sections/money/2016/10/19/498571623/episode-730-self-checkout.
3 Note that we make this assumption for simplicity in this exam, but it could be extended by organizing customer interactions into sessions and allowing for new sessions to be started in other edge service instance in case of failures.
Other than the edge service instances, a third kind of client interacts directly with the backend cloud service. These admin clients are used occasionally by the staff of the supermarket to query and update several items to replenish stocks.
The overall organization of components in the acertainsupermarket.com’s system architecture is summarized in the following figure.
Figure 2: Organization of components in acertainsupermarket.com's system architecture
The edge service layer exposes to clients the Cart interface, while the cloud service layer exposes to the edge service layer the Supermarket interface. For better use of computational resources, both service layers are multi-threaded, and we wish to make the implementations of the operations in both Cart and Supermarket behave atomically. Client programs invoke functions on Cart and Supermarket instances via RPC, and so do Cart instances on the Supermarket instance.
Your implementation should be focused on the Cart and Supermarket services. For testing and experimentation purposes, you will need to create programs that simulate the calls made to these services by client programs.
To limit the workload in this exam, all services are assumed not to provide durability. In other words, all data should be stored in data structures in main memory, and you do not need to implement a mechanism for durability for the methods of either the Cart or the Supermarket interfaces.
The Cart Abstraction
The Cart service exposes as its API the following operations:
1) add(int cartId, int itemId): This function adds a unit of the item with given item ID to the cart identified by the provided cart ID. The operation must be atomic with respect to all other operations in the same Cart instance. The operation validates the cart ID to ensure that it is
nonnegative and among the IDs managed by this Cart instance. You may assume for the purposes of this exam that the collection of cart IDs handled by a given Cart instance is fixed and known a priori. Cart IDs are unique within a Cart instance, but are not required to be globally unique. Once validation of the cart ID succeeds, if the item is already among the items in the customer cart, then the quantity of the item is incremented by one. Otherwise, the operation looks up the item by calling getItems on the Supermarket service. This returns all the details of the item or raises an appropriate exception if the item ID is not valid. If the item has not yet been associated to the cart, then the item name and price are saved in the Cart instance along with a quantity of one as a CartItem, so as to ensure that no subsequent price changes are observed by the customer. Note that validation failures should raise an appropriate exception. Moreover, if an exception is raised by the call to the Supermarket service, this exception should be propagated further to the client.
2) remove(int cartId, int itemId): This operations removes one unit of the item with given item ID from the cart identified by the provided cart ID. The operation must be atomic with respect to all other operations in the same Cart instance. The operation validates the cart ID in the same manner as the add operation, raising appropriate exceptions if needed. Moreover, the operation also raises an exception if the item is not associated to the cart. To make this operation behave as an inverse of add, two cases are handled. If the operation would make the quantity of the item drop to zero in the cart, then the corresponding CartItem instance is simply removed. Otherwise, the quantity of the item is decremented by one.
3) getCartItems(int cartId) à List<CartItem>: This operation lists the items in the cart identified by the given cart ID. The operation must be atomic with respect to all other operations in the same Cart instance. The operation validates the cart ID in the same manner as the operations above, raising appropriate exceptions if needed.
4) checkout(int cartId): This operation performs the checkout of the current contents of the cart identified by the given cart ID. The operation must be atomic with respect to all other operations in the same Cart instance. The operation validates the cart ID in the same manner as the operations above, raising appropriate exceptions if needed. Afterwards, the operation invokes updateStocks in the Supermarket service to reduce the stocks for all items in the cart by their quantity. If the update is successful, then the function purges all items from the cart, leaving it empty. If an exception is raised by the call to the Supermarket service, however, then this exception should be propagated to the client.
As a constraint, the method you use for ensuring before-or-after atomicity at Cart instances must allow for concurrent read-only operations, i.e., two getCartItems operations executed in different threads must not block each other. In addition, solutions that allow for some concurrency of getCartItems with other operations in the interface will be valued higher than ones that do not.
The Supermarket Abstraction
The Supermarket service exposes as its API the following operations:
1) updateStocks(List<ItemDeltas> itemDeltas): This operation adds to or removes from the stocks of multiple items the amounts specified as differences to item quantities (itemDeltas). The operation must be atomic with respect to all other operations in the Supermarket service. Each item ID provided is validated by this operation to ensure that it is nonnegative and among the IDs managed by the Supermarket service. Appropriate exceptions must be raised upon validation failures.
2) getItems(Set<Integer> itemIds) à List<Item>: This operation returns the details of the items identified by the provided item IDs. The operation must be atomic with
respect to all other operations in the Supermarket service. Each item ID is validated as in the updateStocks operation, raising appropriate exceptions if needed.
As a constraint, the method you use for ensuring before-or-after atomicity at Supermarket instances must allow for concurrent read-only operations, i.e., two getItems operations executed in different threads must not block each other. In addition, solutions that allow for some concurrency among updateStocks and getItems operations will be valued higher than ones that do not.
Failure handling
Your implementation only needs to tolerate failures that respect the fail-stop model: Network partitions do not occur, and failures can be reliably detected. We model the situation of components hosted in a single data center, and a service configured so that network timeouts can be taken to imply that the component being contacted indeed failed. In other words, the situations that the component was just overloaded and could not respond in time, or that the component was not reachable due to a network outage are just assumed not to occur in our scenario.
Since durability is not required in this exam, failures imply loss of the entire data stored in main memory at the affected component. However, individual components in your implementation must be isolated, and other components in the system should continue operating normally in case of such a failure. This strategy ensures that Cart instances follow a fail-soft design with respect to the Supermarket instance. In other words, if the Supermarket instance fails, Cart instances should still be able to respond to queries on the state of shopping carts, but will raise exceptions when some operations, namely, item additions or checkout, are invoked.
Data and Initialization
As mentioned above, all the data for the Cart and Supermarket services is stored in main memory. You may generate and load initial data for the services at class constructors according to a procedure of your own choice; only note that the distribution of values generated must make sense for the experiment you will design and carry out below.
You may assume that any configuration information is loaded once each component is initialized also at its constructor, e.g., naming information needed by Cart service instances to access the Supermarket instance. For simplicity, you can encode configuration information as constants in a separate configuration class.
High-Level Design Decisions, Modularity, Fault-Tolerance
First, you will document the main organization of modules and data in your system.
Question 1 (LG1, LG2, LG4, LG6, LG7): Describe your overall implementation of the Cart and the Supermarket interfaces. In addition to an overview of the organization of your code, include the following aspects in your answer:
• What RPC semantics are implemented between clients and the Cart or Supermarket services? What about between the Cart and the Supermarket? Explain.
• How are failures of the Supermarket instance contained at the Cart instances? Why does your failure containment implementation turn out to guarantee a fail-soft design for the Cart instances with respect to the Supermarket instance?
• How did you achieve all-or-nothing atomicity at the Cart service, even in the cases where exceptions are propagated from the Supermarket service? How did you achieve all-or-
nothing atomicity at the Supermarket service? Explain.
(1 paragraph for overall code organization + 3 paragraphs, one for each of three points above)
Before-or-After Atomicity
Now, you will argue for your implementation choices regarding before-or-after atomicity for both the Cart and Supermarket services. NOTE: For both questions below, the method you design for before-or-after atomicity does not need to be complex, as long as you argue convincingly for its correctness, its trade-off in complexity of implementation and performance, and how it fits in the system as a whole. In general, implementations that provide for more concurrency will be valued higher than ones providing less, as long as it can be reasonably argued that the system can take advantage of the added concurrency.
Question 2 (LG1, LG4, LG6, LG7): Each instance of Cart needs to provide for before-or-after atomicity on the operations of the interface. Describe how you ensured before-or-after atomicity of these operations. In particular, mention the following aspects in your answer:
• Which method did you use for ensuring serializability at each Cart instance? Describe your method at a high level.
• Argue for the correctness of your method; to do so, show how your method is logically equivalent to a trivial solution based on a single global lock or to a well-known locking protocol, e.g., a variant of two-phase locking.
• Argue for whether or not you need to consider the issue of reads on predicates vs. multi-granularity locking in your implementation, and explain why.
• Argue for the performance of your method; to do so, explain your assumptions about the workload the service is exposed to and why you believe other alternatives you considered (e.g., locking vs. optimistic approach) would be better or worse than your choice.
(4 paragraphs, one for each point)
Question 3 (LG1, LG4, LG6, LG7): The Supermarket service executes operations originated at multiple clients. Describe how you ensured before-or-after atomicity of these operations. In particular, mention the following aspects in your answer:
• Which method did you use for ensuring serializability at the Supermarket service (e.g., locking vs. optimistic approach)? Describe your method at a high level.
• Argue for the correctness of your method; to do so, show how your method is logically equivalent to a trivial solution based on a single global lock or to a well-known locking protocol, e.g., a variant of two-phase locking.
• Argue for whether or not you need to consider the issue of reads on predicates vs. multi-granularity locking in your implementation, and explain why.
• Argue for the performance of your method; to do so, explain your assumptions about the
workload the service is exposed to and why you believe other alternatives you considered (e.g., locking vs. optimistic approach) would be better or worse than your choice.
(4 paragraphs, one for each point)
Testing
You will then describe your testing strategy for the two services, with a focus on before-or-after atomicity. NOTE: While testing for all-or-nothing atomicity may help you eliminate errors from your implementation, affecting the evaluation of Question 1, these tests will not per se be evaluated for the exam. We will consider test code and arguments for the property of before-or-after atomicity only.
Question 4 (LG4, LG6): Describe your high-level strategy to test your implementation of both the Cart and the Supermarket services. In particular, how did you test before-or-after atomicity of operations at both the Cart and the Supermarket services? Recall that you must document how your tests verify that anomalies do not occur (e.g., dirty reads or dirty writes). (1-2 paragraphs)
Experiments
Finally, you will evaluate the scalability of one component of your system experimentally.
Question 5 (LG5): Design, describe the setup for, and execute an experiment that shows how well your implementation of the Supermarket service behaves as concurrency in the number of clients is increased. You will need to argue for a basic workload mix involving calls from the clients accessing the service, including distribution of operations and data touched. Depending on the workload, you may wish to also scale the corresponding data sizes with increasing number of clients. Given a mix of operations from clients, you should report how the throughput of the service scales as more clients are added. Remember to thoroughly document your setup. In particular, mention the following aspects in your answer:
• Setup: Document the hardware, data size and distribution, and workload characteristics you have used to make your measurements. In addition, describe your measurement procedure, e.g., procedure to generate workload calls, use of timers, and numbers of repetitions, along with short arguments for your decisions. Also make sure to document your hardware configuration and how you expect this configuration to affect the scalability results you obtain.
• Results: According to your setup, show a graph with your throughput measurements for the Supermarket service on the y-axis and the numbers of clients on the x-axis, while maintaining the workload mix you argued for in your setup and any other parameters fixed. How does the observed throughput scale with the number of clients? Describe the trends observed and any other effects. Explain why you observe these trends and how much that matches your expectations.
(3 paragraphs + figure: 2 paragraphs for workload design and experimental setup + figure required for results + 1 paragraph for discussion of results)
readme:
———————最最重要的写在前面———————————
1.代码查重非常严格，会人工和软件两重查重的，即使思路一致也极有可能会被查出来。
2.所以，请只接我这一单，如果有遇到跟我一样的单，请一定一定务必用不同的思路（java RPC, 加锁什么的模式确实较为固定，但测试，功能实现之类的方面请绝对不要一点点雷同，真的会死人的…）
3.要求使用JDK 8，不然他们批改的系统会报错。写作业的时候推荐使用的ide是eclipse。
4.框架没有给完整，RPC可以用我之前作业里的现成的框架代码，所有作业里用到的代码都可以reuse在考试题里。
5.如果中途有试题更新（比如会有些错误更正），我会第一时间告知的。
6.附上了我平时的作业的题目和代码，代码是基本正确的，有小瑕疵，可参考。
———————请按照要求完成programing task部分（包括文字描述部分）——————-
2.报告描述部分（是关于code的完成问题，有时会有写延伸的问题）：请尽可能详细每点都答到，且要尽量具体（举例子），每一个做的决定都要写为什么，比如排序用来priority queue，就要说为什么用这个数据结构
3.对于测试的描述：要包含：输入，输出，预期结果。。。尽量详细，在完成它要求的几个方面的测试之后，尽可能多的写测试是加分项。
4.import了原先starting code里没有的包要在报告里写出来，同理，如果下载使用了新的jar包什么的，也要在报告里说出来。
5.如果有从网络，书，publication或其他地方直接引用了代码，甚至参考了idea请在文末写上引用。
———————其他一些小细节tips（在作业里遇到的，考试可能也会遇到——————–
=======================================老师推荐的加锁格式==================================
lock here
try {
return value (if needed)
}
finally {
unlock here
}
而不是下面这种：
下面这种会扣分：
lock here
if( should throw exception 1) {
unlock
throw }
if( should throw exception 2) {
unlock
throw
}
unlock
return
===============完成all or nothing性质===============
-Validate the input (in one loop！),
– Perform the updates (in another loop！).
========atomicity原子性实现=====================
第一步：check all input validation.
第二步：all locks are granted before data processing.
==============multiple threads===============
Use ThreadLocalRandom when working with multiple threads: ThreadLocalRandom.current().nextX(…) (where X is Int, Long, etc)
====可能会遇到多个server的情况（replication，master server和slave server）===========
起多个server的时候，会需要用Apache ant来运行测试。
———————————————————————————–
前情提要：
1.一定用JDK 8.
2.在实现RPC的时候只能使用jetty， XStream 和Kryo（我的之前的作业里有RPC框架，可以直接copy过来改改）
3. 用JUnit 测试框架（之前作业里有）
4.用之前的测量方法去进行workload测量，（之前的作业里，那个画图的文件夹里有）
5.可以用java.util.concurrent
————————————————————————-
背景介绍：
这个题目就是想要模拟自助结账的超市的场景。人们把mobile client装到手机上可以随时查看自己的当前购物状态，store client可能是什么购物车啥的上的只能组件可以通过add和removefunction来添加删除东西。然后你想走了，就用mobile client去checkout
——————————第五页————————————
事件会触发function call 到edge service，edge service就是保存cart的状态什么的；一个edge service的实例可以支持很多附近的超市的活动，但是一个超市只跟一个edge service的实例交互。
edge service会调用cloud service的function call，cloud service会存item的price和stock，（可以查询单个item的价格和其他detail，同样也能更新item stocks）
有3种客户端（client）：mobile client和store client，还有admin client。
其中，mobile client和store client和edge service交互。
客户可以通过询问edge service实例去查询太当前的购物状态，mobile client在想离开store的时候还可以出发checkout操作，
store client能从cart中add或者remove item（通过add和remove修改edge service所记录的cart状态）
第三种客户：admin client 直接和cloud service交互
admin client是由超市员工偶尔调用来查询和更新一些items和补充stock（库存）的
（文档第六页的图显示的很清晰，edge service层在Cart 接口里，cloud service在Supermarket接口里，我感觉，对于mobile client和store client来说Cart是server， 对于cart和admin client来说，supermarket是server）
—————————-第六页————————————
client 程序代用Cart和Supermarket的function是通过RPC（加proxy），【具体说应该是mobileclient和store client调用cart的function是通过proxy， 然后cart和admin client调用supermarket的function是通过proxy。】
写测试的话，就可以模拟client调用这些服务。
—————————————————————-
在.com.acertainsupermarket.interface的Cart。java里完成：
1. add(int cartId, int itemId):
这个function是根据itemID的去添加 a unit of the item（一个单位的item）到Cart（由提供的cartId）里。
这个操作也是原子性的。
首先， 验证cart id以确保它是非负数，而且是在Cart实例管理的一堆cart中（即存在这个cart id不是无中生有）。
在这里我们假设由cart实例处理的cart id的集合是固定的且事先知道的。（验证不成功要抛出相应的异常）
在一个cart实例中， cart ids 是唯一的，但不要求它全局唯一。
一旦验证cart id成功，如果这个item已经在客户的购物车里了，那么这个item数量加一；
如果这个item没有放到购物车里，我们通过调用supermarket接口里的 getItems函数来查询这个item， 这个getItems函数会返回这个item的详细信息，或者如果这个item id不合法的话，会抛出exception。这个item的名字和价格就会以CartItem的形式被存在cart实例里。这样子是为了避免客人发现随后有价格变动什么的（我理解大概就是把东西放进购物车后，如果价格再改变，我买的还是这个价）。
note：如果验证失败的话，要抛出合理的异常，
如果调用getitems时，由supermarket抛出了异常，这个异常应该传递到client，（调用getitems抛出了异常，在add这里也要抛出异常）
2. remove(int cartId, int itemId):
跟add对应，这里是根据cartid和itemid去从对应的cart里删除一个单位的item。
这个操作也要是原子性的。
首先，和add函数一样，去验证cart id，并在有必要的时候抛出异常， 而且，如果这个item不在购物车里（cart里）， 要抛出异常，
如果remove操作使某个item在cart中数量为0了，那么相对应的cartitem实例就要被删除了。如果购物车中海油这个item，这个item的数量就减一。
3. getCartItems(int cartId)——> List<CartItem>:
这个函数是给一个cartid，返回一个Cartitem的list，（即在这个cart里的所有cartitem的list）。
这个操作必须是原子性的。
首先，要先验证cartid（跟上面的验证方式一样），如有需要抛出异常。
4. checkout(int cartId):
对当前购物车（由给的cartid确定购物车是哪一个）里的东西，实施checkout结账操作。
此操作要是原子性的
首先， 验证cart id（和前面一样）
然后，调用supermarket接口中的updateStocks， 去减少在cart中的所有item的相应stock（库存）。
如果update成功的话，这个函数清除cart（购物车）中的所有item，（清空购物车）。
如果在调用updatestock的时候有抛出异常，在这个函数这批也要抛出相应的异常
Note：在cart实例里，确保before-and-after 原子性的方法不能影响并发 只读 操作，比如说，在不同的线程在执行 getcartitems， 他们不能相互阻塞。
而且， 如果能让getcartitems操作和其他操作并发的话，就更好了！！（即， getcartitems的时候并发执行add和remove之类的。）
————————————————————————————-
在.com.acertainsupermarket.interface的Supermarket .java里完成
1.updateStocks(List<ItemDeltas> itemDeltas):
这个操作add指定数量的多个items到库存（stock）里，或者，从库存中删除制定数量的多个items。
首先要验证item id， 确保他是非负的，且是在supermarket 服务管理的一堆id之中， 如有必要合理的异常应该抛出。
这操作要是原子性的。
2.getItems(Set<Integer> itemIds) –> List<Item>:
该操作return所给的items的详细信息。
要像前面updateStocks函数一样去验证item id，如有需要抛出异常。
note，同理，两个getitems在不同线程上执行，不能相互阻塞。
尽量实现updatestocks和getitems的并发。
————————————————————————-
Failure handling：
我们这个程序的容错机制要采用：fail-stop，即是说，网络分区这种状况不会出现， failure能被有效的检测出来。
我们对托管在单个数据中心中的组件的情况进行建模，并对服务进行配置，以便可以使用 网络超时 来暗示正在联系的组件发生 故障。换句话说就是， 组件overload了不能及时回复的情况，或者由于网络中断而导致组件无法访问的情况不会发生在我们的程序场景中。
由于在这里，对durability不做要求，failure就意味着，所有存在main memory里的数据都会丢失。
但是，我们的程序里的单个组件应该是 isolated（隔离的）， 其他组件在某些组件发生failure的时候仍然能正常的工作。这确保了Cart实例遵循了fail soft原则（换句话说， supermarket实例fails了，cart实例应该能够继续正常的回应如 getCartItems之类的查询工作，只是在add和checkout等需要调用supermarket的功能时候会抛出异常）。
—————————————————————–
data initialization
Cart和Supermarket的所有数据都存在main memory里。
我们需要根据自己的选择在constructors类里去generate和load 初始数据。
注意：这个初始值要合理，因为我们要用这些值来画图衡量性能。
第八页的这一段我没有太看懂：
You may assume that any configuration information is loaded once each component is initialized also at its constructor, e.g., naming information needed by Cart service instances to access the Supermarket instance. For simplicity, you can encode configuration information as constants in a separate configuration class
—————————————————————-
测试用例
要求写测试用例的关注点在测试before-and-after原子性上。
多写测试用例， 针对cart和supermarket service都要写。
————————————————————–
评估系统的可扩展性
可以参考我之前作业里的做法。
计算supermarket的troughput并且画图，
我的想法计算吞吐量可以是：（可能是错的）
Throughput = (number of success requests) / (total time)
同一时间，让几个client执行一些操作（并发的），可能失败也可能成功，计算成功的数量
total time 是从让这几个client开始执行操作到操作执行完返回失败或者成功的这段时间。
随着client数量的增加，执行操作的数量也会增加。
画个折线图，y轴是supermarket的throughput（算出来的）， x轴是client的数量。
代写计算机编程类/金融/高数/论文/英文
本网站支持淘宝 支付宝 微信支付 paypal等等交易。如果不放心可以用淘宝或者Upwork交易！
E-mail:850190831@qq.com 微信：BadGeniuscs 工作时间：无休息工作日-早上8点到凌晨3点
如果您用的手机请先保存二维码到手机里面，识别图中二维码。如果用电脑，直接掏出手机果断扫描。
