[go: up one dir, main page]

WO2010093084A1 - 분산 스페이스를 이용하여 분산 프로그래밍 환경을 제공하기 위한 방법, 시스템 및 컴퓨터 판독 가능한 기록 매체 - Google Patents

분산 스페이스를 이용하여 분산 프로그래밍 환경을 제공하기 위한 방법, 시스템 및 컴퓨터 판독 가능한 기록 매체 Download PDF

Info

Publication number
WO2010093084A1
WO2010093084A1 PCT/KR2009/002014 KR2009002014W WO2010093084A1 WO 2010093084 A1 WO2010093084 A1 WO 2010093084A1 KR 2009002014 W KR2009002014 W KR 2009002014W WO 2010093084 A1 WO2010093084 A1 WO 2010093084A1
Authority
WO
WIPO (PCT)
Prior art keywords
data
virtual space
application
distributed
node
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Ceased
Application number
PCT/KR2009/002014
Other languages
English (en)
French (fr)
Inventor
김우현
김두호
윤태일
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
NHN Corp
Original Assignee
NHN Corp
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by NHN Corp filed Critical NHN Corp
Priority to JP2011549050A priority Critical patent/JP5646511B2/ja
Priority to US13/201,098 priority patent/US8799619B2/en
Publication of WO2010093084A1 publication Critical patent/WO2010093084A1/ko
Anticipated expiration legal-status Critical
Ceased legal-status Critical Current

Links

Images

Classifications

    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F9/00—Arrangements for program control, e.g. control units
    • G06F9/06—Arrangements for program control, e.g. control units using stored programs, i.e. using an internal store of processing equipment to receive or retain programs
    • G06F9/46—Multiprogramming arrangements
    • G06F9/50—Allocation of resources, e.g. of the central processing unit [CPU]
    • G06F9/5005—Allocation of resources, e.g. of the central processing unit [CPU] to service a request
    • G06F9/5011—Allocation of resources, e.g. of the central processing unit [CPU] to service a request the resources being hardware resources other than CPUs, Servers and Terminals
    • G06F9/5016—Allocation of resources, e.g. of the central processing unit [CPU] to service a request the resources being hardware resources other than CPUs, Servers and Terminals the resource being the memory
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F9/00—Arrangements for program control, e.g. control units
    • G06F9/06—Arrangements for program control, e.g. control units using stored programs, i.e. using an internal store of processing equipment to receive or retain programs
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F12/00—Accessing, addressing or allocating within memory systems or architectures
    • G06F12/02—Addressing or allocation; Relocation
    • G06F12/08—Addressing or allocation; Relocation in hierarchically structured memory systems, e.g. virtual memory systems
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F12/00—Accessing, addressing or allocating within memory systems or architectures
    • G06F12/02—Addressing or allocation; Relocation
    • G06F12/08—Addressing or allocation; Relocation in hierarchically structured memory systems, e.g. virtual memory systems
    • G06F12/10—Address translation
    • G06F12/1027—Address translation using associative or pseudo-associative address translation means, e.g. translation look-aside buffer [TLB]
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F15/00—Digital computers in general; Data processing equipment in general
    • G06F15/16—Combinations of two or more digital computers each having at least an arithmetic unit, a program unit and a register, e.g. for a simultaneous processing of several programs
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L9/00—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols
    • H04L9/14—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols using a plurality of keys or algorithms

Definitions

  • the present invention relates to a method, a system and a computer readable recording medium for providing a distributed programming environment using distributed space. More specifically, the present invention provides a method, system and computer for enabling distributed programming by creating a distributed space accessible by multiple nodes or processes and allowing data to be shared through the distributed space. A readable recording medium.
  • SBA Space-Based Architecture
  • DHT Distributed Hash Table
  • P2P service Because it can provide fast lookup service while guaranteeing scalability and robustness of network by equal distribution of resources and structured topology.
  • the object of the present invention is to solve all the above-mentioned problems.
  • an effect of ensuring linear scalability of a distributed programming environment can be achieved.
  • access to data can be performed quickly under a distributed programming environment.
  • FIG. 1 is a view schematically showing the configuration of an entire system according to an embodiment of the present invention.
  • FIG. 2 is a diagram exemplarily illustrating a virtual space according to an embodiment of the present invention.
  • 3 through 4 illustrate two types of master-walker models according to an embodiment of the present invention.
  • 5 to 6 are diagrams exemplarily illustrating how a failover is performed according to an embodiment of the present invention.
  • FIG. 7 is a diagram exemplarily illustrating data exchange performed when a node is added under a 3-copy replication policy.
  • a method for processing data in a distributed environment comprising: creating a virtual space using resources provided by a plurality of nodes, and a first application reading data from the virtual space or Writing data to a virtual space, wherein the data is mapped to a specific location area on the virtual space that is determined according to an attribute of the data, and the first application reads or writes the data to the location area.
  • a method of performing a task is provided.
  • a system for processing data in a distributed environment comprising: a virtual space created using resources provided by a plurality of nodes, and reading data from or writing data to the virtual space And a first application, wherein the data is mapped to a specific location area on the virtual space determined according to the attribute of the data, and the first application performs a read operation or a write operation on the data in the location area.
  • FIG. 1 is a view schematically showing the configuration of an entire system according to an embodiment of the present invention.
  • the entire system includes a communication network 100, a cluster 200 constituting a distributed programming environment, and a plurality of applications performed based on a distributed programming environment. 300.
  • the communication network 100 may be configured regardless of communication modes such as wired and wireless, and may include a local area network (LAN), a metropolitan area network (MAN), and a wide area network (WAN). Network).
  • LAN local area network
  • MAN metropolitan area network
  • WAN wide area network
  • the cluster 200 is composed of a plurality of computers (hereinafter referred to as "nodes"), and resources such as computing devices, memory, etc. to the application 300 so that distributed programming can be performed. You can perform the function provided. That is, the cluster 200 according to an embodiment of the present invention provides an apparatus for allowing a plurality of applications 300 to share data or program codes, and provides specific data at the request of the application 300, The result of performing the operation requested by the application 300 may be returned to the application 300.
  • the application 300 may operate as if it is working with one computer. Can be.
  • each area of the integrated space may be mapped to at least one virtual space according to a request of the application 300, and a specific application 300 may be included in the virtual space.
  • the application 300 may be a program to perform distributed programming by using the cluster 200.
  • the application 300 may communicate with another application 300 by performing a task of reading data from or writing data to the virtual space, thereby enabling distributed programming. This may be done.
  • the application 300 is shown to be executed on another computer that is physically separated from the nodes constituting the cluster 200.
  • the application 300 may include the cluster 200. It may be a program running on a node included in the).
  • the application 300 is a generic term for a program designed to perform a predetermined task or to perform a predetermined task.
  • the application 300 is not only an application program but also includes a process, a thread, and the like. It should be understood as meaning.
  • the application 300 that wants to perform a specific task performs the task by storing data in the virtual space allocated to the application or using the stored data.
  • the data handled by the application 300 may be composed of a pair of (key, value).
  • the key may function as an index for the data
  • the value may be a value of the data.
  • the above data is stored in the virtual space according to a predetermined criterion, which will be described with reference to FIG. 2.
  • FIG. 2 is a diagram exemplarily illustrating a virtual space according to an embodiment of the present invention.
  • the virtual space is a combination of spaces provided by at least one virtual node 210 to 270, and it can be seen that it is represented as one large memory. Accordingly, the virtual nodes 210 to 270 may perform a function of a reference point for dividing an area of the virtual space into a plurality of sections.
  • the space provided by each virtual node is a specific resource (for example, existing on the nodes 200a to 200f where each virtual node (one of 210 to 270) is created).
  • Memory e.g, that a specific node (eg, 200a) creates a virtual node means that a resource (eg, a region of memory) of the node 200a is allocated to the corresponding virtual node.
  • each of the virtual nodes 210-270 shown in FIG. 2 may be generated by at least one node 200a-200f.
  • both virtual node F 260 and virtual node G 270 may be created by node 200a
  • virtual node F 260 may be generated by node 200a
  • virtual node G ( 270 may be generated by node 200b.
  • the stored data when data is stored in the virtual space, the stored data may be mapped to a specific area within the virtual space. More specifically, a predetermined hash function may be applied to a key of data and mapped in a virtual space. Referring to FIG. 2, when a hash function is applied using a key of specific data as a parameter, the data is mapped to an area 3107 of the virtual space.
  • each virtual node has information about a data area of the virtual space that each virtual node (one of 210 to 270) can take on an ID (hereinafter, In the form of a "space ID".
  • a space ID is assigned as the space ID in the case of the virtual node F 260
  • "3485” is assigned as the space ID in the case of the virtual node G 270.
  • Such a space ID can be used to distribute data in the virtual space to each virtual node. For example, in the case of the virtual node F 260 of FIG. 2, processing for data mapped into a virtual space area having a space ID of 2906 or more and less than 3485 of a space ID of the virtual node G 270 (for example, , read, write, take, etc.).
  • the space ID can be assigned in various ways. According to one embodiment of the invention, the space ID may be manually assigned by an operator managing a distributed programming environment, but may be automatically determined as the virtual space is created or the number of virtual nodes participating in the virtual space changes.
  • the space ID given to the virtual node is closely related to the area where data stored in the virtual space can be mapped, the space ID is assigned the same hash function as the hash function used to map the data into the virtual space. It may be determined using.
  • the parameters input to the hash function for determining the space ID include IP address information, communication port information, attribute information of the virtual space, name information of the virtual space, etc. of the node that created the virtual node. May be included.
  • a method of storing data in a virtual space is applied to an actual distributed programming environment, and it may be assumed that a large-scale work is divided into a plurality of segments and distributed to a plurality of applications. That is, a specific application may divide a large-scale job into a plurality of partial jobs capable of distributed processing and store them in a distributed space, thereby allowing the partial jobs to be distributed by a plurality of different applications.
  • data stored according to the above method may be looked up in the same manner by the application 300 to perform a read / take operation on the data. That is, when the application 300 wants to look up data having a specific key, a hash function is applied to the corresponding key to obtain a location in the virtual space, and the key is obtained from the virtual node in charge of processing the corresponding location area. It will be possible to obtain the data corresponding to.
  • the lookup for data stored in the virtual space may be performed in a manner that ensures locality. That is, the area of the virtual space that the application 300 can look up may be limited to a specific area within the virtual space. For example, the application 1 is allowed to look up only the area that the virtual node A 210 and the virtual node B 220 is responsible for, and the application 2 is the virtual node B 220 and the virtual node C 230. Only the lookup for the region is allowed, and the application 3 may allow only the lookup for the region in which the virtual node D 240 and the virtual node E 250 are in charge.
  • the data is processed.
  • the area of the virtual space that can be looked up by the application 300 can be limited to the area that is in charge of the virtual nodes generated from the node where the application 300 exists, and thus, the application 300 to which the data is allocated. Only network communication is required in the process of distributing the work, and network communication is unnecessary in the process of processing the distributed work by the application 300 that wants to process data, thereby reducing the load on the network in the distributed programming process. It can have the advantage that it is.
  • a specific application 300 can look up for two or more virtual nodes, there may be various criteria as to which virtual node should be prioritized. For example, a plurality of virtual nodes may be sequentially or arbitrarily selected. It is also possible to look up with a lookup, or assume that the lookup is given priority to the virtual node that stores the largest amount of data.
  • the guarantee of locality may be used not only for the data lookup process but also for the data storage process.
  • an application 300 for distributing a job may store the data only in a specific area allowed by the application.
  • the application 300 for processing the distributed work may be a method of looking up and processing data from an arbitrary virtual node.
  • the client-server model is a representative network programming model for distributed environments.
  • the client-server model according to an embodiment of the present invention can be easily implemented by allocating one virtual space and using a write-take function for different keys.
  • Table 1 exemplarily illustrates actual implementation code of the client-server model according to an embodiment of the present invention.
  • Table 1 Example of distributed program code in a client-server model
  • the master-worker model may be useful to support parallel processing to maintain load balance in a distributed environment. Therefore, the meaning of the master-walker model for performing parallel processing in a distributed environment is very large.
  • 3 through 4 illustrate two types of master-walker models according to an embodiment of the present invention.
  • the master-walker model according to an embodiment of the present invention can be executed in two ways.
  • One is a method of distributing work by performing a write-take operation between the master and workers using the same key as shown in FIG. 3, and the other is a master performing write operations with various keys as shown in FIG. 4. Workers perform the take operation only on the keys of the distributed space that they are allocated. In the former case, the workers are competitively assigned and processed by the master, and in the latter case, the master distributes the work evenly, and the workers process only the tasks assigned to them, ensuring locality.
  • Table 2 exemplarily shows actual implementation code of a master-walker model according to an embodiment of the present invention.
  • Table 2 Example of distributed program code in the master-worker model
  • the function of the scheduler may be added to the master-walker model as described above.
  • the scheduler can dynamically adjust the number of workers while monitoring the job's queuing time and processing time. In other words, when the number of tasks to be processed increases or the execution time of the task becomes longer, the processing performance of the entire task may be improved by allocating more workers to available nodes or virtual nodes.
  • the scatter-gather model is useful for distributing large amounts of data.
  • the scatter-gather model according to an embodiment of the present invention may have various advantages because it supports an on-the-fly method that can collect and process data immediately after distributing the data. This is like a pipeline for a distributed environment, which can be an excellent effect when you need to efficiently distribute large requests in real time.
  • the scatter-gather model may be a method in which a plurality of gathers are allocated and processed data input to the virtual space when a plurality of scatters are input to the virtual space.
  • the gather may be competitively assigned tasks using the same key, or may be guaranteed locality by processing only the tasks assigned to its own virtual space region.
  • Table 3 exemplarily shows actual implementation code of a scatter-gather model according to an embodiment of the present invention.
  • Table 3 Example of distributed program code for the scatter-gather model
  • the distributed programming environment may cope with a failure by a data replication method. This is because data stored in one node (here, node is used collectively as a physical node and a virtual node) is repeatedly stored in another node, so that even if a specific node fails, the data of the failed node can be recovered. That's how we do it.
  • 5 to 6 are diagrams exemplarily illustrating how a failover is performed according to an embodiment of the present invention. In the figure, it is assumed that data existing in one node is replicated to two other nodes so that a total of three copies are maintained.
  • FIG. 6 illustrates an operation of an application 300 to access data a when a failure occurs in node D. More specifically, the application 300 fails to look up for data a at node D. In this case, data a may be obtained by performing sequential lookups on nodes E and F which are subsequent nodes of node D. FIG. If the lookup for data a succeeds at node E, the lookup at node F may be omitted.
  • FIG. 7 is a diagram exemplarily illustrating data exchange performed when a node is added under a 3-copy replication policy.
  • FIG. 7 is assuming that a node F is added between node E and node G in a virtual space consisting of nodes A, B, C, D, E, and G.
  • FIG. 7 is assuming that a node F is added between node E and node G in a virtual space consisting of nodes A, B, C, D, E, and G.
  • predecessor (space id ) passes the space id the data that the space id is to replicate.
  • the predecessor passes the data to the space id for the space id to replicate.
  • Such a process may be similarly implemented even when a particular node is excluded from the virtual space.
  • the distributed programming environment according to an embodiment of the present invention may be used for a merge sort operation for sorting a large amount of data.
  • a merge sort operation on a large amount of data in a distributed programming environment distributes the data to be merged to n nodes so that a partial sort is performed on each piece of data at each node, and then n sorted
  • the process of generating a new data fragment by merging some of the data fragments according to the sorting criteria is performed by repeatedly performing all data fragments until they are merged into one data. In this case, as the number of times that the merge is repeated increases, the number of movements between nodes of the data fragments increases, so that the load on the network increases and the processing capacity decreases.
  • merge sorting may be performed with the above problem minimized.
  • the detailed process is as follows.
  • data to be merged and sorted is distributed to n processes so that each node stores the data to be sorted in a distributed space using a predetermined hash function.
  • the stored data may be mapped to a predetermined area in the distributed space according to the sorting criteria. For example, if the data to be sorted consists of a natural number of 1,000 or less, and the virtual space consists of 10 virtual nodes, the data between 1 and 100 may be converted to virtual node 1 by having the hash function include a modular operation. It may be mapped to the region of, the data between 101 ⁇ 200 is mapped to the region of the virtual node 2, the data between 901 ⁇ 1,000 may be mapped to the region of the virtual node 10.
  • merging sorting can be completed by sequentially merging data stored in the area of virtual node 1 to data stored in the area of virtual node 10. .
  • the network load can be reduced, and the repetitive merging process is omitted, and thus the processing capacity is improved.
  • the data may be mapped onto the virtual space biased according to the characteristics of the data.
  • the data to be sorted is composed of only a few numbers, the data may be concentrated in a specific virtual node, thereby reducing the efficiency of distributed programming.
  • the merge sort operation described above will be described in detail.
  • the number of data having a value between 1 and 300 If it is estimated that it occupies about 10 percent, some of the virtual nodes can be adjusted by adjusting the hash function to store data between 1 and 300 in virtual node 1's area, or by increasing the area in virtual space that virtual node 1 is responsible for. This can prevent data from biasing.
  • the distributed programming environment according to an embodiment of the present invention may be applied to a model for reusing legacy code. More specifically, most of the source code is at least partially dependent on the platform of the system. When the platform of the system is upgraded or changed, modification of the existing source code is inevitably required.
  • the effect of reusing the legacy code can be achieved by inputting and outputting data processed by the legacy code through the distributed space. More specifically, even when the platform of the system is changed, the format of the data stored in the distributed space may be kept constant so that the data processing result by the legacy code may be applied even under the changed platform.
  • Embodiments according to the present invention described above can be implemented in the form of program instructions that can be executed by various computer components and recorded on a computer-readable recording medium.
  • the computer-readable recording medium may include program instructions, data files, data structures, etc. alone or in combination.
  • Program instructions recorded on the computer-readable recording medium may be those specially designed and configured for the present invention, or may be known and available to those skilled in the computer software arts.
  • Examples of computer readable recording media include magnetic media such as hard disks, floppy disks and magnetic tape, optical recording media such as CD-ROMs, DVDs, and magneto-optical media such as floptical disks. media), and hardware devices specifically configured to store and execute program instructions, such as ROM, RAM, flash memory, and the like.
  • Examples of program instructions include not only machine code generated by a compiler, but also high-level language code that can be executed by a computer using an interpreter or the like.
  • the hardware device may be configured to operate as one or more software modules to perform the process according to the invention, and vice versa.

Landscapes

  • Engineering & Computer Science (AREA)
  • Theoretical Computer Science (AREA)
  • Software Systems (AREA)
  • Physics & Mathematics (AREA)
  • General Engineering & Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Computer Hardware Design (AREA)
  • Computer Security & Cryptography (AREA)
  • Computer Networks & Wireless Communication (AREA)
  • Signal Processing (AREA)
  • Information Retrieval, Db Structures And Fs Structures Therefor (AREA)

Abstract

본 발명은 분산 스페이스를 이용하여 분산 프로그래밍 환경을 제공하기 위한 방법, 시스템 및 컴퓨터 판독 가능한 기록 매체에 관한 것이다. 본 발명의 일 태양에 따르면, 분산 환경에서 데이터를 처리하기 위한 방법으로서, 다수의 노드가 제공하는 자원을 이용하여 가상 스페이스를 생성하는 단계, 및 제1 어플리케이션이 상기 가상 스페이스로부터 데이터를 읽거나 상기 가상 스페이스에 데이터를 쓰는 단계를 포함하고, 상기 데이터는 상기 데이터의 속성에 따라 결정되는 상기 가상 스페이스 상의 특정 위치 영역에 맵핑되고, 상기 제1 어플리케이션은 상기 위치 영역에 상기 데이터에 대한 읽기 작업 또는 쓰기 작업을 수행하는 방법이 제공된다.

Description

분산 스페이스를 이용하여 분산 프로그래밍 환경을 제공하기 위한 방법, 시스템 및 컴퓨터 판독 가능한 기록 매체
본 발명은 분산 스페이스를 이용하여 분산 프로그래밍 환경을 제공하기 위한 방법, 시스템 및 컴퓨터 판독 가능한 기록 매체에 관한 것이다. 보다 상세하게는, 본 발명은 다수의 노드 또는 프로세스(process)가 접근할 수 있는 분산 스페이스를 생성하고, 상기 분산 스페이스를 통하여 데이터가 공유될 수 있도록 함으로써 분산 프로그래밍이 가능하도록 하는 방법, 시스템 및 컴퓨터 판독 가능한 기록 매체에 관한 것이다.
네트워크 통신 기술의 발전으로 인하여 원격 컴퓨터들 간에 대용량 데이터의 전송이 용이하게 되었고, 이에 따라, 다수의 컴퓨터가 협력하여 하나의 작업을 처리하는 분산 프로그래밍(또는 컴퓨팅) 기술이 점차 보편화되어 가고 있다.
이와 같은 분산 프로그래밍 환경을 구축하기 위한 주요 기술로서 SBA(Space-Based Architecture)를 들 수 있다. SBA는 튜플 스페이스(tuple space)를 이용하여 상태 기반의(stateful) 고성능 어플리케이션들의 선형 확장성(scalability)을 달성하기 위한 소프트웨어 구조 패턴으로서, 예일 대학의 David Gelernter에 의해 제안된 린다(Linda)의 튜플 스페이스 개념으로부터 출발한다. SBA에 따르면, 모든 분산 프로세스들은 스페이스를 기반으로 하여 상호 통신과 자원 공유를 수행하기 때문에 서로에 대한 자세한 정보를 알 필요가 없고, 시간과 공간의 제약 없이 단순한 인터페이스만으로도 다양한 방식의 분산 프로그래밍이 가능하게 된다는 장점을 가진다.
최근 DHT(Distributed Hash Table)라는 비중앙집권형 분산 시스템 이 주목 받고 있는데, DHT는 해쉬 테이블(hash table)과 유사한 룩업(lookup) 서비스를 제공하는 특징을 가지고 있다. DHT는 자원의 균등한 분산과 구조화된 토폴로지(topology)에 의해 네트워크의 확장성과 강건함(robustness)을 보장하면서도, 빠른 룩업 서비스를 제공할 수 있기 때문에 P2P 서비스와 같은 다양한 분야에서 활용되고 있다.
이러한 DHT의 기술적 우위에도 불구하고, 분산 환경에서 대규모 계산 문제에 관하여 이를 적용한 사례를 찾기는 쉽지 않은 것이 사실이다. 이에 따라, SBA와 DHT의 장점을 모두 포괄하는 새로운 분산 프로그래밍 환경에 대한 필요성이 대두되고 있다.
본 발명은 상술한 문제점을 모두 해결하는 것을 그 목적으로 한다.
또한, 본 발명은 작업의 분배를 통해 분산 처리의 효율성을 증대시키되, 분산 프로그래밍 환경의 선형적 확장성을 보장하는 것을 다른 목적으로 한다.
또한, 본 발명은 구조화된 토폴로지를 기반으로 하여 데이터에 대한 접근이 빠르게 수행될 수 있도록 하는 것을 또 다른 목적으로 한다.
본 발명에 의하면, 대규모의 계산 문제를 다수의 컴퓨터를 이용하여 분산 처리함으로써 작업의 효율성을 증대시킬 수 있다.
본 발명에 의하면, 분산 프로그래밍 환경의 선형적 확장성이 보장되는 효과를 달성할 수 있다.
본 발명에 의하면, 분산 프로그래밍 환경 하에서 데이터에 대한 접근이 빠르게 수행되도록 할 수 있다.
도 1은 본 발명의 일 실시예에 따른 전체 시스템의 구성을 개략적으로 나타내는 도면이다.
도 2는 본 발명의 일 실시예에 따른 가상 스페이스를 예시적으로 나타내는 도면이다.
도 3 내지 도 4는 본 발명의 일 실시예에 따른 두 가지 방식의 마스터-워커 모델을 도시하고 있다.
도 5 내지 도 6은 본 발명의 일 실시예에 따라 장애 조치가 수행되는 모습을 예시적으로 나타내는 도면이다.
도 7은 3-copy 리플리케이션 정책 하에서 노드가 추가된 경우 수행되는 데이터 교환을 예시적으로 나타내는 도면이다.
<주요 도면부호에 관한 간단한 설명>
100: 통신망
200: 클러스터
200a~200f: 노드
210~270: 가상노드
300: 어플리케이션
상기 목적을 달성하기 위한 본 발명의 대표적인 구성은 다음과 같다.
본 발명의 일 태양에 따르면, 분산 환경에서 데이터를 처리하기 위한 방법으로서, 다수의 노드가 제공하는 자원을 이용하여 가상 스페이스를 생성하는 단계, 및 제1 어플리케이션이 상기 가상 스페이스로부터 데이터를 읽거나 상기 가상 스페이스에 데이터를 쓰는 단계를 포함하고, 상기 데이터는 상기 데이터의 속성에 따라 결정되는 상기 가상 스페이스 상의 특정 위치 영역에 맵핑되고, 상기 제1 어플리케이션은 상기 위치 영역에 상기 데이터에 대한 읽기 작업 또는 쓰기 작업을 수행하는 방법이 제공된다.
본 발명의 다른 태양에 따르면, 분산 환경에서 데이터를 처리하기 위한 시스템으로서, 다수의 노드가 제공하는 자원을 이용하여 생성되는 가상 스페이스, 및 상기 가상 스페이스로부터 데이터를 읽거나 상기 가상 스페이스에 데이터를 쓰는 제1 어플리케이션을 포함하고, 상기 데이터는 상기 데이터의 속성에 따라 결정되는 상기 가상 스페이스 상의 특정 위치 영역에 맵핑되고, 상기 제1 어플리케이션은 상기 위치 영역에 상기 데이터에 대한 읽기 작업 또는 쓰기 작업을 수행하는 시스템이 제공된다.
이 외에도, 본 발명을 구현하기 위한 다른 방법, 시스템 및 상기 방법을 실행하기 위한 컴퓨터 프로그램을 기록하기 위한 컴퓨터 판독 가능한 기록 매체가 더 제공된다.
후술하는 본 발명에 대한 상세한 설명은, 본 발명이 실시될 수 있는 특정 실시예를 예시로서 도시하는 첨부 도면을 참조한다. 이들 실시예는 당업자가 본 발명을 실시할 수 있기에 충분하도록 상세히 설명된다. 본 발명의 다양한 실시예는 서로 다르지만 상호 배타적일 필요는 없음이 이해되어야 한다. 예를 들어, 여기에 기재되어 있는 특정 형상, 구조 및 특성은 일 실시예에 관련하여 본 발명의 정신 및 범위를 벗어나지 않으면서 다른 실시예로 구현될 수 있다. 또한, 각각의 개시된 실시예 내의 개별 구성요소의 위치 또는 배치는 본 발명의 정신 및 범위를 벗어나지 않으면서 변경될 수 있음이 이해되어야 한다. 따라서, 후술하는 상세한 설명은 한정적인 의미로서 취하려는 것이 아니며, 본 발명의 범위는, 적절하게 설명된다면, 그 청구항들이 주장하는 것과 균등한 모든 범위와 더불어 첨부된 청구항에 의해서만 한정된다. 도면에서 유사한 참조부호는 여러 측면에 걸쳐서 동일하거나 유사한 기능을 지칭한다.
이하에서는, 본 발명이 속하는 기술분야에서 통상의 지식을 가진 자가 본 발명을 용이하게 실시할 수 있도록 하기 위하여, 본 발명의 바람직한 실시예들에 관하여 첨부된 도면을 참조하여 상세히 설명하기로 한다.
[본 발명의 바람직한 실시예]
전체 시스템의 구성
도 1은 본 발명의 일 실시예에 따른 전체 시스템의 구성을 개략적으로 나타내는 도면이다.
도 1에 도시되어 있는 바와 같이, 본 발명의 일 실시예에 따른 전체 시스템은, 통신망(100), 분산 프로그래밍 환경을 구성하는 클러스터(200), 및 분산 프로그래밍 환경을 기반으로 하여 수행되는 다수의 어플리케이션(300)으로 구성될 수 있다.
먼저, 통신망(100)은 유선 및 무선과 같은 그 통신 양태를 가리지 않고 구성될 수 있으며, 근거리 통신망(LAN; Local Area Network), 도시권 통신망(MAN; Metropolitan Area Network), 광역 통신망(WAN; Wide Area Network) 등 다양한 통신망으로 구성될 수 있다.
본 발명의 일 실시예에 따르면, 클러스터(200)는 다수의 컴퓨터(이하, "노드"라고 칭함)로 구성되고, 분산 프로그래밍이 수행될 수 있도록 연산 장치, 메모리 등과 같은 자원을 어플리케이션(300)에 제공하는 기능을 수행할 수 있다. 즉, 본 발명의 일 실시예에 따른 클러스터(200)는 다수의 어플리케이션(300)이 데이터 또는 프로그램 코드를 공유할 수 있도록 장치를 제공하고, 어플리케이션(300)의 요청에 따라 특정 데이터를 제공하거나, 어플리케이션(300)이 요청한 작업을 수행한 결과를 어플리케이션(300)에 반환할 수 있다.
또한, 본 발명의 일 실시예에 따르면, 다수의 노드로 구성된 클러스터(200)가 제공하는 자원은 하나의 통합 스페이스를 형성하므로, 어플리케이션(300)은 마치 하나의 컴퓨터와 작업을 수행하는 것처럼 동작할 수 있다.
또한, 본 발명의 일 실시예에 따르면, 상기 통합 스페이스의 각 영역은 어플리케이션(300)의 요청에 따라 적어도 하나의 가상 스페이스(virtual space)에 맵핑될 수 있고, 상기 가상 스페이스에는 특정 어플리케이션(300)들만이 접근할 수 있도록 함으로써, 공통된 작업을 수행하고자 하는 다수의 어플리케이션(300) 간에 통신이나 데이터 공유가 가능하도록 하고, 서로 독립된 어플리케이션(300)들 간의 간섭이 배제되도록 할 수 있다.
본 발명의 일 실시예에 따르면, 어플리케이션(300)은 클러스터(200)를 이용하여 분산 프로그래밍 작업을 수행하고자 하는 프로그램일 수 있다.
본 발명의 일 실시예에 따르면, 어플리케이션(300)은 가상 스페이스로부터 데이터를 읽는 작업을 수행하거나 가상 스페이스에 데이터를 쓰는 작업을 수행함으로써, 다른 어플리케이션(300)과 통신할 수도 있고, 이를 통해 분산 프로그래밍이 수행될 수도 있다.
한편, 도 1에서 어플리케이션(300)은 클러스터(200)를 구성하는 노드와 물리적으로 분리된 다른 컴퓨터 상에서 실행되는 것처럼 도시되어 있지만, 본 발명의 다른 실시예에 따르면, 어플리케이션(300)은 클러스터(200) 내에 포함된 노드 상에서 동작하는 프로그램일 수 있다. 또한, 본 발명에 있어서 어플리케이션(300)이란 소정의 작업을 수행하거나 소정 작업의 수행을 돕기 위하여 설계된 프로그램을 통칭하는 것으로서, 응용 프로그램만이 아니라, 프로세스, 쓰레드(thread) 등을 포괄하는 최광의의 의미로 이해되어야 할 것이다.
데이터의 저장 및 이용
본 발명의 일 실시예에 따르면, 특정 작업을 수행하고자 하는 어플리케이션(300)은 해당 어플리케이션에 할당된 가상 스페이스에 데이터를 저장하거나 저장된 데이터를 이용함으로써 해당 작업을 수행하게 된다. 보다 구체적으로는, 어플리케이션(300)에 의해 다루어지는 데이터는 (key, value)의 쌍으로 구성될 수 있다. 여기서, key는 데이터에 대한 인덱스로서 기능할 수 있고, value는 데이터의 값일 수 있다.
본 발명의 일 실시예에 따르면, 상기와 같은 데이터는 소정의 기준에 따라 가상 스페이스 내에 저장되는데, 그 구체적인 태양을 도 2를 참조하여 설명하면 다음과 같다.
도 2는 본 발명의 일 실시예에 따른 가상 스페이스를 예시적으로 나타내는 도면이다.
도 2를 참조하면, 가상 스페이스는 적어도 하나의 가상 노드(210~270)가 제공하는 스페이스들이 통합된 것으로서, 마치 하나의 거대 메모리와 같이 표현된 것을 알 수 있다. 따라서, 가상 노드(210~270)는 가상 스페이스의 영역을 다수의 섹션으로 구분 짓는 기준점의 기능을 수행할 수 있다. 또한, 각각의 가상 노드(210~270 중 하나)가 제공하는 스페이스는 각각의 가상 노드(210~270 중 하나)가 생성되어 있는 노드(200a~200f) 상에 존재하는 특정 자원(예를 들면, 메모리)에 맵핑될 수 있다. 여기서, 특정 노드(예를 들면, 200a)가 가상 노드를 생성한다는 것은 상기 노드(200a)의 자원(예를 들면, 메모리의 일 영역)이 해당 가상 노드에 할당되는 것을 의미한다.
본 발명의 일 실시예에 따르면, 도 2에 도시된 각각의 가상 노드(210~270 중 하나)는 적어도 하나의 노드(200a~200f)에 의해 생성될 수 있다. 예를 들면, 가상 노드 F(260)와 가상 노드 G(270)가 모두 노드(200a)에 의해 생성될 수도 있고, 가상 노드 F(260)는 노드(200a)에 의해 생성되고, 가상 노드 G(270)는 노드(200b)에 의해 생성될 수도 있다.
본 발명의 일 실시예에 따르면, 가상 스페이스에 데이터가 저장되는 경우, 저장된 데이터는 가상 스페이스 내의 특정 영역에 맵핑될 수 있다. 보다 구체적으로는, 데이터의 key에 소정의 해쉬 함수를 적용하여 가상 스페이스 내에 맵핑시킬 수 있을 것이다. 도 2를 참조하면, 특정 데이터의 key를 파라미터로 하여 해쉬 함수를 적용하면, 상기 데이터가 가상 스페이스의 3107 영역에 맵핑되는 것을 볼 수 있다.
본 발명의 일 실시예에 따르면, 각각의 가상 노드(210~270 중 하나)에는 각각의 가상 노드(210~270 중 하나)가 담당할 수 있는 가상 스페이스의 데이터 영역에 관한 정보가 ID(이하, "스페이스 ID"라고 함)의 형태로 부여되어 있을 수 있다. 도 2를 참조하면, 가상 노드 F(260)의 경우 스페이스 ID로서 "2906"이 부여되어 있고, 가상 노드 G(270)의 경우 스페이스 ID로서 "3485"가 부여되어 있는 것을 확인할 수 있다. 이와 같은 스페이스 ID를 이용하여 가상 스페이스 내의 데이터를 각각의 가상 노드에 분배할 수 있다. 예를 들면, 도 2의 가상 노드 F(260)의 경우, 자신의 스페이스 ID인 2906 이상이고 가상 노드 G(270)의 스페이스 ID인 3485 미만인 가상 스페이스 영역 내로 맵핑되는 데이터에 대한 처리(예를 들면, read, write, take 등)를 담당할 수 있을 것이다.
위와 같은 스페이스 ID는 다양한 방식으로 부여될 수 있다. 본 발명의 일 실시예에 따르면, 스페이스 ID는 분산 프로그래밍 환경을 관리하는 운영자에 의하여 수동으로 부여될 수도 있지만, 가상 스페이스가 생성되거나 가상 스페이스에 참여하는 가상 노드의 수가 변경됨에 따라 자동적으로 결정되도록 할 수도 있을 것이다.
보다 구체적으로는, 가상 노드에 부여되는 스페이스 ID는 가상 스페이스에 저장되는 데이터가 맵핑될 수 있는 영역과 밀접하게 관련되어 있으므로, 데이터를 가상 스페이스 내에 맵핑시키는 데에 이용되는 해쉬 함수와 동일한 해쉬 함수를 이용하여 결정될 수 있을 것이다. 본 발명의 일 실시예에 따르면, 스페이스 ID의 결정을 위하여 해쉬 함수에 입력되는 파라미터에는 가상 노드를 생성한 노드의 IP 주소 정보, 통신 포트 정보, 가상 스페이스의 속성 정보, 가상 스페이스의 명칭 정보 등이 포함될 수 있다.
상기와 같이 가상 스페이스에 데이터를 저장하는 방식이 실제 분산 프로그래밍 환경에 적용된 모습의 일 예로서, 대규모 작업이 다수의 세그먼트로 분할되어 다수의 어플리케이션에게 분배되는 경우를 상정할 수 있다. 즉, 특정 어플리케이션이 대규모 작업을 분산 처리가 가능한 다수의 부분 작업으로 분할하여 이를 분산 스페이스에 저장함으로써, 상기 부분 작업들이 다수의 다른 어플리케이션에 의해 분산 처리되도록 할 수 있다.
본 발명의 일 실시예에 따르면, 상기와 같은 방법에 따라 저장되는 데이터는 해당 데이터에 대한 read/take 작업을 수행하고자 하는 어플리케이션(300)에 의해 동일한 방식으로 룩업될 수 있다. 즉, 어플리케이션(300)이 특정 key를 가지는 데이터를 룩업하고자 하는 경우, 해당 key에 해쉬 함수를 적용하여 가상 스페이스 내에서의 위치를 획득하고, 해당 위치 영역에 대한 처리를 담당하는 가상 노드로부터 상기 key에 대응되는 데이터를 획득할 수 있을 것이다.
본 발명의 다른 실시예에 따르면, 가상 스페이스에 저장된 데이터에 대한 룩업은 지역성이 보장되는 방식으로 수행될 수 있다. 즉, 어플리케이션(300)이 룩업할 수 있는 가상 스페이스의 영역을 가상 스페이스 내의 특정 영역으로 제한할 수 있다. 예를 들면, 어플리케이션1에게는 가상 노드 A(210) 및 가상 노드 B(220)가 담당하는 영역에 대한 룩업만을 허용하고, 어플리케이션2에게는 가상 노드 B(220) 및 가상 노드 C(230)가 담당하는 영역에 대한 룩업만을 허용하며, 어플리케이션3에게는 가상 노드 D(240) 및 가상 노드 E(250)가 담당하는 영역에 대한 룩업만을 허용할 수 있다. 이때, 가상 스페이스에 저장되는 데이터를 미리 샘플링하여 데이터의 특성을 파악함으로써 데이터가 가상 스페이스 상에서 고르게 분포됨에 따라 분산 프로그래밍이 보다 효율적으로 수행되도록 할 수 있다. 이는, 데이터 처리의 지역성이 보장되는 마스터-워커 모델이나 스캐터-개더 모델에서 더욱 중요할 수 있는데, 데이터 처리 모델에 관한 구체적인 내용은 후술하기로 한다.
본 발명의 일 실시예에 따르면, 가상 스페이스를 이용하는 다수의 어플리케이션(300)이 가상 스페이스에 참여하는 노드(200a~200f) 상에 존재하는 경우에 상기와 같은 방식을 채택하게 되면, 데이터를 처리하고자 하는 어플리케이션(300)이 룩업할 수 있는 가상 스페이스의 영역을 해당 어플리케이션(300)이 존재하는 노드로부터 생성된 가상 노드들이 담당하는 영역으로 한정할 수 있고, 따라서, 데이터를 할당하는 어플리케이션(300)에 의해 작업이 분산되는 과정에만 네트워크 통신이 요구될 뿐, 데이터를 처리하고자 하는 어플리케이션(300)이 분산된 작업을 처리하는 과정에는 네트워크 통신이 불필요하게 되므로, 분산 프로그래밍 과정에서 네트워크에 걸리는 부하를 줄일 수 있다는 장점을 가질 수 있다.
이때, 특정 어플리케이션(300)이 2개 이상의 가상 노드에 대하여 룩업할 수 있는 경우, 어느 가상 노드가 우선시되어야 하는지에 대하여는 다양한 기준이 있을 수 있는데, 예를 들면, 복수의 가상 노드를 순차적으로 또는 임의적으로 룩업할 수도 있고, 가장 큰 용량의 데이터가 저장된 가상 노드를 우선하여 룩업하는 경우도 상정할 수 있을 것이다.
또한, 상기와 같은 지역성의 보장은 데이터의 룩업 과정뿐만 아니라, 데이터의 저장 과정에도 이용될 수 있는데, 예를 들면, 작업을 분산시키는 어플리케이션(300)이 자신에게 허용된 특정 영역에만 데이터를 저장하고, 분산된 작업을 처리하는 어플리케이션(300)은 임의의 가상 노드로부터 데이터를 룩업하여 처리하는 방식도 가능할 것이다.
이하에서는, 본 발명의 일 실시예에 따른 가상 스페이스를 이용하여 작성되는 실제의 분산 프로그래밍 코드의 예를 살펴봄으로써, 본 발명을 보다 구체적으로 살펴보기로 한다.
1. 클라이언트-서버 모델
클라이언트(client)-서버(server) 모델은 분산 환경을 위한 대표적인 네트워크 프로그래밍 모델이다. 본 발명의 일 실시예에 따른 클라이언트-서버 모델은 하나의 가상 스페이스를 할당 받고 서로 다른 key를 대상으로 write-take 함수를 사용함으로써 쉽게 구현할 수 있다.
표 1은 본 발명의 일 실시예에 따른 클라이언트-서버 모델의 실제 구현 코드를 예시적으로 나타내고 있다.
Figure PCTKR2009002014-appb-I000001
<표 1: 클라이언트-서버 모델의 분산 프로그램 코드의 예>
표 1의 프로그램 코드를 살펴보면, 네트워크 관련 이슈들(socket, thread, process, signal, pipe 등)은 분산 스페이스 클래스(상기 코드에 따르면 "Coord" 클래스)에 감추고, 사용자는 단지 write 메쏘드(method) 또는 take 메쏘드 등을 이용하여 분산 스페이스에 접근 가능하도록 함으로써 사용자가 자신의 개발 목적과 의도에만 집중할 수 있도록 투명한 분산 환경을 지원한다. 따라서, 사용자는 클라이언트-서버 모델을 개발하기 위한 별도의 네트워크 관련 프로그래밍에 대하여 숙지할 필요가 없게 된다는 장점이 있다.
2. 마스터-워커 모델
마스터(master)-워커(worker) 모델은 분산 환경에서 로드 밸런스(load balance)를 유지하는 병렬 처리(parallel processing)를 지원하기 위하여 유용하게 활용될 수 있다. 따라서, 분산 환경에서 병렬 처리를 수행하기 위하여 마스터-워커 모델이 가지는 의미는 매우 크다고 할 수 있다.
도 3 내지 도 4는 본 발명의 일 실시예에 따른 두 가지 방식의 마스터-워커 모델을 도시하고 있다.
도 3 내지 도 4를 참조하면, 본 발명의 일 실시예에 따른 마스터-워커 모델은 크게 두 가지 방식으로 실행될 수 있음을 알 수 있다. 하나는 도 3에 나타난 바와 같이 마스터와 워커들 사이에서 동일 key를 사용하여 write-take 작업을 수행함으로써 작업을 분배하는 방식이고, 다른 하나는 도 4에 나타난 바와 같이 마스터가 다양한 key로 write 작업을 수행하고 워커들은 자신이 할당 받은 분산 스페이스 영역의 key에 관해서만 take 작업을 수행하는 방식이다. 전자의 경우에는 워커들이 마스터의 작업을 경쟁적으로 할당 받아 처리하고, 후자의 경우에는 마스터가 작업을 균등하게 분산시키면, 워커들은 자신에게 할당된 작업만 지역성을 보장하면서 처리하게 된다.
표 2는 본 발명의 일 실시예에 따른 마스터-워커 모델의 실제 구현 코드를 예시적으로 나타내고 있다.
Figure PCTKR2009002014-appb-I000002
<표 2: 마스터-워커 모델의 분산 프로그램 코드의 예>
표 2의 프로그램 코드를 살펴보면, 마스터와 워커가 "job"이라는 공통된 key를 사용하여 write-take 작업을 수행함으로써 작업이 분배되는 것을 확인할 수 있다. 상기와 같은 마스터-워커 모델의 장점은 마스터의 경우 워커들이 어디에 위치해 있고 얼마나 많은지를 인식할 필요가 없다는 사실이다. 마스터는 단지 자신이 해결하고자 하는 작업을 분산 스페이스에 입력하는 것으로 충분하며, 워커들은 작업이 할당되는 것을 대기하고 있다가 할당된 작업을 수행하기만 하면 된다.
본 발명의 일 실시예에 따르면, 상기와 같은 마스터-워커 모델에 스케쥴러의 기능을 추가할 수 있다. 스케쥴러는 작업의 큐잉 타임(queuing time)과 프로세싱 타임(processing time)을 모니터링하면서 워커의 개수를 동적으로 조절할 수 있다. 즉, 처리할 작업이 증가하거나 작업의 수행 시간이 길어지면 사용 가능한 노드 또는 가상 노드에 워커를 더 할당함으로써 전체 작업의 처리 성능을 향상시킬 수 있다.
3. 스캐터-개더 모델
스캐터(scatter)-개더(gather) 모델은 대용량 데이터를 분산 처리할 때에 유용하게 사용된다. 본 발명의 일 실시예에 따른 스캐터-개더 모델은 데이터를 분산하는 즉시 데이터를 수집 처리할 수 있는 on-the-fly 방식을 지원하므로 다양한 장점을 가질 수 있다. 이는 분산 환경을 위한 pipeline과 같은 것으로 실시간으로 대량의 리퀘스트(request)를 효율적으로 분산 처리해야 하는 경우에 탁월한 효과를 가질 수 있다.
본 발명의 일 실시예에 따르면, 스캐터-개더 모델은 다수의 스캐터가 처리될 작업을 가상 스페이스에 입력하면, 다수의 개더가 가상 스페이스에 입력된 데이터를 할당 받아 처리하는 방식일 수 있다. 이때, 앞서 클라이언트-마스터 모델에서 설명한 바와 같이, 개더는 동일한 key를 이용하여 경쟁적으로 작업을 할당 받을 수도 있고, 자신만의 가상 스페이스 영역에 할당된 작업만을 처리함으로써 지역성을 보장 받을 수도 있을 것이다.
표 3은 본 발명의 일 실시예에 따른 스캐터-개더 모델의 실제 구현 코드를 예시적으로 나타내고 있다.
Figure PCTKR2009002014-appb-I000003
<표 3: 스캐터-개더 모델의 분산 프로그램 코드의 예>
표 3의 프로그램 코드를 살펴보면, 스캐터가 get_kv() 메쏘드를 이용하여 임의의 key를 생성하여 데이터를 가상 스페이스에 입력하면, 개더는 입력된 데이터의 key를 구별하지 않고, 자신에게 할당된 영역에 입력된 데이터에 대하여 작업을 수행하는 것을 확인할 수 있다. 상기와 같은 스캐터-개더 모델의 장점은 스캐터에서 단순히 (key, value) 쌍으로 데이터를 입력하면, 가상 스페이스로 데이터가 고르게 분산되고, 개더는 자기 자신에게 할당된 데이터만 처리하는 방식으로 지역성이 보장되기 때문에 성능 향상에 도움이 될 수 있다는 점이다. 뿐만 아니라 on-the-fly 방식으로 데이터를 분산하고 수집하여 처리하기 때문에 분산 처리의 효율성이 높아진다는 장점도 있다.
장애 조치
본 발명의 일 실시예에 따른 분산 프로그래밍 환경은 데이터 리플리케이션(data replication) 방식으로 장애에 대처할 수 있다. 이는, 하나의 노드(여기서, 노드는 물리적 노드와 가상 노드를 통칭하는 의미로 사용됨)에 저장되는 데이터를 다른 노드에 중복하여 저장함으로써, 특정 노드에 장애가 발생하는 경우에도 장애가 발생한 노드의 데이터를 복구할 수 있도록 하는 방식이다.
도 5 내지 도 6은 본 발명의 일 실시예에 따라 장애 조치가 수행되는 모습을 예시적으로 나타내는 도면이다. 상기 도면에서는 하나의 노드에 존재하는 데이터가 다른 2개의 노드에 복제되어 총 3개의 카피(3-copy)가 유지되는 상황을 가정하였다.
도 5를 참조하면, 특정 어플리케이션(300)에 의해 입력된 데이터 a가 노드 D에 맵핑되어 저장되는 경우, 노드 D에 저장되는 데이터 a는 노드 D의 후속 노드인 노드 E 및 노드 F에 복제되어 저장될 수 있다.
한편, 도 6은 노드 D에 장애가 발생한 경우 데이터 a에 접근하고자 하는 어플리케이션(300)의 동작에 관하여 도시하고 있는데, 보다 구체적으로는, 어플리케이션(300)은 노드 D에서 데이터 a에 대한 룩업에 실패하는 경우, 노드 D의 후속 노드인 노드 E 및 노드 F에 대하여 순차적인 룩업을 수행함으로써 데이터 a를 획득할 수 있다. 만약 노드 E에서 데이터 a에 대한 룩업이 성공하는 경우, 노드 F에서의 룩업은 생략될 수 있을 것이다.
상기와 같은 n-copy 리플리케이션 정책이 가상 스페이스에 노드가 추가되거나 제외되는 경우에도 유지될 수 있도록 하기 위해서는, 가상 스페이스에 노드가 추가되거나 삭제되는 시점에 데이터의 교환이 수행되어야 한다.
도 7은 3-copy 리플리케이션 정책 하에서 노드가 추가된 경우 수행되는 데이터 교환을 예시적으로 나타내는 도면이다. 도 7은 노드 A, B, C, D, E 및 G로 구성된 가상 스페이스에서 노드 E와 노드 G 사이에 노드 F가 추가된 상황을 가정하여 도시되었다.
도 7에 도시된 상황에서, 3-copy 리플리케이션 정책을 유지하기 위하여는, 노드 D 및 노드 E의 데이터가 새로이 추가된 노드 F에 복제되어야 하고, 기존에 노드 G가 담당하던 데이터 역시 노드 F로 복제되어야 할 것이다. 즉, 새로이 추가된 노드를 spaceid라고 가정하고, 임의의 노드 x의 선행 노드 및 후행 노드를 각각 predecessor(x) 및 successor(x)로 가정하면, 다음과 같은 세 단계의 과정이 수행될 수 있다.
1. successor(spaceid)는 spaceid에게 spaceid가 담당할 데이터를 전달한다.
2. predecessor(spaceid)는 spaceid에게 spaceid가 리플리케이션할 데이터를 전달한다.
3. predecessor(predecessor(spaceid))는 spaceid에게 spaceid가 리플리케이션할 데이터를 전달한다.
상기와 같은 프로세스는 가상 스페이스 상에서 특정 노드가 제외되는 경우에도 유사하게 구현될 수 있을 것이다.
기타 실시예
이하에서는, 본 발명의 이해를 돕기 위하여, 본 발명에 따른 분산 프로그래밍 환경을 이용하여 작업을 처리하는 실시예를 살펴보기로 한다.
본 발명의 일 실시예에 따른 분산 프로그래밍 환경은 대용량의 데이터를 정렬하기 위한 병합 정렬(merge sort) 작업에 이용될 수 있다.
일반적으로 분산 프로그래밍 환경에서 수행되는 대규모 데이터에 대한 병합 정렬 작업은, 병합 정렬될 데이터를 n개의 노드에 분배하여 각각의 노드에서 데이터의 단편에 대하여 부분적으로 정렬이 수행되도록 한 후, 정렬된 n개의 데이터 단편들 중 일부를 정렬 기준에 부합하게 병합하여 새로운 데이터 단편을 생성하는 과정을, 모든 데이터 단편이 하나의 데이터로 병합될 때까지 반복하여 수행함으로써 이루어지게 된다. 이때, 병합이 반복되는 횟수가 증가할수록 데이터 단편의 노드 간 이동 횟수가 증가하므로 네트워크의 부하가 증가하고 처리 능력이 저하되게 된다.
그러나, 본 발명에 따른 분산 프로그래밍 환경 하에서는, 상기와 같은 문제점을 최소화시킨 채로 병합 정렬을 수행할 수 있는데, 그 구체적인 과정은 다음과 같다.
우선, 병합 정렬될 데이터를 n 개의 프로세스에 분배하여 각각의 노드가 정렬될 데이터를 소정의 해쉬 함수를 이용하여 분산 스페이스에 저장하게 된다. 이때, 해쉬 함수를 적절히 설정하는 경우, 저장되는 데이터가 정렬 기준에 따라 분산 스페이스 내의 소정의 영역에 맵핑될 수 있다. 예를 들면, 정렬될 데이터가 1,000 이하의 자연수로 구성되고, 가상 스페이스가 10개의 가상 노드로 구성되는 경우, 해쉬 함수가 모듈라(modular) 연산을 포함하게 함으로써 1~100 사이의 데이터는 가상 노드 1의 영역에 맵핑되고, 101~200 사이의 데이터는 가상 노드 2의 영역에 맵핑되며, 901~1,000 사이의 데이터는 가상 노드 10의 영역에 맵핑되도록 할 수 있을 것이다. 이와 같은 경우, 각각의 가상 노드의 영역에 저장된 데이터를 정렬한 후, 가상 노드 1의 영역에 저장된 데이터부터 가상 노드 10의 영역에 저장된 데이터까지를 순차적으로 병합함으로써 병합 정렬 작업을 완료할 수 있게 된다. 이와 같은 방법에 따르는 경우, 기존의 병합 정렬 방식에 비하여 노드 간의 데이터 전송량이 감소하므로 네트워크의 부하를 줄일 수 있고, 반복적인 병합 과정이 생략되므로 처리 능력이 향상되는 것을 확인할 수 있다.
이때, 주의하여야 할 점은, 데이터의 특성에 따라 데이터가 가상 스페이스에 편중적으로 맵핑될 수 있다는 것이다. 예를 들면, 상기 병합 정렬의 예에서 정렬될 데이터가 몇몇 숫자들로만 구성되는 경우, 특정 가상 노드에 데이터가 집중되게 되어, 분산 프로그래밍의 효율이 저하될 수 있다.
본 발명의 일 실시예에 따르면, 가상 스페이스에 데이터를 저장하기 이전에, 저장될 데이터 집합에 대한 샘플링 작업을 통하여 데이터의 특성을 파악함으로써 상기와 같은 상황을 방지할 수 있다. 앞서 예시한 병합 정렬 작업을 예로 들어 보다 자세히 설명하면, 병합 정렬이 수행될 데이터의 일부를 샘플링하고, 샘플링된 데이터에 해쉬 함수를 적용하여 본 결과, 1~300 사이의 값을 가지는 데이터의 개수가 10퍼센트 정도를 차지하는 것으로 파악되는 경우, 가상 노드 1의 영역에 1~300 사이의 데이터가 저장될 수 있도록 해쉬 함수를 조정하거나 가상 노드 1이 담당하는 가상 스페이스 상의 영역을 늘림으로써 일부의 가상 노드에 데이터가 편중되는 현상을 방지할 수 있을 것이다.
한편, 본 발명의 일 실시예에 따른 분산 프로그래밍 환경은 레거시 코드(legacy code)를 재사용하기 위한 모델에도 적용될 수 있다. 보다 구체적으로는, 대부분의 소스 코드는 부분적으로라도 시스템의 플랫폼에 종속되는 특성이 있는데, 시스템의 플랫폼이 업그레이드되거나 변경되는 경우에 기존의 소스 코드에 대한 변경 작업이 필요할 수밖에 없다. 그러나, 본 발명에 따른 분산 프로그래밍 환경 하에서는, 레거시 코드에 의해 처리되는 데이터를 분산 스페이스를 통해 입출력함으로써 레거시 코드를 재사용할 수 있는 효과를 달성할 수 있다. 보다 구체적으로는, 시스템의 플랫폼이 변경되는 경우에도, 분산 스페이스에 저장되는 데이터의 형식을 일정하게 유지함으로써 레거시 코드에 의한 데이터 처리 결과가 변경된 플랫폼 하에서도 적용되도록 할 수 있을 것이다.
이상 설명된 본 발명에 따른 실시예들은 다양한 컴퓨터 구성요소를 통하여 수행될 수 있는 프로그램 명령어의 형태로 구현되어 컴퓨터 판독 가능한 기록 매체에 기록될 수 있다. 상기 컴퓨터 판독 가능한 기록 매체는 프로그램 명령어, 데이터 파일, 데이터 구조 등을 단독으로 또는 조합하여 포함할 수 있다. 상기 컴퓨터 판독 가능한 기록 매체에 기록되는 프로그램 명령어는 본 발명을 위하여 특별히 설계되고 구성된 것들이거나 컴퓨터 소프트웨어 분야의 당업자에게 공지되어 사용 가능한 것일 수도 있다. 컴퓨터 판독 가능한 기록 매체의 예에는, 하드 디스크, 플로피 디스크 및 자기 테이프와 같은 자기 매체, CD-ROM, DVD와 같은 광기록 매체, 플롭티컬 디스크(floptical disk)와 같은 자기-광 매체(magneto-optical media), 및 ROM, RAM, 플래시 메모리 등과 같은 프로그램 명령어를 저장하고 수행하도록 특별히 구성된 하드웨어 장치가 포함된다. 프로그램 명령어의 예에는, 컴파일러에 의해 만들어지는 것과 같은 기계어 코드뿐만 아니라 인터프리터 등을 사용해서 컴퓨터에 의해서 실행될 수 있는 고급 언어 코드도 포함된다. 상기 하드웨어 장치는 본 발명에 따른 처리를 수행하기 위해 하나 이상의 소프트웨어 모듈로서 작동하도록 구성될 수 있으며, 그 역도 마찬가지이다.
이상에서 본 발명이 구체적인 구성요소 등과 같은 특정 사항들과 한정된 실시예 및 도면에 의해 설명되었으나, 이는 본 발명의 보다 전반적인 이해를 돕기 위해서 제공된 것일 뿐, 본 발명이 상기 실시예들에 한정되는 것은 아니며, 본 발명이 속하는 기술분야에서 통상적인 지식을 가진 자라면 이러한 기재로부터 다양한 수정 및 변형을 꾀할 수 있다.
따라서, 본 발명의 사상은 상기 설명된 실시예에 국한되어 정해져서는 아니되며, 후술하는 특허청구범위뿐만 아니라 이 특허청구범위와 균등하게 또는 등가적으로 변형된 모든 것들은 본 발명의 사상의 범주에 속한다고 할 것이다.

Claims (19)

  1. 분산 환경에서 데이터를 처리하기 위한 방법으로서,
    다수의 노드가 제공하는 자원을 이용하여 가상 스페이스를 생성하는 단계, 및
    제1 어플리케이션이 상기 가상 스페이스로부터 데이터를 읽거나 상기 가상 스페이스에 데이터를 쓰는 단계
    를 포함하고,
    상기 데이터는 상기 데이터의 속성에 따라 결정되는 상기 가상 스페이스 상의 특정 위치 영역에 맵핑되고,
    상기 제1 어플리케이션은 상기 위치 영역에 상기 데이터에 대한 읽기 작업 또는 쓰기 작업을 수행하는 방법.
  2. 제1항에 있어서,
    상기 다수의 노드의 각각은 상기 가상 스페이스에서 적어도 하나의 가상 노드에 대응되는 방법.
  3. 제1항에 있어서,
    상기 위치 영역은 상기 데이터에 소정의 해쉬 함수를 적용함으로써 결정되는 방법.
  4. 제3항에 있어서,
    상기 해쉬 함수는 상기 데이터를 상기 가상 스페이스 상의 특정 위치로 맵핑시키기 위한 것인 방법.
  5. 제4항에 있어서,
    상기 해쉬 함수에 의해 처리되는 데이터는 미리 샘플링된 것인 방법.
  6. 제5항에 있어서,
    상기 해쉬 함수, 또는 상기 다수의 노드의 각각이 제공하는, 상기 가상 스페이스의 일 영역은, 상기 샘플링을 통하여 조절될 수 있는 방법.
  7. 제1항에 있어서,
    상기 쓰여진 데이터를 제2 어플리케이션에 제공하는 단계를 더 포함하는 방법.
  8. 제7항에 있어서,
    상기 제1 어플리케이션 및 상기 제2 어플리케이션은 동일한 키(key)를 공유하는 방법.
  9. 제8항에 있어서,
    상기 데이터의 속성은 상기 키를 포함하고, 상기 제2 어플리케이션은 상기 키를 이용하여 상기 데이터를 획득하는 방법.
  10. 제1항 내지 제9항 중 어느 한 항에 따른 방법을 실행하기 위한 컴퓨터 프로그램을 기록하는 컴퓨터 판독 가능한 기록 매체.
  11. 분산 환경에서 데이터를 처리하기 위한 시스템으로서,
    다수의 노드가 제공하는 자원을 이용하여 생성되는 가상 스페이스, 및
    상기 가상 스페이스로부터 데이터를 읽거나 상기 가상 스페이스에 데이터를 쓰는 제1 어플리케이션
    을 포함하고,
    상기 데이터는 상기 데이터의 속성에 따라 결정되는 상기 가상 스페이스 상의 특정 위치 영역에 맵핑되고,
    상기 제1 어플리케이션은 상기 위치 영역에 상기 데이터에 대한 읽기 작업 또는 쓰기 작업을 수행하는 시스템.
  12. 제11항에 있어서,
    상기 다수의 노드의 각각은 상기 가상 스페이스에서 적어도 하나의 가상 노드에 대응되는 시스템.
  13. 제11항에 있어서,
    상기 위치 영역은 상기 데이터에 소정의 해쉬 함수를 적용함으로써 결정되는 시스템.
  14. 제13항에 있어서,
    상기 해쉬 함수는 상기 데이터를 상기 가상 스페이스 상의 특정 위치로 맵핑시키기 위한 것인 시스템.
  15. 제14항에 있어서,
    상기 해쉬 함수에 의해 처리되는 데이터는 미리 샘플링된 것인 시스템.
  16. 제15항에 있어서,
    상기 해쉬 함수, 또는 상기 다수의 노드의 각각이 제공하는, 상기 가상 스페이스의 일 영역은, 상기 샘플링을 통하여 조절될 수 있는 시스템.
  17. 제11항에 있어서,
    상기 쓰여진 데이터를 제공 받는 제2 어플리케이션을 더 포함하는 시스템.
  18. 제17항에 있어서,
    상기 제1 어플리케이션 및 상기 제2 어플리케이션은 동일한 키를 공유하는 시스템.
  19. 제18항에 있어서,
    상기 데이터의 속성은 상기 키를 포함하고, 상기 제2 어플리케이션은 상기 키를 이용하여 상기 데이터를 획득하는 시스템.
PCT/KR2009/002014 2009-02-11 2009-04-17 분산 스페이스를 이용하여 분산 프로그래밍 환경을 제공하기 위한 방법, 시스템 및 컴퓨터 판독 가능한 기록 매체 Ceased WO2010093084A1 (ko)

Priority Applications (2)

Application Number Priority Date Filing Date Title
JP2011549050A JP5646511B2 (ja) 2009-02-11 2009-04-17 分散スペースを用いて分散プログラミング環境を提供するための方法、システム及びコンピュータ読み取り可能な記録媒体
US13/201,098 US8799619B2 (en) 2009-02-11 2009-04-17 Method and system for providing distributed programming environment using distributed spaces, and computer readable recording medium

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
KR1020090011103A KR100983479B1 (ko) 2009-02-11 2009-02-11 분산 스페이스를 이용하여 분산 프로그래밍 환경을 제공하기 위한 방법, 시스템 및 컴퓨터 판독 가능한 기록 매체
KR10-2009-0011103 2009-02-11

Publications (1)

Publication Number Publication Date
WO2010093084A1 true WO2010093084A1 (ko) 2010-08-19

Family

ID=42561918

Family Applications (1)

Application Number Title Priority Date Filing Date
PCT/KR2009/002014 Ceased WO2010093084A1 (ko) 2009-02-11 2009-04-17 분산 스페이스를 이용하여 분산 프로그래밍 환경을 제공하기 위한 방법, 시스템 및 컴퓨터 판독 가능한 기록 매체

Country Status (4)

Country Link
US (1) US8799619B2 (ko)
JP (1) JP5646511B2 (ko)
KR (1) KR100983479B1 (ko)
WO (1) WO2010093084A1 (ko)

Families Citing this family (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
KR101140484B1 (ko) * 2010-08-24 2012-04-30 엔에이치엔비즈니스플랫폼 주식회사 수평적 구조의 파일 시스템을 이용하여 계층적 구조의 파일 시스템을 지원하는 파일 관리 시스템 및 파일 관리 방법
RU2708043C2 (ru) * 2016-11-01 2019-12-03 Общество с ограниченной ответственностью "НПО Аналитика" Способ сбора информации в оффлайне для анализа аудиторий в наружной рекламе и измерения эффективности размещения наружной рекламы
KR102019799B1 (ko) * 2016-11-09 2019-09-09 건국대학교 산학협력단 읽기 및 쓰기가 가능한 가상 디스크의 병합 마운팅을 통한 가상 클러스터 구축 방법 및 장치
RU2725056C1 (ru) * 2019-08-30 2020-06-29 Общество с ограниченной ответственностью "Шопстер Технологии" Способ измерения контактов с рекламным носителем в наружной рекламе

Citations (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
KR100349658B1 (ko) * 2000-12-04 2002-08-24 한국전자통신연구원 분산 가상환경을 위한 실시간 상태관리 서버와 그의공유공간 상태정보 관리방법
JP2006065525A (ja) * 2004-08-26 2006-03-09 Hitachi Ltd 分散環境における仮想共有空間の実現方法
KR20070083489A (ko) * 2004-07-21 2007-08-24 비치 언리미티드 엘엘씨 블록 맵 캐싱 및 ｖｆｓ 적층 가능 파일 시스템 모듈들에기초한 분산 저장 아키텍처

Family Cites Families (8)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US5845331A (en) * 1994-09-28 1998-12-01 Massachusetts Institute Of Technology Memory system including guarded pointers
US7613796B2 (en) * 2002-09-11 2009-11-03 Microsoft Corporation System and method for creating improved overlay network with an efficient distributed data structure
JP4068473B2 (ja) 2003-02-19 2008-03-26 株式会社東芝 ストレージ装置、分担範囲決定方法及びプログラム
US7734890B2 (en) * 2006-10-06 2010-06-08 Okralabs Llc Method and system for using a distributable virtual address space
JP5373295B2 (ja) * 2008-02-04 2013-12-18 インターナショナル・ビジネス・マシーンズ・コーポレーション マルチノード・サーバシステム、負荷分散方法、リソース管理サーバ、およびプログラム
US8386750B2 (en) * 2008-10-31 2013-02-26 Cray Inc. Multiprocessor system having processors with different address widths and method for operating the same
US20110276776A1 (en) * 2010-05-07 2011-11-10 Tatu Ylonen Oy Ltd Addressing for Huge Direct-Mapped Object Systems
KR101694977B1 (ko) * 2010-12-17 2017-01-11 한국전자통신연구원 통합 메모리 서비스를 위한 소프트웨어 구조 및 이 소프트웨어 구조를 이용한 통합 메모리 서비스 제공 방법

Patent Citations (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
KR100349658B1 (ko) * 2000-12-04 2002-08-24 한국전자통신연구원 분산 가상환경을 위한 실시간 상태관리 서버와 그의공유공간 상태정보 관리방법
KR20070083489A (ko) * 2004-07-21 2007-08-24 비치 언리미티드 엘엘씨 블록 맵 캐싱 및 ｖｆｓ 적층 가능 파일 시스템 모듈들에기초한 분산 저장 아키텍처
JP2006065525A (ja) * 2004-08-26 2006-03-09 Hitachi Ltd 分散環境における仮想共有空間の実現方法

Also Published As

Publication number Publication date
US8799619B2 (en) 2014-08-05
JP5646511B2 (ja) 2014-12-24
US20120030446A1 (en) 2012-02-02
KR100983479B1 (ko) 2010-09-27
JP2012517631A (ja) 2012-08-02
KR20100091757A (ko) 2010-08-19

Similar Documents

Publication Publication Date Title
CN103414761B (zh) 一种基于Hadoop架构的移动终端云资源调度方法
Lu et al. Accelerating spark with RDMA for big data processing: Early experiences
US9497264B2 (en) Apparatus, method and system for aggregating computing resources
CN110134636A (zh) 模型训练方法、服务器和计算机可读存储介质
US9535756B2 (en) Latency-hiding context management for concurrent distributed tasks in a distributed system
WO2012111905A2 (ko) 맵 리듀스를 이용한 분산 메모리 클러스터 제어 장치 및 방법
JP2006202337A (ja) データ処理の方法及び装置
Chang et al. Adaptable replica consistency service for data grids
CN116418700B (zh) 一种基于dpdk的分布式数据捕获方法
WO2014069827A1 (en) System and method for providing data analysis service in a cloud environment
Zhang et al. Egraph: efficient concurrent GPU-based dynamic graph processing
WO2010093084A1 (ko) 분산 스페이스를 이용하여 분산 프로그래밍 환경을 제공하기 위한 방법, 시스템 및 컴퓨터 판독 가능한 기록 매체
JP2004046372A (ja) 分散処理システム、リソース割当方法およびプログラムならびにリソース割当プログラムが記録された記録媒体
CN111064619A (zh) 一种配置信息管理方法、装置、电子设备和存储介质
JP4362839B1 (ja) 仮想単一メモリストレージ上におけるメタ情報共有型分散データベース・システム
CN119341992B (zh) 基于dpu服务网格分布式限流方法、装置、设备及介质
WO2023153558A1 (ko) 구조화 문서에 포함된 자원들에 관한 권한을 관리하는 방법 및 이를 이용한 장치
Goldsztajn et al. Server saturation in skewed networks
US11321205B2 (en) Enterprise-scale time series graphite backend infrastructure
WO2023177136A1 (ko) 서비스 제공을 위한 블록체인 데이터 저장 방법 및 저장 관리장치
Abramson et al. A cache-based data movement infrastructure for on-demand scientific cloud computing
WO2020184982A1 (ko) 이종클러스터 시스템에서 실행되는 프로그램을 실행시키는 방법 및 컴퓨터 프로그램
CN101488872B (zh) 生物信息计算网格系统
CN118827672B (zh) 容器集群流量调度方法、电子设备及计算机可读存储介质
WO2018155748A1 (ko) 가상화 기반 체험 콘텐츠 제공 클라우드 시스템

Legal Events

Date Code Title Description
121 Ep: the epo has been informed by wipo that ep was designated in this application

Ref document number: 09840074

Country of ref document: EP

Kind code of ref document: A1

WWE Wipo information: entry into national phase

Ref document number: 2011549050

Country of ref document: JP

NENP Non-entry into the national phase

Ref country code: DE

WWE Wipo information: entry into national phase

Ref document number: 13201098

Country of ref document: US

122 Ep: pct application non-entry in european phase

Ref document number: 09840074

Country of ref document: EP

Kind code of ref document: A1